Article ID: | iaor20022266 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 3 |
Start Page Number: | 275 |
End Page Number: | 294 |
Publication Date: | Mar 2002 |
Journal: | Computers and Operations Research |
Authors: | Sung Chang Sup, Kim Young Hwan |
Keywords: | heuristics |
This paper considers a scheduling problem for a two-machine flowshop where a discrete processing machine is followed by a batch processing machine and a finite number of jobs arrive dynamically at the first machine. In the flowshop, the discrete processing machine processes one job at a time and the batch processing machine processes a batch of jobs simultaneously. The objective is to find the optimal schedule which minimizes the maximum completion time (makespan) of all jobs. In the situation where preemption is allowed on the discrete processing machine, it is shown that the optimal schedule can be found in polynomial time. However, in the situation where no preemption is allowed on the discrete processing machine, it is shown that the problem is NP-complete, for which an efficient heuristic solution algorithm is constructed and its tight worst-case error bound is derived. Numerical experiments show that the heuristic algorithm consistently generates good schedules.