退化条件下的工期指派的单机排序问题

研究退化条件下的工期指派的单机排序问题。每个工件均有一个关于工期的连续非减的惩罚函数。工件的加工时间是退化的,即工件的加工时间是其开始加工时间的一个线性增函数,所有工件都有一个相同的退化率。目标是确定工件的最优加工顺序、最优工期和最优开始加工时间,使总工期、误工工件数及总完工时间之和最小。工件在工期之后完成则称为误工工件,工件在工期之前完成则是提前工件。工期指派分两种情况,一种是所有的工件工期都相等,另一种是不同的工件有不同的工期。对于上述两种情况分别给出了最优解的3个性质,并且证明了这个问题是多项式时间可解的。

Due date assignments scheduling of single machine under linear deteriorating

The authors study a due date assignments scheduling of single machine with deteriorating, and assume the due date assignment penalty is continuous and non-decreasing function and the processing of jobs are deteriorating, i. e. The actual processing times of jobs are a linear increasing function of their start processing times, where each job has a common deterioration rate. The objective is to find an optimal due date, the optimal processing sequence and the optimal start processing time to minimize the sum of due date assignment penalties and minimize the weighted number of tardy jobs and the total of completion time. The job is tardy if it complete after the due date, the job is early if it complete before the due date. There are two different due date assignment methods. The first is a method in which the assigned due dates are restricted to be equal while the second is a method that allows us to assign different due dates to different jobs. The authors provide three properties of the optimal solution for above two cases, and show that the problem is solvable in polynomial time.