Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/27809
Title: | Optimization of Large-Scale Single Machine and Parallel Machine Scheduling |
Other Titles: | Large-Scale Single Machine and Parallel Machine Scheduling in the Steel Industry with Sequence-Dependent Changeover Costs |
Authors: | Lee, Che |
Advisor: | Swartz, Christopher |
Department: | Chemical Engineering |
Keywords: | single machine scheduling;parallel machine scheduling;mixed-integer programming;metaheuristics;variable neighborhood descent |
Publication Date: | 2022 |
Abstract: | Hundreds of steel products need to be scheduled on a single or parallel machine in a steel plant every week. A good feasible schedule may save the company millions of dollars compared to a bad one. Single and parallel machine scheduling are also encountered often in many other industries, making it a crucial research topic for both the process system engineering and operations research communities. Single or parallel machine scheduling can be a challenging combinatorial optimization problem when a large number of jobs are to be scheduled. Each job has unique job characteristics, resulting in different setup times/costs depending on the processing sequence. They also have specific release dates to follow and due dates to meet. This work presents both an exact method using mixed-integer quadratic programming, and an approximate method with metaheuristics to solve real-world large-scale single/parallel machine scheduling problems faced in a steel plant. More than 1000 or 350 jobs are to be scheduled within a one-hour time limit in the single or parallel machine problem, respectively. The objective of the single machine scheduling is to minimize a combined total changeover, total earliness, and total tardiness cost, whereas the objective of the parallel machine scheduling is to minimize an objective function comprising the gaps between jobs before a critical time in a schedule, the total changeover cost, and the total tardiness cost. The exact method is developed to benchmark computation time for a small-scale single machine problem, but is not practical for solving the actual large-scale problem. A metaheuristic algorithm centered on variable neighborhood descent is developed to address the large-scale single machine scheduling with a sliding-window decomposition strategy. The algorithm is extended and modified to solve the large-scale parallel machine problem. Statistical tests, including Student's t-test and ANOVA, are conducted to determine efficient solution strategies and good parameters to be used in the metaheuristics. |
URI: | http://hdl.handle.net/11375/27809 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Lee_Che_finalsubmission202208_MASc.pdf | 10.57 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.