nach oben

Soft Computing

Erschienen in:

12.02.2016 | Methodologies and Application

A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems

verfasst von: Hui Wang, Wenjun Wang, Hui Sun, Zhihua Cui, Shahryar Rahnamayan, Sanyou Zeng

Erschienen in: Soft Computing | Ausgabe 15/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Cuckoo search (CS) is a recently developed meta-heuristic algorithm, which has shown good performance on many continuous optimization problems. In this paper, we present a new CS algorithm, called NCS, for solving flow shop scheduling problems (FSSP). The NCS hybridizes four strategies: (1) The FSSP is a typical NP-hard problem with discrete characteristics. To deal with the discrete variables, the smallest position value (SPV) rule is employed to convert continuous solutions into discrete job permutations; (2) To generate high quality initial solutions, a new method based on the Nawaz-Enscore-Ham (NEH) heuristic is used for population initialization; (3) A modified generalized opposition-based learning (GOBL) is utilized to accelerate the convergence speed; and (4) To enhance the exploitation, a local search strategy is proposed. Experimental study is conducted on a set of Taillard’s benchmark instances. Results show that NCS obtains better performance than the standard CS and some other meta-heuristic algorithms.

Vorheriger Artikel An improved NSGA-III algorithm based on objective space decomposition for many-objective optimization

Nächster Artikel Endocrine-based coevolutionary multi-swarm for multi-objective workflow scheduling in a cloud system

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

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

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

Abd Elazim SM, Ali ES (2016) Optimal power system stabilizers design via cuckoo search algorithm. Int J Electr Power Energy Syst 75:99–107CrossRef

Andreas C (2004) Nearchou. The effect of various operators on the genetic search for large scheduling problems. International Journal of Production Economics 88(2):191–203CrossRef

Bansal SP (1977) Minimizing the sum of completion times of n jobs over m machines in a flowshopa branch and bound approach. AIIE Trans. 9(3):306–311CrossRef

Basu M, Chowdhury A (2013) Cuckoo search algorithm for economic dispatch. Energy 60:99–108CrossRef

Bhandari AK, Singh VK, Kumar A, Singh GK (2014) Cuckoo search algorithm and wind driven optimization based study of satellite image segmentation for multilevel thresholding using kapurs entropy. Expert Syst Appl 41(7):3538–3560CrossRef

Chen J, Lin Q, Hu Q (2010) Application of novel clonal algorithm in multiobjective optimization. International Journal of Information Technology & Decision Making 9(02):239–266

Chen B, Shu H, Coatrieux G, Chen G, Sun X, Coatrieux JL (2015) Color image analysis by quaternion-type moments. J Math Imaging Vis 51(1):124–144MathSciNetCrossRefMATH

Croce FD, Ghirardi M, Tadei R (2002) An improved branch-and-bound algorithm for the two machine total completion time flow shop problem. Eur J Oper Res 139(2):293–301MathSciNetCrossRefMATH

Cui L, Li G, Lin Q, Chen J, Lu N (2016) Adaptive differential evolution algorithm with novel mutation strategies in multiple sub-populations. Comput Oper Res 67:155–173MathSciNetCrossRefMATH

Dhivya M, Sundarambal M (2011) Cuckoo search for data gathering in wireless sensor networks. Int J Mob Commun 9(6):642–656CrossRef

Djelloul H, Layeb A, Chikhi S (2015) Quantum inspired cuckoo search algorithm for graph colouring problem. Int J Bio-Inspired Comput 7(3):183–194CrossRef

Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B Cybern 26(1):29–41CrossRef

Fu Z, Sun X, Liu Q, Zhou L, Shu J (2015) Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans Commun E98–B(1):190–200

García S, Fernández A, Luengo J, Herrera F (2010) Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power. Inf Sci 180(10):2044–2064CrossRef

Goel S, Sharma A, Bedi P (2013) Novel approaches for classification based on cuckoo search strategy. Int J Hybrid Intell Syst 10(3):107–116CrossRef

Gu B, Sheng VS, Tay KY, Romano W, Li S (2015a) Incremental support vector learning for ordinal regression. IEEE Trans Neural Netw Learn Syst 26(7):1403–1416MathSciNetCrossRef

Gu B, Sheng VS, Wang Z, Ho D, Osman S, Li S (2015b) Incremental learning for \(\nu \)-support vector regression. Neural Netw 67:140–150CrossRef

