Two-machine flowshop scheduling with intermediate transportation under job physical space consideration

In this paper, we study a coordinated production-transportation scheduling problem in a two-machine flowshop environment where a single transporter may carry several jobs simultaneously as a batch between the machines. Each job has its own physical-space requirement while being loaded into the transporter. The goal is to minimize the makespan. For the jobs with the same size of physical space during transportation, we present a heuristic algorithm with an absolute worst-case ratio of 2 and a polynomial-time optimal algorithm for a special case with given job sequence. For the jobs having different size of physical storage space, a heuristic algorithm is constructed with an absolute worst-case ratio of 7/3 and asymptotic worst-case ratio of 20/9. Computational experiments demonstrate that the two heuristic algorithms developed are capable of generating near-optimal solutions quickly. (C) 2010 Elsevier Ltd. All rights reserved.