平行机排序与转包问题的动态规划算法

作者：陈荣军; 唐国春^*

来源：纯粹数学与应用数学, 2022, 38(04): 487-493.

• 排序
• 转包
• 动态规划
• 平行机

研究制造商具有若干台平行机且允许工件转包给仅有一台单机的承包商加工排序问题.工件转包需要一定的转包费用以及运输时间.研究确定要转包工件集以及所有工件的加工顺序,分别为极小化工件总完工时间,最大延误,误工工件数与转包费用之和,证明了问题的NP困难性,并分别设计动态规划算法.

• 单位
  上海第二工业大学; 常州工学院