一种改进离散磷虾群的复杂产品装配调度算法

doi:10.3969/j.issn.1000-1093.2018.08.016

摘要/Abstract

摘要： 针对复杂产品装配车间调度问题，提出了一种改进的离散磷虾群（IDKH）装配调度算法。以工期最小化为调度目标，通过分析复杂产品装配工艺流程特点，建立了复杂产品装配调度模型。基于排列的编码方式和启发式规则的改进解码方式实现了调度解与种群个体之间的转换，并通过局部搜索和重启操作对标准磷虾群（KH）算法进行了改进，增强了算法的局部开采能力和全局搜索能力。采用正交试验方法分析了不同参数设置对算法性能的影响，确定了IDKH算法的最佳参数组合。基于标准实例对不同算法性能进行了比较，对比结果表明，IDKH装配调度算法在求解质量和稳定性上均优于遗传算法、分布估计算法、引力搜索算法和标准KH算法。

关键词: 磷虾群算法, 装配调度, 复杂产品, 混合流水车间调度

Abstract: An improved discrete krill herd (IDKH) algorithm is proposed for the complex product assembly scheduling problem. The objective is to minimize the makespan. An assembly scheduling model is established by analyzing the characteristics of a complex product process flow. The transformation between scheduling solution and population individual is realized by using permutation-based coding and heuristic-based decoding methods. A local search and a restart operation procedure are presented to improve the exploitation and global exploration ability of basic krill herd (KH). The parameters of the proposed IDKH are calibrated by using a design of experimental approach. And a comparative evaluation is conducted with the well-known algorithms. The results show that the proposed IDKH has advantage over genetic algorithm, estimation of distribution algorithm, gravitational search algorithm, and basic KH in terms of quality and stability. Key

Key words: krillherdalgorithm, assemblyscheduling, complexproduct, hybridflow-shopscheduling

中图分类号:

TB497

庄存波，熊辉，刘检华，唐承统. 一种改进离散磷虾群的复杂产品装配调度算法[J]. 兵工学报, 2018, 39(8): 1590-1600.

ZHUANG Cun-bo， XIONG Hui， LIU Jian-hua， TANG Cheng-tong. An Improved Discrete Krill Herd Algorithm for Complex Product Assembly Scheduling Problem[J]. Acta Armamentarii, 2018, 39(8): 1590-1600.

参考文献

［1］李伯虎，柴旭东. 复杂产品虚拟样机工程［J］. 计算机集成制造系统, 2002，8(9): 678-683.
LI Bo-hu, CHAI Xu-dong. Virtual prototyping engineering for complex product［J］. Computer Integrated Manufacturing Systems, 2002, 8(9): 678-683.(in Chinese)
［2］刘检华，丁向峰，袁丁,等. 复杂产品计算机辅助装配过程控制与管理系统［J］. 计算机集成制造系统，2010，16(8): 1622-1633.
LIU Jian-hua，DING Xiang-feng，YUAN Ding, et al. Computer aided assembly process control and management system for complex product［J］. Computer Integrated Manufacturing Systems, 2010, 16(8): 1622-1633. (in Chinese)
［3］高亮，张国辉，王晓娟. 柔性作业车间调度智能算法及其应用［M］. 武汉：华中科技大学出版社，2012.
GAO Liang, ZHANG Guo-hui, WANG Xiao-juan. Flexible job shop scheduling intelligent algorithms and applications［M］. Wuhan: Huazhong University of Science & Technology Press, 2012. (in Chinese)
［4］ Engin O, Dyen A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system［J］. Future Generation Computer Systems, 2004, 20(6): 1083-1095.
［5］ Soewandi H, Elmaghraby S E. Sequencing on two-stage hybrid flow shops with uniform machines to minimize makespan［J］. IIE Transactions, 2003, 35(5): 467-477.
［6］ Jungwattanakit J, Reodecha M, Chaovalitwongse P, et al. Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria［J］. International Journal of Advanced Manufacturing Technology, 2008, 37(3/4): 354-370.
［7］ Linn R, Zhang W. Hybrid flow shop scheduling: a survey［J］. Computers & Industrial Engineering, 1999, 37: 57-61.
［8］ Johnson S M. Optimal two and three stage production schedules with setup times included ［J］. Naval Research Logistics Quarterly,1954, 1(1): 61-68.
［9］ Brah S A, Hunsucker J L. Branch and bound algorithm for the flow shop with multiple processors［J］. European Journal of Operational Research, 1991, 51:88-99.

