Novel solution algorithms for machine scheduling problems emerging in complex systems

Abstract

Efficient production scheduling is a central challenge in modern manufacturing systems, where organizations must simultaneously address machine utilization, delivery requirements, operational complexity, and increasing demands for energy efficiency. This dissertation investigates a range of complex scheduling problems and develops optimization, heuristic, and metaheuristic approaches to support effective production planning and decision-making. The first contribution addresses parallel-machine scheduling problems with delivery times and tardiness objectives. A mixed-integer linear programming formulation is complemented by Variable Neighborhood Search and a Memetic Algorithm. Fast evaluation techniques are developed to accelerate local search, and extensive computational experiments compare the proposed approaches with established heuristics and exact optimization methods. The second contribution extends the scheduling problem to distributed manufacturing systems with unrelated parallel machines. A Tabu Search metaheuristic is developed to address the resulting allocation and scheduling decisions, and its performance is evaluated computationally. The third contribution considers unrelated parallel-machine scheduling with eligibility constraints and delivery times, with the objective of minimizing total weighted tardiness. Structural properties of the problem are identified and used to improve local search and accelerate neighborhood evaluation. Based on these properties, heuristic and Variable Neighborhood Search approaches are developed and compared with mixed-integer programming and established dispatching methods. The fourth contribution addresses energy-efficient scheduling in flexible job-shop manufacturing systems under time-of-use electricity pricing. For a fixed production sequence, shifting and dynamic-programming-based procedures are developed to determine energy-efficient schedules. Computational experiments evaluate their performance and examine the potential for reducing total electricity costs without compromising production requirements. Overall, the dissertation contributes to production and operations research by developing computationally efficient solution methods for scheduling problems characterized by multiple machines, distributed production environments, delivery requirements, eligibility restrictions, and energy considerations. The findings demonstrate how mathematical optimization and advanced metaheuristics can be combined with problem-specific structural insights to improve solution quality and computational efficiency. The proposed approaches provide both methodological contributions to scheduling research and practical insights for improving the efficiency, reliability, and sustainability of manufacturing operations.