My professor gave us the following article and asked us to answer several questi
ID: 3148253 • Letter: M
Question
My professor gave us the following article and asked us to answer several questions regarding the article that I will post below. Thank you in advance for any help you might be able to give me in the analysis of this article:
Link to article: http://www.csupom.org/PUBLICATIONS/2009/2009-10.pdf
Q1: What company or organization used optimization or linear programming? What was the broad purpose of the project?
Q2: 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).
Q3: What were the key constraints? (in words) Q4: 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).
Q5: What were the key lessons learned from the project for the company?
This article describes how an optimization model has been used recently to more effectively schedule classes in an average-sized business school department. Each semester this department offers approximately 46 classes taught by 20 different instructors in one of 32 time slots. A myriad of constraints must be satisfied while trying to maximize faculty preferences for courses and teaching times. Using the model has reduced the time needed to generate high-quality schedules from more than a day to less than three hours, and kept our schedule within the department’s allocated time slots, eliminating the need for staff to find additional rooms.
I. INTRODUCTION
of eight academic departments within the College of Business (COB) at San Francisco State University (SFSU). One of the main recurring duties of department chairs at SFSU and most other universities is to schedule their department’s classes and assign faculty members to teach them. Historically, class scheduling at SFSU has been done one semester ahead of time, i.e., planning for courses to be offered in the next semester has occurred early in the current semester. Recently, though, SFSU administrators decided to schedule two semesters ahead of time to give students greater ability to plan their future coursework. This has proven difficult for chairs to satisfactorily accomplish due to the inherent uncertainty in the process (e.g., budgetary concerns and personnel availability), as well as the time-consuming nature of the scheduling task. As a compromise, chairs were asked to tentatively schedule Spring 2009 classes during July 2008 (rather than during Spring 2008), and to finalize the Spring 2009 schedule in October 2008. At present, it is unclear how far in advance chairs will be asked to provide schedules for the Fall 2009 semester. To initiate the scheduling process for a given semester, the central SFSU administration provides each department chair with a “block allocation” or set of openings at various times of the day and week called time slots or “blocks” during which courses may be offered on the main campus. Familiar blocks include the 9:10- 10:00 AM slot on Mondays, Wednesdays and Fridays (abbreviated here as “MWF0910”) and the 12:35-13:50 PM slot on Tuesdays and Thursdays (“TTH1235”). Cells B2:W3 of Figure 1 show all the standard blocks used on the main campus for the Spring 2009 semester. While department chairs in the COB are supposed to fit all of their undergraduate classes into these blocks, many end up offering a significant number of classes either in excess of their allocation (referred to as “out of allotment”) or during non-standard blocks such as the two shown in cells X2:Y3 of Figure 1. In doing so, chairs create problems for staff and administrators (e.g., a shortage of rooms in which to house classes during standard blocks), as well as for students (e.g., conflicting times for classes and finals. Class scheduling in the COB became further complicated in January 2007 by the relocation of all graduate business programs to a new downtown campus (DTC) situated.
II. LITERATURE REVIEW
The literature contains a wealth of articles that have examined variations of the class scheduling or timetabling problem, as documented in Schmidt and Strohlein (1980) and in Schaerf (1999), who subdivided the field into three categories: (1) school, (2) university course, and (3) timetabling problems. The problem analyzed here clearly falls into the second category because it addresses how a department chair at a university can appropriately assign instructors to teach courses during specific blocks. Some researchers, e.g., Deris, Omatu and Ohta (2000), have focused on heuristic algorithms to solve problems in the second category, while others, e.g., Burke and Petrovic (2002), have developed heuristics and metaheuristics to address problems in the third category. Dimopoulou and Miliotis (2001) addressed problems in both categories with a two-stage PC-based system; however, in the course scheduling stage of their system, they assigned courses to time slots and rooms, but did not consider instructors. Foulds and Johnson (2000) developed a decision support system to aid experienced timetablers at each stage of the process by pointing out scheduling conflicts, suggesting alternatives, and presenting a variety of reports. Shih and Sullivan (1977) used binary integer programming models first to assign courses to instructors, and then to assign courses to time slots, in each of possibly several terms. However, they reported no computational results on the second model, and apparently never implemented their work. Nonetheless, their relatively small models do share some common features with that reported here, such as a desire to maximize instructor preferences for courses and time slots. Ferland and Fleurent (1994) developed a decision support system for course scheduling when student registrations for courses are already known (not the case at SFSU). Their course scheduling process aims to reduce conflicts for students, instructors and rooms, e.g., when a common group of students needs to take two classes held at the same time. Likewise, Hinkin and Thompson (2002) helped eliminate problems such as conflicts among required core courses and among electives, as well as the use of non-standard time blocks. They took many factors into account, including room capacity, room features and building utilization (not a departmental concern at SFSU). Solving their large, nonlinear problem required the use of a simulated annealing (heuristic) algorithm, which took more than a year to develop fully. Once COB chairs have determined their own departmental schedules, the central SFSU administration takes the next step of assigning classes to classrooms, an important related problem addressed by Glassey and Mizrach (1986). Martin (2004) solved a mixed integer LP model to not only assign instructors to courses and time slots, but also to assign these to classrooms, for the entire College of Business at Ohio University. Our model and Martin’s also have some features in common, such as concern for back-to-back teaching assignments and special course sets. Though more ambitious in scope, Martin’s formulation is (surprisingly) smaller than ours in terms of number of variables and constraints. This article concentrates more on the formulation and unusual aspects of our class scheduling problem, which may be relevant for academic departments with similar characteristics. In particular, I address scheduling issues faced by an average-sized academic department that operates within the confines of a large business school, which itself is part of a large state university. The problem’s formulation leads to an optimization model that is medium-sized by today’s standards – more than 8,300 binary variables and 10,000 constraints – one not readily formulated or solved with Microsoft Excel. The problem has been successfully tackled with a widelyavailable software package (not specially-written Saltzman An Optimization Model for Scheduling Classes in a Business School Department California Journal of Operations Management, Volume 7, Number 1, February 2009 87 code) that can be adapted easily by others willing to use this or other similar optimization package. Since the model reads in several data files from Excel, much of the model maintenance can be done within the familiar environment of Excel. With both a linear objective function and linear constraints, the model solves quickly, allowing for fast experimentation. To date, the model has been used twice; over time, further refinements may be made as more experience is gained
III. PROBLEM DEFINITION AND MODEL FORMULATION
Saltzman An Optimization Model for Scheduling Classes in a Business School Department California Journal of Operations Management, Volume 7, Number 1, February 2009 88 graduate blocks, and graduate courses cannot be offered during undergraduate blocks: Xi,c,b = 0, for all i Instructor, c CourseUG, b BlockGR, and Xi,c,b = 0, for all i Instructor, c CourseGR, b BlockUG, where BlockUG (BlockGR) is the set of all undergraduate (graduate) blocks. As stated in the introduction, the number of undergraduate courses must not exceed the block allocations set by the administration; likewise, the number of graduate courses offered at the DTC cannot exceed the allocations set by the COB Associate Dean: i c
CourseUG Xi,c,b AllocationUGb, for all b BlockUG, and i c CourseGR Xi,c,b AllocationGRb, for all b BlockGR, where AllocationUGb and AllocationGRb are the maximum number of undergraduate and graduate sections, respectively, that the department may offer during block b. To serve students who work during the day, we endeavor to offer sections of some undergraduate courses, such as DS 212, at night: 1 ib BlockNight Xi,DS212,b 3. Similar constraints, with potentially different upper bounds, are in place for the undergraduate core courses DS 110 and DS 412. Night-time sections of some courses, such as DS 110, should be offered on different nights to give non-traditional students the most chance to take the course: i Xi,DS110,b 1, for all b BlockNight. Similar constraints exist for evening sections of DS 212, DS 412, DS 856 and BUS 786. Some undergraduate concentration courses, such as DS 312 and DS 601, ought to be taught on different nights so that DS majors can take both courses in the same semester, if desired: i (Xi,DS312,b + Xi,DS601,b) 1, for all b BlockNight.
Faculty-Oriented Constraints
First, a set of constraints is needed to enforce faculty teaching loads: cb Xi,c,b = Loadi , for all i Instructor, where Loadi is the number of classes instructor i is supposed to teach in the semester. In the DS department the typical load is three classes per semester for full-time faculty, and one or two for part-time lecturers. The model also contains constraints that improve the overall quality of life for the faculty. For instance, to reduce monotony, no tenured/tenure track instructor is asked to teach three sections of the same course: b Xi,c,b 2, for all i InstructorTTT, c Course. DS faculty members often one night class per week, but never more than two: c b
BlockNight Xi,c,b 2, for all i Instructor. Good, “coherent” schedules (Burke and Petrovic, 2002, p. 267) avoid requiring instructors to teach classes on both MWF and TTH: c (Xi,c,b1 + Xi,c,b2 ) 1, for all i Instructor, b1 BlocksMWF, b2 BlocksTTH. T
Travel Time Considerations
Saltzman An Optimization Model for Scheduling Classes in a Business School Department California Journal of Operations Management, Volume 7, Number 1, February 2009 89 {MWF1210, MWF1310, MWF1410, MWF1510, M1610, MW1410, MW1535, M1900}. The model contains a related constraint set to allow an instructor at least two hours to get from the main campus to the DTC for a class that starts at 1830 on Monday. Similar constraint sets are in place for the other days of the week. All told, the model used to plan the Spring 2009 schedule included more than 10,000 constraints.
The Objective Function
The DS class scheduling problem’s objective function is to maximize instructors’ total preferences for the courses assigned to them and the blocks during which these courses are offered, along with terms that try to keep multiple sections of one course taught by an instructor close together. In particular, the weighted linear objective function contains four components: w1CoursePrefs + w2BlockPrefs + w3TotalProxMWF + w4TotalProxTTH, where user-adjustable weights w1, w2, w3, and w4 reflect the relative importance of the associated quantities. The first two terms each require a distinct set of input data. One input is a matrix of instructor course preferences (ICP), while the other is a matrix consisting of instructor block preferences (IBP). Prior to developing the schedule, DS instructors are asked to provide positive integer weights summing to 10 for two or more courses that they wish to teach. The greater instructor i’s preference for teaching course c, the higher the weight ICPi,c. The term CoursePrefs is calculated as icb ICPi,c Xi,c,b. Before the schedule is developed, DS faculty are also asked to submit a list of hard and soft constraints regarding their availability and preferences for teaching at specific times, which I then translate into primarily ones and zeros (see Figure 1). In particular, IBPi,b is the preference value of instructor i for teaching during block b. If an instructor has an especially strong affinity for or aversion to a particular block, IBPi,b can be further adjusted up or down. While most instructors prefer to teach on a TTH schedule rather than a MWF schedule, some DS courses simply must be offered on MWF to make better use of our allocated blocks and to give students more options. Consequently, we’ve devised a rotation system to achieve this in a balanced way over time. Instructors whose turn it is to teach on MWF are given values of 1 for the MWF blocks, and 0s for the TTH blocks, while the opposite is true for those instructors who need not teach on MWF. The term BlockPrefs is found as icb IBPi,b Xi,c,b. DS department tenure/tenure-track faculty members typically teach two sections of a core undergraduate class, and a third class for either graduate or undergraduate students each semester. In such cases, instructors almost always wish to teach two sections of the same core course back-to-back, i.e., in consecutive blocks such as TTH0935 and TTH1100. One way to achieve back-to-back course assignments is by adding a series of hard constraints, as in Shih and Sullivan (1977). I chose to treat this desire as a soft constraint and try to satisfy it by incorporating appropriate terms into the objective function. Note that an instructor has been assigned to teach during two blocks b1 and b2 if the value of Xi,c,b1 Xi,c,b2 is one. However, this nonlinear approach cannot be handled by my version of OPL Studio, so I developed an additive linear approach involving (Xi,c,b1 +Xi,c,b2 ). This required finding two matrices ProxMWF (the proximity of MWF blocks) and ProxTTH (the proximity of TTH blocks) such that the quantities TotalProxMFW and TotalProxTTH increase when an instructor is assigned to teach during consecutive blocks and decrease when assigned to teach during nonconsecutive blocks. Determining appropriate elements for these matrices is itself an interesting problem, but will not be covered here. The terms measuring proximity of assigned courses are: Saltzman An Optimization Model for Scheduling Classes in a Business School Department California Journal of Operations Management, Volume 7, Number 1, February 2009 90 TotalProxMWF = icb1
BlocksMWF b2 BlocksMWF (Xi,c,b1 +Xi,c,b2 )ProxMWFb1 ,b2 , and TotalProxTTH = icb1 BlocksTTH b2 BlocksTTH (Xi,c,b1 +Xi,c,b2 )ProxTTHb1 ,b2 . While this linear approach works reasonably well and helps to model to solve quickly, it sometimes leads to schedules in which an instructor’s two core class sections are not back-to-back. Fortunately, it is usually not difficult to manually interchange courses or instructors to achieve back-to-back classes for all instructors who desire it. To briefly summarize, the DS class scheduling problem can be formulated as a fairly large assignment-type integer linear program, which is highly constrained. The only substantial assumption made is that all required data must be placed in spreadsheet files prior to model execution. In particular, the model reads in lists of the blocks, instructors, and courses involved in the upcoming semester’s schedule, along with instructor course loads; block allocation quantities for all undergraduate and graduate blocks; and course and block preference information from instructors.
IV. RESULTS
An OPL script was written to run the DS class scheduling model and format the resulting schedule by course and by instructor (e.g., see Figure 2 below). Model output also shows the number of sections of each course offered and how the usage of blocks compares to the department’s allocation. Some of this output is copied into Excel and given to the department FIGURE 2: THE OUTPUT SPRING 2009 SCHEDULE, BY INSTRUCTOR Instructor Course Block Instructor Course Block AZOURY DS212 MWF1010 ROEDER DS408 TH1900 AZOURY DS212 MWF1110 ROEDER DS411 TTH0935 AZOURY DS411 W1610 SALTZMAN DS851 W1830 CHOLETTE DS412 TTH0810 UDAYABHANU DS412 TTH1100 CHOLETTE DS412 TTH0935 UDAYABHANU DS412 TTH1235 CHOLETTE DS856 W1830 UDAYABHANU BUS786 W1400 ELIMAM DS412 T1900 Carter DS110 T1535 ELIMAM DS412 TTH1410 Carter DS110 TH1535 ELIMAM DS856 TH1830 Chan DS212 M1900 ENG DS212 TTH0935 Danko DS712 W1830 ENG DS212 TTH1100 Danko DS712 TH1830 ENG DS853 M1830 Klimkovskaia DS212 TTH0810 MEHROTRA DS624 M1900 Klimkovskaia DS212 TTH0935 MEHROTRA DS854 T1830 Lee DS212 TH1900 MIYAOKA DS412 MWF1210 Rainaldi DS710 T1830 MIYAOKA DS412 MWF1110 Sepah DS412 TH1900 MIYAOKA DS604 W1900 Shibuya DS110 T1900 OZLUK DS412 TTH1100 Shibuya DS710 M1830 OZLUK DS412 TTH1235 Wing DS110 MWF0810 OZLUK DS212 T1900 Wing DS110 MWF0910 OZSEN DS412 TTH1235 Wing DS110 MWF1010 OZSEN DS412 TTH1410 Wing DS110 MWF1110 OZSEN BUS786 T1830 Wing DS110 MWF1210 Saltzman An Optimization Model for Scheduling Classes in a Business School Department California Journal of Operations Management, Volume 7, Number 1, February 2009 91 office manager in a format she prefers for input to the university’s scheduling system. The model was first run on the Fall 2008 schedule, even though I had already planned that semester’s schedule out manually, in order to test the quality of the model’s solutions and make improvements to the model. The Spring 2009 schedule was planned primarily by running the model, with only a few manual adjustments made later. Because the model generally solves in less than 30 seconds on a Dell Inspiron 6400 laptop, several schedules can be tried out quickly with, say, alternate course preference values. For instance, I can try to modify the schedule for a particular junior faculty member by changing his or her preference values (or someone else’s) for a specific course. All told, preparing this schedule took less than three hours, including data entry and making minor changes to the Fall 2008 model. As more experienced is gained with the process, it may take even less time to prepare a high-quality schedule in the future. Besides reducing the time required to generate high-quality schedules, running the model has had other benefits. First, it has kept our schedule completely within the department’s block allocation (a claim not many other departments can make), eliminating the need for staff to spend time looking for additional rooms to accommodate our classes. Second, it’s made the scheduling process more transparent to DS faculty, who now better appreciate how difficult it really is to develop a feasible schedule. They may even perceive the scheduling process as more objective and fair than the previous manual approach.
V. CONCLUSION AND FUTURE WORK
One possible area to investigate further is whether or not a nonlinear objective function (a more natural choice to ensure back-to-back assignments of courses) would actually improve the quality of the schedules found. If I had a nonlinear solver, I could determine whether or not the improvement is worth the longer computational time most-likely required. Perhaps more importantly, much greater effort would be required to get this planning tool adopted by other departments within the COB or elsewhere who face issues similar to those of the Decision Sciences department. I have found that the other COB department chairs have devised their own manual processes to plan their schedules, with at least one making limited use of Excel to partially check the feasibility of their schedules. However, getting other chairs to actually adopt an optimization-based approach such as the one presented here would be a major challenge for several reasons: (1) they don’t understand or trust mathematical models; (2) they can’t afford to buy an expensive software package such as OPL Studio; (3) they fear losing control of the scheduling process; and/or (4) they prefer not to share the details of their scheduling process with someone outside of their own department. In the future, it would also be desirable to examine the rescheduling problem, i.e., how to alter an existing schedule after something has changed, such as a tenured or tenure-track faculty member being awarded a sabbatical or a course release late in the planning cycle. What is the best way to repair the current schedule so as to minimize changes from the current schedule? Should “change” be defined in terms of the number of instructors whose schedule changes, the number of classes that are assigned to a different instructor or block, or some other measure? The answer may depend on whether the rescheduling is done before or after students have registered for classes, and will likely require considerable discussion and experimentation.
Explanation / Answer
1)The Decision Sciences (DS) department within the College of Business (COB) at San Francisco State University (SFSU),
less time to prepare a high-quality schedule ,
it has kept schedule completely within the department’s block allocation
eliminating the need for staff to spend time looking for additional rooms to accommodate classes.
it’s made the scheduling process more transparent to DS faculty, who now better appreciate how difficult it really is to develop a feasible schedule.
2) objective function:The DS class scheduling problem’s objective function is to maximize instructors’ total preferences for the courses assigned to them and the blocks during which these courses are offered, along with terms that try to keep multiple sections of one course taught by an instructor close together
3)
set of constraints ineeded to enforce faculty teaching loads,Sufficient time must be allowed for instructors to travel from the main campus to the DTC.
4)
less time to prepare a high-quality schedule ,
it has kept schedule completely within the department’s block allocation
eliminating the need for staff to spend time looking for additional rooms to accommodate classes.
5)it would also be desirable to examine the rescheduling problem, i.e., how to alter an existing schedule after something has changed, such as a tenured or tenure-track faculty member being awarded a sabbatical or a course release late in the planning cycle
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.