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.
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
.
DOI: 10.16381/j.cnki.issn1003-207x.2017.03.016
[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.
