浙江大学学报(理学版)
浙江大學學報(理學版)
절강대학학보(이학판)
JOURNAL OF ZHEJIANG UNIVERSITY
2010年
1期
34-37,45
,共5页
单机排序%共同交货期%退化工件%准时%多项式时间算法
單機排序%共同交貨期%退化工件%準時%多項式時間算法
단궤배서%공동교화기%퇴화공건%준시%다항식시간산법
single machine scheduling%common due-date%deteriorating jobs%just-in-time%polynomial algorithm
研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(n log n)时间的最优算法.
研究帶退化工件的單機排序問題,即工件的加工時間是其開始加工時間的線性遞增函數,且不同的工件具有不同的退化率.要求為所有工件尋找一共同的最優交貨期和最優序,以極小化這些工件的共同交貨期、超前罰和遲後罰之和.給齣瞭一O(n log n)時間的最優算法.
연구대퇴화공건적단궤배서문제,즉공건적가공시간시기개시가공시간적선성체증함수,차불동적공건구유불동적퇴화솔.요구위소유공건심조일공동적최우교화기화최우서,이겁소화저사공건적공동교화기、초전벌화지후벌지화.급출료일O(n log n)시간적최우산법.
One single machine scheduling problem with deteriorating jobs is studied, which means the jobs whose processing times are an increasing liner function of their start times, and the different job deterioration are inequality for all jobs. The problem is to determine an optimal common due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. An O(n log n) time algorithm is given to solve this problem.