Optimally Scheduling Basic Courses at the Defense Language Institute using Integer Programming

摘要

The Defense Language Institute (DLI) offers 23 beginning language courses and in 2004 began to provide a smaller class size for these courses. Restrictions on when classes can begin and a limited number of instructors prevent all students from being trained in a smaller class. This thesis develops integer linear programs (ILPs) that generate schedules for all student classes and maximize the number of smaller class starts for a given number of instructors. Secondary scheduling goals include avoiding weekly changes to instructor levels and scheduling preference such as the number of classes to start simultaneously. The ILPs solve in less than one minute and offer a significant improvement in the number of students that may be trained in the smaller class size. Computational results using real data for the Arabic, Chinese-Mandarin, and Persian-Farsi courses verify the ILPs find feasible multiyear schedules that incorporate the DLI's scheduling preferences while exceeding the DLI's published schedule results. For example, the ILPs find schedules for Arabic that train 8%, 34% and 76% of students in the smaller class in 2006, 2007, and 2008, whereas DLI's manual schedules at best can train 8%, 7% and 64%.