［10］ Neron E, Baptiste P, Gupta J N D. Solving hybrid flow shop problem using energetic reasoning and global operations［J］. Omega, 2001, 29:501-511.
［11］ Gupta J N D. Two-stage hybrid flowshop scheduling problem［J］. The Journal of the Operation Society, 1988, 39(4):359-364.
［12］ Riane F, Artibaa A, Elmaghraby S E. A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan［J］. European Journal of Operational Research, 1998, 109:321-329.
［13］ Ruiz R, Maroto C. A genetic algorithm for hybrid flow-shops with sequence dependent setup times and machine eligibility［J］. European Journal of Operational Research, 2006, 169: 781-800.
［14］ Pan Q, Wang L, Li J, et.al. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation［J］. Omega, 2014, 45:42-56.
［15］ Nawaz M, Enscore E E J, Ham I. A heuristic algorithm for the m-machine, n-job flow shop sequencing problem［J］, Omega, 1983, 11: 91-95.
［16］ Ouz C, Ercan M F. A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks［J］. Journal of Scheduling, 2005, 8(4): 323-351.
［17］ Engin O, Ceran G, Yilmaz M K. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems［J］. Applied Soft Computing, 2011, 11(3): 3056-3065.
［18］ Ouz C, Zinder Y, Do V H, et.al. Hybrid flow-shop scheduling problems with multiprocessor task systems［J］. European Journal of Operations Research, 2004, 152：115-131.
［19］ Bo[KG-*9]z·ejko W, Pempera J, Smutnicki C. Parallel tabu search algorithm for the hybrid flow shop problem［J］. Computers & Industrial Engineering, 2013, 65(3): 466-474.
［20］ Wang H M, Chou F D, Wu F C. A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan［J］. The International Journal of Advanced Manufacturing Technology, 2011, 53(5): 761-776.
［21］ Engin O, Dyen A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system［J］. Future Generation Computer Systems, 2004, 20(6): 1083-1095.
［22］ Komaki G M, Teymourian E, Kayvanfar V. Minimising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immune systems［J］. International Journal of Production Research, 2016, 54(4): 963-983.
［23］ Pan Q, Ruiz R, Alfaro-Fernández P. Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows［J］. Computers and Operations Research, 2017, 80: 50-60.
［24］ Tseng C T, Liao C J. A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks［J］. International Journal of Production Research, 2008, 46(17): 4655-4670.
［25］ Liao J C, Tjandradjaja E, Chung T P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem［J］. Applied Soft Computing, 2012, 12(6):1755-1764.
［26］ Li J, Pan Q. Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm［J］. Information Sciences, 2015, 316：487-502.
［27］ Pan Q, Gao L, Li X, et al. Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times［J］. Applied Mathematics and Computation, 2017, 303: 89-112.
［28］ Ying K C, Lin S W. Multiprocessor task scheduling in multistage hybrid flowshops: an ant colony system approach［J］. International Journal of Production Research, 2006, 44: 3161-3177.
［29］ Alaykran K, Engin O, Dyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems［J］. The International Journal of Advanced Manufacturing Technology, 2007, 35(5): 541-550.
［30］ Gandomi A H, Alavi A H. Krill herd: a new bio-inspired optimization algorithm［J］. Communications in Nonlinear Science and Numerical Simulation, 2012, 17(12): 4831-4845.
［31］ Wang G, Gandomi A H, Alavi A H. Stud krill herd algorithm［J］. Neurocomputing, 2014, 128(5):363-370.
［32］ Wang G, Guo L, Gandomi A H, et al. Chaotic krill herd algorithm［J］. Information Sciences, 2014, 274:17-34.
［33］ Guo L, Wang G, Gandomi A H, et al. A new improved krill herd algorithm for global numerical optimization［J］. Neurocomputing, 2014, 138: 392-402.
［34］ Bolaji A L, Al-Betar M A, Awadallah M A, et al. A comprehensive review: krill herd (KH) algorithm and its applications［J］. Applied Soft Computing, 2016, 49: 437-446.
［35］ Kowalski P A, Lukasik S. Training neural networks with krill herd algorithm［J］. Neural Processing Letters, 2016, 44(1):5-17.
［36］ Yaghoobi S, Mojallali H. Tuning of a PID controller using improved chaotic krill herd algorithm［J］. Optik, 2016, 127:4803-4807.
［37］ Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey［J］. Annals of Discrete Mathematics, 1979, 5: 287-326.
［38］王圣尧，王凌，许烨，等. 求解混合流水车间调度问题的分布估计算法［J］. 自动化学报, 2012, 38(3): 437-443.
WANG Sheng-yao, WANG Ling, XU Ye, et al. An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem［J］. Acta Automatica Sinica, 2012, 38(3):437-443. (in Chinese)
［39］ Wang S, Wang L, Liu M, et al. An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machines［J］. The International Journal of Advanced Manufacturing Technology, 2013, 68(9/10/11/12): 2043-2056.
［40］ Guinet A G P, Solomon M M. Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time［J］. International Journal of Production Research, 1996, 34(6): 1643-1654.
［41］ Ruiz R, Maroto C, Alcaraz J. Two new robust genetic algorithms for the flowshop scheduling problem［J］. Omega, 2006, 34: 461-476.
［42］ Bahrololoum A, Nezamabadi-Pour H, Bahrololoum H, et al. A prototype classifier based on gravitational search algorithm［J］. Applied Soft Computing, 2012, 12(2): 819-825.
［43］ Xu Y, Wang L. Differential evolution algorithm for hybrid flow-shop scheduling problems［J］. Journal of Systems Engineering and Electronics, 2011, 22(5): 794-798.
［44］王圣尧, 王凌, 许烨. 求解相同并行机混合流水线车间调度问题的分布估计算法［J］. 计算机集成制造系统, 2013, 19(6): 1304-1312.
WANG Sheng-yao, WANG Ling, XU Ye. Estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machine［J］. Computer Integrated Manufacturing Systems, 2013, 19(6): 1304-1312. (in Chinese)
［45］王芳，唐秋华，饶运清，等. 求解柔性流水车间调度问题的高效分布估算算法［J］. 自动化学报, 2017, 43(2): 280-293.
WANG Fang, TANG Qiu-hua, RAO Yun-qing, et al. Efficient estimation of distribution for flexible hybrid flow shop scheduling［J］. Acta Automatica Sinica, 2017, 43(2): 280-293. (in Chinese)
［46］张凤超. 改进的分布估计算法求解混合流水车间调度问题研究［J］. 软件导刊, 2014, 13(8):23-26.
ZHANG Feng-chao. An improved estimation of distribution algorithm to solve the hybrid flow shop scheduling problem［J］. Software Guide, 2014, 13(8): 23-26. (in Chinese)

第39卷
第8期2018 年8月兵工学报ACTA
ARMAMENTARIIVol.39No.8Aug.2018