Master Thesis : Optimization Strategies for Industrial-size Job Shop Scheduling

Abstract

This thesis investigates the optimization of a large-scale job shop scheduling process. Scheduling plays a crucial role in resource allocation and productivity maximization for companies. We evaluate the performance of established optimization techniques, including simulated annealing, branch and bound, dive, and a relaxation with a linear program we call the ranking method. We use three instances from the database of TOOWHE Enterprise Resource Planning (ERP) software, developed by Hi-pass. Through extensive experimentation on three instances of industrial-scale job shop problems, we assess the effectiveness and limitations of each algorithm. The simulated annealing algorithm shows promise by achieving significant objective value improvements within a reasonable execution time. However, the ranking method quickly outperforms it, providing equivalent solutions in a fraction of a second. By solving a relaxation of the problem with a linear program, the ranking method provides lower bounds and generates efficient operation schedules. To overcome the limitations of the branch and bound method, we propose the dive approach, which allows deeper exploration of the solution space while maintaining model consistency. By incorporating different strategies for operation selection, the dive approach achieves high-quality schedules within a limited number of dives. Our results highlight the limited scalability of the branch and bound method and the effectiveness of the simulated annealing algorithm, ranking method, and dive approach in generating reliable initial schedules. We recommend using the ranking method or dive approach to obtain an initial schedule and applying the simulated annealing algorithm for further refinement. This research contributes to the advancement of scheduling optimization in ERP systems, providing insights into algorithm performance and practical recommendations for improving scheduling efficiency and resource utilization in industrial contexts.