Top

Memetic Computing

Published in:

01-06-2014 | Regular research paper

Tailoring hyper-heuristics to specific instances of a scheduling problem using affinity and competence functions

Authors: Abdellah Salhi, José Antonio Vázquez Rodríguez

Published in: Memetic Computing | Issue 2/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Hyper-heuristics are high level heuristics which coordinate lower level ones to solve a given problem. Low level heuristics, however, are not all as competent/good as each other at solving the given problem and some do not work together as well as others. Hence the idea of measuring how good they are (competence) at solving the problem and how well they work together (their affinity). Models of the affinity and competence properties are suggested and evaluated using previous information on the performance of the simple low level heuristics. The resulting model values are used to improve the performance of the hyper-heuristic by tailoring it not only to the specific problem but the specific instance being solved. The test case is a hard combinatorial problem, namely the Hybrid Flow Shop scheduling problem. Numerical results on randomly generated as well as real-world instances are included.

previous article Editorial

next article Dynamic economic dispatch using Lbest-PSO with dynamically varying sub-swarms

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Cowling P, Kendall G, Soubeiga E (2000) A hyperheuristic approach to scheduling a sales summit. In: Burke EK, Erben W (ed) Proceedings of the third international conference on the practice and theory of automated timetabling III. Lecture notes in computer science, vol 2079. Springer, Berlin, pp 176–190

Soubeiga E (2003) Development and application of hyperheuristics to personnel scheduling. PhD thesis, School of Computer Science and Information Technology, The University of Nottingham

Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Hyper-heursitics RQU (2010) A survey of the state of the art. Technical report, School of Computer Science and Information Technology, University of Nottingham, UK

Burke EK, Hyde M, Kendall G, Ochoa G, Ozcani E, Woodward JR (2009) Exploring hyper-heursitic methodologies with genetic programming. In: Mumford C, Jain L (eds) Computational intelligence: collaboration, fusion and emergence. Springer, Berlin

Burke E, Soubeiga E (2003) Scheduling nurses using a tabu-search hyperheuristic. In: Proceedings of the 1st multidisciplinary international conference on scheduling: theory and applications (MISTA 2003)

Cowling P, Kendall G, Han L (2002) An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Proceedings of congress on evolutionary computation (CEC2002). IEEE, New York, pp 1185–1190

Burke E, Kendall G, Landa SD, O‘Brien R, Soubeiga E (2005) An ant algorithm hyperheuristic for the project presentation scheduling problem. In: Proceedings of the congress on evolutionary computation (CEC 2005). IEEE Press, New York, pp 2263–2270

Ayob M, Kendall G (2003) A monte carlo hyper-heuristic to optimise component placement sequencing for multi head placement machine. In: Proceedings of the international conference on intelligent technologies, InTech’03, pp 132–141

Petrovic S, Qu R (2002) Case-based reasoning as a heuristic selector in a hyper-heuristic for course timetabling problems. In: Proceedings of the 6th international conference on knowledge-based intelligent information engineering systems and applied technologies (KES’02), pp 336–340

10.

Burke EK, McCarthy BL, Petrovic S, Qu R (2002) Knowledge discovery in a hyper-heuristic for course timetabling using case-based reasoning. In: Proceedings of the 4th international conference on the practice and theory of automated timetabling (PATAT 2002). Lecture notes in computer science, vol 2740. Springer, Berlin, pp 276–286

11.

Petrovic S, Fayad C, Petrovic D (2005) Job shop scheduling with lot-sizing and batching in an uncertain real-world environment. In: Kendall G, Lei L, Pinedo M (eds) Proceedings of the 2nd multidisciplinary international conference on scheduling: theory and applications (MISTA 2005), New York, pp 363–379

12.

Hart E, Ross P (1998) A heuristic combination method for solving job-shop scheduling problems. In: Lecture notes in computer sciences (1498). Springer, Berlin, pp 845–854

13.

Fang H-L, Ross P, Corne D (1994) A promising hybrid GA/heuristic approach for open-shop scheduling problems. In: Cohn A (ed) 11th european conference on artificial intelligence (ECAI 94). Wiley, New York, pp 590–594

14.

Burke E, Dror M, Petrovic S, Qu R (2005) Hybrid graph heuristic within a hyper-heuristic approach to exam timetabling problems. In: Golden BL, Raghavan S, Wasil EA (eds) Proceedings of the 9th informs computing society conference. Springer, Berlin, pp 79–91

15.

Vázquez Rodríguez JA (2007) Meta-hyper-heuristics for hybrid flow shops. PhD thesis, Department of Mathematical Sciences, University of Essex, Colchester

