三台带两个服务等级的平行机排序问题算法研究

Research for algorithm on the scheduling problem of three parallel machines with two GoS levels

研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设计了一个近似比严格小于3/2的新算法,改进了已知结果。同时,在加工时间满足2的幂次方条件下,设计了一个新算法,并证明了该算法总能得到一个最优分配。

The problem of scheduling parallel machines with two grades of service(GoS) is investigated. Given are three machines and independent jobs, each job and machine assigned the GoS levels of 1 or 2. The processing rule is that the job is allowed to be processed on some particular machines only when the GoS level of the job is no less than that of the machine, the objective is to minimize the makespan. For this problem, a new algorithm with an approximation ratio strictly less than 3/2 is proposed, which is better than the previous algorithm. Moreover, a new algorithm is obtained for the problem of processing time satisfying a power of 2 condition for the scheduling problem with GoS levels, and it is shown that the algorithm always obtains an optimal assignment.