基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题，即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达，新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题，其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列，基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．

Minimize total lateness with deteriorating jobs based on rescheduling problem

In this paper, we consider two single machine rescheduling problems with deteriorating jobs under sequence disruptions, the actual processing time of a job is a linear function of the starting time for deteriorating job. Rescheduling means that a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total lateness under a limit of the sequence disruption for deteriorating job. We research 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 αj. For each problem, the polynomial algorithm is proposed by sorting by stages or dynamic programming method, respectively.