Approach to Hybrid Flow-Shop Scheduling Problem Based on Self-Guided Genetic Algorithm

Wen-Zhan Dai; Kai Xia

doi:10.20965/jaciii.2015.p0365

single-jc.php

« previous

JACIII Vol.19 No.3 pp. 365-371

doi: 10.20965/jaciii.2015.p0365

(2015)

Paper:

Views over last 60 days: 676

Approach to Hybrid Flow-Shop Scheduling Problem Based on Self-Guided Genetic Algorithm

Wen-Zhan Dai and Kai Xia

School of Information and Electronic Engineering, Zhejiang Gongshang University
Hangzhou 310018, China

Received:

December 15, 2013

Accepted:

February 2, 2015

Published:

May 20, 2015

Keywords:

hybrid flow shop scheduling problem, genetic algorithm, estimation of distribution algorithm, bivariate probability model, self-guided genetic algorithm

Abstract

The effective self-guided genetic algorithm (SGGA) which we proposed is based on the characteristics of a hybrid flow shop scheduling problem. A univariate probability model based on workpiece permutation is introduced together with a bivariate probability model based on a similar workpiece blocks. An approach to updating a probability model parameters is given based on superior individuals. A novel probability calculation function is proposed taking advantages of statistical learning information provided by univariate and bivariate probabilistic model to calculate the probability of workpieces located in different positions. A method for evaluating the quality of individual candidates generated by GA crossover and mutation operators is suggested for selecting promising and excellent individual candidates as offspring. Simulation results show that the SGGA has excellent performance and robustness.

Cite this article as:

W. Dai and K. Xia, “Approach to Hybrid Flow-Shop Scheduling Problem Based on Self-Guided Genetic Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.19 No.3, pp. 365-371, 2015.

Data files:

References

[1] G. Ulusoy et al., “Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach,” J. of the Operational Research Society, Vol.55, No.5, pp. 504-512, 2004.
[2] M.-C. Portmann, A. Vignier, D. Dardilhac, and D. Dezalay, “Branch and bound crossed with GA to solve hybrid flowshops,” European J. of Operational Research, Vol.107, No.2, pp. 389-400, 1998.
[3] H. Soewandi and S. E. Elmaghraby, “Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan,” IIE Trans., Vol.35, No.5, pp. 467-477, 2003.
[4] E. Figielska, “A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources,” Computers & Industrial Engineering, Vol.56, No.1, pp. 142-151, 2009.
[5] L. Lopez, M. W. Carter, and M. Gendreau, “The hot strip mill production scheduling problem: A tabu search approach,” European J. of Operational Research, Vol.106, No.2, pp. 317-335, 1998.
[6] R. Linn and W. Zhang, “Hybrid flow shop scheduling: a survey,” Computers & Industrial Engineering, Vol.37, No.1, pp. 57-61, 1999.
[7] J. N. Gupta, “Two-stage, hybrid flowshop scheduling problem,” J. of the Operational Research Society, pp. 359-364, 1988.
[8] P.-C. Chang, S.-H. Chen, and K.-L. Lin, “Two-phase sub population genetic algorithm for parallel machine-scheduling problem,” Expert Systems with Applications, Vol.29, No.3, pp. 705-712, 2005.
[9] Y. Zhang, X. Li, and Q. Wang, “Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization,” European J. of Operational Research, Vol.196, No.3, pp. 869-876, 2009.
[10] Y. Zhang, X. Li, and Q. Wang, “Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization,” European J. of Operational Research, Vol.196, No.3, pp. 869-876, 2009.
[11] M. M. Eusuff and K. E. Lansey, “Optimization of water distribution network design using the shuffled frog leaping algorithm,” J. of Water Resources Planning and Management, Vol.129, No.3, pp. 210-225, 2003.
[12] Q.-K. Pan and R. Ruiz, “An estimation of distribution algorithm for lot-streaming flow shop problems with setup times,” Omega, Vol.40, No.2, pp. 166-180, 2012.
[13] B. Jarboui, M. Eddaly, and P. Siarry, “An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems,” Computers & Operations Research, Vol.36, No.9, pp. 2638-2646, 2009.
[14] N. Mladenovi’c and P. Hansen, “Variable neighborhood search,” Computers & Operations Research, Vol.24, No.11, pp. 1097-1100, 1997.
[15] J. Pena, V. Robles, P. Larra naga, V. Herves, F. Rosales, and M. S. Péerez, “GA-EDA: Hybrid evolutionary algorithm using genetic and estimation of distribution algorithms,” Innovations in Applied Artificial Intelligence, pp. 361-371, Springer, 2004.
[16] Y.-M. Chen, M.-C. Chen, P.-C. Chang, and S.-H. Chen, “Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems,” Computers & Industrial Engineering, Vol.62, No.2, pp. 536-545, 2012.
[17] S.-H. Chen, P.-C. Chang, T. Cheng, and Q. Zhang, “A self-guided genetic algorithm for permutation flowshop scheduling problems,” Computers & Operations Research, Vol.39, No.7, pp. 1450-1457, 2012.
[18] S.-H. Chen and M.-C. Chen, “Addressing the advantages of using ensemble probabilistic models in estimation of distribution algorithms for scheduling problems,” Int. J. of Production Economics, Vol.141, No.1, pp. 24-33, 2013.
[19] I. Kacem, S. Hammadi, and P. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Trans. on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol.32, No.1, pp. 1-13, 2002.
[20] A. Biswas, K. Mishra, S. Tiwari, and A. Misra, “Physics-inspired optimization algorithms: A survey,” J. of Optimization, 2013.
[21] Y. Xu, L. Wang, G. Zhou, and S. Wang, “An effective shuffled frog leaping algorithm for solving hybrid flow-shop scheduling problem,” Advanced Intelligent Computing, pp. 560-567, Springer, 2012.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] G. Ulusoy et al., “Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach,” J. of the Operational Research Society, Vol.55, No.5, pp. 504-512, 2004.

