Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm

Guohui Zhang; Jinghe Sun; Xing Liu; Guodong Wang; Yangyang Yang; Guohui Zhang; Jinghe Sun; Xing Liu; Guodong Wang; Yangyang Yang

doi:10.3934/mbe.2019065

Mathematical Biosciences and Engineering

2019, Volume 16, Issue 3: 1334-1347. doi: 10.3934/mbe.2019065

Previous Article Next Article

Research article Special Issues

Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm

School of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450015, China

Received: 20 November 2018 Accepted: 21 January 2019 Published: 20 February 2019

In the practical production, after the completion of a job on a machine, it may be transported between the different machines. And, the transportation time may affect product quality in certain industries, such as steelmaking. However, the transportation times are commonly neglected in the literature. In this paper, the transportation time and processing time are taken as the independent time into the flexible job shop scheduling problem. The mathematical model of the flexible job shop scheduling problem with transportation time is established to minimize the maximum completion time. The FJSP problem is NP-hard. Then, an improved genetic algorithm is used to solve the problem. In the decoding process, an operation left shift insertion method according to the problem characteristics is proposed to decode the chromosomes in order to get the active scheduling solutions. The actual instance is solved by the proposed algorithm used the Matlab software. The computational results show that the proposed mathematical model and algorithm are valid and feasible, which could effectively guide the actual production practice.
- flexible job shop scheduling problem,
- transportation time,
- genetic algorithm,
- active scheduling
Citation: Guohui Zhang, Jinghe Sun, Xing Liu, Guodong Wang, Yangyang Yang. Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm[J]. Mathematical Biosciences and Engineering, 2019, 16(3): 1334-1347. doi: 10.3934/mbe.2019065

Related Papers:

Abstract

In the practical production, after the completion of a job on a machine, it may be transported between the different machines. And, the transportation time may affect product quality in certain industries, such as steelmaking. However, the transportation times are commonly neglected in the literature. In this paper, the transportation time and processing time are taken as the independent time into the flexible job shop scheduling problem. The mathematical model of the flexible job shop scheduling problem with transportation time is established to minimize the maximum completion time. The FJSP problem is NP-hard. Then, an improved genetic algorithm is used to solve the problem. In the decoding process, an operation left shift insertion method according to the problem characteristics is proposed to decode the chromosomes in order to get the active scheduling solutions. The actual instance is solved by the proposed algorithm used the Matlab software. The computational results show that the proposed mathematical model and algorithm are valid and feasible, which could effectively guide the actual production practice.

References

[1]	X. Y. Li and L. Gao, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, Int. J. Prod. Econ., 174 (2016), 93–110.
[2]	X. Y. Li, C. Lu, L. Gao, et al., An effective multi-objective algorithm for energy efficient scheduling in a real-life welding shop, IEEE T. Ind. Inf., 14 (2018), 5400–5409.
[3]	X. Y. Li, L. Gao, Q. K. Pan, et al., An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop, IEEE T. Syst. Man. Cy. A., (2018), DOI: 10.1109/TSMC.2018.2881686.
[4]	G. H. Zhang, L. J. Zhang, X. H. Song, et al., A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem, Clust. Comput., (2018), 1–12.
[5]	G. H. Zhang, L. Gao and Y. Shi, An effective genetic algorithm for the flexible job-shop scheduling problem, Expert. Syst. Appl., 38 (2011), 3563–3573.
[6]	G. H. Zhang, X. Y. Shao, P. G. Li, et al., An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Comput. Ind. Eng., 56 (2009), 1309–1318.
[7]	J. Zhang, J. Jie, W. L. Wang, et al., A hybrid particle swarm optimisation for multi-objective flexible job-shop scheduling problem with dual-resources constrained, Int. J. Comput. Sci. Math., 8 (2018), 526.
[8]	J. Wu, G. D. Wu, J. J. Wang, et al., Flexible job-shop scheduling problem based on hybrid ACO algorithm, Int. J. Simul. Model., 16 (2017), 497–505.
[9]	D. M. Lei, Y. L. Zheng and X. P. Guo, A shuffled frog-leaping algorithm for flexible job shop scheduling with the consideration of energy consumption, Int. J. Prod. Res., 55 (2017), 3126–3140.
[10]	Y. Xu, L. Wang, S. Y. Wang, et al., An effective teaching–learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time, Neurocomputing, 148 (2015), 260–268.
[11]	C. Lu, X. Y. Li, L. Gao, et al., An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times, Comput. Ind. Eng., 104 (2017), 156–174.
[12]	Y. Z. Zhou, W. C. Yi, L. Gao, et al., Adaptive differential evolution with sorting crossover rate for continuous optimization problems, IEEE T. Cybern., 47 (2017), 2742–2753.
[13]	J. Hurink and S. Knust, Tabu search algorithms for job-shop problems with a single transport robot, Eur. J. Oper. Res., 162 (2005), 99–111.
[14]	B. Naderi, M. Zandieh, A. K. G. Balagh, et al., An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness, Expert. Syst. Appl., 36 (2009), 9625–9633.
[15]	M. Boudhar and A. Haned, Preemptive scheduling in the presence of transportation times, Comput. Oper. Res., 36 (2009), 2387–2393.
[16]	B. Naderi, A. A. Javid and F. Jolai, Permutation flowshops with transportation times: Mathematical models and solution methods, Int. J. Adv. Manuf. Tech., 46 (2010), 631–647.
[17]	A. Rossi, Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships, Int. J. Prod. Econ., 153 (2014), 253–267.
[18]	S. Karimi, Z. Ardalan and B. Naderi, et al., Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm, Appl. Math. Model., 41 (2017), 667–682.

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)