文献类型：期刊文献

英文题名：Minimizing the number of late jobs under the group technology assumption

作者：Liu, ZH; Yu, WC

机构：[1]E China Univ Sci & Technol, Inst Appl Math, Shanghai 200237, Peoples R China

年份：1999

卷号：3

期号：1

起止页码：5

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：;EI(收录号：2004057906721);WOS:【SSCI(收录号:WOS:000081774600001)，SCI-EXPANDED(收录号:WOS:000081774600001)】；

语种：英文

外文关键词：one-machine scheduling; group technology; number of late jobs; NP-hardness; polynomial algorithm

摘要：We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date.