Chinese Journal of Mechanical Engineering >

2019 , Vol. 32 >Issue 2: 21 - 21

DOI: https://doi.org/10.1186/s10033-019-0337-7

Intelligent Manufacturing Technology

A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem

  • Ghiath Al Aqel ,
  • Xinyu Li ,
  • Liang Gao
展开
  • State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

收稿日期: 2017-11-22

  网络出版日期: 2019-07-19

基金资助

Supported by National Natural Science Foundation of China (Grant Nos.51825502, 51775216), Hubei Provincial Natural Science Foundation of China (Grant No. 2018CFA078), and Program for HUST Academic Frontier Youth Team

收起

A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem

  • Ghiath Al Aqel ,
  • Xinyu Li ,
  • Liang Gao
Expand
  • State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Received date: 2017-11-22

  Online published: 2019-07-19

Supported by

Supported by National Natural Science Foundation of China (Grant Nos.51825502, 51775216), Hubei Provincial Natural Science Foundation of China (Grant No. 2018CFA078), and Program for HUST Academic Frontier Youth Team

Fold

摘要

The flexible job shop scheduling problem (FJSP) is considered as an important problem in the modern manufacturing system. It is known to be an NP-hard problem. Most of the algorithms used in solving FJSP problem are categorized as metaheuristic methods. Some of these methods normally consume more CPU time and some other methods are more complicated which make them difficult to code and not easy to reproduce. This paper proposes a modified iterated greedy (IG) algorithm to deal with FJSP problem in order to provide a simpler metaheuristic, which is easier to code and to reproduce than some other much more complex methods. This is done by separating the classical IG into two phases. Each phase is used to solve a sub-problem of the FJSP: sequencing and routing sub-problems. A set of dispatching rules are employed in the proposed algorithm for the sequencing and machine selection in the construction phase of the solution. To evaluate the performance of proposed algorithm, some experiments including some famous FJSP benchmarks have been conducted. By compared with other algorithms, the experimental results show that the presented algorithm is competitive and able to find global optimum for most instances. The simplicity of the proposed IG provides an effective method that is also easy to apply and consumes less CPU time in solving the FJSP problem.

关键词： Iterated greedy; Flexible job shop scheduling problem; Dispatching rules

本文引用格式

Ghiath Al Aqel , Xinyu Li , Liang Gao . A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem[J]. Chinese Journal of Mechanical Engineering, 2019 , 32(2) : 21 -21 . DOI: 10.1186/s10033-019-0337-7

Abstract

The flexible job shop scheduling problem (FJSP) is considered as an important problem in the modern manufacturing system. It is known to be an NP-hard problem. Most of the algorithms used in solving FJSP problem are categorized as metaheuristic methods. Some of these methods normally consume more CPU time and some other methods are more complicated which make them difficult to code and not easy to reproduce. This paper proposes a modified iterated greedy (IG) algorithm to deal with FJSP problem in order to provide a simpler metaheuristic, which is easier to code and to reproduce than some other much more complex methods. This is done by separating the classical IG into two phases. Each phase is used to solve a sub-problem of the FJSP: sequencing and routing sub-problems. A set of dispatching rules are employed in the proposed algorithm for the sequencing and machine selection in the construction phase of the solution. To evaluate the performance of proposed algorithm, some experiments including some famous FJSP benchmarks have been conducted. By compared with other algorithms, the experimental results show that the presented algorithm is competitive and able to find global optimum for most instances. The simplicity of the proposed IG provides an effective method that is also easy to apply and consumes less CPU time in solving the FJSP problem.

Key words： Iterated greedy; Flexible job shop scheduling problem; Dispatching rules

参考文献

