A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling*

Chin.J.Chem.Eng. ›› 2012, Vol. 20 ›› Issue (6): 1067-1073.

• PROCESS SYSTEMS ENGINEERING • Previous Articles Next Articles

A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^*

DENG Guanlong, XU Zhenhao, GU Xingsheng

Key Laboratory of Advanced Control and Optimization for Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

Received:2012-05-21 Revised:2012-07-18 Online:2012-12-28 Published:2012-12-28
Supported by:
Supported by the National Natural Science Foundation of China (61174040;61104178);the Fundamental Research Funds for the Central Universities

A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^*

邓冠龙, 徐震浩, 顾幸生

Key Laboratory of Advanced Control and Optimization for Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

通讯作者: GU Xingsheng,E-mail:xsgu@ecust.edu.cn
基金资助:
Supported by the National Natural Science Foundation of China (61174040;61104178);the Fundamental Research Funds for the Central Universities

Abstract

Abstract: A discrete artificial bee colony algorithm is proposed for solving the blocking flow shop scheduling problem with total flow time criterion.Firstly,the solution in the algorithm is represented as job permutation.Secondly,an initialization scheme based on a variant of the NEH (Nawaz-Enscore-Ham) heuristic and a local search is designed to construct the initial population with both quality and diversity.Thirdly,based on the idea of iterated greedy algorithm,some newly designed schemes for employed bee,onlooker bee and scout bee are presented.The performance of the proposed algorithm is tested on the well-known Taillard benchmark set,and the computational results demonstrate the effectiveness of the discrete artificial bee colony algorithm.In addition,the best known solutions of the benchmark set are provided for the blocking flow shop scheduling problem with total flow time criterion.

Key words: blocking flow shop scheduling, artificial bee colony algorithm, total flow time

摘要： A discrete artificial bee colony algorithm is proposed for solving the blocking flow shop scheduling problem with total flow time criterion.Firstly,the solution in the algorithm is represented as job permutation.Secondly,an initialization scheme based on a variant of the NEH (Nawaz-Enscore-Ham) heuristic and a local search is designed to construct the initial population with both quality and diversity.Thirdly,based on the idea of iterated greedy algorithm,some newly designed schemes for employed bee,onlooker bee and scout bee are presented.The performance of the proposed algorithm is tested on the well-known Taillard benchmark set,and the computational results demonstrate the effectiveness of the discrete artificial bee colony algorithm.In addition,the best known solutions of the benchmark set are provided for the blocking flow shop scheduling problem with total flow time criterion.

关键词: blocking flow shop scheduling, artificial bee colony algorithm, total flow time

DENG Guanlong, XU Zhenhao, GU Xingsheng. A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^*[J]. Chin.J.Chem.Eng., 2012, 20(6): 1067-1073.

邓冠龙, 徐震浩, 顾幸生. A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^*[J]. Chinese Journal of Chemical Engineering, 2012, 20(6): 1067-1073.

References

