Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimizing satisfaction in a multi-courses allocation problem combined with a timetabling problem

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

The resource allocation problem and the timetabling problem are traditional kinds of NP-hard problems. Both problems can be found in universities where students can select courses they would like to attend before or after the timetabling is done. When demand exceeds capacity, the universities may allocate the available seats independently from the timetabling, but students may have then to decide which courses they are going to attend because of clashes in their timetable. To avoid this situation, some universities prepare their timetable considering students selection. In addition to that, students may submit preferences over courses, and the school administration has to assign seats and do the timetable considering both preferences and clashes. In this paper, both problems, seats allocation and timetabling, have been modeled separately and combined as constraint satisfaction optimization problems (CSOP). Two algorithms have been designed and implemented to find a solution to both problems simultaneously maximizing the satisfaction of students using a CSOP solver and an Ant colony optimization algorithm for the timetabling problem. The results of both algorithms are then compared. The allocation and timetabling procedures are based on preferences for courses defined by students, and on the administration’s constraints at Ecole Hôtelière de Lausanne. Three real data sets have been used to carry out a complete experimental analysis. High-quality solutions are obtained in a few minutes with both approaches; those solutions are currently used at Ecole Hôtelière de Lausanne.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Agustín-Blas LE, Salcedo-Sanz S, Ortíz-García EG, Portilla-Figueras A, Pérez-Bellido ÁM (2009) A hybrid grouping genetic algorithm for assigning students to preferred laboratory groups. Expert Syst Appl 36(3):7234–7241. doi:10.1016/j.eswa.2008.09.020

    Article  Google Scholar 

  • Babaei H, Karimpour J, Hadidi A (2015) A survey of approaches for university course timetabling problem. Comput Ind Eng 86:43–59

    Article  Google Scholar 

  • Budish E, Cantillon E (2012) The multi-unit assignment problem: theory and evidence from course allocation at harvard. Am Econ Rev 102(5):2237–2271

  • Cano JI, Sánchez L, Camacho D, Pulido E, Anguiano E (2009) Allocation of educational resources through happiness maximization. In: Proceedings of the 4th international conference on software and data technologies

  • Cano JI, Sánchez L, Camacho D, Pulido E, Anguiano E (2009) Using preferences to solve student–class allocation problem. In: Intelligent data engineering and automated learning-IDEAL 2009. Springer, Berlin, pp 626–632

  • de Werra D (1985) An introduction to timetabling. Eur J Oper Res 19(2):151–162

  • Di Gaspero L (2015) Integration of metaheuristics and constraint programming. In: Springer handbook of computational intelligence. Springer, Berlin, pp 1225–1237

  • Di Gaspero L, McCollum B, Schaerf A (2007) The second international timetabling competition (itc-2007): curriculum-based course timetabling (track 3). Tech. rep., Technical Report QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1. 0, Queens University, Belfast, UK

  • Diebold F, Aziz H, Bichler M, Matthes F, Schneider A (2014) Course allocation via stable matching. Bus Inf Syst Eng 6(2):97–110

    Article  Google Scholar 

  • Dorigo M, Birattari M (2010) Ant colony optimization. In: Encyclopedia of machine learning. Springer, Berlin, pp 36–39

  • Kojima F (2013) Efficient resource allocation under multi-unit demand. Games Econ Behav 82:1–14

    Article  MathSciNet  MATH  Google Scholar 

  • Landa-Torres I, Manjarres D, Salcedo-Sanz S, Ser JD, Gil-Lopez S (2013) A multi-objective grouping harmony search algorithm for the optimal distribution of 24-h medical emergency units. Expert Syst Appl 40(6):2343–2349. doi:10.1016/j.eswa.2012.10.051

    Article  Google Scholar 

  • Lewis R (2008) A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum 30(1):167–190

    Article  MathSciNet  MATH  Google Scholar 

  • Lewis R, Paechter B, McCollum B et al (2007) Post enrolment based course timetabling: a description of the problem model used for track two of the second international timetabling competition. Cardiff Business School

  • McCollum B, Ireland N (2006) University timetabling: bridging the gap between research and practice. E Burke HR ed: PATAT pp 15–35

  • Nogareda AM, Camacho D (2014) Integration of ant colony optimization algorithms with gecode. In: Doctoral program proceedings of the 20th international conference on principles and practice of constraint programming

  • Nogareda AM, Camacho D (2016) Optimizing satisfaction in a multi-courses allocation problem. In: Intelligent distributed computing IX. Springer, Berlin, pp 247–256

  • Nothegger C, Mayer A, Chwatal A, Raidl GR (2012) Solving the post enrolment course timetabling problem by ant colony optimization. Ann Oper Res 194(1):325–339

    Article  MathSciNet  MATH  Google Scholar 

  • Rossi F, Venable KB, Walsh T (2011) A short introduction to preferences: between artificial intelligence and social choice. Synth Lect Artif Intell Mach Learn 5(4):1–102

    Article  Google Scholar 

  • Schulte C, Tack G, Lagerkvist MZ (2010) Modeling and programming with gecode. http://www.gecode.org/doc/4.4.0/MPG.pdf. Accessed 3 Oct 2016

  • Socha K, Sampels M, Manfrin M (2003) Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In: Applications of evolutionary computing. Springer, Berlin, pp 334–345

  • Solnon C (2010) Ant colony optimization and constraint programming. Wiley Online Library

  • Solnon C (2002) Ants can solve constraint satisfaction problems. IEEE Trans Evolut Comput 6(4):347–357

    Article  Google Scholar 

  • Sönmez T, Ünver MU (2010) Course bidding at business schools*. Int Econ Rev 51(1):99–123

    Article  MathSciNet  Google Scholar 

  • Stützle T, Hoos HH (2000) Max-min ant system. Future Gener Comput Syst 16(8):889–914

    Article  MATH  Google Scholar 

  • Tassopoulos IX, Beligiannis GN (2012) Using particle swarm optimization to solve effectively the school timetabling problem. Soft Comput 16(7):1229–1252

    Article  Google Scholar 

  • Tsang E (2014) Foundations of constraint satisfaction: the classic text. BoD–Books on Demand

Download references

Acknowledgments

This work has been supported by following research grants: Comunidad Autonoma de Madrid, under CIBERDINE S2013/ICE-3095 project, and EphemeCH (TIN2014-56494-C4-4-P) project, under Spanish Ministry of Economy and Competitivity, both supported by the European Regional Development Fund FEDER.

Author information

Authors and Affiliations

  1. Ecole Hôtelière de Lausanne, HES-SO, University of Applied Sciences Western Switzerland, Lausanne, Switzerland

    Ana-Maria Nogareda

  2. Escuela Politécnica Superior, Universidad Autonónoma de Madrid, Madrid, Spain

    David Camacho

Authors
  1. Ana-Maria Nogareda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Camacho
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ana-Maria Nogareda.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Ethical approval

This article does not contain any studies with human participants performed by any of the authors.

Additional information

Communicated by C. Analide.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nogareda, AM., Camacho, D. Optimizing satisfaction in a multi-courses allocation problem combined with a timetabling problem. Soft Comput 21, 4873–4882 (2017). https://doi.org/10.1007/s00500-016-2375-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-016-2375-8

Keywords

Search

Navigation