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

随机机器故障下加工时间可控的并行机鲁棒调度

展开
  • 1. 大连理工大学系统工程研究所, 辽宁 大连 116023;
    2. 东北财经大学管理科学与工程学院, 辽宁 大连 116025

收稿日期: 2015-03-21

  修回日期: 2015-10-13

  网络出版日期: 2017-05-27

基金资助

国家自然科学基金资助项目(71271039,71672019,71502026);教育部"新世纪优秀人才支持计划"项目(NCET-13-0082);中央高校基本科研业务费专项资金资助项目(DUT14YQ211)

Robust Scheduling of Unrelated Parallel Machines Subject to Stochastic Breakdowns and Controllable Processing Times

Expand
  • 1. Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China;
    2. School of Management Science and Engineering, Dongbei University of Finance & Economics, Dalian 116025, China

Received date: 2015-03-21

  Revised date: 2015-10-13

  Online published: 2017-05-27

摘要

现实生产环境中经常面临随机机器故障,造成初始调度方案性能恶化。针对并行机环境下工件加工时间可控,提出内外两层嵌套式的鲁棒调度策略,旨在降低随机机器故障造成的成本损失期望,干扰发生后通过局部修复实现跟初始计划的匹配。内层建立非线性0-1混合整数规划模型,通过二次锥化方法来求解初始调度方案在随机机器故障干扰情景下的成本损失期望。外层设计基于工件柔性和机器不可用概率的排序算法;由于问题内在的复杂性,利用遗传算法优化工件柔性参数,进而增强初始调度方案的鲁棒性。最后设计随机仿真实验,分别验证了在机器故障所造成的单位时间扰动成本不同时和机器维修水平不同时所提鲁棒调度策略的有效性。

本文引用格式

王建军, 刘晓盼, 刘锋, 王杜娟 . 随机机器故障下加工时间可控的并行机鲁棒调度[J]. 中国管理科学, 2017 , 25(3) : 137 -146 . DOI: 10.16381/j.cnki.issn1003-207x.2017.03.016

Abstract

Inevitable machine breakdowns always degrade the performance of the initial schedule in the practice. Considering the controllable processing time in unrelated parallel machines layout, how to generate a robust schedule to reduce the expectation value of the loss cost caused by the stochastic machine failures is studied. Therefore, a robust scheduling strategy of two nested layers is designed. In the inner layer, a nonlinear 0-1 mixed integer model is built to calculate the expectation of the loss cost. Because of the model's complexity, it is translated into second-order cone constrains for solving efficiency. In the outer layer, sorting algorithm is designed based on the job's flexibility and the probability of machine unavailability. Due to inherent complex and unstructured nature, genetic algorithm is used to optimize job's flexible parameters, and to further enhance the robustness of the initial schedule. Through randomly generated numerical experiments, It shows that the proposed scheduling strategy is robust against different disturbance cost per unit time and different mean time to repair of machine breakdown. The research has a certain reference for sorting robust schedule and optimizing job's flexible parameters.

参考文献

[1] 刘乐, 周泓. 一种常见干扰条件下的开放式车间重调度研究[J].管理科学学报,2014, 17(6):28-48.

[2] Ahmadi E, Zandieh M, Farrokh M, et al. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms[J]. Computers & Operations Research, 2016, 73:56-66.

[3] Fazayeli M, Aleagha M R, Bashirzadeh R, et al. A hybrid meta-heuristic algorithm for flowshop robust scheduling under machine breakdown uncertainty[J]. International Journal of Computer Integrated Manufacturing, 2016, 29(7):709-719.

[4] Mehta S V, Uzsoy R M. Predictable scheduling of a job shop subject to breakdowns[J]. IEEE Transactions on Robotics and Automation, 1998, 14(3):365-378.

[5] 尹文君, 刘民, 吴澄. 随机故障下单机鲁棒调度算法的遗传编程方法[J]. 清华大学学报(自然科学版), 2005, 45(1):81-84.

[6] 李巧云, 王冰, 王晓明. 随机机器故障下单机预测调度方法[J]. 系统工程理论与实践, 2011, 31(12):2387-2393.

[7] Liu Lin, Gu Hanyu, Xi Yugeng. Robust and stable scheduling of a single machine with random machine breakdowns[J]. International Journal of Advanced Manufacturing Technology, 2007, 31(7-8):645-654.

[8] Al-Hinai N, ElMekkawy T Y. Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm[J]. International Journal of Production Economics, 2011, 132(2):279-291.

[9] Xiong Jian, Xing Lining, Chen Yingwu. Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns[J]. International Journal of Production Economics, 2013, 141(1):112-126.

[10] Yang Bibo, Geunes J. Predictive-reactive scheduling on a single resource with uncertain future jobs[J]. European Journal of Operational Research, 2008, 189(3):1267-1283.

[11] Akturk M S, Atamturk A, Gurel S. Parallel machine match-up scheduling with manufacturing cost considerations[J]. Journal of Scheduling, 2010, 13(1):95-110.

[12] Gurel S, Korpeoglu E, Akturk M S. An anticipative scheduling approach with controllable processing times[J]. Computers & Operations Research, 2010, 37(6):1002-1013.

[13] 刘锋, 王征, 王建军, 等. 加工能力受扰的可控排序干扰管理[J]. 系统管理学报, 2013, 22(4):505-512.

[14] 边志兴. 作业车间的模糊动态调度问题研究[J].中国管理科学,2008,16(S1):76-83.

[15] Tang Lixin, Zhao Yue, Liu Jiyin. An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production[J].IEEE Transactions onEvolutionary Computation, 2014, 18(2):209-225.

[16] Felix T S, Shekhar P, Tiwari M K. Dynamic scheduling of oil tankers with splitting of cargo at pickup and delivery locations:A multi-objective ant colony-based approach[J]. International Journal of Production Research, 2014, 52(24):7436-7453.

[17] Shen Xiaoning, Yao Xin. Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems[J]. Information Sciences, 2015, 298:198-224.

[18] Liu Le, Zhou Hong. On the identical parallel-machine rescheduling with job rework disruption[J]. Computers & Industrial Engineering, 2013, 66(1):186-198.

[19] Cui Weiwei, Lu Zhiqiang, Pan Ershun. Integrated production scheduling and maintenance policy for robustness in a single machine[J]. Computers & Operations Research, 2014, 47:81-91.

[20] Akturk M S, Atamturk A, Gurel S. A strong conic quadratic reformulation for machine-job assignment with controllable processing times[J]. Operations Research Letters, 2009, 37(3):187-191.

[21] 李素粉, 朱云龙, 尹朝万. 具有随机加工时间和机器故障的流水车间调度[J]. 计算机集成制造系统, 2005, 11(10):1425-1429.

[22] 刘锋, 王建军, 饶卫振, 等. 安装时间与次序相关的生产调度干扰管理研究[J].中国管理科学,2014, 22(1):45-54.

[23] Bonfill A, Espuna A, Puigjaner L. Proactive approach to address the uncertainty in short-term scheduling[J]. Computers & Chemical Engineering, 2008, 32(8):1689-1706.

[24] Wu S D, Byeon E, Storer R H. A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[J]. Operations Research, 1999, 47(1):113-124.

[25] Alizadeh F, Goldfarb D. Second-order cone programming[J]. Mathematical Programming, 2003, 95(1):3-51.

[26] Adiri I, Bruno J, Frostig E, et al. Single-machine flow-time scheduling with a single breakdown[J]. Acta Informatica, 1989, 26(7):679-685.
文章导航

/