带有拒绝、恶化效应和安装时间的单机排序

Single machine scheduling problems with job rejection, deterioration effects and past-sequence-dependent setup times

研究带有安装时间、工件加工时间具有恶化效应及工件可拒绝的单机排序问题。工件的安装时间依赖于已完工工件的加工时间总和,且工件的加工时间同时受到双重恶化效应的影响。工厂可以拒绝加工工件,因而将工件分为接受与拒绝工件集,拒绝工件需要支付拒绝惩罚。目的是确定接受工件的集合、拒绝工件的集合以及接受工件集合中工件的最优排序,分别使最大完工时间、总完工时间、总完工时间的绝对差以及总等待时间的绝对差与总拒绝惩罚之和最小。将上述4个目标函数对应的问题分别转化为指派问题进行求解,给出了一个多项式时间算法,并证明了其时间复杂度。利用数值算例进行了验证,说明给出的求解算法有效。

In this paper, we consider the single machine scheduling problems with past sequence dependent setup times, deterioration effects and job rejection. The time to setup the machine depends on the total processing time of the jobs processed before, and the processing time of jobs are affected by two kinds of deterioration effects. The factory can reject some jobs, so the jobs are divided into acceptance and rejection sets. If one job is rejected, then a penalty should be imposed. The goal is to obtain the acceptance job set, the rejection job set and the optimal sequence of acceptance job set to minimize the sum of the given scheduling objectives, including the makespan, the total completion time, the total absolute differences in completion times and the total absolute differences in waiting times of the accepted jobs and the total rejection penalty of the rejected jobs. The above four problems are transformed into assignment problems. It is proved that these problems remain polynomially solvable under the proposed algorithm. The time complexity of the algorithm is obtained. A numerical example shows that the proposed algorithm is effective.