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

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

作　　者：陈全乐[1] 孙世杰[1] 

机构地区：[1]上海大学理学院数学系,上海200436

出　　处：《高校应用数学学报（A辑）》2000年第4期440-448,共9页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金!( 1 9771 0 57)

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

关 键 词：排序 共同宽容期 加权超前延误工件数 复杂性 算法 

分 类 号：O223[理学—运筹学与控制论]