A Lagrangian relaxation approach to solve the second phase of the exam scheduling problem |
| |
| Affiliation: | 1. Department of Physics, University of Bari, Bari, Italy;2. National Institute for Nuclear Physics, Bari, Italy;3. Innovation Lab, Exprivia S.p.A., Molfetta, Italy;4. Department of Computer Science, University of Bari, Bari, Italy;1. University at Buffalo (SUNY), Buffalo, NY 14260, United States;2. University of Connecticut, Storrs, CT 06268, United States;1. ISEL – Instituto Superior de Engenharia de Lisboa, Instituto Politécnico de Lisboa, Rua Conselheiro Emídio Navarro, n.° 1, Lisboa 1959-007, Portugal;2. LARSyS: Laboratory for Robotics and Systems in Engineering and Science, Universidade de Lisboa, Av. Rovisco Pais, n.° 1, Lisboa 1049-001, Portugal;3. Department of Bioengineering/Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais, n.° 1, Lisboa 1049-001, Portugal |
| |
| Abstract: | The problem of scheduling final exams at a large university can be viewed as a three phase process. The first phase consists of grouping the exams into sets called exam blocks. The second phase deals with the assignment of exam blocks to exam days and the third phase consists of arranging the exam days and also arranging the blocks within days.In this paper, we present new integer programming formulations for the second phase of the scheduling problem. We present an integer program with a single objective of minimizing the number of students with two or more exams per day. We then present a Lagrangian relaxation based solution procedure to solve this problem. Further, we present a bicriterion integer programming formulation to minimize the number of students with two exams per day and the number of students with three exams per day. Finally, we present some computational experience using randomly generated problems as well as real world data obtained from the State University of New York at Buffalo. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
