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

摘要：

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

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

所属期刊栏目：15

分类号：O223(运筹学)

资助基金：中国科学院资助项目19771057

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：440-448