面向分段涂装作业的混合流水车间调度

上海交通大学学报（自然版） ›› 2014, Vol. 48 ›› Issue (03): 382-387.

• 自动化技术、计算机技术 • 上一篇下一篇

面向分段涂装作业的混合流水车间调度

张志英1，林晨1，杨连生1,2，薛士枚3，刘建峰2

（1．同济大学机械与能源工程学院，上海 201804；2．上海外高桥造船有限公司，上海 200137；3．上海江南长兴造船有限责任公司，上海 201913）

收稿日期:2013-06-24
基金资助:
国家自然科学基金资助项目（70872076），上海科技创新行动计划资助项目（11dz1121803），江苏省南通市2010AA科技创新计划（工业）项目（AA2010048）

Block-Painting-Operation-Oriented Hybrid Flow Shop Scheduling

ZHANG Zhiying1,LIN Chen1,YANG Liansheng1, 2,XUE Shimei3,LIU Jianfeng2

(1. School of Mechanical Engineering, Tongji University, Shanghai 201804, China; 2. Shanghai Waigaoqiao Shipbuilding Co. Ltd., Shanghai 200137, China;
3. Shanghai Jiangnan Changxing Shipbuilding Co. Ltd., Shanghai 201913, China)

Received:2013-06-24

摘要/Abstract

摘要：

基于船舶分段涂装作业，提炼出具有重入和等待时间约束的两阶段混合流水车间调度问题.其中第一阶段含多台批处理机，第二阶段含多台离散机且存在一次重入过程，两阶段间有等待时间约束.以最小化最大完工时间为优化目标建立数学模型，提出一种结合Metropolis抽样准则和变邻域搜索的混合量子粒子群优化算法，并利用多种启发式规则进行解码.实例验证和数值分析表明，所提算法是解决分段涂装调度问题的一种有效方法.

关键词: 分段涂装, 混合流水车间, 批离散, 量子粒子群

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

中图分类号:

TP 301.6

张志英1，林晨1，杨连生1,2，薛士枚3，刘建峰2. 面向分段涂装作业的混合流水车间调度[J]. 上海交通大学学报（自然版）, 2014, 48(03): 382-387.

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.

参考文献

［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]	汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
[2]	江春冬1,2，王景玉1，杜太行1,2，郝静1,3，龙超1. 基于变分模态分解算法的单通道无线电混合信号分离[J]. 上海交通大学学报（自然版）, 2018, 52(12): 1618-1626.
[3]	黄泽霞1, 2, 俞攸红3, 黄德才1. 惯性权自适应调整的量子粒子群优化算法 [J]. 上海交通大学学报（自然版）, 2012, 46(02): 228-232.