带有恶化和拒绝的工期指派的单机排序问题

讨论带有恶化和拒绝工件的工期指派的单机排序问题。工件的实际加工时间是其开始加工时间的线性增函数。如果工件被拒绝,则有一个惩罚费用,否则工件被加工。每个工件都要确定一个工期,文章讨论的工期指派分为CON(共同工期指派)和SLK(相同松弛工期指派)两种情况。对于CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的总费用最小。将该问题归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。对于SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的总费用最小。将其归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法。

Scheduling deteriorating and rejection jobs with due date assignment on a single machine

The authors consider the scheduling problems with deteriorating jobs,rejection jobs and due date assignment on a single machine.The actual processing times of jobs are a linear increasing function of their start processing times.If the job is rejected,there is a rejection cost,otherwise the job is processed.Every job has a due date.In this paper,we consider two popular due date assignment methods：common due date （CON）,equal slack （SLK）.For the CON due date assignment method,the problem is to find an optimal due date and the processing sequence simultaneously to minimize the total costs for the common due date assignment,earliness,tardiness and rejection penalties.We reduce the problems to a set of assignment problems which can be solved in O（n4） time.For the SLK due date assignment method,the objective is to find an optimal slack and the processing sequence simultaneously to minimize the total costs for the slack due date assignment,earliness,tardiness and rejection penalties.We reduce the problems to a set of assignment problems,we have shown that the optimal solution can be obtained in polynomial time.