Research article Special Issues

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

  • 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.

    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:

  • 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.


    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(7726) PDF downloads(1200) Cited by(31)

Article outline

Figures and Tables

Figures(9)  /  Tables(4)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog