| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 480897 | European Journal of Operational Research | 2009 | 7 Pages |
Abstract
The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Yaroslav Goncharov, Sergey Sevastyanov,