摘要
重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.
This paper considers rescheduling, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives and creates a disruption. The objective function is to minimize total completion time and total lateness under a limit of the weighted sequence disruption or the weighted time disruption of deteriorating job. We also consider the rescheduling problem to minimize the total completion and the maximum lateness under a limit of the sequence or time disruption for deteriorating job. The position disruption is the difference with the positions of the original job in the original schedule and any job sequence, time disruption is the difference with the completion time of the original job in the original schedule and any job sequence. When the weight coefficient or the disruption satisfies a special case, we study the properties of feasible schedules and optimal schedules for two problems, the jobs in the set of original jobs or new jobs are ordered by non-decreasing order of the processing rate. Finally, the polynomial algorithms or pseudo-polynomial time algorithms are provided by dynamic programming method.
作者
康宇红
张新功
KANG Yuhong;ZHANG Xingong(School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331)
出处
《系统科学与数学》
CSCD
北大核心
2018年第4期511-520,共10页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金(11571321,71561007)
贵州省教委厅自然科学创新群体基金项目(KY[2017]051)资助课题
关键词
重新排序
加权序列错位
加权时间错位
退化工件
Rescheduling
weighted sequence disruption
weighted time disruption
deteriorating jobs.
