Solution to Scheduling Professors

Solution to Scheduling Professors¹

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 X_ij to be a binary variable representing the assignment of professor i to class j. If professor i ends up teaching class j, then X_ij = 1. If professor i does not end up teaching class j, then X_ij = 0.

Define C_ij 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 demand². 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:

1 Based on 5-74 (p. 269) in Practical Management Science (2^nd ed., Winston and Albright, 2001 Duxbury Press). Solution by David Juran, 2001.

2 These problems were originally studied by management scientists such as F. L. Hitchcock, T. C. Koopmans, G. B. Danzig, W. W. Cooper, and A. Charnes in the 1940s and 1950s.