PARALLEL MACHINE SCHEDULING WITH BATCH SETUP TIMES

被引：18

作者：

CHENG, TCE ^{[1
]}

CHEN, ZL ^{[1
]}

机构：

[1] SHANGHAI TRANSPORTAT PLANNING INST,SHANGHAI,PEOPLES R CHINA

来源：

OPERATIONS RESEARCH | 1994年 / 42卷 / 06期

关键词：

D O I：

10.1287/opre.42.6.1171

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider a problem of scheduling several batches of jobs on two identical parallel machines to minimize the total completion time of jobs. A setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. When the number of jobs is arbitrary, the computational complexity of the problem is posed as an open problem in the literature. We show in this note that the problem is binary NP-hard even when the setup times are sequence independent and all processing times are equal.

引用

页码：1171 / 1174

页数：4