工件具有任意尺寸的混合分批平行机排序问题的近似算法

摘要

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中,一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸,每台机器可以同时处理多个工件,称为一个批,只要这些工件尺寸之和不超过其容量;一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和;目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形,为强NP-困难的。对此给出了一个(2+2α+α^(2))-近似算法,其中α为给定的权重参数,满足0≤α≤1。