Ohio University’s College of Business Uses Integer Programming to Schedule Classes Clarence H. Martin College of Business, Ohio University, 512 Copeland Hall, Athens, Ohio 45701-2979, [email protected] Ohio University’s College of Business uses an integer-programming model to assign instructors to courses, classrooms, and time slots. The model deals with a variety of issues, such as back-to-back classes, maximum number of teaching days, time slots of any configuration, multiple instructors for courses, departmental balance, and preassignments. CPLEX solves the problem for the College of Business quite easily. The college has used the model for about six years, and the administration and faculty view it very favorably. Key words: educational systems: planning; programming: integer. History: This paper was refereed. I n January 1998, the College of Business (COB) at Ohio University began using integer-programming models to schedule instructors and courses into classrooms and time slots. Prior to that time, COB did the scheduling manually for each academic term. COB has the sole responsibility of assigning its courses to instructors, to classrooms within its home building (Copeland Hall), and to time slots. Typically COB has 65 to 75 instructors, 110 to 130 courses, and 14 to 16 classrooms. In this paper, I use the term course to refer to individual sections of a given course (that is, each of the four sections of Marketing 101 is a course). COB specifies time slots (arbitrary subsets of the available hours during a week) as options for course times, and they can be of any configuration (Table 1). Cluster courses meet for 16 hours each week and require multiple instructors. In the manual process, an associate dean first allocated specific rooms in Copeland Hall to individual departments (Accounting, Finance, Management Information Systems, Management Systems, and Marketing). Department chairpersons then assigned the department’s undergraduate classes to those rooms. The associate dean specified other classrooms to be shared between two or more departments and still others to be held for graduate courses. Each department chairperson determined what courses to offer and the faculty available, assigned courses to instructors, and then tried to schedule the department’s classes into the allocated and shared classrooms, sometimes taking instructors’ preferences into account. Separate staff scheduled graduate courses. If a department chairperson were able to schedule all the classes of the department without using all the available classrooms and time slots, he or she would inform other departments of their availability. The chairperson assigned any courses that could not be assigned by this process to rooms outside of Copeland Hall. While this approach generally worked, it did not optimize the use of classroom space in Copeland Hall, and faculty members frequently taught courses outside of our home building because rooms of the sizes appropriate for the courses were not available. As enrollments increased, the need for another approach was becoming acute. This problem is a special case of the timetabling problem, which many researchers have studied. The problem is of great practical interest and has been approached through optimization, heuristics, and expert systems. It also is of theoretical interest in its combinatorial characteristics. Schmidt and Strohlein (1979) provided an early survey of the field with over 200 entries. Schaerf (1999) listed 110 entries with most published after 1979. Carter and Tovey (1992) identified characteristics of the problem that can help analysts to estimate how difficult it will be to solve particular instances. Glassey and Mizrach (1986) developed a 0–1 integerprogramming model to assign 4,000 university classes to 250 rooms. They solved the model heuristically and used an improvement routine to produce a final solution. Foulds and Johnson (2000) described SlotManager, a decision-support system for university timetabling written in Microsoft Access. Burke and Petrovic (2002) described applications of heuristics and metaheuristics in university timetabling. Drexl and Salewski (1997) employed two-phase parallel greedy randomized and genetic methods on problems found in primary education in Germany. 460 Downloaded from informs.org by [165.230.225.52] on 28 November 2017, at 16:10 . For personal use only, all rights reserved. Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes 462 Interfaces 34(6), pp. 460–465, ©2004 INFORMS Multiple Instructors per Course With innovative designs, courses increasingly integrate various disciplines, with several instructors assigned to a course. For example, at Ohio University, the undergraduate program includes two cluster courses taught by four or five instructors. These courses are scheduled for 16 contact hours per week, usually with only one instructor meeting with the class at a given time. However, all the instructors must be available to meet with the class during any of the 16 hours. Hence, others courses in their schedules cannot be assigned to time slots that contain any of the 16 hours assigned to the cluster class. Special Course Sets Obviously, instructors cannot be scheduled to teach more than one course at the same time. COB may also want to ensure that two or more courses with different instructors are not taught at the same time, for example, when students in a particular major are required to take them. Minimum Number of Courses Scheduled by Day It may be desirable to schedule courses so that classroom utilizations are approximately equal for all days of the week. For example, while students generally prefer not to have Friday classes, empty classrooms on Fridays often attract the attention of those who suggest universities are not using resources effectively. Departmental Leveling When a college schedules for all its departments and it does not have enough classroom space in its home building to accommodate all courses, it should avoid leaving some departments with a disproportionate share of their courses not assigned. At COB, any courses not assigned to classrooms in Copeland Hall are subsequently submitted to the university for assignment outside Copeland. Preassignments In the literature, researchers use the term preassignment to mean making an assignment prior to an automated solution, and in some approaches, it is a complicating factor. COB typically uses preassignment for its cluster courses. The New Approach In 1998, I approached the associate dean with an offer to attempt to develop a scheduling system in exchange for modest software support and agreement to try the system in practice. I wrote the system in about three months using Microsoft Visual Basic. The system has a front end that provides a customized approach to managing the data for the problem and a back end that provides on-screen review of the results and report-writing capabilities. Prior to 2003, the system included two FORTRAN modules that read the data, generated the objective functions and constraint matrices, and solved the integer programs for two optimization problems. The first problem dealt with the assignment of instructors to courses, and the second handled the assignment of instructorcourse pairings to classrooms and time slots. The optimization code was a branch-and-bound code that I wrote in the early 1980s. In 2003, I modified the system to use a single model that made all assignments simultaneously and used an academic version of the commercial optimization code CPLEX to solve the integer program. The development of a schedule starts six months prior to a given academic quarter. It begins with the individual department chairpersons assigning instructors to courses and specifying the various preferences for the instructors. In some cases, the instructors themselves express the preferences, while, in others, the chairpersons express preferences based on departmental needs. The chairpersons also specify special course sets, that is, courses that cannot be scheduled at the same time even though they have different instructors. The chairpersons or their administrative assistants enter this information on standard forms. Each department chairperson submits the forms to an associate dean who then adds any additional requirements, such as reserving blocks of time for noncourse activities and specifying different importance levels for various instructors and courses. For example, the cluster courses are preassigned specific classrooms and time slots by giving them large preference values. The associate dean may also set the minimum number of courses to be scheduled each day and departmental leveling parameters. Once the scheduling system is run, the associate dean and the department chairpersons review the results and make any necessary adjustments to the data. Typically, a final schedule is completed in one or two runs. I give the details of the model formulation in the appendix. Results The implementation of the scheduling system at COB was an immediate success. It has been used every term since its inception in 1998. CPLEX solves the integer-programming problems created very quickly. Typically, the problem dimensions are as follows: Instructors: 65–75Courses: 110–130 Classrooms: 14–16Time Slots: 28–35 Hours: 7 (in each day of week) . Downloaded from informs.org by [165.230.225.52] on 28 November 2017, at 16:10 . For personal use only, all rights reserved. Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes 464 Interfaces 34(6), pp. 460–465, ©2004 INFORMS measured by Ri. Finally, constraint set (10) requires that, if one or more instructors are assigned to multiple instructor course j in room k and time slot l, then Mjkl = 1. In the case of courses that are to be assigned multiple instructors, no constraint is imposed requiring all instructors to be assigned to the same classroom/time slot. When classroom/time slot resources are tight, the optimum solution will naturally assign the same classroom/time slot. In other cases, the solution provides alternative assignments. Index Sets I = index set of instructors. J = index set of courses. J M = index set of courses that require the assignment of more than one instructor. Ij= index set of instructors that can be assigned to course j. J i= index set of courses that can be assigned to instructor i. K = index set of classrooms. Ki j= index set of classrooms acceptable for instructor i for course j. L = index set of time slots. Li j= index set of time slots acceptable for instructor i for course j. T = index set of hours. S = index set of days. Lt= index set of time slots that include hour t. Ls= index set of time slots that include day s. l= index of time slot that follows time slot l (back-to-back). P = index set of course-conflict index sets. Gp= pth index set of courses that cannot be taught at the same time. st= day that includes hour t. H = index set of departments. J h= index set of courses belonging to department h. Qi = index set of time-slot groups for instructor i. qt= time-slot group that includes hour t. Parameters InstrImpi = importance of instructor i. CoursesForInstri = number of courses to be assigned to instructor i. InstrForCoursej = number of instructors to be assigned to course j. CoursePrefij = preference of instructor i for course j. RoomPrefijk = preference of instructor i for classroom k for course j. SlotPrefij l = preference of instructor i for time slot l for course j. InstrPeni = penalty for underassigning instructor i. CoursePenj = penalty for not assigning course j. RoomAvailkt = 1 if classroom k is specified as available at hour t; 0 otherwise. TeachDaysi = number of teaching days to be eliminated for instructor i. MinCoursesPerDays = minimum number of courses to be taught on day s. DayPens = per course penalty for underassignment on day s. MaxUnAsgnCoursesh = maximum number of unassigned courses for department h. DeptPenh = per course penalty for underassigning department h courses. Decision Variables Xijkl = 1 if instructor i is assigned to course j, in classroom k, and in time slot l; 0 otherwise. Mjkl = 1 if multiple-instructor course j is assigned to classroom k and time slot l; 0 otherwise. Ri = number of courses by which instructor i is underassigned. Yj = underassignment measure for course j. Zs = number of courses underassigned on day s. Uh = number of courses underassigned for department h. Vis = 1 if day s is eliminated for instructor i; 0 otherwise. Wiq = 1 if time slot group q is eliminated for instructor i; 0 otherwise. Formulation Max i∈I j∈J i k∈Ki j l∈Li j CoursePrefij + RoomPrefijk + SlotPrefij lInstrImpi Xijkl − j∈J CoursePenj Yj − s∈S DayPens Zs − h∈H DeptPenh Uh − i∈I InstrPeni Ri subject to i∈Ij k∈Kij l∈Lij Xijkl+Yj =InstrForCoursej j ∈J (1) i∈I j∈J i\J M l∈Lij∩Lt Xijkl+ j∈J M l∈Lt Mjkl ≤RoomAvailkt k∈Kt∈T (2) i∈I j∈J i k∈Kij l∈Lij∩Lt Xijkl+Xijkl +Vist+Wiqt≤1 i∈It∈T (3) i∈I j∈J i∩Gp k∈Kij l∈Lij∩Lt Xijkl ≤1 p∈Pt∈T (4) Downloaded from informs.org by [165.230.225.52] on 28 November 2017, at 16:10 . For personal use only, all rights reserved. Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes Interfaces 34(6), pp. 460–465, ©2004 INFORMS 465 i∈I j∈J i k∈Kij l∈Lij∩Ls Xijkl+Zs ≥MinCoursesPerDays s∈S(5) q∈Qj Wiq =Qi−1 i∈I(6) s∈S Vis =TeachDaysi i∈I(7) j∈J h Yj −Uh ≤MaxUnAsgnCoursesh h∈H(8) j∈J i k∈Kij l∈Lij Xijkl+Ri =CoursesForInstri i∈I(9) Xijkl−Mjkl ≤0 i∈Ij ∈J i∩J M k∈Kij l∈Lij(10) XjklMjklVisand Wiq =0 or 1 ZsYjRiand Uh ≥0 References Baker, K., M. Magazine, G. Polak. 2002. Optimal block designs models for course timetabling. Oper.Res.Lett. 30(1) 1–8. Burke, E., S. Petrovic. 2002. Recent research directions in automated timetabling. Eur.J.Oper.Res. 140(2) 266–280. Carter, M., C. Tovey. 1992. When is the classroom assignment problem hard? Oper.Res. 40(1S) 28–39. Deris, S., S. Omatu, H. Ohta. 2000. Timetable planning using the constraint-based reasoning. Comput.Oper.Res. 27(9) 819–840. Dimopoulou, M., P. Miliotis. 2001. An introduction to timetabling. Eur.J.Oper.Res. 130(1) 202–213. Drexl, A., F. Salewski. 1997. Distribution requirements and compactness constraints in school timetabling. Eur.J.Oper.Res. 102(1) 93–214. Foulds, L., D. Johnson. 2000. SlotManager: A microcomputer-based decision support system for university timetabling. Decision Support Systems 27(4) 367–381. Glassey, C., M. Mizrach. 1986. A decision support system for assigning classes to rooms. Interfaces 16(5) 92–100. Gunadhi, H., V. Anand, Y. Yong. 1996. Automated timetabling using an object-oriented scheduler. Expert Systems Appl. 10(2) 243–256. Hinkin, T., G. Thompson. 2002. SchedulExpert: Scheduling courses in the Cornell University School of Hotel Administration. Interfaces 32(6) 45–57. Schaerf, A. 1999. A survey of automated timetabling. Artificial Intelligence Rev. 13(2) 87–127. Schmidt, G., T. Strohlein. 1979. Timetable construction—An annotated bibliography. Comput.J. 23(4) 307–316. Shih, W., J. Sullivan. 1977. Dynamic course scheduling for college faculty via zero-one programming. Decision Sci. 8(4) 711–721. Wright, M. 2001. Subcost-guided search-experiments with timetabling problems. J.Heuristics 7(3) 251–260. Glenn E. Corlett, Dean, College of Business, Ohio University, 614 Copeland Hall, Athens, Ohio 45701- 2979, writes: “For a number of years the College of Business at Ohio University had struggled with the problem of matching room sizes and availability against of variety of instructor preferences for times, days, and rooms. Professor Martin developed a system for scheduling instructors, courses, classrooms, and times slots, which we have been using for about five years now. Professor Martin’s system has brought tremendous efficiency to the process and has eliminated complaints, rescheduling, and other conflicts. “Ohio University assigns priority to certain classroom space on the Ohio University Athens campus to various degree colleges. The administration of the degree colleges must utilize this priority space to assign faculty to classrooms and time slots. Student course demand analysis enables us to predict the approximate size of classroom which will be appropriate for each course offering; however, faculty preferences, equipment and configuration constraints, and time slot duplication had caused a great deal of dif- ficulty in this process. The amount of time spent by our associate dean in scheduling and rescheduling classrooms was exceeded only by the aggravation level caused by the complaints that necessarily followed this attempt. Since Professor Martin developed his system, we have been able to greatly reduce the amount of time and effort that goes into the planning of this process and, at the same time, have all but eliminated faculty complaints. I do not have an accurate estimate of the amount of dollar savings attributable to the use of Professor Martin’s system. However, I have estimated that it saves one week of associate dean time per quarter. Three weeks of time is roughly equivalent to $10,000, taking into consideration compensation and benefits. The real savings, however, is in the time that is saved through the elimination of faculty complaint and consternation. “I am very pleased with the system that Professor Martin developed, and we are continuing to experience its benefits.”
1. What company or organization used optimization or linear programming? What was the broad purpose of the project?
2. State the key decision variables (in words) and state the objective function in words (i.e., maximize profit or minimize cost or whatever the objective was).
3. What were the key constraints? (in words)
4. What was the IMPACT of using the model? (e.g., millions of dollars saved – some projects will not have a dollar impact but may improve some operation. Write down whatever you find).
5. What were the key lessons learned from the project for the company?