文献类型：期刊文献

英文题名：Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard

作者：Yu, Wenci[1]; Hoogeveen, Han[2]; Lenstra, Jan Karel[3]

机构：[1]Univ Utrecht, Dept Comp Sci, NL-3508 TB Utrecht, Netherlands;[2]E China Univ Sci & Technol, Inst Appl Math, Shanghai 200237, Peoples R China;[3]CWI, NL-1090 GB Amsterdam, Netherlands

年份：2004

卷号：7

期号：5

起止页码：333

外文期刊名：JOURNAL OF SCHEDULING

收录：;EI(收录号：2004358327143);WOS:【SCI-EXPANDED(收录号:WOS:000224754500001)】；

语种：英文

外文关键词：flow shop scheduling; intermediate delays; makespan; computational complexity; strong NP-hardness

摘要：One of the first problems to be studied in scheduling theory was the problem of minimizing the makespan in a two-machine flow shop. Johnson showed that this problem can be solved in O(n log n) time. A crucial assumption here is that the time needed to move a job from the first to the second machine is negligible. If this is not the case and if this 'delay' is not equal for all jobs, then the problem becomes NP-hard in the strong sense. We show that this is even the case if all processing times are equal to one. As a consequence we show strong NP. hardness of a number of similar problems, including a severely restricted version of the Numerical 3-Dimensional latching problem.