nach oben

Neural Computing and Applications

Erschienen in:

27.07.2020 | Original Article

Artificial bee colony algorithm including some components of iterated greedy algorithm for permutation flow shop scheduling problems

verfasst von: Oğuzhan Ahmet Arık

Erschienen in: Neural Computing and Applications | Ausgabe 8/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The permutation flow shop scheduling problem has been investigated by researchers for more than 40 years due to its complexity and lots of real-life examples of the problem. Many exact or approximate solution approaches have been presented for the problem. Among solution approaches in the literature, iterated greedy algorithm and its variants are the most effective solution methods for the problem. This paper proposes a hybrid solution algorithm that uses the best components such as local search operators and destruction/construction operators of the variants of iterated greedy algorithm in an artificial bee colony algorithm. An ANOVA is made for determining the most proper components of iterated greedy algorithm. Then, these components are combined with artificial bee colony algorithm. Furthermore, a design of experiment is made for determining the best parameter setting for the proposed hybrid artificial bee colony. The experimental results of the proposed algorithm compared with variants of iterated greedy algorithms in the literature show that the proposed algorithm produces better solutions that deviate less from the optimum or lower-bound solutions for permutation flow shop scheduling problems with the makespan performance criterion.

Vorheriger Artikel Intoxicated person identification using Markov chains and neural networks

Nächster Artikel Frequency–amplitude coupling: a new approach for decoding of attended features in covert visual attention task

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129. https://doi.org/10.1287/moor.1.2.117MathSciNetCrossRefMATH

Nawaz M, Enscore EE Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11:91–95. https://doi.org/10.1016/0305-0483(83)90088-9CrossRef

Fernandez-Viagas V, Ruiz R, Framinan JM (2017) A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation. Eur J Oper Res 257:707–721. https://doi.org/10.1016/j.ejor.2016.09.055MathSciNetCrossRefMATH

Yenisey MM, Yagmahan B (2014) Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega (UK) 45:119–135. https://doi.org/10.1016/j.omega.2013.07.004CrossRef

Reza Hejazi S, Saghafian S (2005) Flowshop-scheduling problems with makespan criterion: a review. Int J Prod Res 43:2895–2929. https://doi.org/10.1080/0020754050056417CrossRefMATH

Framinan JM, Gupta JND, Leisten R (2004) A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. J Oper Res Soc 55:1243–1255. https://doi.org/10.1057/palgrave.jors.2601784CrossRefMATH

Framinan JM, Leisten R, Ruiz-Usano R (2002) Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. Eur J Oper Res 141:559–569. https://doi.org/10.1016/S0377-2217(01)00278-8CrossRefMATH

Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Nav Res Logist Q 1:61–68. https://doi.org/10.1002/nav.3800010110CrossRefMATH

Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285. https://doi.org/10.1016/0377-2217(93)90182-MCrossRefMATH

10.

Vallada E, Ruiz R, Framinan JM (2015) New hard benchmark for flowshop scheduling problems minimising makespan. Eur J Oper Res 240:666–677. https://doi.org/10.1016/j.ejor.2014.07.033CrossRefMATH

11.

Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049. https://doi.org/10.1016/j.ejor.2005.12.009CrossRefMATH

12.

Pan Q-K, Tasgetiren MF, Liang Y-C (2008) A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput Ind Eng 55:795–816. https://doi.org/10.1016/j.cie.2008.03.003CrossRef

13.

Rad SF, Ruiz R, Boroojerdian N (2009) New high performing heuristics for minimizing makespan in permutation flowshops. Omega 37:331–345. https://doi.org/10.1016/j.omega.2007.02.002CrossRef

14.

Dubois-Lacoste J, Pagnozzi F, Stützle T (2017) An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem. Comput Oper Res 81:160–166. https://doi.org/10.1016/j.cor.2016.12.021MathSciNetCrossRefMATH

15.

