TWO-MACHINE FLOW SHOP SCHEDULING WITH AN INTERSTAGE TRANSPORTER: TWO SHIPMENTS

摘要

We consider the two-machine flow shop scheduling problem to minimize the makespan, provided that the jobs have to be transported between the machines by a single transporter or carrier. The transporter may take an arbitrary number of jobs at a time. For this NP-hard problem, we describe a heuristic that behaves as a 6/5 -- approximation algorithm, provided that there exists an optimal schedule with exactly two shipments. The obtained result should be viewed as a necessary step towards an algorithm with a better worst-case behaviour than 3/2|--approximation algorithm by Lee and Strusevich (2005).