1 Hall,N.G.,Sriskandarajah,C.,"A survey of machine scheduling problems with blocking and no-wait in process",Oper.Res.,44 (3),510-525 (1996).
2 Ronconi,D.P.,"A note on constructive heuristics for the flowshop problem with blocking",Int.J.Prod.Econ.,87 (1),39-48 (2004).
3 Qian,Y.,Pan,M.,Huang,Y.,"Modeling and optimization for scheduling of chemical batch processes",Chin.J.Chem.Eng.,17 (1),1-7 (2009).
4 Grabowski,J.,Pempera,J.,"Sequencing of jobs in some production system",Eur.J.Oper.Res.,125 (3),535-550 (2000).
5 Gong,H.,Tang,L.,Duin,C.W.,"A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times",Comput.Oper.Res.,37 (5),960-969 (2010).
6 Martinez,S.,Peres,S.D.,Gueret,C.,Mati,Y.,Sauer,N.,"Complexity of flowshop scheduling problems with a new blocking constraint",Eur.J.Oper.Res.,169 (3),855-864 (2006).
7 Graham,R.L.,Lawler,E.L.,Lenstra,J.K.,Rinnooy Kan,A.H.G.,"Optimization and approximation in deterministic sequencing and scheduling: A survey",Ann.Discrete Math.,5 (1),287-326 (1979).
8 McCormick,S.T.,Pinedo,M.L.,Shenker,S.,Wolf,B.,"Sequencing in an assembly line with blocking to minimize cycle time",Oper.Res.,37 (6),925-936 (1989).
9 Leisten,R.,"Flowshop sequencing problems with limited buffer storage",Int.J.Prod.Res.,28 (11),2085-2100 (1990).
10 Nawaz,M.,Enscore,J.E.E.,Ham,I.,"A heuristic algorithm for the m-machine,n-job flow-shop sequencing problem",OMEGA,11 (1),91-95 (1983).
11 Caraffa,V.,Ianes,S.,Bagchi,T.P.,Sriskandarajah,C.,"Minimizing makespan in a blocking flowshop using genetic algorithms",Int.J.Prod.Econ.,70 (2),101-115 (2001).
12 Grabowski,J.,Pempera,J.,"The permutation flowshop problem with blocking: a tabu search approach",OMEGA,35 (3),302-311 (2007).
13 Wang,L.,Pan,Q.K.,Suganthan,P.N.,Wang,W.H.,Wang,Y.M.,"A novel hybrid discrete differential evolution algorithm for blocking flowshop scheduling problems",Comput.Oper.Res.,37 (3),509-520 (2010).
14 Ribas,I.,Companys,R.,Tort-Martorell,X.,"An iterated greedy algorithm for the flowshop scheduling with blocking",OMEGA,39 (3),293-301 (2011).
15 Wang,L.,Pan,Q.K.,Tasgetiren,M.F.,"A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem",Comput.Ind.Eng.,61 (1),76-83 (2011).
16 Wang,L.,Pan,Q.K.,Tasgetiren,M.F.,"Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms",Expert Syst.Appl.,37 (12),7929-7936 (2010).
17 Zhao,X.Q.,Rong,G.,"Blending scheduling under uncertainty based on particle swarm optimization algorithm",Chin.J.Chem.Eng.,13 (4),535-541 (2005).
18 Wang,J.L.,Xue,Y.Y.,Yu,T.,Zhao,L.Q.,"Run-to-run optimization for fed-batch fermentation process with swarm energy conservation particle swarm optimization algorithm",Chin.J.Chem.Eng.,18 (5),787-794 (2010).
19 Karaboga,D.,"An idea based on honey bee swarm for numerical optimization",Technical Report TR06,Computer Engineering Department,Erciyes University,Turkey (2005).
20 Karaboga,D.,Basturk,B.,"A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm",J.Global Optim.,39 (3),459-471 (2007).
21 Karaboga,D.,Basturk,B.,"On the performance of artificial bee colony (ABC) algorithm",Appl.Soft Comput.,8 (1),687-697 (2008).
22 Karaboga,D.,"A new design method based on artificial bee colony algorithm for digital IIR filters",J.Franklin Inst.,346 (4),328-348 (2009).
23 Karaboga,D.,Akay,B.,"A comparative study of artificial bee colony algorithm",Appl.Math.Comput.,214 (1),108-132 (2009).
24 Pan,Q.K.,Tasgetiren,M.F.,Suganthan,P.N.,Chua,T.J.,"A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem",Inform.Sci.,181 (12),2455-2468 (2011).
25 Tasgetiren,M.F.,Pan,Q.K.,Suganthan,P.N.,Chen,A.H.L.,"A discrete artificial bee colony algorithm for the total flow time minimization in permutation flow shops",Inform.Sci.,181 (16),3459-3475 (2011).
26 Ruiz,R.,Stutzle,T.,"A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem",Eur.J.Oper.Res.,177 (3),2033-2049 (2007).
27 Hansen,P.,Mladenovi,N.,Moreno,P.J.A.,"Variable neighborhood search: methods and applications",Ann.Oper.Res.,175 (1),367-407 (2010).
28 Taillard,E.,"Benchmarks for basic scheduling problems",Eur.J.Oper.Res.,64 (2),278-285 (1993).

A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^*

A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^*

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments