nach oben

Journal of Scheduling

Erschienen in:

01.08.2016

Late acceptance hill-climbing for high school timetabling

verfasst von: George H. G. Fonseca, Haroldo G. Santos, Eduardo G. Carrano

Erschienen in: Journal of Scheduling | Ausgabe 4/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The application of the Late Acceptance Hill-Climbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.

Vorheriger Artikel Configuration and the advantages of the shifting bottleneck procedure for optimizing the job shop total weighted tardiness scheduling problem

Nächster Artikel Scheduling evacuation operations

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

We denote by \(N_k(s)\) the subset of \(N_k(s)\) involving only moves of type k.

http://sydney.edu.au/engineering/it/~jeff/hseval.cgi.

Code, solutions and reports are available at http://www.goal.ufop.br/softwares/hstt.

Abuhamdah, A. (2010). Experimental result of late acceptance randomized descent algorithm for solving course timetabling problems. IJCSNS-International Journal of Computer Science and Network Security, 10(1), 192–200.

Burke, E. K., & Bykov, Y. (2008). A late acceptance strategy in hill-climbing for exam timetabling problems. In PATAT’08 proceedings of the 7th international conference on the practice and theory of automated timetabling.

Burke, E. K., & Bykov, Y. (2012). The late acceptance hill-climbing heuristic. Technical Report CSM-192, Department of Computing Science and Mathematics, University of Stirling.

de Haan, P., Landman, R., Post, G., & Ruizenaar, H. (2007). A case study for timetabling in a dutch secondary school. In Lecture notes in computer science: VI. Practice and theory of automated timetabling (Vol. 3867, pp. 267–279). Berlin: Springer.

Dorneles, Á. P., de Araújo, O. C., & Buriol, L. S. (2014). A fix-and-optimize heuristic for the high school timetabling problem. Computers & Operations Research, 52, 29–38.CrossRef

Fonseca, G., Santos, H., Toffolo, T., Brito, S., & Souza, M. (2012). A SA-ILS approach for the high school timetabling problem. In PATAT’12 proceedings of the 9th international conference on the practice and theory of automated timetabling.

Fonseca, G. H. G., Santos, H. G., Toffolo, T. A. M., Brito, S. S., & Souza, M. J. F. (2014). GOAL solver: A hybrid local search based solver for high school timetabling. Annals of Operations Research, 1–21. doi:10.1007/s10479-014-1685-4.

Garey, M. R., & Jonhson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA: Freeman.

IDSIA (2012). International Timetabling Competition 2002 (2012). Retrieved December, 2012 from http://www.idsia.ch/Files/ttcomp2002/.

Kheiri, A., Ozcan, E., & Parkes, A. J. (2012). Hysst: Hyper-heuristic search strategies and timetabling. In Proceedings of the ninth international conference on the practice and theory of automated timetabling (PATAT 2012) (pp. 497–499).

Kingston, J. (2014). KHE14 an algorithm for high school timetabling. In 10th international conference on the practice and theory of automated timetabling (pp. 26–29).

Kingston, J. H. (2005) A tiling algorithm for high school timetabling. In Lecture notes in computer science: V. Practice and theory of automated timetabling (Vol. 3616, pp. 208–225). Berlin: Springer.

Kingston, J. H. (2012). A software library for school timetabling (2012). Retrieved May, 2012, from http://sydney.edu.au/engineering/it/~jeff/khe/.

Kingston, J. H. (2012). A software library for school timetabling (2012). Retrieved December 2012, from http://sydney.edu.au/engineering/it/~jeff/khe/.

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671–680.CrossRef

Kostuch, P. (2005). The university course timetabling problem with a three-phase approach. In Proceedings of the 5th international conference on practice and theory of automated timetabling, PATAT’04 (pp. 109–125). Berlin: Springer. doi:10.1007/11593577_7.

Kristiansen, S., Srensen, M., Stidsen, T. (2014). Integer programming for the generalized high school timetabling problem. Journal of Scheduling, 1–16. doi:10.1007/s10951-014-0405-x.

McCollum, B. (2012). International timetabling competition 2007. Retrieved December, 2012 from http://www.cs.qub.ac.uk/itc2007/.

Moura, A. V., & Scaraficci, R. A. (2010). A grasp strategy for a more constrained school timetabling problem. International Journal of Operational Research, 7(2), 152–170.CrossRef

Muller, T. (2009). ITC2007 solver description: a hybrid approach. Annals OR 172(1), 429–446. http://dblp.uni-trier.de/db/journals/anor/anor172.html#Muller09.

Nurmi, K., & Kyngas, J. (2007). A framework for school timetabling problem. In Proceedings of the 3rd multidisciplinary international scheduling conference: theory and applications, Paris (pp. 386–393).

Özcan, E., Bykov, Y., Birben, M., & Burke, E. K. (2009). Examination timetabling using late acceptance hyper-heuristics. In Proceedings of the eleventh conference on congress on evolutionary computation, CEC’09 (pp. 997–1004). IEEE Press, Piscataway, NJ http://dl.acm.org/citation.cfm?id=1689599.1689731.

Pillay, N. (2013) A survey of school timetabling research. Annals of Operations Research, 1–33.

Post, G., Kingston, J., Ahmadi, S., Daskalaki, S., Gogos, C., Kyngas, J., et al. (2014). XHSTT: An XML archive for high school timetabling problems in different countries. Annals of Operations Research, 218(1), 295–301.CrossRef

Romrs, J., & Homberger, J. (2012). An evolutionary algorithm for high school timetabling. In PATAT’12 proceedings of the 9th international conference on the practice and theory of automated timetabling.

Santos, H. G., Uchoa, E., Ochi, L. S., & Maculan, N. (2012). Strong bounds with cut and column generation for class-teacher timetabling. Annals OR, 194(1), 399–412.CrossRef

Srensen, M., Kristiansen, S., & Stidsen, T. (2012). International timetabling competition 2011: An adaptive large neighborhood search algorithm (pp. 489–492).

Tuga, M., Berretta, R., & Mendes, A. (2007) A hybrid simulated annealing with kempe chain neighborhood for the university timetabling problem. In 6th IEEE/ACIS international conference on computer and information science, 2007. ICIS 2007, IEEE (pp. 400–405).

Valourix, C., & Housos, E. (2003). Constraint programming approach for school timetabling. In Computers & Operations Research (pp. 1555–1572).

Verstichel, J., & Vanden Berghe, G. (2009). A late acceptance algorithm for the lock scheduling problem. In S. Voss, J. Pahl, & S. Schwarze (Eds.), Logistik management (pp. 457–478). Dordrecht: Springer.CrossRef

Wright, M. (1996). School timetabling using heuristic search. Journal of Operational Research Society, 47, 347–357.CrossRef

Titel: Late acceptance hill-climbing for high school timetabling
verfasst von: George H. G. Fonseca
Haroldo G. Santos
Eduardo G. Carrano
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2016
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0458-5

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"

Weitere Artikel der Ausgabe 4/2016

A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing

A Step Counting Hill Climbing Algorithm applied to University Examination Timetabling

Configuration and the advantages of the shifting bottleneck procedure for optimizing the job shop total weighted tardiness scheduling problem

Temporal linear relaxation in IBM ILOG CP Optimizer

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations