At the United States Military Academy (USMA) in West Point, the academic program is uniquely designed around the requirement that all students must graduate in four years, a total of eight academic semesters or terms (8TAP = eight term academic program). Adding to the unique character of USMA is the fact that each student’s daily activities are a carefully regimented balance of academic, military, and physical requirements. The ~4,500 enrolled cadets compile their individual 8TAPs which results in challenging scheduling problems. Hence, USMA relies on a highly customized decision support system, based on GAMS, to address different scheduling tasks like

• regular term scheduling
• term-end exam scheduling and
• room scheduling.

All of these scheduling tasks deal with multiple (often competing) objectives that need to be optimized under consideration of numerous business rules, which can be prioritized by the operator as needed. Given the uniqueness of the scheduling tasks at USMA, no off-the-shelf software is able to provide satisfactory results in reasonable time and is at the same time flexible enough to allow reacting to changed requirements due to unforeseen events like the Covid-19 pandemic.

With tailor-made scheduling applications based on GAMS, USMA has a powerful decision support system in place. The scheduling tools were developed by GAMS application specialists in close collaboration with the USMA registrar office and USMA’s Software Engineering Branch (SEB).

It is hard to imagine academic term scheduling, term-end exam scheduling and room scheduling here at the United States Military Academy without the robust tools and systems that GAMS has provided. When we reached out to GAMS (in late 2015) to discuss review and enhancement of the academic term and term-end exam scheduling processes that had been in place since 2000, they suggested that we consider taking a data-driven approach. This has allowed us to respond to required (and desired) changes in a timely and efficient manner. When we added room scheduling in 2018, the same approach was taken. This allowed us to schedule rooms in the Covid-19 environment by simply changing room capacities and moving out. Collaborating with GAMS is always a pleasure and the support is top-notch. Five stars!!!

Technical Implementation

The USMA scheduling problems can be modelled as Mathematical Programs, e.g. Mixed Integers Programs (MIP) or Mixed Integer Nonlinear Programs (MINLP). Even with state-of-the-art solver technology the resulting models are often too complex to be solved in a monolithic approach. Hence, custom solution approaches that combine

• decomposition methods
• heuristics
• multi-objective optimization and
• state-of-the-art MIP and MINLP solver technology
• have been implemented.

Crucially, the implemented solutions are designed to support the scheduling workflow at USMA in the best possible way. While from a mathematical perspective, it is desirable to have a well defined problem and well defined data and then run the scheduler once, in practice scheduling is a multi week process that involves many interactive “negotiations” between the registrar, departments, and instructors concerning the course offering details like times, rooms, etc. Hence, in addition to “just” computing optimal schedules, the scheduling engines also support

• efficient computation of multiple alternative schedules such that the registrar can choose from a set of schedules
• fixing of partial schedules and
• a mechanism to control the trade-off between runtime and solution quality.

The scheduling applications come with an interface designed to seamlessly integrate them into USMA’s IT Infrastructure.

How do the Scheduling applications support quick reactions to unforeseen events?

An important aspect during the development of the USMA scheduling applications was to provide an optimal solution for today’s scheduling problems that is well prepared for the problems of tomorrow.

Unforeseen events like the Covid-19 pandemic pose new challenges for the room scheduling where suddenly social distancing has to be considered. Rooms that had sufficient capacity for courses with a certain enrollment in the past are no longer suitable because they are too small to allow the cadets to keep the required distance. Thanks to the flexibility of the room scheduling engine such a new requirement was easy to add to the underlying models and allowed to quickly adjust the room schedule to the new situation.

A more enjoyable example for the flexibility of the scheduling examples was the Armed Forces Bowl 2017 . USMA’s football team, the Army Black Knights, qualified for the Bowl game which happened to take place during the already completely scheduled term-end exam week. On short notice, 566 individual exams of 141 affected cadets had to be rescheduled without changing any of the exams of unaffected cadets. Thanks to the flexibility of the term-end exam scheduler, this task has been accomplished with a minimum number of extra exam dates.

Summary

The GAMS USMA Scheduling applications…

• provide tailor-made software solutions to a set of challenging scheduling problems
• consider multiple objectives and allow the operator to prioritize them as needed
• are seamlessly integrated into USMA’s IT infrastructure
• provide the flexibility to react to unforeseen events.