混合无等待流水线干扰管理调度方法研究

doi:10.12005/orms.2016.0109

运筹与管理 ›› 2016, Vol. 25 ›› Issue (3): 246-254.DOI: 10.12005/orms.2016.0109

混合无等待流水线干扰管理调度方法研究

薄洪光,张鑫,潘裕韬

大连理工大学运营与物流管理研究所,辽宁大连 116023

收稿日期:2013-05-18 出版日期:2016-06-25
作者简介:薄洪光(1975-),男,博士,副教授,主要研究方向:生产调度与干扰管理。
基金资助:
国家自然科学基金重点项目(61533005);国家科技支撑计划项目(2015BAF08B02);教育部人文社会科学研究青年基金项目(11YJC630005);中国博士后科学基金特别资助和面上项目(201104592, 20100481222);中央高校基本科研业务费资助(DUT14RW101)

Study on Scheduling Method Based on Disruption Management for Hybrid N-wait Flow Shop

BO Hong-guang, ZHANG Xin, PAN Yu-tao

Institute of Production Operation and Logistics Management, Dalian University of Technology, Dalian 116023, China

Received:2013-05-18 Online:2016-06-25

摘要/Abstract

摘要： 针对带分批约束的混合无等待流水加工环境中干扰事件的出现导致初始调度计划发生偏离的问题,研究如何运用干扰管理理论来应对工件变更扰动情况,建立了兼顾最小化工件完工时间加权和指标(初始调度目标)和最小化工件完工滞后时间加权和指标(偏离校正目标)的干扰管理调度模型,提出了双层微粒群优化策略与随机多邻域搜索机制相结合的混合求解算法。数值算例仿真实验结果表明,包含“插入-交换”大概率邻域搜索算子的混合微粒群优化算法求解本文所构建的干扰管理调度模型是有效的。

关键词: 运筹学, 生产调度, 干扰管理, 微粒群优化算法, 混合无等待流水线

Abstract: To solve the batch scheduling problem for a random or an anticipated job-change disruption in hybrid no-wait flow shop, a novel scheduling method based on disruption management is presented. The scheduling model is built considering both the target to minimize total weighted completion time(the original objective)and the target to minimize total weighted delay time(the disruption repairing objective). By combining multi-objective approaching policy with the bi-level particle swarm optimization and stochastic probability multi-neighborhood search mechanism, a heuristic hybrid algorithm is proposed. The numerical experiments show that the hybrid PSO algorithm is effective to the disruption management-based scheduling model, including “insert-change” great probability neighborhood search operator.

Key words: operations research, production scheduling, disruption management, PSO algorithm, hybrid no-wait flow shop

中图分类号:

O223

薄洪光,张鑫,潘裕韬. 混合无等待流水线干扰管理调度方法研究[J]. 运筹与管理, 2016, 25(3): 246-254.

BO Hong-guang, ZHANG Xin, PAN Yu-tao. Study on Scheduling Method Based on Disruption Management for Hybrid N-wait Flow Shop[J]. Operations Research and Management Science, 2016, 25(3): 246-254.

参考文献

