带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

doi:10.3901/JME.2019.24.236

机械工程学报 ›› 2019, Vol. 55 ›› Issue (24): 236-252.doi: 10.3901/JME.2019.24.236

扫码分享

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

韩忠华^1,2,3,4, 张权², 史海波^1,3,4, 张竞元²

1. 中国科学院沈阳自动化研究所沈阳 110016;
2. 沈阳建筑大学信息与控制工程学院沈阳 110168;
3. 中国科学院网络化控制系统重点实验室沈阳 110016;
4. 中国科学院机器人与智能制造创新研究院沈阳 110016

收稿日期:2018-08-16 修回日期:2019-03-28 出版日期:2019-12-20 发布日期:2020-02-18
通讯作者: 张权(通信作者),男,1994年出生,硕士。主要研究方向为车间排产与生产调度算法的工程应用。E-mail:zhangq0716@163.com
作者简介:韩忠华,男,1977年出生,博士,硕士研究生导师。主要研究方向为生产与运作管理、企业自动化系统集成技术、车间排产与生产调度算法的工程应用。E-mail:hanzhonghua@sia.cn;史海波,男,1966年出生,博士,研究员,博士研究生导师。主要研究方向为生产与运作管理、企业自动化系统集成技术、车间排产与生产调度算法的工程应用。E-mail:hbshi@sia.cn
基金资助:
国家自然科学基金（61873174）、辽宁省重点研发计划指导计划（2018106008）、辽宁省高等学校基本科研（LJ2017015）和沈阳市科技计划双百工程（Z18-5-015）资助项目。

Multi-queue Limited Buffer Scheduling Problems in Flexible Flow Shop with Setup Times

HAN Zhonghua^1,2,3,4, ZHANG Quan², SHI Haibo^1,3,4, ZHANG Jingyuan²

1. Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016;
2. Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168;
3. Key Laboratory of Network Control System, Chinese Academy of Sciences, Shenyang 110016;
4. Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110016

Received:2018-08-16 Revised:2019-03-28 Online:2019-12-20 Published:2020-02-18

摘要/Abstract

摘要： 针对带准备时间的柔性流水车间多序列有限缓冲区排产优化问题，提出一种改进的紧致遗传算法（Improved compactgenetic algorithm，ICGA）与局部指派规则结合的方法来解决该问题。全局优化过程采用改进的紧致遗传算法，为了克服紧致遗传算法（Compact genetic algorithm，CGA）易早熟收敛的问题，提出一种基于高斯映射的概率模型更新方式，在保持紧致遗传算法快速收敛特性的前提下，扩展了种群中个体的多样性，增强了算法进化活力。为减少生产阻塞和降低准备时间对排产过程的影响，设计了多种局部启发式规则来指导工件进出多序列有限缓冲区的分配和选择过程。采用某客车制造企业中的实例数据进行测试，测试结果表明，改进的紧致遗传算法与局部指派规则配合使用，能够有效解决带准备时间的柔性流水车间多序列有限缓冲区排产优化问题。

关键词: 柔性流水车间, 多序列有限缓冲区, 高斯映射, 改进的紧致遗传算法

Abstract: Aiming at solving the multi-queue limited buffer scheduling problems in flexible flow shop with setup times, an improved compact genetic algorithm(ICGA) with local dispatching rules is proposed. Specifically, the global optimization process adopts ICGA algorithm. In order to overcome the issue of premature convergence of compact genetic algorithm (CGA), a Gaussian-mapping-based probabilistic updating method is proposed. Under the premise of maintaining the fast search feature of CGA, ICGA algorithm expand the diversity of population individuals and enhance the evolutionary vigor of the algorithm. In order to reduce the impact of production blocking and setup times on the scheduling process, multiple local heuristic rules are designed to guide the distribution and selection process of the jobs into and out of the multi-queue limited buffer. The instance data in a bus manufacturing enterprise is used for testing. The test results show that the ICGA algorithm combined with local dispatching rules can effectively solve the problem of multi-queue limited buffer scheduling problems in flexible flow shop with setup times.

