NWHFS多扰动调度问题的干扰管理方法
|
摘要
针对多扰动并发工况下无等待混合流水线(NWHFS)生产调度问题,构建了多重约束下兼顾初始调度目标(最小化工件完工时间加权和)和扰动修复目标(最小化工件完工滞后时间加权和)的干扰管理调度模型,设计了搜索方向动态可变的多目标随机加权处理策略。并将基于高斯变异的全局寻优改进策略与基于随机邻域结构的局部精细搜索策略相结合,提出了一种混合微粒群优化求解算法。数值算例仿真结果表明,包含高斯变异算子和随机邻域结构的混合微粒群优化算法求解本文干扰管理调度模型是有效的。
This paper addresses the scheduling problem of dealing with either a random or an anticipated disturbance event, which simultaneously occurs after a subset of jobs has been processed in the no-wait hybrid flow shop(NWHFS). The approach proposed in this paper differs from most rescheduling analysis and countermeasure in that the cost objective(minimize total weighted completed time) associated with the deviation objective(minimize total weighted delayed time) between the original and the new schedule is included. A novel combinational solution strategy is based on the Gauss mutation global optimization, and on a random multi-neighborhood local search. Besides, a disruption recovery model for NWHFS is constructed and a mixed PSO algorithm is designed to solve the model proposed. Cases are concentrated on in which computational results are reported and the effectiveness of the proposed solution is verified.
This paper addresses the scheduling problem of dealing with either a random or an anticipated disturbance event, which simultaneously occurs after a subset of jobs has been processed in the no-wait hybrid flow shop(NWHFS). The approach proposed in this paper differs from most rescheduling analysis and countermeasure in that the cost objective(minimize total weighted completed time) associated with the deviation objective(minimize total weighted delayed time) between the original and the new schedule is included. A novel combinational solution strategy is based on the Gauss mutation global optimization, and on a random multi-neighborhood local search. Besides, a disruption recovery model for NWHFS is constructed and a mixed PSO algorithm is designed to solve the model proposed. Cases are concentrated on in which computational results are reported and the effectiveness of the proposed solution is verified.
引文
[1] Rock H. The three-machine no-wait flow shop problem is NP-complete[J]. Journal of the Association for Computing Machinery, 1984, 31(2): 336-345.
[2] Pinedo M.Scheduling theory, algorithm and systems[M]. 4th ed. New York: Springer Science+Business Media, LLC, 2012.
[3] Goyal S K, Sriskandarajah C. No-wait shop scheduling: computational complexity and approximate algorithms[J]. Operations Research, 1988, 25: 220-244.
[4] Wang H. Flexible flow shop scheduling: Optimum, heuristics and arti?cial intelligence solutions[J]. Expert Systems, 2005, 22(2): 78-85.
[5] Aldowaisan T. A new heuristic and dominance relations for no-wait flow shops with setups[J]. Comput. Oper. Res., 2001, 28: 563-584.
[6] Aldowaisan T, Allahverdi A. New heuristics for no-wait flow shops to minimize makespan[J]. Computation Operation Research, 2003, 30: 1219-1231.
[7] Huang R H, Yang C L, Liu S C. No-wait flexible flow shop scheduling with due windows[J]. Mathematical Problems in Engineering, 2015, 501: 456719.
[8] Asefi H, Jolai F, Rabiee M, et al. A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flow shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2014, 75(5-8): 1017-1033.
[9] 潘全科, 赵保华, 屈玉贵. 无等待流水车间调度问题的优化[J]. 计算机学报, 2008, 31 (7): 1147-1154.
[10] Akhshabi M, Tavakkoli R, Rahnamay F. A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time[J]. The International Journal of Advanced Manufacturing Technology, 2014, 70(5-8): 1181-1188.
[11] 庞新福,俞胜平,张志宇,等. 炼钢-连铸生产优化重调度方法[J]. 系统工程学报, 2010, 25(1): 98-104.
[12] Qi X T, Bard J F, Yu G. Disruption management for machine scheduling: The case of SPT schedules[J]. International Journal of Production Economics, 2006, 103(1): 166-184.
[13] Lee C Y, Yu G. Parallel-machine scheduling under potential disruption[J]. Optimization Letters, 2008, 2(1): 27-37.
[14] Liu F, Wang J J, Yang D L. Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics[J]. Journal of Manufacturing Systems, 2013, 32(4): 715-723.
[15] 薄洪光,张鑫,潘裕韬. 具有外包选择的无等待流水线干扰修复模型[J]. 系统管理学报, 2015, 24(4): 485-495.
[16] 潘逢山,叶春明. 微粒群优化算法在流水线干扰管理调度中的应用[J]. 工业工程与管理, 2012, 17(4): 48-53.
[17] 刘锋,王征,王建军,等. 加工能力受扰的可控排序干扰管理[J]. 系统管理学报, 2013, 22(4): 505-512.
[18] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science. [s.l]:[s.n],1995, 1: 39-43.
[19] 刘小龙, 李荣钧, 杨萍. 基于高斯分布估计的细菌觅食优化算法[J]. 控制与决策, 2011, 26(8): 1233-1238.
[20] 王凌,刘波. 微粒群优化与调度算法[M]. 北京: 清华大学出版社, 2008.
[21] Reeves C R, Yamada T. Genetic algorithms, path relinking and the flow shop problem[J]. Evolutionary Computation, 1998, 6: 45-60.
[22] Reeves C R. Landscapes, operations and heuristic search[J]. Annals of Operations Research, 1999,86: 473-490.
[2] Pinedo M.Scheduling theory, algorithm and systems[M]. 4th ed. New York: Springer Science+Business Media, LLC, 2012.
[3] Goyal S K, Sriskandarajah C. No-wait shop scheduling: computational complexity and approximate algorithms[J]. Operations Research, 1988, 25: 220-244.
[4] Wang H. Flexible flow shop scheduling: Optimum, heuristics and arti?cial intelligence solutions[J]. Expert Systems, 2005, 22(2): 78-85.
[5] Aldowaisan T. A new heuristic and dominance relations for no-wait flow shops with setups[J]. Comput. Oper. Res., 2001, 28: 563-584.
[6] Aldowaisan T, Allahverdi A. New heuristics for no-wait flow shops to minimize makespan[J]. Computation Operation Research, 2003, 30: 1219-1231.
[7] Huang R H, Yang C L, Liu S C. No-wait flexible flow shop scheduling with due windows[J]. Mathematical Problems in Engineering, 2015, 501: 456719.
[8] Asefi H, Jolai F, Rabiee M, et al. A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flow shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2014, 75(5-8): 1017-1033.
[9] 潘全科, 赵保华, 屈玉贵. 无等待流水车间调度问题的优化[J]. 计算机学报, 2008, 31 (7): 1147-1154.
[10] Akhshabi M, Tavakkoli R, Rahnamay F. A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time[J]. The International Journal of Advanced Manufacturing Technology, 2014, 70(5-8): 1181-1188.
[11] 庞新福,俞胜平,张志宇,等. 炼钢-连铸生产优化重调度方法[J]. 系统工程学报, 2010, 25(1): 98-104.
[12] Qi X T, Bard J F, Yu G. Disruption management for machine scheduling: The case of SPT schedules[J]. International Journal of Production Economics, 2006, 103(1): 166-184.
[13] Lee C Y, Yu G. Parallel-machine scheduling under potential disruption[J]. Optimization Letters, 2008, 2(1): 27-37.
[14] Liu F, Wang J J, Yang D L. Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics[J]. Journal of Manufacturing Systems, 2013, 32(4): 715-723.
[15] 薄洪光,张鑫,潘裕韬. 具有外包选择的无等待流水线干扰修复模型[J]. 系统管理学报, 2015, 24(4): 485-495.
[16] 潘逢山,叶春明. 微粒群优化算法在流水线干扰管理调度中的应用[J]. 工业工程与管理, 2012, 17(4): 48-53.
[17] 刘锋,王征,王建军,等. 加工能力受扰的可控排序干扰管理[J]. 系统管理学报, 2013, 22(4): 505-512.
[18] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science. [s.l]:[s.n],1995, 1: 39-43.
[19] 刘小龙, 李荣钧, 杨萍. 基于高斯分布估计的细菌觅食优化算法[J]. 控制与决策, 2011, 26(8): 1233-1238.
[20] 王凌,刘波. 微粒群优化与调度算法[M]. 北京: 清华大学出版社, 2008.
[21] Reeves C R, Yamada T. Genetic algorithms, path relinking and the flow shop problem[J]. Evolutionary Computation, 1998, 6: 45-60.
[22] Reeves C R. Landscapes, operations and heuristic search[J]. Annals of Operations Research, 1999,86: 473-490.