nach oben

Natural Computing

Erschienen in:

01.06.2014

Robust swarm optimisation for fuzzy open shop scheduling

verfasst von: Juan José Palacios, Inés González-Rodríguez, Camino R. Vela, Jorge Puente

Erschienen in: Natural Computing | Ausgabe 2/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we consider a variant of the open shop problem where task durations are allowed to be uncertain and where uncertainty is modelled using fuzzy numbers. Solutions to this problem are fuzzy schedules, which we argue should be seen as predictive schedules, thus establishing links with the concept of robustness and a measure thereof. We propose a particle swarm optimization (PSO) approach to minimise the schedule’s expected makespan, using priorities to represent particle position, as well as a decoding algorithm to generate schedules in a subset of possibly active ones. Our proposal is evaluated on a varied set of several benchmark problems. The experimental study includes a parametric analysis, results of the PSO compared with the state-of-the-art, and an empirical study of the robustness of taking into account uncertainty along the scheduling process.

Vorheriger Artikel Virtual player design using self-learning via competitive coevolutionary algorithms

Nächster Artikel On balance and dynamism in procedural content generation with self-adaptive evolutionary algorithms

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

Nur mit Berechtigung zugänglich

Ahmadizar F, Farahani MH (2012) A novel hybrid genetic algorithm for the open shop scheduling problem. Int J Adv Manuf Technol 62:775–787CrossRef

Bidot J, Vidal T, Laboire P (2009) A theoretic and practical framework for scheduling in stochastic environment. J Sched 12:315–344CrossRefMATHMathSciNet

Blum C (2005) Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput Oper Res 32(6):1565–1591CrossRef

Brucker P, Hunrink J, Jurisch B, Wöstmann B (1997) A branch & bound algorithm for the open-shop problem. Discrete App Math 76:43–59CrossRefMATHMathSciNet

Dubois D, Fargier H, Fortemps P (2008) Scheduling under flexible constraints and uncertain data: the fuzzy approach. In: Production scheduling, chap. 11, Wiley, Weinheim, p 301–332

Dubois D, Fargier H, Fortemps P (2003) Fuzzy scheduling: modelling flexible constraints vs. coping with incomplete knowledge. Eur J Oper Res 147:231–252CrossRefMATHMathSciNet

Dubois D, Prade H (1986) Possibility theory: an approach to computerized processing of uncertainty. Plenum Press, New York

Fortemps P (1997) Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE Trans Fuzzy Syst 7:557–569CrossRef

Giffler B, Thompson GL (1960) Algorithms for solving production scheduling problems. Oper Res 8:487–503CrossRefMATHMathSciNet

10.

Gonçalves J, Mendes J, de M RM (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167:77–95CrossRefMATH

11.

González-Rodríguez I, Palacios JJ, Vela CR, Puente J (2010) Heuristic local search for fuzzy open shop scheduling. In: Proceedings IEEE International conference on fuzzy systems, FUZZ-IEEE2010. pp 1858–1865. IEEE

12.

González-Rodríguez I, Puente J, Vela CR, Varela R (2008) Semantics of schedules for the fuzzy job shop problem. IEEE Trans Syst Man Cybern Part A 38(3):655–666CrossRef

13.

González-Rodríguez I, Vela CR, Puente J (2007) A memetic approach to fuzzy job shop based on expectation model. In: Proceedings of IEEE international conference on fuzzy systems, FUZZ-IEEE2007. pp 692–697. IEEE, London

14.

Graham R, Lawler E, Lenstra J, Rinnooy Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 4:287–326CrossRefMathSciNet

15.

Guéret C, Prins C (1998) Classical and new heuristics for the open-shop problem: a computational evaluation. Eur J Oper Res 107:306–314CrossRefMATH

16.

Herroelen W, Leus R (2005) Project scheduling under uncertainty: Survey and research potentials. Eur J Oper Res 165:289–306CrossRefMATH

17.

Hu Y, Yin M, Li X (2011) A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm. Int J Adv Manuf Technol 56:1125–1138CrossRef

18.

Huang YM, Lin JC (2011) A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems. Expert Syst Appl 38(5):5438–5447CrossRef

19.

Kalaï R, Lamboray C, Vanderpooten D (2012) Lexicographic α-robustness: an alternative to min-max criteria. Eur J Oper Res 220:722–728CrossRefMATH

20.

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: IEEE international conference on neural networks. pp 1942–1948. IEEE Press, New Jersey

21.

Konno T, Ishii H (2000) An open shop scheduling problem with fuzzy allowable time and fuzzy resource constraint. Fuzzy Sets Syst 109:141–147CrossRefMathSciNet

22.

Lei D (2010) Solving fuzzy job shop scheduling problems using random key genetic algorithm. International Int J Adv Manuf Technol 49:253–262CrossRef

23.

Liaw CF (1999) A tabu search algorithm for the open shop scheduling problem. Comput Oper Res 26:109–126CrossRefMATHMathSciNet

24.

Liu B, Liu YK (2002) Expected value of fuzzy variable and fuzzy expected value models. IEEE Trans Fuzzy Syst 10:445–450CrossRef

25.

Noori-Darvish S, Mahdavi I, Mahdavi-Amiri N (2012) A bi-objective possibilistic programming model for open shop scheduling problems with sequence-dependent setup times, fuzzy processing times, and fuzzy due-dates. Appl Soft Comput 12:1399–1416CrossRef

26.

Palacios JJ, Puente J, Vela CR, González-Rodríguez I (2009) A genetic algorithm for the open shop problem with uncertain durations. In: Proceedings of IWINAC 2009, Part I. Lecture notes in computer science, vol 5601, pp 255–264. Springer

27.

Pinedo ML (2008) Scheduling: theory, algorithms, and systems, 3rd edn. Springer, Secaucus

28.

Puente J, Vela CR, González-Rodríguez I (2010) Fast local search for fuzzy job shop scheduling. In: Proceedings of 19th European conference on artificial intelligence, ECAI 2010. pp 739–744. IOS Press

29.

Sha DY, Cheng-Yu H (2006) A modified parameterized active schedule generation algorithm for the job shop scheduling problem. In: Proceedings of the 36th international conference on computers and industrial engineering, ICCIE2006. pp 702–712

30.

Sha DY, Cheng-Yu H (2008) A new particle swarm optimization for the open shop scheduling problem. Comput Oper Res 35:3243–3261CrossRefMATH

31.

Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285CrossRefMATH

32.

Tavakkoli-Moghaddam R, Safei N, Kah M (2008) Accessing feasible space in a generalized job shop scheduling problem with the fuzzy processing times: a fuzzy-neural approach. J Oper Res Soc 59:431–442CrossRefMATH

33.

Zheng Y, Li Y, Lei D (2011) Swarm-based neighbourhood search for fuzzy job shop scheduling. Int J Innovative Comput Appl 3(3):144–151CrossRef

Titel: Robust swarm optimisation for fuzzy open shop scheduling
verfasst von: Juan José Palacios
Inés González-Rodríguez
Camino R. Vela
Jorge Puente
Publikationsdatum: 01.06.2014
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2014
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-014-9413-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+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2014

Non conventional computing and constraint optimization

A genetic algorithm for job-shop scheduling with operators enhanced by weak Lamarckian evolution and search space narrowing

Virtual player design using self-learning via competitive coevolutionary algorithms

Symbol representations and signal dynamics in evolving droplet computers

Generation of classification trees from variable weighted features

A self-adaptive communication strategy for flocking in stationary and non-stationary environments

Premium Partner