摘要
证明了成组加工的单机延误工件个数问题是强ＮＰ困难的，即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期，又有相同加工时间的进一步限制情形，由于输入规模的减少，证明了其是普通意义下ＮＰ困难的。
This paper considers the onemachine 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 NPhard,even for the case of unit processing time and zero setup 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 NPhard if the jobs in a group have the same processing time as well as the same due date.
出处
《华东理工大学学报（自然科学版）》
CAS
CSCD
北大核心
1998年第2期235-242,共8页
Journal of East China University of Science and Technology
基金
国家自然科学基金
关键词
单机时间表
成组技术
延误工件个数
NP困难性
onemachine scheduling
group technology
number of late jobs
NPhardness
polynomial time algorithm
