混合流水作业的排序问题

Scheduling problem of hybrid flow job

研究了一类混合流水作业的排序问题,设置了2个处理中心,第1个处理中心含1台机器,第2个处理中心含m台机器.当作业在第2个处理中心加工时,需要多台机器同时加工.目标函数为最小化最大完工时间.讨论了3种情况,得到了以下结论:对于问题HF(1,P_(2))|M_(j)|C_(max)提出了3/2-近似算法,对于问题HF(1,P_(3))|M_(j)|C_(max),提出了3-近似算法,对于问题HF(1,P_(m))|M_(j)|C_(max),可以得到目标函数与最优解的比值为1+2 m.

In this paper,a hybrid flow job scheduling problem which consists of two processing centers is considered.The first processing center contains one machine,the second processing center contains an identical machines.When the job is processed in the second processing center,multiple machines are required to process simultaneously.The objective function is to minimize makespan.In this paper,three cases are discussed and the following conclusions are obtained.For HF(1,P_(2))|M_(j)|C_(max),we proposed the 3/2-approximation algorithm;for HF(1,P_(3))|M_(j)|C_(max),we proposed the 3-approximation algorithm;for HF(1,P_(m))|M_(j)|C_(max),the ratio of objective function to optimal solution is1+2 m.