科研之友
微信
新浪微博
Facebook
分享链接
摘要
本文研究了加工工件的机器集具有嵌套型限制下的混合分批平行机排序问题。具体来说,给定一个待加工的工件集需在多台平行批处理机中的一台进行加工,每个工件有它的加工时间和可加工它的机器集,这些机器集之间满足嵌套型加工限制;每台机器可以同时加工多个工件,称为一个批次,只要批内工件总个数不超过其容量即可;一个批次的加工时间等于该批中工件的最大加工时间与总加工时间的加权和;目标函数是极小化最大完工时间。该问题包含经典的平行机排序问题为其特殊情形,为强NP-困难的。对此设计了一个性能比为(2+α)的近似算法,其中α为给定的权重参数,满足0≤α≤1。
- 单位
