| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 723808 | IFAC Proceedings Volumes | 2006 | 5 Pages |
Abstract
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 a ***3/2–approximation algorithm by Lee and Strusevich (2005).
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
