Solution to Scheduling Professors1
Three professors must be assigned to teach six sections of finance. Each professor must teach two sections of finance, and each has ranked the six time periods during which finance is taught, as shown in the table below. A rating of 10 means that the professor wants to teach at that time, and a ranking of 1 means that he or she does not want to teach at that time.
|
9 A.M.
|
10 A.M.
|
11 A.M.
|
1 P.M.
|
2 P.M.
|
3 P.M.
|
Professor 1
|
8
|
7
|
6
|
5
|
7
|
6
|
Professor 2
|
9
|
9
|
8
|
8
|
4
|
4
|
Professor 3
|
7
|
6
|
5
|
6
|
9
|
5
|
Preferences for Teaching Problem
Determine an assignment of professors to sections that maximizes the total satisfaction of the professors.
Managerial Formulation
Decision Variables
We need to identify who is teaching which class. In other words, we need to make one-to-one links between the classes to be taught and the available professors.
Objective
Maximize total satisfaction (although we haven’t figured out yet how to quantify that).
Constraints
All classes need to be covered by exactly one professor.
Each professor needs to be assigned to exactly two classes.
Mathematical Formulation
Decision Variables
Define Xij to be a binary variable representing the assignment of professor i to class j. If professor i ends up teaching class j, then Xij = 1. If professor i does not end up teaching class j, then Xij = 0.
Define Cij to be the “preference” score of professor i for class j.
Objective
Maximize Z =
Constraints
for all j.
for all i.
Notes:
-
The objective function uses the nice attributes of binary variables to create an overall measure of “professorial delight”. If a professor is assigned to a class for which he/she has a preference score of 6, for example, then the six gets multiplied by a one (6 x 1 = 6) and gets added into the overall objective score. If the professor is not assigned to that class, then the six gets multiplied by a zero (6 x 0 = 0) and has no effect on the overall objective.
-
These constraints are not exactly like the “English” versions; in particular they are not as “strict”. For example, the first constraint seems to imply that more than one professor could feasibly be assigned to a class. The second constraint implies that a professor could feasibly be assigned to fewer than two classes. That’s OK, because the two constraints together force exactly one professor per class, and two classes per professor.
-
It is not necessary to constrain the decision variables to be binary; the optimal linear solution will automatically have zeros and ones for the decision variables.
Solution Methodology
Here’s the spreadsheet model:
Conclusion
In the optimal solution, professor 1 teaches at 9:00 and 3:00, professor 2 teaches at 10:00 and 11:00, and professor 3 teaches at 1:00 and 2:00.
The maximum overall preference score is 46.
This problem is an example of an entire category of classic operations research models called network flow problems, so called because they can be represented as networks of nodes (balls) and arcs (arrows). For example, the nodes in this diagram can be used to represent the professor-scheduling problem.
One important sub-category of network flow problems is transportation problems, centering on the problem of distributing products from multiple points of supply to multiple points of demand2. In this case, the professors (green nodes) are called “source” or “supply” nodes, and the class times (blue nodes) are called “destination” or “demand” nodes. Here is our optimal solution, with the assignments of professors to classes represented by arcs:
Dostları ilə paylaş: |