Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Swarm Intelligence and Evolutionary Computation: Overview and Analysis Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Discrete Cuckoo Search Applied to Job Shop Scheduling Problem

verfasst von : Aziz Ouaarab, Belaïd Ahiod, Xin-She Yang

Erschienen in: Recent Advances in Swarm Intelligence and Evolutionary Computation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Discrete Cuckoo Search (DCS) algorithm is applied to solve combinatorial optimization problems. In this chapter we discuss how DCS solves the Job Shop Scheduling Problem (JSSP), one of the most difficult NP-hard combinatorial optimization problems. DCS is recently developed by Ouaarab et al. in 2013, based on Cuckoo Search (CS) which was proposed by Yang and Deb in 2009. DCS seeks solutions, in the discrete search space, via Lévy flights and a switching parameter p a of the worst solution in the population. Its search uses a subtle balance between local and global random walks. This first version of DCS for JSSP is designed without using an advanced local search method or hybrid with other metaheuristics. Our experimental results show that DCS can find the optimum solutions for a number of JSSP instances.

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

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
Vorheriges Kapitel Bat Algorithm Application for the Single Row Facility Layout Problem
Nächstes Kapitel Cuckoo Search and Bat Algorithm Applied to Training Feed-Forward Neural Networks
Literatur
1.
Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA J. comput. 3(2), 149–156 (1991)CrossRefMATH
2.
3.
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. (CSUR) 35(3), 268–308 (2003)CrossRef
4.
Gandomi, A.H., Yang, X.S., Talatahari, S., Alavi, A.H.: Metaheuristic applications in structures and infrastructures. Newnes (2013)
5.
Yang, X.S.: Nature-inspired metaheuristic algorithms. Luniver Press, Bristol (2010)
6.
Ouaarab, A., Ahiod, B., Yang, X.S.: Improved and discrete cuckoo search for solving the travelling salesman problem. In: Cuckoo Search and Firefly Algorithm, pp. 63–84. Springer, Berlin (2014)
7.
Davis, L., et al.: Handbook of genetic algorithms, vol. 115. Van Nostrand Reinhold, New York (1991)
8.
Sivanandam, S., Deepa, S.: Genetic Algorithm Optimization Problems. Springer, Berlin (2008)
9.
Glover, F., Laguna, M.: Tabu search. Springer, Berlin (1999)
10.
Van Laarhoven, P.J., Aarts, E.H.: Simulated annealing. Springer, Berlin (1987)
11.
12.
Kennedy, J.: Particle swarm optimization. In: Encyclopedia of Machine Learning, pp. 760–766. Springer, Berlin (2010)
13.
Karaboga, D., Basturk, B.: On the performance of artificial bee colony (abc) algorithm. Appl. Soft Comput. 8(1), 687–697 (2008)CrossRef
14.
Mucherino, A., Seref, O.: Monkey search: a novel metaheuristic search for global optimization. In: Data Mining, Systems Analysis and Optimization in Biomedicine, vol. 953, pp. 162–173. AIP Publishing, New York (2007)
15.
Geem, Z.W., Kim, J.H., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simulation 76(2), 60–68 (2001)CrossRef
16.
Yang, X.S.: Firefly algorithms for multimodal optimization. In: Stochastic algorithms: foundations and applications, pp. 169–178. Springer, Berlin (2009)
17.
Shah-Hosseini, H.: The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. Int. J. Bio-Inspired Comput. 1(1), 71–79 (2009)CrossRef
18.
Yang, X.S.: A new metaheuristic bat-inspired algorithm. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pp. 65–74. Springer, Berlin (2010)
19.
Yang, X.S., Deb, S.: Cuckoo search via lévy flights. In: Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, pp. 210–214. IEEE, New York (2009)
20.
Yang, X.S.: Nature-Inspired Optimizaton Algorithms. Elsevier (2014)
21.
Yang, X.S., Karamanoglu, M., He, X.: Flower pollination algorithm: a novel approach for multiobjective optimization. Eng. Optim. 46, 1222–1237 (2014)CrossRefMathSciNet
22.
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. Evolut. Comput. IEEE Trans. 1(1), 67–82 (1997)CrossRef
23.
Dell’Amico, M., Trubian, M.: Applying tabu search to the job-shop scheduling problem. Ann. Oper. Res. 41(3), 231–252 (1993)CrossRefMATH
24.
Taillard, E.D.: Parallel taboo search techniques for the job shop scheduling problem. ORSA J. Comput. 6(2), 108–117 (1994)CrossRefMATH
25.
Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job shop problem. Manage. Sci. 42(6), 797–813 (1996)CrossRefMATH
26.
27.
Van Laarhoven, P.J., Aarts, E.H., Lenstra, J.K.: Job shop scheduling by simulated annealing. Oper. Res. 40(1), 113–125 (1992)CrossRefMATHMathSciNet
28.
Davis, L.: Job shop scheduling with genetic algorithms. In: Proceedings of an International Conference on Genetic Algorithms and Their Applications, vol. 140 (1985)
29.
Della Croce, F., Tadei, R., Volta, G.: A genetic algorithm for the job shop problem. Comput. Oper. Res. 22(1), 15–24 (1995)
30.
Gonçalves, J.F., de Magalhães Mendes, J.J., Resende, M.G.: A hybrid genetic algorithm for the job shop scheduling problem. Eur. J. Oper. Res. 167(1), 77–95 (2005)
31.
Lin, T.L., Horng, S.J., Kao, T.W., Chen, Y.H., Run, R.S., Chen, R.J., Lai, J.L., Kuo, I., et al.: An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Syst. Appl. 37(3), 2629–2636 (2010)CrossRef
32.
Huang, K.L., Liao, C.J.: Ant colony optimization combined with taboo search for the job shop scheduling problem. Comput. Oper. Res. 35(4), 1030–1046 (2008)CrossRefMATHMathSciNet
33.
Zhang, C.Y., Li, P., Rao, Y., Guan, Z.: A very fast ts/sa algorithm for the job shop scheduling problem. Comput. Oper. Res. 35(1), 282–294 (2008)CrossRefMATHMathSciNet
34.
Aiex, R.M., Binato, S., Resende, M.G.: Parallel grasp with path-relinking for job shop scheduling. Parallel Comput. 29(4), 393–430 (2003)CrossRefMathSciNet
35.
Binato, S., Hery, W., Loewenstern, D., Resende, M.: A grasp for job shop scheduling. In: Essays and Surveys in Metaheuristics, pp. 59–79. Springer, Berlin (2002)
36.
Chong, C.S., Low, M.Y.H., Sivakumar, A.I., Gay, K.L.: A bee colony optimization algorithm to job shop scheduling. In: Simulation Conference, 2006. WSC 06. Proceedings of the Winter, pp. 1954–1961. IEEE, New York (2006)
37.
Sha, D., Hsu, C.Y.: A hybrid particle swarm optimization for job shop scheduling problem. Comput. Ind. Eng. 51(4), 791–808 (2006)CrossRef
38.
Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. pp. 1069–1072 (1990)
39.
Pinedo, M.L.: Scheduling: theory, algorithms, and systems. Springer, Berlin (2012)
40.
T’kindt, V., Scott, H., Billaut, J.C.: Multicriteria scheduling: theory, models and algorithms. Springer, Berlin (2006)
41.
Ponsich, A.: Coello Coello, C.A.: A hybrid differential evolution—tabu search algorithm for the solution of job-shop scheduling problems. Appl. Soft Comput. 13(1), 462–474 (2013)CrossRef
42.
Błażewicz, J., Domschke, W., Pesch, E.: The job shop scheduling problem: Conventional and new solution techniques. Eur. J. Oper. Res. 93(1), 1–33 (1996)CrossRefMATH
43.
Jain, A.S., Meeran, S.: Deterministic job-shop scheduling: Past, present and future. Eur. J. Oper. Res. 113(2), 390–434 (1999)CrossRefMATH
44.
45.
Roy, B., Sussmann, B.: Les problemes d’ordonnancement avec contraintes disjonctives. Note ds 9 (1964)
46.
Esquirol, P., Lopez, P., professeur de robotique) Lopez, P.: L’ordonnancement. Économica (1999)
47.
Herrmann, J.W.: Handbook of production scheduling, vol. 89. Springer, Berlin (2006)
48.
Payne, R.B.: The cuckoos, vol. 15. Oxford University Press, Oxford (2005)
49.
Shlesinger, M.F., Zaslavsky, G.M., Frisch, U.: Lévy flights and related topics in physics. In: Levy flights and related topics in Physics, vol. 450 (1995)
50.
Ouaarab, A., Ahiod, B., Yang, X.S.: Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput. Appl. pp. 1–11 (2013)
51.
Ouaarab, A., Ahiod, B., Yang, X.S.: Random-key cuckoo search for the travelling salesman problem. Soft Comput. pp. 1–8 (2014)
Metadaten
Titel
Discrete Cuckoo Search Applied to Job Shop Scheduling Problem
verfasst von
Aziz Ouaarab
Belaïd Ahiod
Xin-She Yang
Copyright-Jahr
2015
Buch
Recent Advances in Swarm Intelligence and Evolutionary Computation

Print ISBN: 978-3-319-13825-1

Electronic ISBN: 978-3-319-13826-8

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-13826-8_7