[1] Rock H. The three-machine no-wait flowshop problem is NP-complete[J]. Journal of the Association for Computing Machinery, 1984, 31(2): 336-345.
[2] Bassem Jarboui, Saber Ibrahim, Patrick Siarry, Abdelwaheb Rebai. A combinatorial particle swarm optimisation for solving permutation flowshop problems[J]. Computers & Industrial Engineering, 2008, 54: 526-538.
[3] Hall N G, Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process[J]. Operations research, 1996, 44(3): 510-525.
[4] Goyal S K, Sriskandarajah C. No-wait shop scheduling: computational complexity and approximate algorithms[J]. Operations research, 1988, 25: 220-244.
[5] Van Deman J M, Baker K R. Minimisation mean flow time in flowshop with no intermediate queues[J]. AIIE Trans, 1974, 6: 28-34.
[6] Tang L X, Luh P B, Liu J Y. Steel-making process scheduling using Lagrangian relaxation[J]. International Journal of Production Research, 2002, 40(1): 55-70.
[7] Xuan H, Tang L X. Scheduling a hybrid flowshop with batch production as the last stage[J]. Computer & Operations Research, 2007, 34(9): 2718-2733.
[8] 庞新福,俞胜平,张志宇,郑秉霖,柴天佑.炼钢-连铸生产优化重调度方法[J].系统工程学报,2010,25(1):98-104.
[9] 刘明周,单晖,蒋增强,葛茂根,扈静,张铭鑫.不确定条件下车间动态重调度优化方法[J].机械工程学报,2009,45(10):137-142.
[10] 杨琴,周国华,林晶晶,赵茜.基于DBR理论的柔性流水车间动态调度[J].控制与决策,2011,26(7):1109-1112.
[11] 王利,赵珺,王伟.基于部分生产重构的冷轧生产重调度方法[J].自动化学报,2011,37(1):99-106.
[12] 胡祥培,张漪,丁秋雷,王旭坪.干扰管理模型及其算法的研究进展[J].系统工程理论与实践,2008,10:40-46.
[13] 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.
[14] 潘逢山,叶春明.微粒群优化算法在流水线干扰管理调度中的应用[J].工业工程与管理,2012,17(4):48-53.
[15] 李铁克,肖拥军,王柏琳.基于局部性修复的HFS机器故障重调度[J].管理工程学报,2010,24(3):45-49.
[16] Pinedo M. Scheduling theory, algorithm and systems[M]. Fourth edition. New York: Springer Science+Business Media, LLC, 2012.
[17] 潘全科,赵保华,屈玉贵.无等待流水车间调度问题的优化[J].计算机学报,2008,31(7):1147-1154.
[18] Yu G, Qi X T. Disruption management: framework, models and applications[M]. First edition. Singapore: World Scientific Publishing Co. Pte. Ltd., 2004.
[19] 王凌,刘波.微粒群优化与调度算法[M].第1版.北京:清华大学出版社,2008.
[20] Ong Y S, Lim M H, Zhu N. Classification of adaptive memetic algorithms: a comparative study[J]. IEEE Trans. On Systems, Man and Cybernetics-B: Cybernetics, 2006, 36: 141-152.
[21] Reeves C R, Yamada T. Genetic algorithms, path relinking and the flowshop sequencing 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.
[23] 李丽,牛奔.粒子群优化算法[M].第1版.北京:冶金工业出版社,2009.
[24] Van Veldhuizen D A. Multiobjective evolutionary algorithms: classifications, analyses, and new innovations[D]. Ohio: Dept. of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, 1999.
[25] Czyak P, Jaskiewica A. Pareto simulated annealing-a metaheuristic technique for multiple-objective combinatorial optimization[J]. Journal of Multi-Criteria Decision Analysis, 1998, 7: 34-47.
[26] Tan K C, Goh C K, Yang Y J. Evolving better population distribution and exploration in evolutionary multi-objective optimization[J]. European Journal of Operational Research, 2006, 171(1): 463-495.

混合无等待流水线干扰管理调度方法研究

Study on Scheduling Method Based on Disruption Management for Hybrid N-wait Flow Shop

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	丁秋雷, 胡祥培, 齐飞, 姜洋. 行驶时间延迟下物流配送干扰管理模型——基于客户终身价值的视角[J]. 运筹与管理, 2021, 30(1): 6-12.
[2]	汪洪涛, 张翔, 王珂. 1996~2017年《Operations Research》期刊发文统计分析[J]. 运筹与管理, 2020, 29(2): 229-239.
[3]	王诺, 丁凯, 吴迪, 吴暖. 面向远海岛礁群的双向物流网络规划[J]. 运筹与管理, 2019, 28(6): 118-128.
[4]	高更君, 罗瑶. 不确定环境下再制造生产调度研究[J]. 运筹与管理, 2019, 28(11): 185-190.
[5]	刘春来, 王建军. 具有学习和退化效应的单机干扰管理问题[J]. 运筹与管理, 2019, 28(1): 94-100.
[6]	陈江涛, 吕建秋. 基于知识图谱的运筹学发展现状及趋势研究[J]. 运筹与管理, 2019, 28(1): 194-199.
[7]	张萌,王能民. 重大事故规避的危险品运输车辆路径优化研究[J]. 运筹与管理, 2018, 27(8): 1-9.
[8]	郑斐峰, 何俊凯, 刘明. 基于Epsilon约束法的短纤维生产调度的双目标优化研究[J]. 运筹与管理, 2018, 27(3): 1-8.
[9]	高沛然, 张金隆, 艾学轶, 李明, 马自香. PLS-DEMATEL方法及其应用研究——以组织敏捷性的IT影响因素分析为例[J]. 运筹与管理, 2018, 27(3): 126-132.
[10]	郭小威, 李保刚, 滕克难. 基于可用度的复杂结构装备检修时机决策模型[J]. 运筹与管理, 2018, 27(2): 11-14.
[11]	董锋, 树琳, 李靖云, 乔均. 产学研协同创新效率及提升路径研究[J]. 运筹与管理, 2018, 27(10): 185-192.
[12]	张源凯, 孙丽君, 胡祥培. 成品油配送多车舱车辆指派及路径优化问题研究[J]. 运筹与管理, 2017, 26(7): 1-9.
[13]	包晓光, 刘朝晖, 余炜. 线形网络上单台车辆分群调度问题[J]. 运筹与管理, 2017, 26(5): 125-129.
[14]	王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.
[15]	丁秋雷, 胡祥培, 姜洋, 阮俊虎. 快件配送地址变化的干扰管理模型研究[J]. 运筹与管理, 2017, 26(12): 46-52.