IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v54y2003i3d10.1057_palgrave.jors.2601495.html
   My bibliography  Save this article

A column generation approach for the timetabling problem of Greek high schools

Author

Listed:
  • K Papoutsis

    (University of Patras)

  • C Valouxis

    (University of Patras)

  • E Housos

    (University of Patras)

Abstract

A column generation (CG) approach for the solution of timetabling problems is presented. This methodology could be used for various instances of the timetabling problem, although in this paper the solution of the high-school situation in Greece is presented. The results obtained show clearly that the CG approach that has been extremely successful in recent years in the solution of airline crew scheduling problems could also be very efficient and robust for the solution of timetabling problems. Several large timetabling problems corresponding to real problems have been successfully solved, with the solutions obtained feasible and of very high quality in accordance with the problem definition. In addition, none of the solutions contained any idle hour for any of the teachers, which was one of the main goals of this optimization effort.

Suggested Citation

  • K Papoutsis & C Valouxis & E Housos, 2003. "A column generation approach for the timetabling problem of Greek high schools," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(3), pages 230-238, March.
    • Handle: RePEc:pal:jorsoc:v:54:y:2003:i:3:d:10.1057_palgrave.jors.2601495
    DOI: 10.1057/palgrave.jors.2601495
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601495
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601495?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Costa, Daniel, 1994. "A tabu search algorithm for computing an operational timetable," European Journal of Operational Research, Elsevier, vol. 76(1), pages 98-110, July.
    2. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    3. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    4. de Werra, D., 1997. "The combinatorics of timetabling," European Journal of Operational Research, Elsevier, vol. 96(3), pages 504-513, February.
    5. M W Carter & D G Johnson, 2001. "Extended clique initialisation in examination timetabling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(5), pages 538-544, May.
    6. Efthymios Housos & Tony Elmroth, 1997. "Automatic Optimization of Subproblems in Scheduling Airline Crews," Interfaces, INFORMS, vol. 27(5), pages 68-77, October.
    7. Dimopoulou, M. & Miliotis, P., 2001. "Implementation of a university course and examination timetabling system," European Journal of Operational Research, Elsevier, vol. 130(1), pages 202-213, April.
    8. Arabinda Tripathy, 1984. "School Timetabling---A Case in Large Binary Integer Linear Programming," Management Science, INFORMS, vol. 30(12), pages 1473-1489, December.
    9. Nirbhay K. Mehta, 1981. "The Application of a Graph Coloring Method to an Examination Scheduling Problem," Interfaces, INFORMS, vol. 11(5), pages 57-65, October.
    10. D. Abramson, 1991. "Constructing School Timetables Using Simulated Annealing: Sequential and Parallel Algorithms," Management Science, INFORMS, vol. 37(1), pages 98-113, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. G N Beligiannis & C Moschopoulos & S D Likothanassis, 2009. "A genetic algorithm approach to school timetabling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 23-42, January.
    2. Haroldo Santos & Eduardo Uchoa & Luiz Ochi & Nelson Maculan, 2012. "Strong bounds with cut and column generation for class-teacher timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 399-412, April.
    3. Meysam Shahvali KOHSHORI & Mehrnaz Shirani LIRI, 2012. "Multi Population Hybrid Genetic Algorithms for University Course Timetabling," Economics and Applied Informatics, "Dunarea de Jos" University of Galati, Faculty of Economics and Business Administration, issue 2, pages 5-16.
    4. K A Willoughby & C J Zappe, 2006. "A methodology to optimize foundation seminar assignments," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(8), pages 950-956, August.
    5. J W Hearne, 2007. "A market-driven approach to the optimal stocking problem on African game ranches," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 423-428, April.
    6. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    7. Al-Yakoob, Salem M. & Sherali, Hanif D., 2007. "A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1028-1044, August.
    8. Nelishia Pillay, 2014. "A survey of school timetabling research," Annals of Operations Research, Springer, vol. 218(1), pages 261-293, July.
    9. Salem Al-Yakoob & Hanif Sherali, 2015. "A column generation mathematical programming approach for a class-faculty assignment problem with preferences," Computational Management Science, Springer, vol. 12(2), pages 297-318, April.
    10. Zhang, Defu & Liu, Yongkai & M'Hallah, Rym & Leung, Stephen C.H., 2010. "A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems," European Journal of Operational Research, Elsevier, vol. 203(3), pages 550-558, June.
    11. Massimiliano Caramia & Stefano Giordani, 2020. "Curriculum-Based Course Timetabling with Student Flow, Soft Constraints, and Smoothing Objectives: an Application to a Real Case Study," SN Operations Research Forum, Springer, vol. 1(2), pages 1-21, June.
    12. Oliver Czibula & Hanyu Gu & Aaron Russell & Yakov Zinder, 2017. "A multi-stage IP-based heuristic for class timetabling and trainer rostering," Annals of Operations Research, Springer, vol. 252(2), pages 305-333, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    2. Kristiansen, Simon & Sørensen, Matias & Stidsen, Thomas R., 2011. "Elective course planning," European Journal of Operational Research, Elsevier, vol. 215(3), pages 713-720, December.
    3. Daskalaki, S. & Birbas, T., 2005. "Efficient solutions for a university timetabling problem through integer programming," European Journal of Operational Research, Elsevier, vol. 160(1), pages 106-120, January.
    4. Salem Al-Yakoob & Hanif Sherali, 2015. "A column generation mathematical programming approach for a class-faculty assignment problem with preferences," Computational Management Science, Springer, vol. 12(2), pages 297-318, April.
    5. Haroldo Santos & Eduardo Uchoa & Luiz Ochi & Nelson Maculan, 2012. "Strong bounds with cut and column generation for class-teacher timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 399-412, April.
    6. Daskalaki, S. & Birbas, T. & Housos, E., 2004. "An integer programming formulation for a case study in university timetabling," European Journal of Operational Research, Elsevier, vol. 153(1), pages 117-135, February.
    7. Massimiliano Caramia & Stefano Giordani, 2020. "Curriculum-Based Course Timetabling with Student Flow, Soft Constraints, and Smoothing Objectives: an Application to a Real Case Study," SN Operations Research Forum, Springer, vol. 1(2), pages 1-21, June.
    8. Haase, Knut & Latteier, Jörg & Schirmer, Andreas, 1997. "The course scheduling problem at Lufthansa Technical Training," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 441, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. Cangalovic, Mirjana & Kovacevic-Vujcic, Vera & Ivanovic, Lav & Drazic, Milan, 1998. "Modeling and solving a real-life assignment problem at universities," European Journal of Operational Research, Elsevier, vol. 110(2), pages 223-233, October.
    10. Dimopoulou, M. & Miliotis, P., 2001. "Implementation of a university course and examination timetabling system," European Journal of Operational Research, Elsevier, vol. 130(1), pages 202-213, April.
    11. Carrasco, M. P. & Pato, M. V., 2004. "A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 65-79, February.
    12. Urban, Timothy L. & Russell, Robert A., 2003. "Scheduling sports competitions on multiple venues," European Journal of Operational Research, Elsevier, vol. 148(2), pages 302-311, July.
    13. De Boeck, Liesje & Beliën, Jeroen & Creemers, Stefan, 2016. "A column generation approach for solving the examination-timetabling problemAuthor-Name: Woumans, Gert," European Journal of Operational Research, Elsevier, vol. 253(1), pages 178-194.
    14. Haase, Knut & Latteier, Jorg & Schirmer, Andreas, 1998. "The course scheduling problem at Lufthansa Technical Training," European Journal of Operational Research, Elsevier, vol. 110(3), pages 441-456, November.
    15. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    16. Schirmer, Andreas & Potzhar, Kathrin, 2001. "Professional course scheduling in airline transport pilot training: A case from Lufthansa flight training," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 539, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    17. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    18. Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.
    19. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    20. Rigo, Cezar Antônio & Seman, Laio Oriel & Camponogara, Eduardo & Morsch Filho, Edemar & Bezerra, Eduardo Augusto & Munari, Pedro, 2022. "A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service," European Journal of Operational Research, Elsevier, vol. 303(1), pages 168-183.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:54:y:2003:i:3:d:10.1057_palgrave.jors.2601495. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.