Self-adaptive Multistage GA-IWO for Solving Flexible Job Shop Scheduling Problem

doi:10.3901/JME.2019.06.223

Abstract

Abstract: For flexible job shop scheduling problem with minimizing makespan, a mathematical model and a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm are proposed. For the characteristics of flexible job shop scheduling problem, invasive weed optimization is improved. Using some new evaluating indicators based on total number of individuals to evaluate the performance of improved invasive weed optimization, how the population size and weed size affect invasive weed optimization is addressed. Using the new evaluating indicators to evaluate improved invasive weed optimization and genetic algorithm, some differences between them are illustrated. Using hamming distance to measure the population diversity, the value of population diversity is used to control the self-adaptive multistage between invasive weed optimization and genetic algorithm, obtaining a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm. Using some instances to test genetic algorithm, invasive weed optimization, and self-adaptive multistage genetic algorithm/invasive weed optimization, the advantages of self-adaptive multistage genetic algorithm/invasive weed optimization are shown. Using some standard instances to compare a self-adaptive multistage genetic algorithm/invasive weed optimization with other algorithms, the simulation results show that the proposed algorithm can solve flexible job shop scheduling problem effectively.

Key words: flexible job shop scheduling problem, genetic algorithm, invasive weed optimization, population diversity, self-adaptive multistage

CLC Number:

TP278

SHI Xiaoqiu, LI Yanyan, DENG Dingshan, LONG Wei. Self-adaptive Multistage GA-IWO for Solving Flexible Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2019, 55(6): 223-232.

References

[1] JOHNSON S. Optimal two-and-three stage production schedules with setup times included[J]. Naval Research Logistics Quarterly,1954,1:61-68.
[2] GAREY M R,JOHNSON D S,SETHI R. The complexity of flow hop and job shop scheduling[J]. Mathematics of Operations Research,1976,1(2):117-129.
[3] BRUCKER P,SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing,1990,45(4):369-375.
[4] AZZOUZ A,ENNIGROU M,BEN S,et al. A hybrid algorithm for flexible job-shop scheduling problem with setup times[J]. International Journal of Production Management and Engineering,2017,5(1):23-30.
[5] CHIANG T,LIN H. A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling[J]. International Journal of Production Economics,2013,141:87-98.
[6] 吴秀丽,张志强,杜彦华,等. 改进细菌觅食算法求解柔性作业车间调度问题[J]. 计算机集成制造系统,2015,21(5):1262-1270. WU Xiuli,ZHANG Zhiqiang,DU Yanhua,et al. Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing systems,2015,21(5):1262-1270.
[7] 徐华,张庭. 混合离散蝙蝠算法求解多目标柔性作业车间调度[J]. 机械工程学报,2016,52(18):201-212. 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-212.
[8] LU C,LI X,GAO L,et al. An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times[J]. Computers and Industrial Engineering,2017,104:156-174.
[9] 刘洲洲,李彬. 基于动态多子族群自适应群居蜘蛛优化算法[J]. 四川大学学报,2017,54(4):721-727. LIU Zhouzhou,LI Bin. An adaptation social spider optimization algorithm based on dynamic multi-swarm strategy[J]. Journal of Sichuan University,2017,54(4):721-727.
[10] ZHANG W,WEN J B,ZHU Y C,et al. Multi-objective scheduling simulation of flexible job-shop based on multi-population genetic algorithm[J]. International Journal of Simulation Modeling,2017,16(2):313-321.
[11] CHANG H C,LIU T K. Optimization of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J]. Journal of Intelligent Manufacturing,2017,28(8):1973-1986.
[12] TANG Qiuhua,LI Zixiang,ZHANG Liping,et al. Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided sssembly lines with multiple constraints[J]. Chinese Journal of Mechanical Engineering,2015,28(5):1067-1079.
[13] 牟健慧. 基于混合遗传算法的车间逆调度方法研究[D]. 武汉:华中科技大学,2015. MU Jianhui. Research on inverse scheduling methods based on hybrid genetic algorithm[D]. Wuhan:Huazhong University of Science and Technology,2015.
[14] ATABAKI M S,MOHAMMADI M,NADERI B. Hybrid genetic algorithm and invasive weed optimization via priority based encoding for location-allocation decisions in a three-stage supply chain[J]. Asla-pacific Journal of Operational Research,2017,32(2):1750008.
[15] MISHRA S K,BOSE P S C,RAO C S P. An invasive weed optimization approach for job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology. 2017,91(9-12):4233-4241.
[16] MEHRABIAN A R,LUCAS C. A novel numerical optimization algorithm inspired from weed colonization[J]. Ecological Informatics,2006,1(4):355-366.
[17] 张超勇,饶运清,李培根,等. 柔性作业车间调度问题的两级遗传算法[J]. 机械工程学报,2007,43(4):119-124. ZHANG Chaoyong,RAO Yunqing,LI Peigen,et al. Bilevel genetic algorithm for the flexible job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering,2007,43(4):119-124.
[18] 石小秋,石宇强,袁雪娇. 离散多种群入侵杂草优化算法求解柔性作业车间调度问题[J]. 信息与控制,2015,44(2):238-243. SHI Xiaoqiu,SHI Yuqiang,YUAN Xuejiao. Invasive weed optimization algorithm with discrete multi-population for the flexible job-shop scheduling problem[J]. Information and control,2015,44(2):238-243.
[19] 张超勇,饶运清,刘向车,等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程,2004,15(23):2149-2153. ZHANG Chaoyong,RAO Yunqing,LIU Xiangjun,et al. An improved genetic algorithm for the job shop scheduling problem[J]. China Mechanical Engineering,2004,15(23):2149-2153.
[20] KACEM I,HAMMADI S,BORNE P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems,Man,and Cybernetics Part C:Applications and Reviews,2002,31(1):1-13.
[21] WANG Ling,WANG Shengyao,XU Ye,et al. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J]. Computers and Industrial Engineering,2012,62(4):917-926.
[22] CHIANG T C,LIN H J. A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling[J]. International Journal of Production Economics,2013,141(1):87-98.
[23] FATTAHI P,MEHRABAD M S,JOLAI F. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J]. Journal of Intelligent Manufacturing,2007,18(3):331342.
[24] YUAN Yuan,XU Hua,YANG Jiadong. A hybrid harmony search algorithm for the flexible job shop scheduling problem[J]. Applied Soft Computing,2013,13(7):3259-3272.
[25] DEMIR Y,ISLEYEN S K. Evaluation of mathematical models for flexible job shop scheduling problems[J]. Applied Mathematical Modelling,2013,37:977-988.
[26] BIRGIN E G,FEOFILOFF P,FERNANDES C G,et al. A MILP model for an extended version of the flexible job shop problem[J]. Optimization Letters,2014,8:1417-1437.
[27] LI Xinyu,GAO Liang. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics,2016,174:93-110.