Huang J, Gao L, Li X (2015) An effective teaching-learning-based cuckoo search algorithm for parameter optimization problems in structure designing and machining processes. Appl Soft Comput 36:349–356CrossRef

Ignall E, Schrage L (1965) Application of the branch and bound technique to some flow-shop scheduling problems. Oper Res 13(3):400–412MathSciNetCrossRef

Johnson SM (1954) Optimal two and three stage production schedules with setup times included. Naval Res Logist Q 1(1):61–68CrossRefMATH

Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical report, Technical report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department

Karthikeyan S, Asokan P, Nickolas S, Page T (2015) A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems. Int J Bio-Inspired Comput 7(6):386–401CrossRef

Kennedy J, Eberhart R (1995) Particle swarm optimization. IEEE Int Conf Neural Netw 4:1942–1948

Li J, Li X, Yang B, Sun X (2015) Segmentation-based image copy-move forgery detection scheme. IEEE Trans Inf Forensics Secur 10(3):507–518CrossRef

Lian Z, Gu X, Jiao B (2008) A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos Solitons Fractals 35(5):851–861

Liang J, Pan Q-K, Tiejun C, Wang L (2011) Solving the blocking flow shop scheduling problem by a dynamic multi-swarm particle swarm optimizer. Int J Adv Manuf Technol 55(5–8):755–762CrossRef

Liang Z, Song R, Lin Q, Du Z, Chen J, Ming Z, Yu J (2015) A double-module immune algorithm for multi-objective optimization problems. App Soft Comput 35:161–174

Liang Z, Sun J, Lin Q, Du Z, Chen J, Ming Z (2016) A novel multiple rule sets data classification algorithm based on ant colony algorithm. Appl Soft Comput 38:1000–1011

Lin Q, Zhu Q, Huang P, Chen J, Ming Z, Yu J (2015a) A novel hybrid multi-objective immune algorithm with adaptive differential evolution. Comput Oper Res 62:95–111MathSciNetCrossRefMATH

Lin Q, Gao L, Li X, Zhang C (2015b) A hybrid backtracking search algorithm for permutation flow-shop scheduling problem. Comput Ind Eng 85:437–446CrossRef

Lin Q, Chen J (2013) A novel micro-population immune multiobjective optimization algorithm. Comput Oper Res 40(6):1590–1601MathSciNetCrossRefMATH

Liu B, Wang L, Jin Y-H (2007) An effective pso-based memetic algorithm for flow shop scheduling. IEEE Trans Sys Man Cybern Part B Cybern 37(1):18–27CrossRef

Li X, Yin M (2012) A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem. Scientia Iranica 19(6):1921–1935CrossRef

Li X, Yin M (2013a) A hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problem. Int J Prod Res 51(16):4732–4754CrossRef

Li X, Yin M (2013b) An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure. Adv Eng Softw 55:10–31CrossRef

Ma T, Zhou J, Tang M, Tian Y, Al-dhelaan A, Al-rodhann M, Lee S (2015) Social network and tag sources based augmenting collaborative recommender system. IEICE Trans Inf Syst E98–D(4):902–910CrossRef

Marichelvam MK (2012) An improved hybrid cuckoo search (ihcs) metaheuristics algorithm for permutation flow shop scheduling problems. Int J Bio-Inspired Comput 4(4):200–205CrossRef

Masoud B, Hooshang J-R (2015) Robust data-driven soft sensor based on iteratively weighted least squares support vector regression optimized by the cuckoo optimization algorithm. J Nat Gas Sci Eng 22:35–41CrossRef

Michael RG, David SJ (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman & Co., San FranciscoMATH

Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097–1100MathSciNetCrossRefMATH

Naik MK, Panda R (2016) A novel adaptive cuckoo search algorithm for intrinsic discriminant analysis based face recognition. Appl Soft Comput 38:661–675CrossRef

Navimipour NJ (2015) Milani FS (2015) Task scheduling in the cloud computing based on the cuckoo search algorithm. Int J Model Optim 5(1):44CrossRef

Nawaz M (1983) E Emory Enscore, and Inyong Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1):91–95CrossRef

Qian B, Wang L, Rong H, Wang W-L, Huang D-X, Wang X (2008) A hybrid differential evolution method for permutation flow-shop scheduling. Int J Adv Manuf Technol 38(7–8):757–777CrossRef

