My professor gave us the following article and asked us to answer several questi
ID: 3142595 • 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:
1. Clearly describe in your own words the problem studied in the article. That is, what is the purpose and motivation for the research? What was the problem that motivated the research?
2. Discuss to the best of your ability the linear or integer programming model. What is the objective of the problem (e.g., minimize cost, maximize profits, maximize productivity, etc.). Briefly explain the constraints of the problem. Again, do your best. The authors should present this material in a clear manner. Use a table or bulleted list for ease of grading (see sample below).
3. What were the results of the linear or integer programming implementation (e.g., improved productivity, reduced costs, etc.)?
4. How does the implementation of linear or integer programming to a real world problem help bring the course concepts alive? Do you see the relevance and power of the techniques we have studied this semester to solve large-sized complex problems? Explain.(NOTE: I am particularly interested in your response to this question and thus urge you to be thoughtfulness). Even if you never solve another math programming problem in your lifetime, I hope you will leave with an appreciation of the power of this method to solve complex, real-life problems. You may want to browse the journal Interfaces to gain additional exposure to other real-life problems solved using mathematical programming).
Begin Article: Vol. 34, No. 6, November–December 2004, pp. 460–465 issn 0092-2102 eissn 1526-551X 04 3406 0460
informs ® doi 10.1287/inte.1040.0106
©2004INFORMS
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, martinc@ohio.edu
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.
In January 1998, the College of Business (COB) at Ohio University began using integer-programming models to schedule instructors and courses into class- rooms 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 mul- tiple instructors.
In the manual process, an associate dean first allo- cated specific rooms in Copeland Hall to individ- ual departments (Accounting, Finance, Management Information Systems, Management Systems, and Mar- keting). 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 depart- ment’s classes into the allocated and shared class- rooms, 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 availabil- ity. 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 out- side 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 inter- est 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 integer- programming 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 univer- sity timetabling written in Microsoft Access. Burke and Petrovic (2002) described applications of heuris- tics and metaheuristics in university timetabling. Drexl and Salewski (1997) employed two-phase par- allel greedy randomized and genetic methods on problems found in primary education in Germany.
460
Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes
Interfaces34(6),pp.460–465,©2004INFORMS 461
Days
Monday and Wednesday Tuesday and Thursday
Monday, Tuesday, and Thursday Tuesday
Hours
8:00–10:00 a.m. 2:00–4:00 p.m. 8:00–Noon 6:00–10:00 p.m.
with the exception of special course sets, potential student conflicts. Once COB knows the instructor preferences, the problem is to make instructor-course- classroom-time-slot assignments in a manner that optimizes some overall preference measure. Some obvious restrictions exist:
(1) An instructor should be assigned the required number of courses and cannot teach more than one course at a time.
(2) A classroom cannot hold more than one course at a time.
(3) As many courses as possible should be assigned to the classrooms and time slots available in the home building.
However, to prepare a schedule that meets the diverse preferences of the members of a university faculty and administration, one must deal with sev- eral other issues.
Maximum Number of Teaching Days
An instructor may be willing to teach courses on any day of the week but would like to limit the num- ber of days on which he or she teaches. For example, the possible time slots for an instructor may include Monday, Wednesday slots and Tuesday, Thursday slots. Without a constraint on the number of teaching days, the instructor’s schedule could include classes on all four days. Enforcing a constraint of a maximum of two teaching days would mean scheduling either Monday, Wednesday classes or Tuesday, Thursday classes (but not both). Burke and Petrovic (2002) call this issue coherence.
Back-to-Back Courses
An instructor may wish to avoid teaching courses back-to-back, that is, two courses in a row without a break. For example, an instructor to be assigned two courses might have the following time slots available on Mondays and Wednesdays:
(1) 8:00 to 10:00 a.m. (2) 10:00 a.m. to noon (3) Noon to 2:00 p.m. (4) 2:00 to 4:00 p.m.
Enforcing a back-to-back restriction would imply selecting time slots 1 and 3, time slots 1 and 4, or time slots 2 and 4.
Time-Slot Groups
Another way of stating instructor preferences is the specification of time-slot groups, which are parti- tions of an instructor’s possible time slots into two or more disjoint groups with the understanding that time slots actually assigned belong to exactly one of those groups. For example, an instructor may wish to have classes scheduled for either mornings or afternoons (but not both) and on either Mondays and Wednesdays or Tuesdays and Thursdays (but not both).
Table 1: Courses at Ohio University’s College of Business can meet in a wide variety of time slots.
Dimopoulou and Miliotis (2001) applied integer pro- gramming to university courses and examinations timetabling. They put courses and rooms into groups prior to optimization and did not consider instruc- tors. Shih and Sullivan (1977) addressed the mul- tiperiod assignment of instructors to courses and time slots through a 0–1 integer-programming model, but did not address classrooms. Because of the lim- ited computational horsepower available in 1977, they solved very small problems. Baker et al. (2002) explored the use of optimal block design models from experimental design to course timetabling problems and developed integer-programming and constraint- programming approaches to their solution. Gunadhi et al. (1996) developed an expert-system approach for scheduling university courses. Wright (2001) incorporated subcost-guided search into simulated- annealing and threshold-acceptance methods applied to timetabling problems arising in primary and sec- ondary education. Deris et al. (2000) formulated the timetabling problem as a constraint-satisfaction prob- lem and tested their algorithm on data from a private college. Hinkin and Thompson (2002) employed sim- ulated annealing to solve a 0–1 integer-programming model of a very detailed course-scheduling problem.
The problem I addressed differs from problems considered previously in two ways:
(1) It includes instructors, courses, classrooms, and time slots.
(2) It includes many practical issues.
Development of theoretical results is not my goal; indeed, incorporating so many practical issues within an integer-programming model as I do in this work largely precludes theoretical insights.
Problem Description
Basic Problem Statement
Instructors have preferences for courses, classrooms, and time slots. Many instructors find only a small subset of all possible time slots acceptable. For example, an instructor who wants to teach only on Mondays and Wednesdays should not be assigned time slots on other days of the week. COB develops the schedule before it has information on individual student enrollment and therefore does not consider,
Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes 462 Interfaces34(6),pp.460–465,©2004INFORMS
Multiple Instructors per Course
With innovative designs, courses increasingly inte- grate various disciplines, with several instructors assigned to a course. For example, at Ohio Univer- sity, the undergraduate program includes two clus- ter 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 sched- ules 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 dispropor- tionate 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 preassign- ment to mean making an assignment prior to an automated solution, and in some approaches, it is a complicating factor. COB typically uses preassign- ment 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 instructor- course 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 assign- ments 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 pref- erences for the instructors. In some cases, the instruc- tors themselves express the preferences, while, in others, the chairpersons express preferences based on departmental needs. The chairpersons also spec- ify special course sets, that is, courses that cannot be scheduled at the same time even though they have different instructors. The chairpersons or their admin- istrative 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 impor- tance levels for various instructors and courses. For example, the cluster courses are preassigned specific classrooms and time slots by giving them large prefer- ence values. The associate dean may also set the min- imum 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–75 Courses: Classrooms: 14–16 Time Slots: Hours: 7 (in each day of week).
110–130 28–35
Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes
Interfaces34(6),pp.460–465,©2004INFORMS 463
The seven hours are actually seven two-hour peri- ods (8:00 to 10:00 a.m., 10:00 a.m. to noon, noon to 2:00 p.m., 2:00 to 4:00 p.m., 4:00 to 6:00 p.m., 6:00 to 8:00 p.m., and 8:00 to 10:00 p.m.) because the vast majority of COB classes meet in two-hour periods. To ensure effective utilization of resources, COB requires instructors who want to teach one-hour classes to teach them back to back in a single two-hour period. The scheduling system treats such courses as single two-hour courses. Using two-hour blocks as the basic unit of time reduces the number of constraints in the model but not the number of decision variables. Of course, the model can be utilized with one-hour time blocks. The number of time slots varies by quarter based on needs and preferences.
Typical dimensions of the integer-programming problem for the instructor-course-classroom-time-slot assignment model are as follows:
meet all instructor-assignment goals or all course- assignment goals. The index sets reflect the compo- nents of the problem, namely, instructors, courses, classrooms, time slots, hours, days, departments, and sets of courses that cannot be taught at the same time. The parameters reflect various preferences of instruc- tors and other desired properties of the solution.
The decision variables include both binary and con- tinuous variables. The binary variable Xijkl indicates the assignment of an instructor to a course, class- room, and time slot. The binary variable Mjkl indi- cates the assignment of a multiple-instructor course to a classroom and time slot. The variable Yj indi- cates the extent to which a course is underassigned with respect to the required number of instructors. The binary variables Vis and Wiq indicate whether days or time slots are not available for assignments to individual instructors. Finally, the continuous vari- ables Zs , Uh , and Ri measure the underassignments for days, departments, and instructors, respectively. The objective function to maximize is the weighted sum of preferences of instructor for courses, class- rooms, and time slots less underassignment penalties for courses, days, departments, and instructors.
Constraint set (1) insures that each course is assigned the appropriate number of instructors or the underassignment is measured by Yj . Constraint set (2) insures that, if a classroom is made available at a given hour, at most one course is assigned to it, and if the classroom is not made available, no courses are assigned. Constraint set (3) handles the issues related to assigning an instructor to teach at a given hour. If, for a given instructor, the optimization eliminates the day corresponding to the hour, then Vis = 1; if the optimization eliminates the time slot corresponding to the hour, then Wiq = 1. In the case of a positive value for either Vis or Wiq, constraint (3) eliminates the pos- sibility of having the instructor assigned to teach at the given hour. Furthermore, having two X variables in the constraint eliminates the possibility of assigning back-to-back courses to the instructor (in case this has been specified as required). Constraint set (4) deals with the issue of courses that cannot be taught at the same time (even if taught by different instructors).
Constraint set (5) ensures that variable Zs measures the underassignment of courses on a given day. Con- straint set (6) enforces the condition that all but one of the time-slot groups for a given instructor is elim- inated. Constraint set (7) ensures that the number of binary variables Vis set equal to one (indicating the corresponding day is eliminated) is equal to the num- ber of days to be eliminated for a given instructor. Constraint set (8) ensures that Uh measures the under- assignment for a given department. Constraint set (9) ensures that each instructor is assigned the required number of courses or that the underassignment is
Binary variables: Continuous variables: Constraints:
Matrix nonzeroes:
1,900–2,400 10–150 1,600–1,900 13,000–17,000
When CPLEX solves the problem, solutions times are on the order of two to five seconds on a 600 MHz Pentium class PC, and often CPLEX finds and proves the optimum solution without the need for branch- ing by using problem reduction, Gomory cuts, and clique cuts.
The users of the system (the associate dean and the department chairpersons) assert that this approach improves the use of classroom space, assigning courses to classrooms whose seating capacity and other resources are closely matched with the require- ments for the course. Faculty members have to teach fewer courses outside of the home building of COB even though enrollments are growing. The time from the beginning to the end of the scheduling process has been cut by at least 50 percent. Department chairper- sons no longer face the resentment of faculty mem- bers who are dissatisfied with their assignments; they now understand the process is not personal. In most cases, faculty members who get poor assignments are given higher priority in schedules developed for the following academic term.
Appendix
Instructor-Course-Classroom-Time-Slot
Assignment Model
I formulated the instructor-course-classroom-time-slot assignment model so that it always possesses a fea- sible solution. However, a feasible solution may not
Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes 464 Interfaces34(6),pp.460–465,©2004INFORMS
measured by Ri. Finally, constraint set (10) requires that, if one or more instructors are assigned to multi- ple instructor course j in room k and time slot l, then Mjkl =1.
In the case of courses that are to be assigned multi- ple 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 pro- vides alternative assignments.
Index Sets
I = index set of instructors.
J = index set of courses.
JM =index set of courses that require the assign-
ment of more than one instructor. I j =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.
K i j =index set of classrooms acceptable for instructor i for course j.
L = index set of time slots.
L i j =index set of time slots acceptable for instruc-
tor i for course j. T = index set of hours.
S = index set of days.
L t = index set of time slots that include hour t. L s = 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.
G p = pth index set of courses that cannot be taught at the same time.
s t = day that includes hour t. H = index set of departments.
J h =index set of courses belonging to depart- ment h.
Qi = index set of time-slot groups for instructor i. q t = 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 class- room k for course j.
SlotPrefijl = 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 avail- able at hour t; 0 otherwise.
TeachDaysi = number of teaching days to be elimi- nated 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 unas- signed 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 class- room 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 depart-
ment h.
Vis = 1 if day s is eliminated for instructor i;
0 otherwise.
Wiq = 1 if time slot group q is eliminated for instruc-
tor i; 0 otherwise. Formulation
Max
CoursePrefij +RoomPrefijk iI jJ i kK i j lL i j
Xijkl +Xijk l iI jJ i kK i j lL i j L t
+Vis t +Wiq t 1 iI tT (3)
+ SlotPrefijl InstrImpi Xijkl
sS
DayPens Zs InstrPeni Ri
hH
iI subject to
iI j kK i j lL i j
Xijkl+Yj =InstrForCoursej
jJ (1)
Mjkl RoomAvailkt kK tT (2)
Xijkl +
iI jJ i JM lL i j L t
jJM lL t
Xijkl 1 pP tT (4) iI jJ i G p kK i j lL i j L t
CoursePenj Yj DeptPenh Uh
jJ
Martin: Ohio University’s College of Business Uses Integer Programming to Schedule Classes
Interfaces34(6),pp.460–465,©2004INFORMS 465
Xijkl+Zs Shih, W., J. Sullivan. 1977. Dynamic course scheduling for college faculty via zero-one programming. Decision Sci. 8(4) 711–721.
iI jJ i kK i j lL i j L s
MinCoursesPerDay sS (5) Wright, M. 2001. Subcost-guided search-experiments with time-
s tablingproblems.J.Heuristics7(3)251–260.
Wiq = Qi 1
iI iI
(6)
(7)
(8) iI (9)
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 sys- tem 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 elimi- nated complaints, rescheduling, and other conflicts.
“Ohio University assigns priority to certain class- room 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 appro- priate for each course offering; however, faculty pref- erences, 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 ourassociatedeaninschedulingandrescheduling classrooms was exceeded only by the aggravation level caused by the complaints that necessarily fol- lowed 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 plan- ning 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 consid- eration compensation and benefits. The real savings, however, is in the time that is saved through the elim- ination of faculty complaint and consternation.
“I am very pleased with the system that Professor Martin developed, and we are continuing to experi- enceitsbenefits.”
sS
qQj
Vis =TeachDaysi
Yj Uh MaxUnAsgnCoursesh
jJ h
hH
Xijkl +Ri =CoursesForInstri X M 0 iI jJ i JM
jJ i kK i j lL i j
ijkl jkl
kK i j lL i j (10) Xjkl Mjkl Vis and Wiq =0 or 1
Zs Yj Ri and Uh0
References
Baker, K., M. Magazine, G. Polak. 2002. Optimal block designs mod- elsforcoursetimetabling.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 prob- lemhard?Oper.Res.40(1S)28–39.
Deris, S., S. Omatu, H. Ohta. 2000. Timetable planning using theconstraint-basedreasoning.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 com- pactnessconstraintsinschooltimetabling.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 assign- ing 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 Intel- ligence Rev. 13(2) 87–127.
Schmidt, G., T. Strohlein. 1979. Timetable construction—An anno- tatedbibliography.Comput.J.23(4)307–316.
Constraint Mathematical Expression . Meaning Insures that each course is assigned that appropriate number of instructors or the xiikl +Y,-InstrForCourse ,EJ under assignment is measured by 2 NOTE: Iused the MS Equation Editor to create the mathematical formulation above. Use the help documentation to learn how MS Equation Editor can be used to produce equations such as the ones in the article.Explanation / Answer
1.)
Motivation of the research was to prepare the university lecture schedule given the multiple real life problems like a professor can’t take back to back classes, or take multiple lectures at a time, max number of teaching days, multiple instructors for the courses, assignment of classroom to course and instructor etc.
The earlier approach didn't properly optimize the use of home building classrooms of department and the enrollment numbers were increasing, so a need was felt for this.
2.)
Objective -
X (C, I, L, T) - X is 1 if the course C is taught by instructor I in lecture hall L at time T, otherwise 0
Objective is to make sure the required Xs are 1
Constraints -
Some obvious restrictions exist:
(A) An instructor should be assigned required number of courses & can't teach more than 1 course at a time.
(2) A classroom cannot hold more than one course at a time.
(3) As many courses as possible should be assigned to classrooms & time slots available in home building.
Other than these, there are real life constraints as well like
Instructors have preferences for courses, classrooms, and time slots.
Not too many departmental courses can be run together to make students choose between courses etc.
3.)
The implentation was huge success, and all the scheduling since then was done using this methodology. More classes were held in departmental building. Happy instructor to get favorite classrooms, slots, courses. Better use of classrooms specially the bigger ones.
4.)
I have been on chegg since last 10 days and I have solved some 50 optimization problems ranging from what raw materials to buy for bakery to deliver different biscuits to oil rig optimization to soup import and distribution to reduce cost. At heart, all the problems are to make lives simpler in terms of reducing costs, increasing profits. better allottment of resoruces, scheduling of manufacturing etc.
It is humanly impossible sometime to consider all the combination and choose best out of them. Optimization using linear programming (and non linear programming) is the most used, connected and with direct impact to real world scenarios I have ever encoutered in my all professional life. I will give you an example. In the beginning of my career as management consultant to the biggest beverage company, I was asked to create the planogram of coolers i.e. to suggest which products should be put in the cooler in what order and number. And linear programming was the saviour. Linear programming is nothing but a easy method to consider all the possible combinations and choose the best suited to our requirements.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.