Scheduling at the United States Military Academy

Latest Project: 2021

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!!!

Cloud Migration of the USMA Schedulers

2021

The United States Military Academy (USMA) has been using scheduling algorithms based on and developed by GAMS for many years. The following three GAMS based scheduling applications are in operation at USMA.

  • The Data-Driven Room Scheduler (DDRS), introduced in 2018
  • The Term End Exam Scheduler (TEE), introduced in 2017
  • The Data-Driven [Term] Scheduler (DDS), introduced in 2016

In February 2021, GAMS introduced GAMS Engine , a technology to run GAMS jobs in cloud environments. In June 2021, USMA and GAMS agreed to migrate all the USMA Scheduling applications to the cloud. Thanks to the simplicity of GAMS Engine’s REST API, the migration from an in house solution to a seamless integration of GAMS Engine into USMA’s cadet administration system went smoothly.

The USMA scheduling algorithms run via GAMS Engine SaaS which is hosted on the AWS cloud infrastructure. The various schedulers are registered with Engine, which means that only input and output data is passed back and forth between the client machines and Engine SaaS.

Fig 1: GAMS Engine Infrastructure used by USMA

The USMA scheduling algorithms run via GAMS Engine SaaS which is hosted on the AWS cloud infrastructure. The various schedulers are registered with Engine, which means that only input and output data is passed back and forth between the client machines and Engine SaaS.

Thanks to the horizontal scalability of GAMS Engine SaaS, it is now possible to evaluate many scenarios in parallel, which drastically reduces the overall time of the scheduling process.

Room Scheduling at USMA

2018

At the United States Military Academy, scheduling rooms for courses can be a complex and time-consuming process, especially during events such as construction work where several rooms may become unavailable. In 2018, USMA approached GAMS to help automate this process with an optimization engine, resulting in the development of a customized Room Scheduler software.

The Room Scheduler takes in all course sections and their corresponding hours, and assigns suitable rooms to each course section. It considers several business rules, including capacity constraints, utilization balancing, room features, same-room-same-course requests, fixed assignments, and several soft business rules. By using these rules, the Room Scheduler finds an optimal assignment of course sections to rooms.

The room scheduling algorithm is an iterative procedure that aims to approach an optimal final room schedule in small steps. In addition, the Room Scheduler provides a Continuity of Operations (COOP) module that allows a room schedule to be repaired with minimal changes when some rooms become unavailable on short notice or when room requirements change due to unforeseen events, such as the sudden consideration of social distancing during the Covid 19 pandemic.

Term End Exam Scheduling at USMA

2017

GAMS experts have successfully implemented a state-of-the-art software solution for term end exam (TEE) scheduling at the United States Military Academy (USMA). This project showcases the competence of our consulting services in developing customized optimization solutions to solve complex scheduling problems.

The TEE scheduling at USMA is a challenging problem with multiple hard and soft requirements. The developed software satisfies all the hard requirements, while optimizing the soft requirements in the best possible way. The hard requirements include no hour conflicts, respecting hard capacity limits, scheduling exclusive courses in different periods, grouping exams of inclusive courses by type, fixing exams to given periods, limiting the number of makeups per course, and respecting finishing periods. The soft requirements include limiting the number of consecutive exams and exams per day for each cadet, moving exams out of certain periods, and accommodating individual off-periods.

To solve this sophisticated multi-objective optimization problem, our solution approach employs a polylithic framework that includes multiple problem-specific preprocessing steps and a powerful fix-and-optimize algorithm that can be parameterized to optimize the soft requirements in various ways. The result is a TEE schedule that meets all the hard requirements and optimizes the soft requirements according to the priorities set by the USMA.

Term Scheduling at USMA

2016

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 makes the scheduling particularly challenging.

For the term scheduling, a sophisticated decision support system that combines decomposition methods, heuristics, multi-objective optimization and state-of-the-art MIP solver technology has been implemented. The term scheduling system thereby supports a broad variety of business rules such as for example

  • individual free hours
  • day to day balancing
  • cohort scheduling (groups of cadets that should not be split for certain courses)
  • next hour free requirements for particularly challenging PE courses
  • enrollment balancing

Crucially, the implemented solution is 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 term scheduler also supports

  • 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.
Cadets are partitioned in batches and then scheduling happens in two phases. In phase 1, individual schedules are optimized. In phase 2, the final enrollment is optimized subject to bounds that limit the deviation from the best individual schedules.

Fig 2: Schematic view of the term scheduling algorithm

Cadets are partitioned in batches and then scheduling happens in two phases. In phase 1, individual schedules are optimized. In phase 2, the final enrollment is optimized subject to bounds that limit the deviation from the best individual schedules.