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

doi:10.3901/JME.2019.24.236

Abstract

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

CLC Number:

TH186

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.

References

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