Hybrid Shuffled Frog-leaping Algorithm for Distributed Flexible Job Shop Scheduling

doi:10.3901/JME.2021.17.263

Abstract

Abstract: Aiming at the distributed flexible job shop scheduling problem (DFJSP) with minimizing makespan, a hybrid shuffled frog-leaping algorithm (HSFLA) is proposed. In this algorithm, the encoding adopts the scheme of partial solution space based on the operation and factory sequences, and the machine selection is determined in the decoding process with a rule. A variable neighborhood search (VNS) algorithm is introduced to improve the local search ability of HSFLA. To make up for the shortcoming that the partial space encoding method cannot search the full solution space, a tabu search algorithm of full solution space is introduced in critical factory to expand the solution space and further improve the local search ability of HSFLA. By solving benchmark instances and comparing HSFLA with the existing state-of-the-art algorithms, the effectiveness and superiority of HSFLA are proved.

Key words: distributed scheduling, flexible job shop, shuffled frog-leaping algorithm, makespan

CLC Number:

TP18

MENG Leilei, ZHANG Biao, REN Yaping, ZHANG Chaoyong. Hybrid Shuffled Frog-leaping Algorithm for Distributed Flexible Job Shop Scheduling[J]. Journal of Mechanical Engineering, 2021, 57(17): 263-272.

References

[1] LUO Q,DENG Q,GONG G,et al. An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers[J]. Expert Systems with Applications, 2020,160:113721.
[2] HUANG J,PAN Q,GAO L. An effective iterated greedy method for the distributed permutation flowshop scheduling problem with sequence-dependent setup times[J]. Swarm and Evolutionary Computation,2020,59:100742.
[3] WANG G,GAO L,LI X,et al. Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm[J]. Swarm and Evolutionary Computation,2020,57:100716.
[4] PAN Q,GAO L,WANG L,et al. Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem[J]. Expert Systems with Applications,2019,124:309-324.
[5] MENG L,ZHANG C,REN Y,et al. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem[J]. Computers & Industrial Engineering,2020,142:106347.
[6] NADERI B,AZAB A. An improved model and novel simulated annealing for distributed job shop problems[J]. The International Journal of Advanced Manufacturing Technology,2015,81(1-4):693-703.
[7] NADERI B,AZAB A. Modeling and heuristics for scheduling of distributed job shops[J]. Expert Systems with Applications,2014,41(17):7754-7763.
[8] 吴秀丽,刘夏晶. 差分进化算法求解分布式柔性作业车间调度问题[J]. 计算机集成制造系统,2019,25(10):2539-2558.WU Xiuli,LIU Xiajing. Differential evolution algorithm for solving distributed flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems,2019,25(10):2539-2558.
[9] 吴锐,郭顺生,李益兵,等. 改进人工蜂群算法求解分布式柔性作业车间调度问题[J]. 控制与决策,2019,34(12):2527-2536.WU Rui,GUO Shunsheng,LI Yibing,et al. An improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem[J]. Control and Decision, 2019,34(12):2527-2536.
[10] CHAN F T S,CHUNG S H,CHAN L Y,et al. Solving distributed FMS scheduling problems subject to maintenance:Genetic algorithms approach[J]. Robotics and Computer-Integrated Manufacturing,2006,22(5-6):493-504.
[11] CHAN F T S,CHUNG S H,CHAN P L Y. Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems[J]. International Journal of Production Research,2006,44(3):523-543.
[12] De GIOVANNI L,PEZZELLA F. An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem[J]. European Journal of Operational Research,2010,200(2):395-408.
[13] 杨江波,陈友玲,曹楠. 面向柔性作业分布式车间的分层调度模型研究[J]. 计算机工程与应用,2014,50(23):239-244.YANG Jiangbo,CHEN Youling,CAO Nan. Research on grading scheduling model of flexible job distributed workshop[J]. Computer Engineering and Applications,2014,50(23):239-244.
[14] ZIAEE M. A heuristic algorithm for the distributed and flexible job-shop scheduling problem[J]. The Journal of Supercomputing,2014,67(1):69-83.
[15] LU P,WU M,TAN H,et al. A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems[J]. Journal of Intelligent Manufacturing,2018,29(1):19-34.
[16] CHANG H,LIU T. Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J]. Journal of Intelligent Manufacturing,2017,28(8):1973-1986.
[17] WU M,LIN C,LIN C,et al. Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems[J]. Computers & Operations Research,2017,80:101-112.
[18] LIN C,LEE I,WU M. Merits of using chromosome representations and shadow chromosomes in genetic algorithms for solving scheduling problems[J]. Robotics and Computer-Integrated Manufacturing,2019,58:196-207.
[19] 黄英杰,姚锡凡. 基于目标级联法和粒子群算法的柔性分布式车间调度[J]. 中南大学学报,2012,43(1):151-158.HUANG Yingjie,YAO Xifan. Planning and scheduling of multiple flexible-shops based on analytical target cascading and particle swarm optimization. Journal of Central South University,2012,43(1):151-158.
[20] EUSUFF M M,LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Resources Planning & Management,2003,129(3):210-225.
[21] PAN Q,WANG L,GAO L,et al. An effective shuffled frog-leaping algorithm for lot-streaming flow shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology,2011,52(5-8):699-713.
[22] LEI D,GUO X. A shuffled frog-leaping algorithm for job shop scheduling with outsourcing options[J]. International Journal of Production Research,2016,54(16):4793-4804.
[23] LEI D,ZHENG Y,GUO X. A shuffled frog-leaping algorithm for flexible job shop scheduling with the consideration of energy consumption[J]. International Journal of Production Research,2016,55(11):3126-3140.
[24] MASTROLILLI M,GAMBARDELLA L M. Effective neighbourhood functions for the flexible job shop problem[J]. Journal of Scheduling,2000,3(1):3-20.
[25] LI X,GAO L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics,2016,174:93-110.