An Improved Biogeography-Based Optimization Algorithm for Blocking Flow Shop Scheduling Problem

LIU Shufen; WANG Pengfei; ZHANG Jiachen

doi:10.1049/cje.2018.01.007

Volume 27 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2018 > 27(2): 351-358

LIU Shufen, WANG Pengfei, ZHANG Jiachen, “An Improved Biogeography-Based Optimization Algorithm for Blocking Flow Shop Scheduling Problem,” Chinese Journal of Electronics, vol. 27, no. 2, pp. 351-358, 2018, doi: 10.1049/cje.2018.01.007

Citation:

LIU Shufen, WANG Pengfei, ZHANG Jiachen, “An Improved Biogeography-Based Optimization Algorithm for Blocking Flow Shop Scheduling Problem,” Chinese Journal of Electronics, vol. 27, no. 2, pp. 351-358, 2018, doi: 10.1049/cje.2018.01.007

Citation:

PDF( 319 KB)

An Improved Biogeography-Based Optimization Algorithm for Blocking Flow Shop Scheduling Problem

doi: 10.1049/cje.2018.01.007

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), the National Key Technology Research and Development Program of China (No.2014BAH29F03).

More Information

Corresponding author: ZHANG Jiachen (corresponding author) was born in Jilin Province, China, in 1969. He received the Ph.D. degree in Computer Science and Technology from Jilin University in 2004. Currently he is a professor of College of Computer Science and Technology in Jilin University. His research interests lie primarily in software maintenance and evolution. (Email:zhangjc@jlu.edu.cn)
Received Date: 2017-07-26
Rev Recd Date: 2017-10-27
Publish Date: 2018-03-10

Abstract

Abstract

To solve the blocking flow shop scheduling with maximum completion time (i.e. makespan) criterion, we proposed an Improved biogeography-based optimization algorithm (IBBO). The framework of basic BBO algorithm is used in the IBBO algorithm, and the introduction of the NEH algorithm make IBBO algorithm with certain quality and diversity. The migration operation based on the insert rules and the mutation operation based on swap rules are presented to avoid the occurrence of illegal solution of the blocking flow shop problem. An insertneighborhood search algorithm was used to strengthen the local search ability of the IBBO. The computational results show the effectiveness of the proposed IBBO algorithm in solving the blocking flow shop scheduling with maximum completion time criterion.
- Blocking flow shop,
- Biogeography-based optimization,
- Makespan,
- Insert-neighborhood search algorithm

FullText(HTML)

References(24)

References

D.Y. Bai and L.X. Tang, "Two asymptotically optimal lower bounds for flow shop problem", Chinese Journal of Electronics, Vol.18, pp.625-629, 2009.

C. Zhou, L. Gao and H.B. Gao, "Particle swarm optimization based algorithm for permutation flow shop scheduling", Acta Electronica Sinica, Vol.34, pp.2008-2011, 2006. (in Chinese)

Y. Tian and D.Y. Liu, "A hybrid particle swarm optimization method for flow shop scheduling problem", Acta Electronica Sinica, Vol.39, pp.1087-1093, 2011. (in Chinese)

C. Wang, S. Song and J.N.D. Gupta, et al., "A threephase algorithm for flowshop scheduling with blocking to minimize makespan", Computers & Operations Research, Vol.39, pp.2880-2887, 2012.

L. Wang, K.P. Quan and P.N. Suganthan, et al., "A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems", Computers & Operations Research, Vol.37, pp.509-520, 2010.

I. Ribas, R. Companys, and X. Tort-Martorell, "An iterated greedy algorithm for the flowshop scheduling problem with blocking", OMEGA, Vol.39, pp.293-301, 2011.

I. Ribas and R. Companys, "Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization", Computers & Industrial Engineering, Vol.87, pp.30-39, 2015.

D. Karaboga, B. Gorkemli and C. Ozturk, et al., "A comprehensive survey:Artificial bee colony (ABC) algorithm and applications", Artificial Intelligence Review, Vol.42, No.1, pp.21-57, 2014.

D. Lei, "Multi-objective artificial bee colony for interval job shop scheduling with flexible maintenance", The International Journal of Advanced Manufacturing Technology, Vol.66, No.9-12, pp.1835-1843, 2012.

J. Li and Q. 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.

D.P. Ronconi, "A branch-and-bound algorithm to minimize the makespan in a flowshop problem with blocking", Annals of Operations Research, Vol.138, pp.53-65, 2013.

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.

H.N. Xuan, R.C. Zhang and S.S. Shi, "An efficient cuckoo search algorithm for system-level fault diagnosis", Chinese Journal of Electronics, Vol.25, No.6, pp.999-1004, 2016.

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

D. Simon, R. Rarick and 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, 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, pp.3605-3615, 2010.

S.H.A. Rahmati and M. Zandieh, "A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem", the International Journal of Advanced Manufacturing Technology, Vol.58, No.9-12, pp.1115-1129, 2012.

J. Framinan, R. Leisten and R. Ruiz, Manufacturing Scheduling Systems:An Integrated View on Models, Methods, and Tools, Springer, London, 2014.

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, pp.91-95, 1983.

E. Taillard, "Bench marks for basic scheduling problems", European Journal of Operational Research, Vol.64, pp.278-285, 1993.

Relative Articles

Supplements(0)

Cited By

Proportional views