-
题名一个宽容交货超前延误单机排序问题
被引量：4
- 1
-
-
作者
陈全乐
孙世杰
-
机构
上海大学理学院数学系
-
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
2000年第4期440-448,共9页
-
基金
国家自然科学基金!( 1 9771 0 57)
-
文摘
此文考虑下述排序问题 (P) :有 n个工件需在同一台机器上加工 ,对各工件有一共同的宽容交货期 .若一工件在此宽容期前完工则为一超前工件 ,若在此宽容期后完工则为一延误工件 ,要求适当安排一加工方式和宽容交货期的位置使加权超前延误工件数最小 .文中证得 (P)是 NP-hard的 ,并给出一伪多项式时间的分枝状精确算法 ,这也就可以认为它是一般意义下的 NP-hard问题而不是强NP-hard问题 .
-
关键词
排序
共同宽容期
加权超前延误工件数
复杂性
算法
-
Keywords
Scheduling
Common Due Window
Weighted Number of Early and Tardy Jobs
Complexity
Algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名工时依赖位置的宽容期单机排序问题
- 2
-
-
作者
赵林
王龙奎
-
机构
安徽建筑工业学院数理系
-
出处
《安徽大学学报（自然科学版）》
CAS
北大核心
2009年第6期34-36,共3页
-
文摘
研究了共同宽容交货期的单机排序问题,即加工时间是位置的函数,所有工件的提前/延误费用相同,共同宽容交货期的开始时间和大小待定,目标函数最小化的总惩罚费用(包括提前、延误、宽容交货期的定位和大小费用四部分).并给出了最优排序的性质,提出了一个多项式时间算法.
-
关键词
排序
单机
共同宽容期
加工时间
-
Keywords
scheduling
single machine
common due window
processing time
-
分类号
O223
[理学—运筹学与控制论]
-
