Case study: Three stages in the planning of postgraduate examinations through binary integer programming

Abstract

The scheduling of examination timetables is a problem that arises in educational institutions such as universities, high schools and junior high schools. Mathematical programming models are used to solve this administrative problem. This is known as an NP-complete problem from the perspective of computational complexity, because of the large number of possible timetable combinations. This article presents a new strategy for defining the scheduling of examinations by stages, by decomposing the original problem, using binary variables, into three mathematical models. The assignment considers students, time slots, classrooms and examiners. We have taken the Department of Postgraduate Studies of the Tecnológico Nacional de México in Celaya as a case study. The strategy generated a significant reduction in the number of binary variables, Making it possible for the exact technique of branch and bound to reach efficient times in the search for an optimum solution at each stage.