一个宽容交货超前延误单机排序问题

此文考虑下述排序问题（P）：有n个工件需在同一台机器上加工,对各工件有一共同的宽容交货期。若一工件在此宽容期前完工则为一超前工件,若在此宽容期后完工则为一延误工件,要求适当安排一加工方式和宽容交货期的位置使加权超前延误工件数量小。文中证得（P）是NP-hard的,并给出一伪多项式时间的分枝状精确算法,这也就可以认为它是一般意义下的NP-hard问题而不是强NP-hard问题。

AN EARLINESS AND TARDINESS PROBLEM IN SINGLE MACHINE SCHEDULING WITH A COMMON DUE WINDOW

This paper considers the following scheduling problem (P): n jobs demand to be processed on the same machine and there exists a common due window for each job.If a job finishes its processing ahead of the common due window,it will be a weighted early job,and if a job finishes its processing after the common due window,then it will be a weighted tardy job.The task is to schedule the n jobs and determinate a location of the common due window such that the weighted number of early and tardy jobs is minimized.This paper proves the NP|hardiness of the problem,and gives a pseudopolynomial branch algorithm.That is to say it is a ordinary NP|hard problem and not a strong NP|hard one.