[2] [2] M.-C. Portmann, A. Vignier, D. Dardilhac, and D. Dezalay, “Branch and bound crossed with GA to solve hybrid flowshops,” European J. of Operational Research, Vol.107, No.2, pp. 389-400, 1998.

[3] [3] H. Soewandi and S. E. Elmaghraby, “Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan,” IIE Trans., Vol.35, No.5, pp. 467-477, 2003.

[4] [4] E. Figielska, “A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources,” Computers & Industrial Engineering, Vol.56, No.1, pp. 142-151, 2009.

[5] [5] L. Lopez, M. W. Carter, and M. Gendreau, “The hot strip mill production scheduling problem: A tabu search approach,” European J. of Operational Research, Vol.106, No.2, pp. 317-335, 1998.

[6] [6] R. Linn and W. Zhang, “Hybrid flow shop scheduling: a survey,” Computers & Industrial Engineering, Vol.37, No.1, pp. 57-61, 1999.

[7] [7] J. N. Gupta, “Two-stage, hybrid flowshop scheduling problem,” J. of the Operational Research Society, pp. 359-364, 1988.

[8] [8] P.-C. Chang, S.-H. Chen, and K.-L. Lin, “Two-phase sub population genetic algorithm for parallel machine-scheduling problem,” Expert Systems with Applications, Vol.29, No.3, pp. 705-712, 2005.

[9] [9] Y. Zhang, X. Li, and Q. Wang, “Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization,” European J. of Operational Research, Vol.196, No.3, pp. 869-876, 2009.

[10] [10] Y. Zhang, X. Li, and Q. Wang, “Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization,” European J. of Operational Research, Vol.196, No.3, pp. 869-876, 2009.

[11] [11] M. M. Eusuff and K. E. Lansey, “Optimization of water distribution network design using the shuffled frog leaping algorithm,” J. of Water Resources Planning and Management, Vol.129, No.3, pp. 210-225, 2003.

[12] [12] Q.-K. Pan and R. Ruiz, “An estimation of distribution algorithm for lot-streaming flow shop problems with setup times,” Omega, Vol.40, No.2, pp. 166-180, 2012.

[13] [13] B. Jarboui, M. Eddaly, and P. Siarry, “An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems,” Computers & Operations Research, Vol.36, No.9, pp. 2638-2646, 2009.

[14] [14] N. Mladenovi’c and P. Hansen, “Variable neighborhood search,” Computers & Operations Research, Vol.24, No.11, pp. 1097-1100, 1997.

[15] [15] J. Pena, V. Robles, P. Larra naga, V. Herves, F. Rosales, and M. S. Péerez, “GA-EDA: Hybrid evolutionary algorithm using genetic and estimation of distribution algorithms,” Innovations in Applied Artificial Intelligence, pp. 361-371, Springer, 2004.

[16] [16] Y.-M. Chen, M.-C. Chen, P.-C. Chang, and S.-H. Chen, “Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems,” Computers & Industrial Engineering, Vol.62, No.2, pp. 536-545, 2012.

[17] [17] S.-H. Chen, P.-C. Chang, T. Cheng, and Q. Zhang, “A self-guided genetic algorithm for permutation flowshop scheduling problems,” Computers & Operations Research, Vol.39, No.7, pp. 1450-1457, 2012.

[18] [18] S.-H. Chen and M.-C. Chen, “Addressing the advantages of using ensemble probabilistic models in estimation of distribution algorithms for scheduling problems,” Int. J. of Production Economics, Vol.141, No.1, pp. 24-33, 2013.

[19] [19] I. Kacem, S. Hammadi, and P. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Trans. on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol.32, No.1, pp. 1-13, 2002.

[20] [20] A. Biswas, K. Mishra, S. Tiwari, and A. Misra, “Physics-inspired optimization algorithms: A survey,” J. of Optimization, 2013.

[21] [21] Y. Xu, L. Wang, G. Zhou, and S. Wang, “An effective shuffled frog leaping algorithm for solving hybrid flow-shop scheduling problem,” Advanced Intelligent Computing, pp. 560-567, Springer, 2012.