IDEAS home Printed from https://ideas.repec.org/a/spr/opmare/v12y2019i3d10.1007_s12063-019-00146-8.html
   My bibliography  Save this article

A novel two-stage optimization scheme for solving university class scheduling problem using binary integer linear programming

Author

Listed:
  • Jilan Samiuddin

    (Uttara University)

  • Mohammad Aminul Haq

    (Uttara University)

Abstract

University Class Scheduling Problem (UCSP) is an inevitable task every university must go through prior to the commencement of a semester. The problem studied in this paper is decomposed into two stages - lab scheduling and theoretical class scheduling. This novel technique of decomposition of the problem not only allowed maximum number of free variables to stricter constraints found in lab scheduling, but also reduced the overall computational cost and combinatorial complexity. The mathematical model for the problem is formulated via Binary Integer Linear Programming (BILP) structure using data collected from the department considered in the study. Part of the contribution of this work also includes developing ways to recognize only the true variables while formulating the model. The model is then optimized using the simplex method with the objectives to optimize classroom utilization and faculty preferences while fulfilling additional constraints. Furthermore, the proposed method is compared to the traditional technique in which the model is optimized in a single stage with both true variables recognized and not recognized.

Suggested Citation

  • Jilan Samiuddin & Mohammad Aminul Haq, 2019. "A novel two-stage optimization scheme for solving university class scheduling problem using binary integer linear programming," Operations Management Research, Springer, vol. 12(3), pages 173-181, December.
    • Handle: RePEc:spr:opmare:v:12:y:2019:i:3:d:10.1007_s12063-019-00146-8
    DOI: 10.1007/s12063-019-00146-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12063-019-00146-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12063-019-00146-8?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. Hertz, A., 1991. "Tabu search for large scale timetabling problems," European Journal of Operational Research, Elsevier, vol. 54(1), pages 39-47, September.
    Full references (including those not matched with items on IDEAS)

    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. Vermuyten, Hendrik & Lemmens, Stef & Marques, Inês & Beliën, Jeroen, 2016. "Developing compact course timetables with optimized student flows," European Journal of Operational Research, Elsevier, vol. 251(2), pages 651-661.
    2. De Causmaecker, Patrick & Demeester, Peter & Vanden Berghe, Greet, 2009. "A decomposed metaheuristic approach for a real-world university timetabling problem," European Journal of Operational Research, Elsevier, vol. 195(1), pages 307-318, May.
    3. Daniel Berend & Ephraim Korach & Shira Zucker, 2012. "Tabu search for the BWC problem," Journal of Global Optimization, Springer, vol. 54(4), pages 649-667, December.
    4. 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.
    5. 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.
    6. Boronico, Jess, 2000. "Quantitative modeling and technology driven departmental course scheduling," Omega, Elsevier, vol. 28(3), pages 327-346, June.
    7. Ozdemir, Mujgan S. & Gasimov, Rafail N., 2004. "The analytic hierarchy process and multiobjective 0-1 faculty course assignment," European Journal of Operational Research, Elsevier, vol. 157(2), pages 398-408, September.
    8. White, George M. & Xie, Bill S. & Zonjic, Stevan, 2004. "Using tabu search with longer-term memory and relaxation to create examination timetables," European Journal of Operational Research, Elsevier, vol. 153(1), pages 80-91, February.
    9. Alvarez-Valdes, Ramon & Crespo, Enric & Tamarit, Jose M., 2002. "Design and implementation of a course scheduling system using Tabu Search," European Journal of Operational Research, Elsevier, vol. 137(3), pages 512-523, March.
    10. Juretzka, Jan & Böhler, Catharina & Drexl, Andreas, 2000. "Ein Decision Support System zur universitären Prüfungsplanung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 530, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    11. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    12. de Werra, D., 1997. "The combinatorics of timetabling," European Journal of Operational Research, Elsevier, vol. 96(3), pages 504-513, February.
    13. Hertz, Alain & Robert, Vincent, 1998. "Constructing a course schedule by solving a series of assignment type problems," European Journal of Operational Research, Elsevier, vol. 108(3), pages 585-603, August.
    14. Lopez, Leo & Carter, Michael W. & Gendreau, Michel, 1998. "The hot strip mill production scheduling problem: A tabu search approach," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 317-335, April.
    15. Gerardo Gonzalez & Christopher Richards & Alexandra Newman, 2018. "Optimal Course Scheduling for United States Air Force Academy Cadets," Interfaces, INFORMS, vol. 48(3), pages 217-234, June.
    16. Drexl, Andreas & Juretzka, Jan & Salewski, Frank, 1993. "Academic course scheduling under workload and changeover constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 337, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    17. Al-Sultan, K. S. & Al-Fawzan, M. A., 1997. "A tabu search Hooke and Jeeves algorithm for unconstrained optimization," European Journal of Operational Research, Elsevier, vol. 103(1), pages 198-208, November.
    18. 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.
    19. Nonobe, Koji & Ibaraki, Toshihide, 1998. "A tabu search approach to the constraint satisfaction problem as a general problem solver," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 599-623, April.
    20. Tomáš Müller & Hana Rudová, 2016. "Real-life curriculum-based timetabling with elective courses and course sections," Annals of Operations Research, Springer, vol. 239(1), pages 153-170, April.

    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:spr:opmare:v:12:y:2019:i:3:d:10.1007_s12063-019-00146-8. 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.springer.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.