Automated timetabling for small colleges and high schools using huge integer programs
This provides a practical solution for small colleges and high schools seeking to deviate from group scheduling, though it is incremental as it applies existing integer programming methods to a specific real-world case.
The authors tackled the academic timetabling problem at the United States Merchant Marine Academy by formulating an integer program with approximately 170,000 rows and columns, which solved to optimality in 4-24 hours on a portable computer.
We formulate an integer program to solve a highly constrained academic timetabling problem at the United States Merchant Marine Academy. The IP instance that results from our real case study has approximately both 170,000 rows and columns and solves to optimality in 4--24 hours using a commercial solver on a portable computer (near optimal feasible solutions were often found in 4--12 hours). Our model is applicable to both high schools and small colleges who wish to deviate from group scheduling. We also solve a necessary preprocessing student subgrouping problem, which breaks up big groups of students into small groups so they can optimally fit into small capacity classes.