Supporting the Air Force:  Cadet Operations Research Projects at USAFA

Guy Barth, Alex Brown, Jeff Moffitt, and Loren Werner

United States Air Force Academy

 

Jim Lowe                                                                                 Mark Parker

Department of Management                                                      Department of Mathematical Sciences

United States Air Force Academy                                             United States Air Force Academy

Abstract

In order to adequately prepare graduates for their professional fields, the Operations Research (OR) curriculum at the United States Air Force Academy (USAFA) requires cadets to perform a major consultation project for a real client organization (either military or civilian).  This requirement is fulfilled via a capstone course taken during a cadet’s final semester.  In addition to providing a summary of a recent cadet project, we also provide additional background of the Academy's OR program.

 

Background - USAFA OR

The Operations Research major at USAFA is a multidisciplinary program jointly administered by the departments of Computer Science, Economics, Management, and Mathematical Sciences.  This paper summarizes the results of one project completed by a group of four OR seniors.  But first, a quick review of the Academy's OR program is provided.  Each USAFA OR graduate must complete 154 total semester hours, of which 45 semester hours are OR-related courses.  The Academy's core course sequence (94 academic hours, 15 hours of physical education and military studies) dominates three years of their four-year undergraduate experience. 

 

The OR curriculum consists of foundation courses within Mathematics (Calc III, Matrix Algebra, Probability, Statistics), Economics (Econ Theory, Econometrics, Forecasting), and Computer Sciences (ADA Programming, Numerical Methods, Simulation) as well as 12 semester hours of OR courses (Problem Solving and Capstone within Management, and Probabilistic Methods and Math Programming within Mathematical Sciences), along with 9 hrs of option courses.  This interdisciplinary OR curriculum graduated its first cadet in 1988, and has served as a benchmark program for other interdisciplinary degrees offer at the Academy.  The four department heads steer the program, while delegating the daily activities of running a degree program to Working Group representatives within their respective departments.  The size of the major has ranged from a low of 16 cadets in 1997 to 69 cadets in the class of 1999.

 

The Capstone Experience

Each August, OR faculty members solicit potential projects from local Air Force organizations and the Colorado Springs community.  During the first week of class, potential clients brief the cadets on their projects and then the cadets meet with clients of their choice before submitting their "wish list" of projects.  Similarly, the clients provide their impressions of the cadet teams, which are used to create team assignments.  Faculty mentors serve a vital role in this experience.  Faculty of the four OR departments volunteer this time and expertise to assist cadet teams.  While mentors do report the team progress to the course instructor, but their primary role is to assist the teams' progress.  Projects have covered a wide range of topics. 

 

Within the past year, cadets developed a methodology for the Mountain West Conference (the Academy’s athletic conference) to create Men’s and Women’s Basketball schedules.  Another team evaluated the effect of nearby housing development on wastewater run-off along the Air Force Academy was performed for the environmental engineers.  The Academy's heat plant operations were optimized using non-linear optimization and Design of Experiment techniques.  While another team relied upon an Air Force legacy simulation, THUNDER, to assess the effectiveness of future US Space Command assets.

 

The projects provide valuable educational experience for the cadets, expose the cadets to a variety of business and governmental organizations, and provide a glimpse of the applicability of their newly developed OR skills within a variety of scenarios.  The success of this capstone course has created an ongoing list of project ideas from local (governmental, non-profit, and private) organizations.  The cadets are provided with an opportunity to experience life as a consultant in a controlled environment.  The remainder of this article summarizes a report submitted by cadets Barth, Brown, Moffitt, and Werner detailing the work they performed in analyzing an allocation of classrooms at the Academy.

 

Cadet Project Description

The Dean of Faculty (DF) of USAFA is an academic body of 20 departments offering 35 different majors. Classrooms and faculty are entirely contained within four buildings, Fairchild Hall, the Consolidated Education Training Facility (CETF), Aeronautics Laboratory, and the Observatory.   Classrooms are centrally assignment by the Registrar.  In an ongoing effort to improve the level of education, an initiative to allow departmental “ownership” of classrooms surfaced.  The Vice Dean requested a feasibility study of departmental ownership of general-purpose classrooms (located within Fairchild Hall).

 

Under current room scheduling procedures, academic departments share classrooms within Fairchild Hall.  Since departments must share rooms, departments cannot modify rooms to meet their unique teaching initiatives.  The Vice Dean posed the following questions regarding the scheduling of rooms among departments:

 

1)      Is there a feasible allocation that provides unique rooms for each department?

