Block-Painting-Operation-Oriented Hybrid Flow Shop Scheduling

Abstract

Abstract:

A two-stage hybrid flow shop scheduling problem with reentrant and limited waiting time constraints was presented based on block painting operations. The first stage contained several identical batching machines which were able to process multiple jobs simultaneously, and the second stage contained several identical discrete machines. Minimization of the makespan was used as the optimization objective to build a mathematical model. A hybrid quantumbehaved particle swarm optimization algorithm combined with Metropolis rule and variable neighborhood search was proposed. The heuristic decoding strategy was developed to generate the scheduling scheme. Application and numerical analysis indicated that the proposed algorithm was an effective solution to the problem of block painting scheduling.

Key words: block painting, hybrid flow shop, batchdiscrete, quantum particle swarm

CLC Number:

TP 301.6

ZHANG Zhiying1,LIN Chen1,YANG Liansheng1, 2,XUE Shimei3,LIU Jianfeng2. Block-Painting-Operation-Oriented Hybrid Flow Shop Scheduling[J]. Journal of Shanghai Jiaotong University, 2014, 48(03): 382-387.

References

［1］Gupta J N D. Twostage hybrid flowshop scheduling problem ［J］. Journal of the Operational Research Society, 1988, 39(4): 359364.

［2］Kashan A H, Karimi B. An improved mixed integer linear formulation and lower bounds for minimizing makespan on a flow shop with batch processing machines ［J］. International Journal Advanced Manufacturing Technology, 2009, 40(56): 582594.

［3］Fu Q, Sivakumar A I, Li K. Optimisation of flowshop scheduling with batch processor and limited buffer ［J］. International Journal of Production Research, 2012, 50(8): 22672285.

［4］Kim Y D, Joo B J, Shin J H. Heuristics for a twostage hybrid flowshop scheduling problem with ready times and a productmix ratio constraint ［J］. Journal of Heuristics, 2009, 15(1): 1942.

［5］Bellanger A, Oulamara A. Scheduling hybrid flowshop with parallel batching machines and compatibilities ［J］. Computer & Operations Research, 2009, 36(6): 19821992.

［6］Luo H, Huang G Q, Zhang Y F, et al. Hybrid flowshop scheduling with batchdiscrete processors and machine maintenance in time windows ［J］. International Journal of Production Research, 2011, 49(6): 15751603.

［7］Sun J, Xu W, Feng B．A global search strategy of quantumbehaved particle swarm optimization ［C］∥Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems. Singapore: IEEE, 2004: 111116.

［8］Sun C, Lu S. Shortterm combined economic emission hydrothermal scheduling using improved quantumbehaved particle swarm optimization ［J］. Expert Systems with Applications, 2010, 37(6): 42324341.

［9］Liu J, Sun J, Xu W. Improving quantumbehaved particle swarm optimization by simulated annealing ［C］∥Proceedings of the 2006 International Conference on Computational Intelligence and Bioinformatics. Heidelberg, Germany: Springer Berlin Heidelberg, 2006: 130136.

［10］Lin T L, Horng S J, Kao T W, et al. An efficient jobshop scheduling algorithm based on particle swarm optimization ［J］. Expert Systems with Applications, 2010, 37 (3): 26292636.

［11］Liu B, Wang L, Jin Y H. An effective PSObased memetic algorithm for flow shop scheduling ［J］. IEEE Transactions on Systems, Man, CyberneticsPart B: Cybernetics, 2007, 37(1): 1827．

［12］尹兆涛, 李铁克. 考虑交货期和等待时间受限的HFS调度问题的混合算法［J］. 工业工程, 2009, 12(1): 7983.

YIN Zhaotao, LI Tieke. Hybrid algorithms for hybrid flowshop scheduling considering due dates and limited waiting times ［J］. Industrial Engineering Journal, 2009, 12(1): 7983.

［13］Pant M, Thangaraj R, Abraham A. A new quantum behaved particle swarm optimization ［C］∥Proceedings of the 10th annual conference on Genetic and evolutionary computation. New York, NY, USA: ACM, 2008: 8794.

[1]	JIANG Chundong，WANG Jingyu，DU Taihang，HAO Jing，LONG Chao. Separation of Single Channel Radio Mixed Signal Based on Variational Mode Decomposition [J]. Journal of Shanghai Jiaotong University, 2018, 52(12): 1618-1626.
[2]	ZENG Qingcheng,CHEN Zigen,HUANG Ling. Multi-Stage Hybrid Flow Shop Model for Quay Crane Dual Cycling in Container Terminals [J]. Journal of Shanghai Jiaotong University, 2015, 49(04): 499-505.