16.

Michalewicz Z (1992) Genetic algorithms + data structures = evolution programs. Springer, BerlinCrossRefMATH

17.

Goldberg David E (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, MassachusettsMATH

18.

Gupta JND (1988) Two-stage hybrid flow shop scheduling problem. Oper Res Soc 39:359–364CrossRefMATH

19.

Hoogeveen JA, Lenstra JK, Veltman B (1996) Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Eur J Oper Res 89:172–175CrossRefMATH

20.

Jin ZH, Ohno K, Ito T, Elmaghraby SE (2002) Scheduling hybrid flowshops in printed circuit board assembly lines. Prod Oper Manag 11:216–230CrossRef

21.

Sherali HD, Sarin SC, Kodialam MS (1990) Models and algorithms for a two-stage production process. Prod Plan Control 1:27–39CrossRef

22.

Guinet AG (1991) Textile production systems: a succession of non-identical parallel processor shops. J Oper Res Soc 42:655–671

23.

Grabowski J, Pempera J (2000) Sequencing of jobs in some production system. Eur J Oper Res 125:535–550

24.

Aghezzaf EH, Van Landeghem H (2002) An integrated model for inventory and production planning in a two-stage hybrid production system. Int J Prod Res 40:4323–4339

25.

Allahverdi A, Al-Anzi FS (2006) Scheduling multi-stage parallel-processor services to minimize average response time. J Oper Res Soc 57:101–110

26.

Lu Chen, Li-Feng Xi, Jian-Guo Ca I, Nathalie Bostel, Pierre Dejax (2006) An integrated approach for modeling and solving the scheduling problem of container handling systems. J Zhejiang Univ SCIENCE A 7:234–239CrossRefMATH

27.

Lin HT, Liao CJ (2003) A case study in a two-stage hybrid flow shop with setup time and dedicated machines. Int J Prod Econ 86:133–143CrossRef

28.

Choong F, Phin-Amnuaisuk S, Alias MY (2011) Metaheuristic methods in hybrid flow shop scheduling problem. Exp Syst Appl 38(9):10787–10793CrossRef

29.

Pinedo Michael (2002) Scheduling theory, algorithms and systems. Prentice Hall, Englewood CliffsMATH

30.

Rodríguez José Antonio Vázquez, Salhi Abdellah (2007) A robust meta-hyper-heuristic approach to hybrid flow shop scheduling. In: Dahal K, Cowling P (eds) Evol Sched. Springer, Berlin, pp 125–142CrossRef

31.

Hollander M, Wolfe DA (1973) Nonparametric statistical methods. Wiley, New YorkMATH

32.

Riane Fouad, Artiba Abdelhakim, Elmaghraby Salah E (2002) Sequencing a hybrid two-stage flowshop with dedicated machines. Int J Prod Res 40:4353–4380CrossRefMATH

33.

García Rubén Ruíz, Maroto Concepción (2006) A genetic algorithm for hybrid flow shops with sequence dependent setup times and machine eligibility. Eur J Oper Res 169:781–800CrossRef

34.

Moscato P, Cotta C (2003) A gentle introduction to memetic algorithms, pp 105–144. In: Handbook of Metaheuristics. Kluwer Academic Publishers, Dordrecht

35.

Ong YS, Kean AJ (2004) Meta-Lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2):99–110CrossRef

36.

Salhi A, Töreyen Ö (2010) A game theory-based multi-agent system for expensive optimisation. In: Tenne Y, Goh C-K (eds) Computational intelligence in optimization—applications and implementations, Chap. 9. Springer, Berlin, pp 212–232

37.

Töreyen Ö (2008) A game theory-based multi-agent system for solving complex optimisation problems. Master’s thesis, Department of Mathematical Sciences, University of Essex, Colchester

Title: Tailoring hyper-heuristics to specific instances of a scheduling problem using affinity and competence functions
Authors: Abdellah Salhi
José Antonio Vázquez Rodríguez
Publication date: 01-06-2014
Publisher: Springer Berlin Heidelberg
Published in: Memetic Computing / Issue 2/2014
Print ISSN: 1865-9284
Electronic ISSN: 1865-9292
DOI: https://doi.org/10.1007/s12293-013-0121-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2014

The break scheduling problem: complexity results and practical algorithms

Dynamic economic dispatch using Lbest-PSO with dynamically varying sub-swarms

Empirical and analytical study of many-objective optimization problems: analysing distribution of nondominated solutions and population size for scalability of randomized heuristics

A memetic algorithm based on multiple learning procedures for global optimal design of composite structures

Editorial

Premium Partner