English

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 111-118.

• 运筹学 • 上一篇    下一篇

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

谷存昌1,2, 张玉忠1,*   

  1. 1. 曲阜师范大学管理学院, 山东日照  276826; 2. 河南工业大学理学院, 郑州 450001; }
  • 收稿日期:2014-02-18 出版日期:2014-12-15 发布日期:2014-12-15
  • 通讯作者: 张玉忠 E-mail:yuzhongrz@163.com
  • 基金资助:

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

The coordination of transportation and serial batching scheduling

GU Cunchang1,2, ZHANG Yuzhong1,*   

  1. 1. School of Management, Qufu Normal University, Rizhao 276826, Shandong,  China; 2. College of Science, Henan University of Technology, Zhengzhou 450001, China
  • Received:2014-02-18 Online:2014-12-15 Published:2014-12-15

PDF

619

摘要： 近年来，工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注. 讨论了先用 $\ m$ 台车辆将工件从等待区域运输到继列分批处理机处, 再进行分批加工的协作排序问题, 加工一批工件需要支付一定的费用, 目标为最小化工件的总完工时间与批的加工费用之和. 在工件的加工时间都相等的情况下, 如果工件运输方案确定, 给出了多项式时间的动态规划算法; 如果工件运输方案不确定, 证明了该问题是{\, NP}-难的, 给出了车辆返回时间 $\ t=0$ 时, 最差性能比等于 $\ 2-\frac{1}{m}$ 的近似算法.

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

Abstract: The coordination of production scheduling and transportation has recently received a lot of attention in logistics and supply chain management. We study a coordinated scheduling problem in which the jobs are transported by $m$ 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 processing 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-\frac{1}{m}$.

Key words: supply chain scheduling, dynamic programming algorithm, complexity, worst case analysis

中图分类号: