工件的运输和继列分批加工协作排序问题  

The coordination of transportation and serial batching scheduling

作　　者：谷存昌[1,2] 张玉忠[1] 

机构地区：[1]曲阜师范大学管理学院,山东日照276826 [2]河南工业大学理学院,郑州450001

出　　处：《运筹学学报》2014年第4期111-118,共8页Operations Research Transactions

基　　金：教育部高等学校博士学科点专项基金(No.20123705110003);国家自然科学基金(Nos.11071142;11201259;11201121);河南省教育厅自然科学基金(Nos.2011B110007;2011B110008);山东省自然科学基金(No.ZR2010AM034)

摘　　要：近年来,工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注.讨论了先用m台车辆将工件从等待区域运输到继列分批处理机处,再进行分批加工的协作排序问题,加工一批工件需要支付一定的费用,目标为最小化工件的总完工时间与批的加工费用之和.在工件的加工时间都相等的情况下,如果工件运输方案确定,给出了多项式时间的动态规划算法;如果工件运输方案不确定,证明了该问题是NP-难的,给出了车辆返回时间t=0时,最差性能比等于2-1/m的近似算法.The coordination of production scheduling and transportation has recent- ly received a lot of attention in logistics and supply chain management. We study a coordinated scheduling problem in which the jobs are transported by ra vehicles from a holding area to a single serial batching machine for further processing, each batch of jobs to be processed occurs a processing cost. The objective is minimizing the sum of the jobs＇ total completion time and the total processing cost. Under the condition of the job pro- cessing times are equal, if the job assignment to the vehicles is predetermined, we provide a polynomial time dynamic programming algorithm, for the general problem, prove that it is NP-hard. When the returning time of vehicle is 0, we present the approximation algorithm and prove that the worst case ratio of the algorithm is 2-1/m.

关 键 词：供应链排序 动态规划算法 复杂性 最差性能分析 

分 类 号：O221.1[理学—运筹学与控制论]