文献类型：期刊文献

中文题名：成组加工的单机延误工件个数问题

英文题名：Onemachine Scheduling to Minimize the Number of Late Jobs in Group Technology

作者：刘朝晖[1];俞文[1]

机构：[1]华东理工大学应用数学研究所

年份：1998

卷号：24

期号：2

起止页码：235

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;Scopus;北大核心:【北大核心1996】；CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：单机时间表;成组技术;延误工件个数;NP困难性

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

摘要：证明了成组加工的单机延误工件个数问题是强ＮＰ困难的，即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期，又有相同加工时间的进一步限制情形，由于输入规模的减少，证明了其是普通意义下ＮＰ困难的。
This paper considers the onemachine scheduling problem to minmize the number of late jobs in group technology,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.