工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中,给定一个待加工工件集,每个工件在到达之后,可以被选择安排到m台同类平行机器中的某一台机器上进行加工,也可以被选择拒绝加工,但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当m为固定常数时,设计了一个伪多项式时间动态规划精确算法;当m为任意输入时,设计了一个近似算法,当接受工件个数大于(m-1)时,该算法近似比为3,当接受工件个数小于(m-1)时,该算法近似比为(2+ρ),其中ρ为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。

In this paper,we consider the uniform parallel machine scheduling problem with release dates and job rejection.In this problem,given a set of jobs to be arranged subject to the job release dates,each job is either accepted to process on one of m uniform parallel machines or rejected by paying its rejection penalty.The goal is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs.When m is a fixed constant,we provide a pseudo-polynomial time dynamic programming exact algorithm.When m is arbitrary,we derive an approximation algorithm.If the number of accepted jobs is no less than(m-1),then the derived approximation algorithm achieves the performance ratio of 3;otherwise,the derived approximation algorithm achieves the performance ratio of(2+ρ),whereρis the ratio of the maximum machine processing speed to the minimum machine processing speed.In the end,by a numerical experiment,we illustrate the running way for the derived approximation algorithm.