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

Dynamic programmings on parallel machine scheduling with outsourcing

作　　者：陈荣军[1] 唐国春[2] Chen Rongjun;Tang Guochun(School of Sciences,Changzhou Institute of Technology,Changzhou 21332,China;Institute of Management Engineering,Shanghai Second Polytechnic University,Shanghai 201209,China)

机构地区：[1]常州工学院理学院,江苏常州213032 [2]上海第二工业大学管理工程研究所,上海201209

出　　处：《纯粹数学与应用数学》2022年第4期487-493,共7页Pure and Applied Mathematics

基　　金：国家自然科学基金(71371120)。

摘　　要：研究制造商具有若干台平行机且允许工件转包给仅有一台单机的承包商加工排序问题.工件转包需要一定的转包费用以及运输时间.研究确定要转包工件集以及所有工件的加工顺序,分别为极小化工件总完工时间,最大延误,误工工件数与转包费用之和,证明了问题的NP困难性,并分别设计动态规划算法.This paper studies parallel machine scheduling,in which jobs are allowed to be outsourced to a subcontractor with s single machine.Outsourcing requires a certain outsourcing cost and transpotation time.In this paper,the jobs′set subcontracted and the schedule of all jobs will be determined such that the sum of outsourcing cost and total completion time,lateness or the number of tardy jobs is minimized,respectively.The complexities are analyzed and three dynamic programming algorithmes are proposed.

关 键 词：排序 转包 动态规划 平行机 

分 类 号：O224[理学—运筹学与控制论]