nach oben

Journal of Scheduling

Erschienen in:

18.08.2018

Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem

verfasst von: Niels-Christian Fink Bagger, Guy Desaulniers, Jacques Desrosiers

Erschienen in: Journal of Scheduling | Ausgabe 2/2019

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 propose an integer-programming relaxation for obtaining lower bounds for the curriculum-based course timetabling problem in which weekly assignments for courses to rooms and periods are considered. The model is a pattern formulation where a pattern is an assignment of a course into a set of periods on one day. Different preprocessing techniques are implemented to reduce the number of variables, and valid inequalities are derived and added to the model. The proposed model is tested on 21 real-world data instances. On 17 of these instances, the best known solutions have been proven optimal, and out of the remaining four, our model improves the lower bounds for three of them.

Vorheriger Artikel Scheduling recurring radiotherapy appointments in an ion beam facility

Nächster Artikel A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem

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

Achterberg, T. (2009). Scip: Solving constraint integer programs. Mathematical Programming Computation 1(1):1–41. http://mpc.zib.de/index.php/MPC/article/view/4

Asín Achá, R., & Nieuwenhuis, R. (2012). Curriculum-based course timetabling with sat and maxsat. Annals of Operations Research, 218, 1–21.

Avella, P., & Vasil’Ev, I. (2005). A computational study of a cutting plane algorithm for university course timetabling. Journal of Scheduling, 8, 497–514.CrossRef

Bettinelli, A., Cacchiani, V., Roberti, R., & Toth, P. (2015). An overview of curriculum-based course timetabling. TOP, 23, 1–37.CrossRef

Bonutti, A., De Cesco, F., Di Gaspero, L., & Schaerf, A. (2012). Benchmarking curriculum-based course timetabling: Formulations, data formats, instances, validation, visualization, and results. Annals of Operations Research, 194(1), 59–70.CrossRef

Bonutti, A., Gaspero, L.D., & Schaerf, A. (2016). Curriculum-based course timetabling. http://tabu.diegm.uniud.it/ctt/index.php. Retrieved December 30 2016.

Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9), 575–577. https://doi.org/10.1145/362342.362367.CrossRef

Burke, E. K., Mareček, J., Parkes, A.J., & Rudová, H. (2008). Penalising patterns in timetables: Novel integer programming formulations. In: Kalcsics J, Nickel S (eds) Operations Research Proceedings 2007, Operations Research Proceedings,( Vol. 2007, pp. 409–414). Springer: Berlin Heidelberg. https://doi.org/10.1007/978-3-540-77903-2_63

Burke, E. K., Mareček, J., Parkes, A. J., & Rudová, H. (2010a). Decomposition, reformulation, and diving in university course timetabling. Computers & Operations Research, 37(3), 582–597.CrossRef

Burke, E. K., Mareček, J., Parkes, A. J., & Rudová, H. (2010b). A supernodal formulation of vertex colouring with application in course timetabling. Annals of Operations Research, 179(1), 105–130.CrossRef

Burke, E. K., Mareček, J., Parkes, A. J., & Rudová, H. (2012). A branch-and-cut procedure for the udine course timetabling problem. Annals of Operations Research, 194(1), 71–87.CrossRef

Cacchiani, V., Caprara, A., Roberti, R., & Toth, P. (2013). A new lower bound for curriculum-based course timetabling. Computers & Operations Research, 40(10), 2466–2477.CrossRef

Di Gaspero L, McCollum B, Schaerf A (2007) The second international timetabling competition (itc-2007): Curriculum-based course timetabling (track 3). Tech. rep., School of Electronics, Electrical Engineering and Computer Science, Queenes University SARC Building, Belfast, United Kingdom.

Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2), 248–264. https://doi.org/10.1145/321694.321699.CrossRef

Gurobi Optimization, Inc.(2016). Gurobi optimizer reference manual. http://www.gurobi.com

Hao, J. K., & Benlic, U. (2011). Lower bounds for the ITC-2007 curriculum-based course timetabling problem. European Journal of Operational Research, 212(3), 464–472.CrossRef

Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(2), 135–139.CrossRef

Lach, G., & Lübbecke, M. (2008). Optimal university course timetables and the partial transversal polytope. In C. McGeoch (Ed.), Experimental algorithms, lecture notes in computer science (Vol. 5038, pp. 235–248). Berlin/Heidelberg: Springer.

Lach, G., & Lübbecke, M. (2012). Curriculum based course timetabling: New solutions to udine benchmark instances. Annals of Operations Research, 194, 255–272.CrossRef

McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A. J., et al. (2010). Setting the research agenda in automated timetabling: The second international timetabling competition. Informs Journal on Computing, 22(1), 120–130.CrossRef

Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York, NY: Wiley-Interscience.CrossRef

Van Roy, T. J., & Wolsey, L. A. (1987). Solving mixed integer programming problems using automatic reformulation. Operations Research, 35(1), 45–57.CrossRef

Titel: Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem
verfasst von: Niels-Christian Fink Bagger
Guy Desaulniers
Jacques Desrosiers
Publikationsdatum: 18.08.2018
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 2/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-018-0582-0

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 2/2019

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem

Online pulse interleaving task scheduling for multifunction radar

Scheduling recurring radiotherapy appointments in an ion beam facility

A note on minimizing total weighted completion time with an unexpected machine unavailable interval

Correction to: Online pulse interleaving task scheduling for multifunction radar