The multiphase course timetabling problem

Rasul Esmaeilbeigi

doi:10.1016/j.ejor.2021.10.014

Return

The multiphase course timetabling problem

2022-08-01

DOI：10.1016/j.ejor.2021.10.014

Original

Save

View PDF

Abstract

En 中文

This paper introduces the multiphase course timetabling problem and presents mathematical formulations and effective solution algorithms to solve it in a real case study. Consider a pool of lessons and a number of students who are required to take a subset of these lessons to graduate. Each lesson consists of a predetermined and consecutive sequence of phases with possibly different resource requirements and duration. Students who take a lesson must be present in certain phases of the lesson. Similarly, resources that are allocated to the lesson must be present in certain phases of the lesson depending on their roles. The objective is to maximize the weighted sum of student-lesson allocations subject to some capacity, availability and prerequisite constraints. The problem is formulated as an integer linear program called the session-index formulation. The formulation is then extended by introducing various side constraints that capture business requirements of a pilot training program. An enhanced branch-and-check algorithm is proposed to solve the problem more efficiently. Large instances of the problem are solved by utilizing an effective fix-and-optimize matheuristic. Results of a computational study on a set of real-world instances of the problem demonstrate the efficacy of the proposed exact and matheuristic algorithms. Due to the novelty and complexity of the problem, the efficacy of the proposed methodology to solve its real world instances, and the implementation and realization of these contributions within a decision support system, this work was recognized as a semi-finalist of INFORMS Franz Edelman Award (2021). Crown Copyright (c) 2021 Published by Elsevier B.V. All rights reserved.

Keywords:

Timetabling

Multiphase

Course scheduling

Matheuristic

Logic-based benders decomposition

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.