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

  • José Israel Hernández-Vázquez Tecnológico Nacional de México en Celaya
  • Salvador Hernández-González Tecnológico Nacional de México en Celaya, Departamento de Ingeniería Industrial
  • María del Rosario Baltazar-Flores Tecnológico Nacional de México en León, División de Estudios de Posgrado e Investigación
  • José Alfredo Jiménez-García Tecnológico Nacional de México en Celaya, Departamento de Ingeniería Industrial
  • José Omar Hernández-Vázquez Tecnológico Nacional de México en Celaya, Departamento de Doctorado en Ciencias de la Ingeniería
  • Moisés Tapia-Esquivias Tecnológico Nacional de México en Celaya, Departamento de Ingeniería Industrial
Keywords: examination timetabling, Integer programming binary, Np-Complete

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.  

Published
2020-01-02
How to Cite
Hernández-Vázquez, J. I., Hernández-González, S., Baltazar-Flores, M. del R., Jiménez-García, J. A., Hernández-Vázquez, J. O., & Tapia-Esquivias, M. (2020). Case study: Three stages in the planning of postgraduate examinations through binary integer programming. International Journal of Combinatorial Optimization Problems and Informatics, 11(2), 46-60. Retrieved from https://ijcopi.org/ojs/article/view/134
Section
Articles