转包费用有限的串行分批加工流水作业排序问题

摘要

研究工件既可以在制造商机器上加工、又可以转包给承包商加工的m台机流水作业排序问题。考虑工件在制造商机器上以串行分批方式加工，即工件按串行方式接连在机器上成批加工，批加工时间为该批中所有工件的工时之和，且加工后被分批运送给客户；同时，因部分工件被转包给承包商加工，还考虑制造商需要支付一定的转包费用。在转包总费用不超过给定值情况下，研究极小化工件加工成本与运输成本之和的有效算法。其中，加工成本分别取制造商处工件最大完工时间及工件总完工时间，运输成本则与工件批数成正比。对于工件加工时间仅依赖于工件的情形，针对不同的加工成本，分析了问题的NP困难性及最优解的结构，分别设计了2个近似算法；对于工件加工时间仅依赖于机器的情形，则在分析解结构的基础上提出了2个多项式时间算法。

关键词

流水作业排序 / 转包 / 串行分批 / 近似算法