The flow shop problem with no-idle constraints: A review and approximation |
| |
Authors: | Yaroslav Goncharov Sergey Sevastyanov |
| |
Institution: | Sobolev Institute of Mathematics, Novosibirsk State University, prosp. Koptjuga 4, 630090 Novosibirsk, Russia |
| |
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. |
| |
Keywords: | Combinatorial optimization Scheduling Flow shop Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |