As a consultant for the Board of Education for the City of Ortown, we are responsible to provide advice as to how to best allocate 10 special education teachers to 10 different schools. One of the specifications is that each teacher is to spend the morning period in one school and the afternoon period in another. In addition, we have to take into account the teachers' preferences for each school, and conversely, each school's preference for the teacher, when designing the most optimal assignment of the teachers.

The extension of the core problem includes:
1) Different preferences for morning and afternoon session.
2) Restricting a special group of teachers to a special set of school.
3) Incorporating the reimbursement of travelling costs.
4) Allow teachers to teach extra classes and taking into account the distance between morning and afternoon class.
5) Restriction on distance travelled between sessions.

Sensitivity Anlaysis is also performed to determine the impact of changes in the data on the optmal assignment.

First, we will take a look the different models for assignment problem.

Theoretical Background of the Assignment Problem

The related problem can be formulated as:

which can be solved by the network simplex method. As shown on the diagram, the network has a source ui with a unit supply for each teacher i, and a sink vj for each school j. The score on each arc ui vj is -sij which is shown on the arc connecting ui and vj.

The problem reflects a situations where the overall satisfaction of the assignment is measured by the worst score resulted from a particular match. Consider the following algorithm of solving the network problem:

1. Let M consist of the arcs u1v1, u2v2, ....u10v10.
2. Let t be the smallest of the 10 scores sij such that uivj e M.
3. If Gt contains no matching M* of size 10, then stop: M represents an optimal solution. Otherwise replace M by M* and return to step 1

In fact, this algorithm to the development of a bottleneck assignment problem which can be shown to be equivalent of finding the largest matching in a bipartite graph.

On the next page, first we will take a look at the relaxed model or the simpler model. It helps us to understanding better on the general structure of the assignment problem before we go to the original problem. Then we further examine the original problem take in to accont of each teacher must go to a different school in the mornng and in the afternoon session. Please click on the right arrow to look at the relaxed model and the original model.

Introduction Relaxed and Original Model