主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院
论文

时间窗口约束下基于改进蚁群算法的协同制造调度研究

展开
  • 1. 大连海事大学交通运输工程学院, 辽宁 大连 116026;
    2. 东南大学交通学院, 江苏 南京 210096;
    3. 大连海事大学航运经济与管理学院, 辽宁 大连 116026

收稿日期: 2015-05-05

  修回日期: 2016-03-10

  网络出版日期: 2018-06-22

基金资助

国家自然科学基金资助项目(71301108,71201106);中国博士后特别资助项目(2014T70462);中国博士后面上项目(2013M530228)

Collaborative Manufacturing Scheduling based on Improved Ant Colony Optimization Algorithm with Time Window Constraint

Expand
  • 1. Transportation Engineering College, Dalian Maritime University, Dalian 116026, China;
    2. School of Transportation, Southeast University, Nanjing 210096, China;
    3. School of Shipping Economic and Management, Dalian Maritime University, Dalian 116026, China

Received date: 2015-05-05

  Revised date: 2016-03-10

  Online published: 2018-06-22

摘要

与传统调度模式不同,协同制造模式下企业之间的调度模式极其复杂。协同企业间的加工工序路线并不固定,且不同类型产品具有不同的加工路线网络。为此本文针对平衡型、瓶颈型、跳跃型、混合型四类具有典型特点的协同制造网络Gp进行分析和设计;考虑制造企业同类产品合并加工策略,构建基于连续加工量的分段生产成本函数;通过设计合理的订单最早交货时间和最晚交货时间,对订单交货进行时间窗口约束,并在此基础上构建了由制造商生产成本Wcm、订单等待WskQkT'k)和提前完工库存成本WskQkTk)、延期惩罚成本构成WlkQkT'″k)的目标函数。为求解该模型,创新性将蒙特卡洛思想引入蚁群算法,提高蚂蚁选择合理性,避免局部最优;同时,采用移动窗口[min, max]奖励机制,并且对信息素奖励乘以平衡系数kN)提高奖励可信度,加快搜索速度并提高求解性能。仿真结果表明,本文构建调度模型合理,可以获得优化的调度结果;同时,本文提出的蚁群改进寻优算法具有良好的求解速度和收敛性,算法具有较好的稳定性。

本文引用格式

唐亮, 何杰, 靖可, 靳志宏 . 时间窗口约束下基于改进蚁群算法的协同制造调度研究[J]. 中国管理科学, 2018 , 26(4) : 97 -107 . DOI: 10.16381/j.cnki.issn1003-207x.2018.04.011

Abstract

Since the collaborative and cooperative manufacturing mode is gaining popularity, which has the merit of utilizing superior resources in collaborative factories to improve production efficiency, thus it becomes important to do the study on scheduling in collaborative manufacturing mode. In a collaborative manufacturing mode, there are multiple processing paths that forming the collaborative manufacturing networks, and thus the corresponding networks are dynamic and changable. Additionally, different type products belong to different type collaborative manufacturing networks and this makes our model more complex. In light of that, four general types of collaborative manufacturing networks Gp are constructed and discussed, including balance type network, bottleneck type network, jump type network, and hybrid type network. Some pramaters of scheduling model are also designed to make problem more reasable, i.e., production cost function, earliest delivery time tfk and latest delivery time tlk. An objective function composed of processing costs Wcm, inventory costs Wsk(Qk, T'k), and the two penalty costs of early completion costs Wsk(Qk, Tk) and tardiness costs Wlk(Qk, T'″k) is then constructed. In order to solve our model, an improved ant colony optimization algorithm is presented, into which the Monte Carlo algorithm is incorporated. In particular, the upper confidence bound zi is used to guide the ant selection. Meanwhile, a moving window award mechanism[min, max] is also designed to improve award criteria. Given that the expectation window moves frequently with the increase of simulation, and thus the credible level of expectation window increases. In view of this, the fixed pheromone concentration should multiply a balance coefficient k(N) as the award value to improve the rewards credibility. The simulation results show that our designed model is reasonable and practical. Meanwhile, our proposed algorithm has fast solving speed, good convergence and stability. Our research work is benefit for enterprise scheduling in collaborative manufacturing mode.

参考文献

[1] 范玉顺. 网络化制造的内涵与关键技术问题[J]. 计算机集成制造系统-CIMS, 2003, 9(7):576-582.

[2] 王宛山, 巩亚东, 郁培丽. 网络化制造[M]. 沈阳:东北大学出版社, 2003.

[3] Thomas A, Venkateswaran J, Singh G, et al. A resource constrained scheduling problem with multiple independent producers and a single linking constraint:A coal supply chain example[J]. European Journal of Operational Research, 2014, 236:946-956.

[4] Selvarajah E, Zhang Rui. Supply chain scheduling at the manufacturer to minimize inventory holding and delivery costs[J]. International Journal of Production Economics, 2014, 147:117-124.

[5] Sawik T. Coordinated supply chain scheduling[J]. International Journal of Production Economics, 2009, 120(2):437-451.

[6] Liu S C, Chen A Z. Variable neighborhood search for the inventory routing and scheduling problem in a supply chain[J]. Expert Systems with Applications, 2012, 39(4):4149-4159.

[7] Hajiaghaei-Keshteli M, Aminnayeri M, Ghomi S M T F. Integrated scheduling of production and rail transportation[J]. Computers & Industrial Engineering, 2014, 74:240-256.

[8] Chen Zhilong. Integrated production and outbound distribution scheduling:review and extensions[J]. Operations Research, 2010, 58(1):130-148.

[9] 孙靖, 林杰. 信息不完全共享下MC供应链动态调度模型研究[J]. 系统仿真学报, 2007, 19(9):1943-1948.

[10] Yimer A, Demirli K. A genetic approach to two-phase optimization of dynamic supply chain scheduling[J]. Computers & Industrial Engineering, 2010, 58(3):411-422.

[11] 刘小华, 林杰. 基于遗传粒子群混合算法的供应链调度优化[J]. 控制与决策, 2011, 26(4):501-506.

[12] 姚建明, 张秀敏, 刘丽文. 基于改进蚂蚁算法的拉动式供应链动态调度分析[J]. 中国管理科学, 2006, 14(3):20-26.

[13] 裴军, 刘心报, 范雯娟, 等. 基于生产与运输集成的供应链调度优化问题[J]. 中国管理科学, 2012, 20(S1):586-593.

[14] 姚建明, 刘丽文, 蒲云, 等. MC模式下供应链动态调度的蚁群寻优分析[J]. 管理科学学报, 2007, 10(3):7-14.

[15] 程八一, 李明, 陈波, 等. 差异分批模式下的供应链调度算法[J]. 系统工程学报, 2014, 29(4):515-526.

[16] Lee Y, Jeong C, Moon C. Advanced planning and scheduling with outsourcing in manufacturing supply chain[J]. Computers & Industrial Engineering, 2002, 43(1), 351-374.

[17] 唐亮, 靖可, 何杰. 网络化制造模式下基于改进蚁群算法的供应链调度优化研究[J]. 系统工程理论与实践, 2014, 34(5):1167-1175.
文章导航

/