
具有错位限制的工件可退化的单机重新排序问题
A Single Machine Rescheduling Problems with Deteriorating Jobs Under Sequence Disruptions
重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达, 新工件的安排使得原始工件重新排序而产生错位. 考虑了加权序列错位以及加权时间错位限制条件下具有退化工件, 目标函数为最小化总完工时间和最小化总延误时间问题. 工件的位置错位和时间错位限制条件下具有退化工件, 目标函数为最小化总完工时间和最小化最大延迟问题. 其中退化效应是指其实际加工时间是开工时间的非减函数, 工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差, 工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差. 对以上两类问题,当权重系数或者错位限制满足特殊情况时, 最优排序是原 始工件集和新工件集中的工件按照退化率非减的序列排列, 基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.
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.
重新排序 / 加权序列错位 / 加权时间错位 / 退化工件. {{custom_keyword}} /
/
〈 |
|
〉 |