Key words: flexible flow shop, multi-queue limited buffer, Gaussian mapping, improved compact genetic algorithm

中图分类号:

TH186

韩忠华, 张权, 史海波, 张竞元. 带准备时间的柔性流水车间多序列有限缓冲区排产优化问题[J]. 机械工程学报, 2019, 55(24): 236-252.

HAN Zhonghua, ZHANG Quan, SHI Haibo, ZHANG Jingyuan. Multi-queue Limited Buffer Scheduling Problems in Flexible Flow Shop with Setup Times[J]. Journal of Mechanical Engineering, 2019, 55(24): 236-252.

参考文献

[1] ZHAO F, TANG J, WANG J, et al. An improved particle swarm optimization with a linearly decreasing disturbance term for flow shop scheduling with limited buffers[J]. International Journal of Computer Integrated Manufacturing, 2014, 27(5):488-499.
[2] 谢展鹏,张超勇,邵新宇,等. 基于Memetic算法的有限缓冲区流水车间调度问题[J]. 计算机集成制造系统, 2015, 21(5):1254-1261. XIE Zhanpeng, ZHANG Chaoyong, SHAO Xinyu, et al. Flow shop scheduling with limited buffers based on Memetic algorithm[J]. Computer Integrated Manufacturing Systems, 2015, 21(5):1254-1261.
[3] PAN Q K, WANG L, GAO L, et al. An effective hybrid discrete differential evolution algorithm for flow shop scheduling with intermediate buffers[J]. Information Sciences, 2011, 181:668-685.
[4] 胡蓉, 钱斌. 一种求解随机有限缓冲区流水线调度的混合差分进化算法[J]. 自动化学报, 2009, 35(12):1580-1586. HU Rong, QIAN Bin. A hybrid differential evolution algorithm for stochastic flow shop scheduling with limited buffers[J]. Acta Automatica Sinica, 2009, 35(12):1580-1586.
[5] QING F, APPALYER S, KUNPENG L. Optimisation of flow-shop scheduling with batch processor and limited buffer[J]. Inernational Journal of Production Research, 2012, 50(8):2267-2285.
[6] 张培文,潘全科,李俊青,等. 有限缓冲区流水车间调度的混合人工蜂群算法[J]. 计算机集成制造系统, 2013, 19(10):2510-2511. ZHANG Peiwen, PAN Quanke, LI Junqing, et al. Hybrid artificial bee colony algorithms for flowshop scheduling problem with limited buffers[J]. Computer Integrated Manufacturing Systems, 2013, 19(10):2510-2511.
[7] ZHANG S, WONG T N. Studying the impact of sequence-dependent set-up times in integrated process planning and scheduling with E-ACO heuristic[J]. International Journal of Production Research, 2016, 54(16):4815-4838.
[8] SHEN L, DSUZERE P, NEUFELD J S. Solving the flexible job shop scheduling problem with sequence-dependent setup times[J]. European Journal of Operational Research, 2018, 265(2):503-516..
[9] TRAN T T, ARAUJO A, BECH J C. Decomposition methods for the parallel machine scheduling problem with setups[J]. INFORMS Journal on Computing, 2016, 28(1):83-95.
[10] 钟涛,萧卫,徐宏云,等. 带机器准备时间的单机调度问题的混合进化算法研究[J]. 计算机应用研究, 2013, 30(11):3249-3252. ZHONG Tao, XIAO Wei, XU Hongyun, et al. Hybrid evolutionary algorithm for solving single-machine scheduling problem with setup times[J]. Application Research of Computer, 2013, 30(11):3249-3252.
[11] BENKALAI I, REEBAINE D, GAGNE C, et al. Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times[J]. International Journal of Production Research, 2017, 55(20):6145-6157.
[12] PAN Q K, GAO L, LI X Y, et al. Effective metaheuristics for scheduling a hybrid flow shop with sequence-dependent setup times[J]. Applied Mathematics and Computation, 2017, 303:89-112.
[13] AN Y J, KIM Y D, CHOI S W. Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times[J]. Computers & Operations Research, 2016, 71:127-136.
[14] LENSTRA J K, KAN A H G R, BRUCKER P. Complexity of machine scheduling problems[J]. Studies in integer programming, 1977, 1:343-362.
[15] HARIK G R, LOBO F G, GOLDBERG D E. The compact genetic algorithm[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4):287-297.
[16] DA S R R, ERIG L C R, LOPES H S. Template matching in digital images using a compact genetic algorithm with elitism and mutation[J]. Journal of Circuits, Systems, and Computers, 2010, 19(1):91-106.
[17] 韩忠华,朱一行,史海波,等. 基于改进紧致遗传算法的柔性流水车间组批排产优化问题研究[J]. 系统工程理论与实践, 2016, 36(6):1617-1624. HAN Zhonghua, ZHU Yihang,, SHI Haibo, et al. Study for the flexible flow shop scheduling problem with batch process machines based on an advanced compact genetic algorithm[J]. Systems Engineering-Theory & Practice, 2016, 36(6):1617-1624.
[18] 李聪波,沈欢,李玲玲,等. 面向能耗的多工艺路线柔性作业车间分批优化调度模型[J]. 机械工程学报, 2017, 53(5):12-23. LI Congbo, ZHEN Huan, LI Lingling, et al. A batch splitting flexible job shop scheduling model for energy saving under alternative process plans[J]. Journal of Mechanical Engineering, 2017, 53(5):12-23.
[19] 赵兴旺, 梁吉业. 一种基于信息熵的混合数据属性加权聚类算法[J]. 计算机研究与发展, 2016, 53(5):1019-1027. ZHAO Xingwang, LING Jiye. An Attribute Weighted Clustering Algorithm for Mixed Data Based on Information Entropy[J]. Journal of Computer Research and Development, 2016, 53(5):1019-1027.
[20] ALAYKYRAN K, ENGIN O, DOYEN A. Using ant colony optimization to solve hybrid flow shop scheduling problems[J]. The International Journal of Advanced Manufacturing Technology, 2007, 35(5-6):541-550.
[21] NERSON E, BAPTISTE P, GUPTA J N D. Solving hybrid flow shop problem using energetic reasoning and global operations[J]. Omega, 2001, 29(6):501-511.
[22] SANTOS D L, HUNSUCKER J L, DEAL D E. Global lower bounds for flow shop with multiple processors[J]. European Journal of Operational Research, 1995, 80(1):112-120.
[23] 徐华, 张庭. 混合离散蝙蝠算法求解多目标柔性作业车间调度[J]. 机械工程学报, 2016, 52(18):201-211. XU Hua, ZHANG Ting. Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J]. Journal of Mechanical Engineering, 2016, 52(18):201-211.

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

Multi-queue Limited Buffer Scheduling Problems in Flexible Flow Shop with Setup Times

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	张利萍, 彭彦平. 基于高斯映射的可展曲面等曲率离散问题研究[J]. 机械工程学报, 2020, 56(5): 226-232.
[2]	孙殿柱, 梁增凯, 薄志成, 李延瑞, 沈江华. 样点邻域同构曲面约束的散乱点云法向估计[J]. 机械工程学报, 2019, 55(19): 146-153.
[3]	李川朱荣荣杨帅. 基于多指标模糊融合的滚动轴承诊断的最优频带解调方法[J]. 机械工程学报, 2015, 51(7): 107-114.
[4]	黎展滔;陈庆新;毛宁. 具有后成组约束的两阶段柔性流水作业计划制订的启发式算法[J]. , 2013, 49(12): 183-192.
[5]	黎展滔;陈庆新;毛宁. 具有前成组约束的两阶段柔性流水车间的启发式算法[J]. , 2012, 48(22): 189-198.
[6]	刘宇;熊有伦. 基于法矢的点云拼合方法[J]. , 2007, 43(8): 7-11.