Fernandez-Viagas V, Framinan JM (2014) On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Comput Oper Res 45:60–67. https://doi.org/10.1016/j.cor.2013.12.012MathSciNetCrossRefMATH

16.

Fernandez-Viagas V, Framinan JM (2019) A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective. Comput Oper Res 112:104767. https://doi.org/10.1016/j.cor.2019.104767MathSciNetCrossRefMATH

17.

Taillard E (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47:65–74. https://doi.org/10.1016/0377-2217(90)90090-XMathSciNetCrossRefMATH

18.

Pan QK, Ruiz R (2014) An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega (UK) 44:41–50. https://doi.org/10.1016/j.omega.2013.10.002CrossRef

19.

Benavides AJ, Ritt M (2018) Fast heuristics for minimizing the makespan in non-permutation flow shops. Comput Oper Res 100:230–243. https://doi.org/10.1016/j.cor.2018.07.017MathSciNetCrossRefMATH

20.

Tasgetiren MF, Liang Y-C, Sevkli M, Gencyilmaz G (2007) A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Oper Res 177:1930–1947. https://doi.org/10.1016/j.ejor.2005.12.024CrossRefMATH

21.

Wang X, Tang L (2012) A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking. Appl Soft Comput J 12:652–662. https://doi.org/10.1016/j.asoc.2011.09.021CrossRef

22.

Chen C-L, Huang S-Y, Tzeng Y-R, Chen C-L (2014) A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem. Soft Comput 18:2271–2282. https://doi.org/10.1007/s00500-013-1199-zCrossRef

23.

Li D, Deng N (2012) Solving permutation flow shop scheduling problem with a cooperative multi-swarm PSO algorithm. J Inf Comput Sci 9:977–987MathSciNet

24.

Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res 155:426–438. https://doi.org/10.1016/S0377-2217(02)00908-6CrossRefMATH

25.

Ahmadizar F (2012) A new ant colony algorithm for makespan minimization in permutation flow shops. Comput Ind Eng 63:355–361. https://doi.org/10.1016/j.cie.2012.03.015CrossRef

26.

Grabowski J, Wodecki M (2004) A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Comput Oper Res 31:1891–1909. https://doi.org/10.1016/S0305-0548(03)00145-XMathSciNetCrossRefMATH

27.

Grabowski J, Pempera J (2007) The permutation flow shop problem with blocking. A tabu search approach. Omega 35:302–311. https://doi.org/10.1016/j.omega.2005.07.004CrossRef

28.

Varadharajan TK, Rajendran C (2005) A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. Eur J Oper Res 167:772–795. https://doi.org/10.1016/j.ejor.2004.07.020MathSciNetCrossRefMATH

29.

Lin S-W, Ying K-C (2013) Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm. Comput Oper Res 40:1625–1647. https://doi.org/10.1016/j.cor.2011.08.009MathSciNetCrossRefMATH

30.

Saravanan M, Noorul Haq A, Vivekraj AR, Prasad T (2008) Performance evaluation of the scatter search method for permutation flowshop sequencing problems. Int J Adv Manuf Technol 37:1200–1208. https://doi.org/10.1007/s00170-007-1053-5CrossRef

31.

Dasgupta P, Das S (2015) A discrete inter-species cuckoo search for flowshop scheduling problems. Comput Oper Res 60:111–120. https://doi.org/10.1016/j.cor.2015.01.005MathSciNetCrossRefMATH

32.

Zobolas GI, Tarantilis CD, Ioannou G (2009) Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Comput Oper Res 36:1249–1267. https://doi.org/10.1016/j.cor.2008.01.007MathSciNetCrossRefMATH

33.

Tseng L-Y, Lin Y-T (2009) A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 198:84–92. https://doi.org/10.1016/j.ejor.2008.08.023CrossRefMATH

34.

Haq AN, Ramanan TR, Shashikant KS, Sridharan R (2010) A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling. Int J Prod Res 48:4217–4231. https://doi.org/10.1080/00207540802404364CrossRefMATH

35.

Nagano MS, Ruiz R, Lorena LAN (2008) A constructive genetic algorithm for permutation flowshop scheduling. Comput Ind Eng 55:195–207. https://doi.org/10.1016/j.cie.2007.11.018CrossRef

36.

Pasupathy T, Rajendran C, Suresh RK (2006) A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. Int J Adv Manuf Technol 27:804–815. https://doi.org/10.1007/s00170-004-2249-6CrossRef

37.

Laha D, Chakraborty UK (2009) An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling. Int J Adv Manuf Technol 44:559–569. https://doi.org/10.1007/s00170-008-1845-2CrossRef

38.

Tzeng Y-R, Chen C-L (2012) A hybrid EDA with ACS for solving permutation flow shop scheduling. Int J Adv Manuf Technol 60:1139–1147. https://doi.org/10.1007/s00170-011-3671-1CrossRef

39.

Moslehi G, Khorasanian D (2014) A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion. Comput Oper Res 52:260–268. https://doi.org/10.1016/j.cor.2013.09.014MathSciNetCrossRefMATH

40.

Chakravorty A, Laha D (2017) A heuristically directed immune algorithm to minimize makespan and total flow time in permutation flow shops. Int J Adv Manuf Technol 93:3759–3776. https://doi.org/10.1007/s00170-017-0679-1CrossRef

41.

Abdel-Basset M, Manogaran G, El-Shahat D, Mirjalili S (2018) A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem. Futur Gener Comput Syst 85:129–145. https://doi.org/10.1016/j.future.2018.03.020CrossRef

42.

Liu Y-F, Liu S-Y (2013) A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Appl Soft Comput J 13:1459–1463. https://doi.org/10.1016/j.asoc.2011.10.024CrossRef

43.

Tasgetiren MF, Pan QK, Suganthan PN, Chen AHL (2010) A discrete artificial bee colony algorithm for the permutation flow shop scheduling problem with total flowtime criterion. 2010 IEEE World Congr Comput Intell WCCI 2010 - 2010 IEEE Congr Evol Comput CEC 2010. https://doi.org/10.1109/CEC.2010.5586300

44.

Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Tech Rep TR06, Erciyes Univ

45.

Tasgetiren MF, Pan Q-K, Suganthan PN, Oner A (2013) A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Appl Math Model 37:6758–6779. https://doi.org/10.1016/j.apm.2013.02.011MathSciNetCrossRefMATH

46.

Peng K, Pan Q, Zhang B (2018) An improved artificial bee colony algorithm for steelmaking–refining–continuous casting scheduling problem. Chin J Chem Eng 26:1727–1735. https://doi.org/10.1016/j.cjche.2018.06.008CrossRef

47.

McCormick ST, Pinedo ML, Shenker S, Wolf B (1989) Sequencing in an assembly line with blocking to minimize cycle time. Oper Res 37:925–935. https://doi.org/10.1287/opre.37.6.925CrossRefMATH

Titel: Artificial bee colony algorithm including some components of iterated greedy algorithm for permutation flow shop scheduling problems
verfasst von: Oğuzhan Ahmet Arık
Publikationsdatum: 27.07.2020
Verlag: Springer London
Erschienen in: Neural Computing and Applications / Ausgabe 8/2021
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI: https://doi.org/10.1007/s00521-020-05174-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 8/2021

A solution to statistical and multidisciplinary design optimization problems using hGWO-SA algorithm

Evaluating the bond strength of FRP-to-concrete composite joints using metaheuristic-optimized least-squares support vector regression

Temporal representation learning for time series classification

How frontal is a face? Quantitative estimation of face pose based on CNN and geometric projection

Simultaneous streamflow forecasting based on hybridized neuro-fuzzy method for a river system

A span-based model for aspect terms extraction and aspect sentiment classification