[1] X Li, L Gao. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 2016, 174:93-110.
[2] A Muthiah, A Rajkumar, R Rajkumar. Hybridization of artificial bee colony algorithm with particle swarm optimization algorithm for flexible job shop scheduling. Energy Efficient Technologies for Sustainability (ICEETS), 2016 International Conference on, 2016:896-903.
[3] H Chen, J Ihlow, C Lehmann. A genetic algorithm for flexible job-shop scheduling. Robotics and Automation, 1999. Proceedings. 1999 IEEE International Conference on, 1999:1120-1125.
[4] P Brucker, R Schlie. Job-shop scheduling with multi-purpose machines. Computing, 1990, 45:369-375.
[5] H E Nouri, O B Driss, K Ghédira. A classification schema for the job shop scheduling problem with transportation resources:State-of-the-art review. Artificial Intelligence Perspectives in Intelligent Systems, Springer, 2016:1-11.
[6] Y Demir, S K İşleyen. Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling, 2013, 37:977-988.
[7] F Pezzella, G Morganti, G Ciaschetti. A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 2008, 35:3202-3212.
[8] A Baykasoğlu, L Özbakır. Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system. International Journal of Production Economics, 2010, 124:369-381.
[9] H Ingimundardottir, T P Runarsson. Evolutionary learning of linear composite dispatching rules for scheduling. Computational Intelligence, Springer, 2016:49-62.
[10] J Huang, G A Süer. A dispatching rule-based genetic algorithm for multi-objective job shop scheduling using fuzzy satisfaction levels. Computers & Industrial Engineering, 2015, 86:29-42.
[11] C Zhang, Y Rao, P Li, et al. Bilevel genetic algorithm for the flexible job-shop scheduling problem. Chinese Journal of Mechanical Engineering, 2007, 19(4):020.
[12] G Zhang, L Gao, P Li, et al. Improved genetic algorithm for the flexible job-shop scheduling problem. Journal of Mechanical Engineering, 2009, 45(7):026(in Chinese).
[13] M Huang, W Mingxu, L Xu. An improved genetic algorithm using opposition-based learning for flexible job-shop scheduling problem. Cloud Computing and Internet of Things (CCIOT), 20162nd International Conference on, 2016:8-15.
[14] H Xu, Z Bao, T Zhang. Solving dual flexible job-shop scheduling problem using a Bat Algorithm. Advances in Production Engineering & Management, 2017, 12:5.
[15] J Wu, G Wu, J Wang. Flexible job-shop scheduling problem based on hybrid ACO algorithm. International Journal of Simulation Modelling (IJSIMM), 2017, 16(3):497-505.
[16] O Sobeyko, L Mönch. Heuristic approaches for scheduling jobs in large-scale flexible job shops. Computers & Operations Research, 2016, 68:97-1096.
[17] J J Palacios, M A González, C R Vela, et al. Genetic tabu search for the fuzzy flexible job shop problem. Computers & Operations Research, 2015, 54:74-89.
[18] M Gaham, B Bouzouia, N Achour. An effective operations permutation-based discrete harmony search approach for the flexible job shop scheduling problem with makespan criterion. Applied Intelligence, 2017:1-19.
[19] I Kacem, S Hammadi, P Borne. Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 2002, 60:245-276.
[20] R Ruiz, T Stützle. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 2007, 177:2033-2049.
[21] L Fanjul-Peyro, R Ruiz. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 2010, 207:55-69.
[22] M Nawaz, E E Enscore, I Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 1983, 11:91-95.
[23] R Ruiz, T Stützle. An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 2008, 187:1143-1159.
[24] F Toyama, K Shoji, J Miyamichi. An iterated greedy algorithm for the node placement problem in bidirectional manhattan street networks. Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008:579-584.
[25] M F Tasgetiren, Q K Pan, Y C Liang. A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research, 2009, 36:1900-1915.
[26] Q K Pan, R Ruiz. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega, 2014, 44:41-50.
[27] T Urlings, R Ruiz. A new algorithm for multidimensional scheduling problems. The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems, 2009:20.
[28] T Urlings, R Ruiz, T Stützle. Shifting representation search for hybrid flexible flowline problems. European Journal of Operational Research, 2010, 207:1086-1095.
[29] M Pranzo, D Pacciarelli. An iterated greedy metaheuristic for the blocking job shop scheduling problem. Journal of Heuristics, 2016, 22:587-611.
[30] G Zhang, L Gao, X Li, et al. Variable neighborhood genetic algorithm for the flexible job shop scheduling problems. International Conference on Intelligent Robotics and Applications, 2008:503-512.
[31] Q K Pan, R Ruiz. Local search methods for the flowshop scheduling problem with flowtime minimization. European Journal of Operational Research, 2012, 222:31-43.
[32] R Haupt. A survey of priority rule-based scheduling. OR Spectrum, 1989, 11:3-16.
[33] J Branke, S Nguyen, C W Pickardt, et al. Automated design of production scheduling heuristics:A review. IEEE Transactions on Evolutionary Computation, 2016, 20:110-124.
[34] Y Mei, M Zhang. A comprehensive analysis on reusability of GP-evolved job shop dispatching rules. Evolutionary Computation (CEC), 2016 IEEE Congress on, 2016:3590-3597.
[35] S Nguyen, M Zhang. A PSO-based hyper-heuristic for evolving dispatching rules in job shop scheduling. Evolutionary Computation (CEC), 2017 IEEE Congress on, 2017:882-889.
[36] T C Chiang, L C Fu. Using dispatching rules for job shop scheduling with due date-based objectives. International Journal of Production Research, 2007, 45:3245-3262.
[37] M F Ausaf, L Gao, X Li, et al. A priority-based heuristic algorithm (PBHA) for optimizing integrated process planning and scheduling problem. Cogent Engineering, 2015, 2:1070494.
[38] H L Fan, H G Xiong, G Z Jiang, et al. Survey of the selection and evaluation for dispatching rules in dynamic job shop scheduling problem. Chinese Automation Congress (CAC) 2015, 2015:1926-1931.
[39] K C Ying, S W Lin, C C Lu. Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window. International Journal of Production Research, 2017, 55:1707-1719.
[40] I Kacem, S Hammadi, P Borne. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2002, 32:1-13.
[41] H E Nouri, O B Driss, K Ghédira. Genetic algorithm combined with Tabu search in a holonic multiagent model for flexible job shop scheduling problem. ICEIS (1), 2015:573-584.
[42] K Z Gao, P N Suganthan, T J Chua, et al. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion. Expert Systems with Applications, 2015, 42:7652-7663.
[43] Y Yuan, H Xu, J Yang. A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing, 2013, 13:3259-3272.
[44] Y Yuan, H Xu. Flexible job shop scheduling using hybrid differential evolution algorithms. Computers & Industrial Engineering, 2013, 65:246-260.
[45] J Gao, L Sun, M Gen. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 2008, 35:2892-2907.
[46] P Fattahi, M S Mehrabad, F Jolai. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 2007, 18:331.
[47] W Teekeng, A Thammano, P Unkaw, et al. A new algorithm for flexible job-shop scheduling problem based on particle swarm optimization. Artificial Life and Robotics, 2016, 21:18-23.
[48] E G Birgin, P Feofiloff, C G Fernandes, et al. A MILP model for an extended version of the Flexible Job Shop Problem. Optimization Letters, 2014, 8:1417-1431.
[49] P Brandimarte. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 1993, 41:157-183.
[50] H C Chang, Y P Chen, T K Liu, et al. Solving the flexible job shop scheduling problem with makespan optimization by using a hybrid Taguchi-genetic algorithm. IEEE Access, 2015, 3:1740-1754.
[51] M Ziaee. A heuristic algorithm for the distributed and flexible job-shop scheduling problem. The Journal of Supercomputing, 2014, 67:69-83.
[52] Y Zuo, M Gong, L Jiao. Adaptive multimeme algorithm for flexible job shop scheduling problem. Natural Computing, 2016:1-22.
Options
文章导航

/

〈 〉

版权所有 © 《Chinese Journal of Mechanical Engineering》编辑部

技术支持：北京玛格泰克科技发展有限公司