Minimizing makespan in a two-machine flowshop scheduling problem with delay time constraints

Abstract

In this thesis, we consider a scheduling problem in the subsystem (foaming and inspection) of a refrigerator manufacturing systems, in which makespan is to be minimized. We focuses on the subsystem (foaming and inspection), which is considered bottleneck in a refrigerator manufacturing systems. This problem is a two-machine flowshop scheduling problem in which there should be delay time between the operations on the first and second machines for each job. For the problem with the objective of minimizing makespan, we develop dominance properties (adjacent job-pair 4 cases and non-adjacent job 1 case), two lower bounds and three heuristic algorithms, and use these to develop a branch and bound algorithm. To evaluate the performance of the algorithm, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.