Optimal Course Scheduling for United States Air Force Academy Cadets

Abstract

Scheduling students and academic courses at the United States Air Force Academy (USAFA), a military commissioning source, has required unique software and considerable manual effort. The recent discontinuation of the Oracle-based student information system mandates that the USAFA superintendent invest in new software, the customization of which will incur millions in additional costs if USAFA continues to rely upon a fixed alternating-day schedule format. We present an integer program that generates a course schedule using the repeated-week format common to most commercial-off-the-shelf (COTS) systems. The integer program uses cadet registration information to determine the number of sections to be offered and how cadets should be assigned to them to ensure on-time graduation, while accomplishing mandatory military training. Hard constraints enforce institutional restrictions that require all athletes to attend practice, limit the number of cadets who delay required courses, keep classroom usage and number of sections to campus and faculty availability, and ensure cadets are assigned only to scheduled sections without overlapping time requirements. Flexible constraints reflect faculty and cadet preferences; their violation is minimized to honor teaching requests from each department, maintain minimum and maximum section sizes, restrict the number of evening sections, and meet cadet registrations. In contrast to the previous USAFA process, we generate schedules that reduce the number of unmet student registrations by more than 75 percent, use 21 percent fewer sections, and respect nearly 90 percent of faculty teaching preferences. Results from our methodology are easily reproducible and measurable in terms of time to adjudicate, desirability, and demand on faculty resources. By accommodating a standard repeated-week format, rather than adhering to the current alternating-day approach, our model integrates easily as a front end to a COTS system and avoids $120 million in customization costs. Our program reduces the reliance on manual manipulation and makes it possible to find feasible schedules that permit section length and patterns to vary according to pedagogy—a break from over 50 years of rigid time-blocking techniques that sacrifice desirability for feasibility and timeliness.