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

doi:10.16381/j.cnki.issn1003-207x.2017.03.016

中国管理科学 ›› 2017, Vol. 25 ›› Issue (3): 137-146.doi: 10.16381/j.cnki.issn1003-207x.2017.03.016

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

王建军¹, 刘晓盼¹, 刘锋², 王杜娟¹

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

收稿日期:2015-03-21 修回日期:2015-10-13 出版日期:2017-03-20 发布日期:2017-05-27
通讯作者: 王建军(1977-),男(汉族),河北保定人,大连理工大学系统工程研究所教授,博士生导师,研究方向:干扰管理、生产调度等,E-mail:.drwangjj@dlut.edu.cn.
基金资助:
国家自然科学基金资助项目（71271039，71672019，71502026）；教育部"新世纪优秀人才支持计划"项目（NCET-13-0082）；中央高校基本科研业务费专项资金资助项目（DUT14YQ211）

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

WANG Jian-jun¹, LIU Xiao-pan¹, LIU Feng², WANG Du-Juan¹

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:2015-03-21 Revised:2015-10-13 Online:2017-03-20 Published:2017-05-27

摘要/Abstract

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

关键词: 鲁棒调度, 并行机, 加工时间可控, 随机机器故障, 匹配

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.

Key words: robust scheduling, unrelated parallel machines, controllable processing time, stochastic breakdowns, match-up

中图分类号:

C939

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

WANG Jian-jun, LIU Xiao-pan, LIU Feng, WANG Du-Juan. Robust Scheduling of Unrelated Parallel Machines Subject to Stochastic Breakdowns and Controllable Processing Times[J]. Chinese Journal of Management Science, 2017, 25(3): 137-146.

参考文献

[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.

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

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

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	徐东洋, 李昆鹏, 崔利刚, 田倩南. 供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题[J]. 中国管理科学, 2021, 29(1): 127-137.
[2]	池毛毛, 李延晖, 王伟军, 卢新元. 信息技术治理影响分销渠道敏捷的机理研究[J]. 中国管理科学, 2020, 28(7): 164-173.
[3]	李永海, 樊治平. 电子中介中考虑第三方评价的多属性商品交易匹配研究[J]. 中国管理科学, 2020, 28(7): 184-195.
[4]	胡春华, 赵慧, 童小芹, 任剑. 推荐系统对消费者网购支出的影响研究[J]. 中国管理科学, 2020, 28(6): 158-170.
[5]	杨皖苏, 杨善林, 杨希. 主动性-被动性员工创新行为:基于分布式领导的作用机制研究[J]. 中国管理科学, 2020, 28(6): 182-192.
[6]	徐小峰, 孙玉萍. 多枢纽轴辐式协同物流网络任务-路径优化匹配研究[J]. 中国管理科学, 2019, 27(9): 175-182.
[7]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[8]	任磊, 任明仑. 基于学习与协同效应的云制造任务动态双边匹模型[J]. 中国管理科学, 2018, 26(7): 63-70.
[9]	吴勇, 李倩, 朱卫东. 董事责任保险能否提升公司价值?——基于公司治理视角的研究[J]. 中国管理科学, 2018, 26(4): 188-196.
[10]	孙晓琳, 金淳, 马琳, 王文波. 云制造环境下基于本体和模糊QoS的供应商匹配方法[J]. 中国管理科学, 2018, 26(1): 128-138.
[11]	石宝峰, 王静, 迟国泰. 普惠金融、银行信贷与商户小额贷款融资——基于风险等级匹配视角[J]. 中国管理科学, 2017, 25(9): 28-36.
[12]	乐琦. 直觉模糊环境下考虑匹配意愿的双边匹配决策[J]. 中国管理科学, 2017, 25(6): 161-168.
[13]	丁斅, 盛昭瀚, 刘慧敏. 基于模糊综合分析和Gale-Shaplev理论的重大工程二阶段招投标机制研究[J]. 中国管理科学, 2017, 25(2): 147-154.
[14]	余顺坤, 杨文茵. 组织-员工发展积分模型与应用研究[J]. 中国管理科学, 2017, 25(11): 168-178.
[15]	姚铮, 马超群, 杨智. 新产品开发网络资源与技术资源匹配关系:基于中国制造业企业的实证研究[J]. 中国管理科学, 2016, 24(4): 148-158.