An Effective Biogeography-Based Optimization Algorithm for Flow Shop Scheduling with Intermediate Buffers

LIU Shufen; WANG Pengfei; YAO Zhilin

doi:10.1049/cje.2018.06.003

Volume 27 Issue 6

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2018 > 27(6): 1141-1150

LIU Shufen, WANG Pengfei, YAO Zhilin, “An Effective Biogeography-Based Optimization Algorithm for Flow Shop Scheduling with Intermediate Buffers,” Chinese Journal of Electronics, vol. 27, no. 6, pp. 1141-1150, 2018, doi: 10.1049/cje.2018.06.003

Citation:

LIU Shufen, WANG Pengfei, YAO Zhilin, “An Effective Biogeography-Based Optimization Algorithm for Flow Shop Scheduling with Intermediate Buffers,” Chinese Journal of Electronics, vol. 27, no. 6, pp. 1141-1150, 2018, doi: 10.1049/cje.2018.06.003

Citation:

PDF( 401 KB)

An Effective Biogeography-Based Optimization Algorithm for Flow Shop Scheduling with Intermediate Buffers

doi: 10.1049/cje.2018.06.003

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61472160) and the National Key Technology Research and Development Program of China (No.2014BAH29F03).

More Information

Corresponding author: YAO Zhilin (corresponding author) was born in Jilin Province, China, in 1973. He received the Ph.D. degree from Jilin University, China, in 2007. He is a lecturer in College of Computer Science and Technology of Jilin University. His research area covers computer supported cooperative work, software engineering, etc. (Email:yaozl@jlu.edu.cn)
Received Date: 2018-01-23
Rev Recd Date: 2018-05-17
Publish Date: 2018-11-10

Abstract

Abstract

This paper proposes an Effective biogeography-based optimization (EBBO) algorithm for solving the flow shop scheduling problem with intermediate buffers to minimize the Total flow time (TFT). Discrete job permutations are used to represent individuals in the EBBO so the discrete problem can be solved directly. The NEH heuristic and NEH-WPT heuristic are used for population initialization to guarantee the diversity of the solution. Migration and mutation rates are improved to accelerate the search process. An improved migration operation using a two-points method and mutation operation using inverse rules are developed to prevent illegal solutions. A new local search algorithm is proposed for embedding into the EBBO algorithm to enhance local search capability. Computational simulations and comparisons demonstrated the superiority of the proposed EBBO algorithm in solving the flow shop scheduling problem with intermediate buffers with the TFT criterion.
- Flow shop scheduling,
- Intermediate buffer,
- Total flow time (TFT),
- Biogeography-based optimization algorithm,
- Local search algorithm

FullText(HTML)

References(24)

References

M.F. Tasgetiren, Q.K. Pan and P.N. Suganthan, et al., “A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops”, Information Sciences, Vol.181, No.16, pp.3459-3475, 2011.

S.A. Fahmy, T.Y. Elmekkawy and S. Balakrishnan, “Mathematical formulations for scheduling in manufacturing cells with limited capacity buffers”, International Journal of Operational Research, Vol.7, No.4, pp.463-486., 2010.

J.Q. Li and Q.K. Pan, “Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm”, Information Sciences, Vol.316, pp.487-502, 2015.

S. Abdollahpour and J. Rezaeian, “Minimizing makespan for flow shop scheduling problem with intermediate buffers by using hybrid approach of artificial immune system”, Applied Soft Computing, Vol.28, pp.44-56, 2015.

L.Q. Zhao, J.X. Tang and J.B. Wang, et al., “An improved particle swarm optimisation with a linearly decreasing disturbance term for flow shop scheduling with limited buffers”, International Journal of Computer Integrated Manufacturing, Vol.27, No.5, pp.488-499, 2014.

G.L. Deng, H.Y. Yang, and S.N. Zhang, “An enhanced discrete artificial bee colony algorithm to minimize the total flow time in permutation flow shop scheduling with limited buffers”, Mathematical Problems in Engineering, Vol.2016, Article ID 7373617,11 pages, 2016.

S.J. Zhang and X.S. Gu, “An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers”, Journal of Central South University, Vol.22, No.9, pp.3471-3484, 2015.

G. Moslehi, D. Khorasanian, et al., “A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion”, Computers & Operations Research, Vol.52, No.Part B, pp.260-268, 2014.

B. Liu, L. Wang and Y.H. Jin, “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”, The International Journal of Advanced Manufacturing Technology, Vol.35,No.9, pp.2791-2806, 2008.

B. Qian, L. Wang, D.X. Huang, et al., “An effective hybrid DEbased algorithm for flow shop scheduling with limited buffers”, International Journal of Production Research, Vol.47, No.1, pp.1-24, 2009.

Q.K. Pan, L. Wang, L. Gao, et al., “An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers”, Information Sciences, Vol.181, No.3, pp.668-685, 2011.

D. Simon, “Biogeography-based optimization”, IEEE Trans. Evolutionary Computation, Vol.12, No.6, pp.702-713, 2008.

D.C. Tran and Z.J. Wu, “Adaptive multi-layer particle swarm optimization with neighborhood search”, Chinese Journal of Electronics, Vol.25, No.6, pp.1079-1088, 2016.

D.S. Shu, Z.X. Huang and J.Y. Li “Application of multi-agent particle swarm algorithm in distribution network reconfiguration”, Chinese Journal of Electronics, Vol.25, No.6, pp.1179-1185, 2016.

Y.W. Zhang, G.M. Cui and X. Guo “A service composition optimization method based on task-granulating”, Acta Electronica Sinica, Vol.46, No.1, pp.245-251, 2018. (in Chinese)

D. Simon, “A dynamic system model of biogeography-based optimization”, Applied Soft Computing, Vol.11, No.8, pp.5652-5661, 2011.

W. Guo, L. Wang and Q. Wu, “An analysis of the migration rates of biogeography-based optimization”, Information Sciences, Vol.254, No.1, pp.111-140, 2014.

D. Simon, R. Rarick, M. Ergezer, et al., “Analytical and numerical comparisons of biogeography-based optimization and genetic algorithms”, Information Sciences, Vol.181, No.7, pp.1224-1248, 2011.

G. Xiong, D. Shi and X. Duan, “Enhancing the performance of biogeography-based optimization using polyphyletic migration operator and orthogonal learning”, Computers & Operations Research, Vol.41, No.1, pp.125-139, 2014.

A. Bhattacharya and P. Chattopadhyay, “Solving complex economic load dispatch problems using biogeography-based optimization”, Expert Systems with Applications, Vol.37, No.5, pp.3605-3615, 2010.

D. Simon, M. Ergezer and D. Du, et al., “Markov models for biogeography-based optimization”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol.41, No.1, pp.299-306, 2011.

M. Nawaz, E.E.J. Enscore and I. Ham, “A heuristic algorithm for the m machine, n-job flow shop sequencing problem”, Omega, Vol.11, No.1, pp.91-95, 1983.

L. Wang, Q.K. Pan and M.F. Tasgetiren, “Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms”, Expert Systems with Applications, Vol.37, No.12, pp.7929-7936, 2010.

E. Taillard, “Bench marks for basic scheduling problems”, European Journal of Operational Research, Vol.64, No.2, pp.278-85, 1993.

Relative Articles

Supplements(0)

Cited By

Proportional views