Rahman HF (2015) Ruhul Sarker, and Daryl Essam. A real-time order acceptance and scheduling approach for permutation flow shop problems. Eur J Oper Res 247(2):488–503CrossRef

Rahnamayan S, Tizhoosh HR, Salama M (2008) Opposition-based differential evolution. Evol Comput IEEE Trans 12(1):64–79CrossRef

Ren Y, Shen J, Wang J, Han J, Lee S (2015) Mutual verifiable provable data auditing in public cloud storage. J Internet Technol 16(2):317–323

Sajwan M, Acharya K, Bhargava S (2014) Swarm intelligence based optimization for web usage mining in recommender system. International Journal of Computer Applications Technology and Research 3(2):119–124

Shen J, Tan H, Wang J, Wang J, Lee S (2015) A novel routing protocol providing good transmission reliability in underwater sensor networks. J Internet Technol 16(1):171–178

Taillard E (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47(1):65–74MathSciNetCrossRefMATH

Tasgetiren MF, Liang Y-C, Sevkli M, Gencyilmaz G (2006) Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem. Int J Prod Res 44(22):4737–4754CrossRefMATH

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(3):1930–1947CrossRefMATH

Tizhoosh HR (2005) Opposition-based learning: A new scheme for machine intelligence. In: International conference on computational intelligence for modelling control and automation IEEE, pp 695–701

Wang H, Wu Z, Rahnamayan S (2011a) Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems. Soft Comput 15(11):2127–2140

Wang H, Wu Z, Rahnamayan S, Liu Y, Ventresca M (2011b) Enhancing particle swarm optimization using generalized opposition-based learning. Inf Sci 181(20):4699–4714

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 12(2):652–662CrossRef

Wen X, Shao L, Xue Y, Fang W (2015) A rapid learning algorithm for vehicle classification. Inf Sci 295:395–406CrossRef

Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82CrossRef

Xia Z, Wang X, Sun X, Liu Q, Xiong N (2014a) Steganalysis of LSB matching using differences between nonadjacent pixels. Multimed Tools Appl. doi:10.1007/s11042-014-2381-8

Xia Z, Wang X, Sun X, Wang B (2014b) Steganalysis of least significant bit matching using multi-order differences. Secur Commun Netw 7(8):1283–1291CrossRef

Xia Z, Wang X, Sun X, Wang Q (2015) A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans Parallel Distrib Syst. doi:10.1109/TPDS.2015.2401003

Xie S, Wang Y (2014) Construction of tree network with limited delivery latency in homogeneous wireless sensor networks. Wireless personal communications 78(1):231–246

Yang X-S, Deb S (2009) Cuckoo search via Lévy flights. In: World congress on nature and biologically inspired computing IEEE, pp 210–214

Yang X-S (2010) Engineering optimization: an introduction with metaheuristic applications. Wiley, New YorkCrossRef

Yang X-S, Deb S (2010) Engineering optimisation by cuckoo search. Int J Math Model Numer Optim 1(4):330–343MATH

Zhang C, Ning J, Ouyang D (2010a) A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Comput Ind Eng 58(1):1–11CrossRef

Zhang J, Zhang C, Liang S (2010b) The circular discrete particle swarm optimization algorithm for flow shop scheduling problem. Expert Syst Appl 37(8):5827–5834CrossRef

Zhang C, Sun J (2009) An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Expert Syst Appl 36(3):5162–5167CrossRef

Zheng Y, Jeon B, Xu D, Wu QM, Zhang H (2015) Image segmentation by generalized hierarchical fuzzy C-means algorithm. J Intel Fuzzy Syst 28(2):961–973

Zhao F, Zhang J, Wang J, Zhang C (2015) A shuffled complex evolution algorithm with opposition-based learning for a permutation flow shop scheduling problem. Int J Comput Integr Manuf 28(11):1220–1235

Titel: A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems
verfasst von: Hui Wang
Wenjun Wang
Hui Sun
Zhihua Cui
Shahryar Rahnamayan
Sanyou Zeng
Publikationsdatum: 12.02.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 15/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2062-9

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+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 15/2017

Tense operators on non-commutative residuated lattices

Improving sampling-based image matting with cooperative coevolution differential evolution algorithm

A novel collaborative optimization algorithm in solving complex optimization problems

Special issue on intelligent analytics and management of mobile data and social media

Link prediction in complex network based on modularity

Lyapunov stability-based control and identification of nonlinear dynamical systems using adaptive dynamic programming