And,

2)      If so, which allocation is best?

 

Model Development

The first step in model development was to understand the client’s (Vice Dean) objective and then convert it into a mathematical model.  The Vice Dean stated that he wanted a “fair” assignment that would remain feasible for 3-5 years (assuming relative minor curriculum changes).  We proposed an objective function that minimizes the number of classrooms not given to the departments relative to their maximum and average demand for rooms (demand is based upon requirements during each of the seven daily offering times).  Defining fairness was the next important step. 

 

One measure of fairness was to assign rooms such that the difference between the utilization rates among departments was minimized.  This concept was more complex that simply reviewing the overall utilization rate (# classrooms used/ # classrooms assigned).  If a department schedules most of their course offerings during one time period, it increased their maximum daily demand.  However, assigning classrooms to meet that particular time period resulted in empty classrooms during other offering times.   Therefore, it was necessary to consider the utilization rate of all seven daily periods.  While utilization rate was an important factor in classroom scheduling, manipulating the data to obtain utilization rates was not easy.  Moreover, classrooms should not be assigned based only on utilization rate because some departments had special classroom activities that required them to have high or low utilization rates.

 

Another criteria considered was assigning classrooms based on average classroom demand.  This meant giving more classrooms to departments who historically used more, and less to departments who had not needed classrooms in the past.  Unfortunately, as with maximum daily demand, classroom demand did not match up well with special activities. 

 

We hoped to reward departments that traditionally had high utilization rates, but we also wanted to give more classrooms to departments with high peak classroom demands.  At first, it hardly seemed fair to give more classrooms to departments that scheduled classes during specific periods of the day (i.e. morning).  However, we realized that departments had conflicting requirements forced them to “squeeze” their sections into portions of the day.  Adjunct faculty staffing, intercollegiate athletes’ schedules, or flying and club activities affect departmental offerings in addition to guest speaker considerations.  The conflicts created several instances of departments having low average demands for classrooms, but high max demand for classrooms per hour.  Therefore, our model penalized assignments that failed to satisfy both high average demands as well as the maximum daily demand for classrooms (see constraint #2).

             

LP Formulation

 

Part One:  The LP Model

 

 

Explanation of the LP Model:

 

Variables:

           X_type,dept =              Number of classrooms of a certain type assigned to a certain department

(e.g., if X _{mini-lectinar, computer science}  =  2, the model assigned two mini-lectinars to the computer science department).

           Feas _{type, department} = Allows the model to break the Maximum Demand of a particular department.

            

           Q _type: =                 Minimizes the difference between Maxdem and Avgdem for each type of

                  classroom for each department.

 

Parameters:

           Maxdem _{type,department}:        = Average maximum number of a certain type of classroom required

           by a certain department.

           Avgdem _{type,department}          = Average number of a certain type of classroom required by a certain

           department.

           #Rooms type                    =  Number of classrooms available for a certain type of classroom.

 

Formulation Explanation:

Objective Function:

           The objective minimizes the number of classroom demand not met by each department.        

           The Q variable in our objective function insures classroom allocation is as equitable as possible.  Q minimizes the number of classrooms under the maximum demand given to the department relative to the difference between their maximum and average demand.

            

Constraints:

(1)    Assign every department their max number of classrooms needed.

(2)    Insures feasibility and fairness by taking away classrooms from the departments with the largest difference between their maximum and average demand.  However, the equation does not make the model feasible by taking away all the classrooms from the department with the largest difference.  The Feas variable in the numerator insures that the reductions are done incrementally.  In other words, once a classroom is taken away, the model compares all departments prior to reducing by another classroom.  

(3)    Insures the number of classrooms assigned does not exceed the number available.  

 

What our LP model actually does and doesn’t do:

Our LP provides the quantities of each type of classroom assigned to each department or division.  The LP does not assign particular room numbers (4J4, for example) to departments.  We displayed the model recommendations using Autocad drawings of Fairchild Hall.  The LP was not intended to assign specific classrooms based upon location; only assign a number of classrooms to departments.

 

Results

The following chart summarized the results.  The first column was the department, the second column was the type of classroom, and the third column totaled the classrooms assigned.  An asterisk indicated that an extra double classroom was assigned to compensate for no mini-lectinars.  Columns M1-T7 contain the difference between the number of classrooms assigned and the number used during the current semester for that time period.  A positive number indicated that the department had a surplus of classrooms; negative values were limited.  Full results for the LP are given in the Appendix.

 

Assignment Chart