Nowadays, many modern day factories have migrated towards a highly- automated production process to efficiently create large quantities of products every day. Thus, production scheduling tasks are often challenging for human planners and there is a strong need for automated solution methods to find optimized schedules. Although various practical scheduling problems have been studied in the literature, still many novel NP-hard problems that originate from the industry remain to be investigated due to the unique requirements that arise from different application domains. This thesis introduces two important scheduling problems that arise from real-life applications in the paint shops of the automotive supply industry and in the manufacturing of artificial teeth for dentures. Both investigated problems, which are called the paint shop scheduling problem and the artificial teeth scheduling problem, are NP-hard and include unique constraints as well as solution objectives that cause the need for efficient novel solution methods to solve large-scale problem instances. Therefore, the thesis proposes a range of innovative exact techniques, metaheuristics, hybrid methods, and hyper-heuristic solution approaches in addition to providing a formal specification and complexity analysis. To experimentally evaluate all the proposed solution methods, the thesis provides a collection of benchmark instances that include real-life scheduling scenarios from factories of the automotive supply industry and teeth manufacturing. Computational results show that the introduced exact techniques could be successfully used to achieve several optimality results and can provide lower bounds for many instances. An extensive empirical evaluation further demonstrates that the proposed metaheuristics and hybrid techniques can be successfully used to produce high-quality schedules even for large real-life scheduling scenarios.