• What is an assignment problem ?
• Why is this worth noting ?
• How is this being modelled ?
• What is an application of the theory ?
• What are the effects of small changes to the data set on the optimal solutions ?

Here's the answers!!

Introduction - The 4 W's (What, When, Why, Who)

From the Operation Research's Perspective

Step-by-step Demonstration of the Problem

H o p e Y o u H a v e E n jo ye d T h i s I n tro d uc t io n To A n A s s ig n ment P ro b l e m!!

For further assignment-related problems or network problems, please visit:

The C&O 370 Homepage

If you have any comments about this homepage, please email to:

s4chan@descartes.uwaterloo.ca

 Introduction - The 4 W's

 WHAT is a typical assignment problem?

Ans.:- A typical assignment problem can be used to allocate n resources to n function groups in order to maximize total profits from respective use of resources or to optimize total satisfaction from the allocation preferences.

 

WHY is this worth noting?

Ans.:- This type of assignment problem is prevalent in various industries and organizational unit. Organizations are constantly finding ways to utilize their resources more efficiently and effectively.

 

WHEN does this occur?

Ans.:- Assignment problems are encountered frequently in virtually every aspect of life. For instance, they span from allocating time (e.g. hours) to various tasks for a person, matching job applicants to employers, to any sort of allocation of human/ financial/ physical resources among various departments/ units in any organization.

 

WHO encounters such problem?

Ans.:- Everyone & every organization.

 

Go Back HOME

From The Operation Research Perspective

What are the special characteristics of an assignment problem?

Ans.:- An assignment problem is an integer program where the decision variables Xij's are binary variables of 1 or 0 indicating assignment or no assignment respectively. The constraints restrict exactly one assignment for each of the source (e.g. resource) and destination (e.g. demand) nodes.

 

How to model an assignment problem?

Ans.:- The basic assignment problem is to maximize the total profits or satisfaction generated from the assignments, subject to constraints of exactly one assignment for every source and every destination. The mathematical representation is as follows:

Max z = åi åj cij Xij,

s.t. åj Xij = 1 (i = 1,2,..,n)

åi Xij = 1 (j = 1,2,.., n)

Xij = 0 or 1

 

 

What category does an assignment problem fit in ?

Step-By-Step Demonstration Of The Problem

To illustrate a concrete application to the assignment problem, we construct a teacher-to-school assignment problem that would be encountered in a hypothetical school board where each teacher is to be assigned to a morning and an afternoon period in two different schools. This special requirement of different school assignments in morning and afternoon periods for each teacher adds some complexity to the basic problem as demonstrated below.

• The Core Problem
• The Approach - How?
• Special Features
• The Models to i) the Core Problem & ii) the Extended Problem
• The Results
• Sensitivity Analysis
• Other Possible Enhancements

Go Back HOME

The Core Problem

What are the requirements ?

• In a school district of 10 schools, 10 special education teachers are to be assigned to different schools based on preferences of teachers and schools.

• Each teacher has to spend the morning period in one school and the afternoon period in another.

Go To Step-by-Step Demo

Go Back HOME

The Approach - How??

How does the preference ranking work ?

• Preference Rankings are to be received from both schools and teachers.

• These preferences are ranked according to the specific guidelines on a prescribed Preference Form.

How are the preferences being converted to modelling (GAMS) table ?

• Each ranking preference form corresponds to a row (for each teacher) or a column (for each school) in GAMS tables for morning or afternoon periods, which are ready for use by the model to solve the problem.

• Thus, there are 4 tables, corresponding to teachers' and schools' preferences for morning and afternoon periods respectively.

How to go about modelling the problem ?

• Operation Research Mixed-Integer-Programming (MIP) models with 2 sets of binary variables Xij's and Yik's using GAMS software are developed to solve the problem.

• The model is to maximize the combined ranking preferences of the teachers and the schools.

• Xij's depict assignments in the morning period and Yik's depict assignments in the afternoon period.

How to incorporate the different schools requirement for the morning and afternoon periods ?

• A mapping table (replaced by a distance table in the extended model) is used to disallow assignment of a teacher to the same school for both morning and afternoon periods. The disallowance is enforced by Constraint 5 of the Core Model.

How to interpret the solution results?

• An assignment value of 1 indicates assignment between the teacher and the school, while an assignment value of 0 indicates no assignment between the teacher and the school.

Go To Step-by-Step Demo

Go Back HOME

Special Features

In addition to the core requirements, there are two common concerns arising from the core problem:

1. Distance between the schools for morning and afternoon assignments
2. Rejections ("unwanted choices") from either the teachers or the schools, (up to a max. of 3 rejections)

An extended model is also developed to address these 2 concerns. They can be incorporated in the model by:

• adding a distance table and a constraint to ensure that only schools within reasonable distance apart could be assigned to each teacher for the morning and afternoon periods. This restriction is enforced by Constraint 6 in the Extended Model.

• adding 4 logical constraints Constraints 7 - 10 in the Extended Model which gives a zero assignment value (i.e. no assignment of a teacher to a school) whenever a preference of zero is ranked by either the teacher or the school.

Go To Step-by-Step Demo

Go Back HOME

The Core Model

Objective Function: Max [ Si Sj tm ij x ij + Si Sk ta ik y ik + Si Sj sm ij x ij + Si Sk sa ik y ik ]

Constraint 1: åj x ij = 1 for i = T1, T2, ...................., T10

Constraint 2: åk y ik = 1 for i = T1, T2, ...................., T10

Constraint 3: åi x ij = 1 for j = S1, S2, ...................., S10

Constraint 4: åi y ik = 1 for k = S1, S2, ...................., S10

Constraint 5: x ij + y ik < = m jk + 1 for

i = T1, T2, ...................., T10

j = S1, S2, ...................., S10

k = S1, S2, ...................., S10

How to interpret the Core Problem ?

Objective Function:

• maximizes the combined teachers' and schools' preferences for the morning and the afternoon periods of the assignments

 Constraints 1 & (2):

• restrict each teacher i to be assigned to exactly one school j (k) in the morning (afternoon) period

Constraints 3 & (4):

• restrict each school j (k) to be assigned to exactly one teacher i in the morning (afternoon) period.

Constraint 5: (logical)

• disallows the same school to be matched to a teacher in both the morning and afternoon periods, as xij and yik cannot both equal to 1 when school j = school k.

Go To Step-by-Step Demo

Go Back HOME

The Extended Model

Objective Function: Max [ Si Sj tm ij x ij + Si Sk ta ik y ik + Si Sj sm ij x ij + Si Sk sa ik y ik ]

 Constraint 1: åj x ij <= 1 for i = T1, T2, ...................., T10

 Constraint 2: åk y ik <= 1 for i = T1, T2, ...................., T10

 Constraint 3: åi x ij <= 1 for j = S1, S2, ...................., S10

Constraint 4: åi y ik <= 1 for k = S1, S2, ...................., S10

Constraint 5: x ij + y ik < = d jk + 1 for

i = T1, T2, ...................., T10

j = S1, S2, ...................., S10

k = S1, S2, ...................., S10

Constraint 6: If djk > 50, then xij + yik <= 1 for all i, j and k.

Constraint 7: xij <= tm ij for all i, j

Constraint 8: yik <= ta ik for all i, k

Constraint 9: xij <= sm ij for all i, j

Constraint 10: yik <= sa ik for all i, k

How to interpret the Extended Problem ?

Objective Function:

• Same as the core problem. See objective function of the core problem for further explanation.

 Constraints 1 to 4:

• these inequalities restrict each teacher to be assigned to at most one school and vice versa
• also handles the case where the number of schools is different from the number of teachers.

 Constraint 5:

• essentially the same as constraint 5 in the core problem with M(J,K) being replaced by D(J,K)

 Constraint 6:

• ensures that a teacher would not be assigned to schools that are apart over a pre-defined distance limit
• Whenever the distance between schools > the pre-defined limit on distance, this constraint disallows xij and yik to be 1 at the same time (for the same teacher i).

 Constraints 7 to 10:

• ensure that no schools or teachers will be assigned to their unwanted choices.
• Whenever a ranking preference equals 0, the applicable inequality constraint restricts the L.H.S variable to be 0.

Go To Step-by-Step Demo

Go Back HOME

SOLUTION SUMMARY

Based on a set of test data of ranking preferences (assumed being received from a school board), our model gives the optimal assignments for each teacher and school.

What are the results from our core model?

Teacher <->School in the Morning Period <-> School in the Afternoon Period

T1 - Ms. A. Bennett <-> S5 - Crispy College <-> S2 - St. Thomas H.S.

T2 - Mr. H. Burger <-> S1 - J. Campbell C.I. <-> S10 - B. Leslie C.I.

T3 - Ms. C. Junior <-> S3 - The Toronto C.I. <-> S4 - Midfield C.I.

T4 - Ms. I. Lee <-> S2 - St. Thomas H.S. <-> S1 - J. Campbell C.I.

T5 - Mr. M. Levy <-> S9 - Warren Watt H.S. <-> S6 - JVC Int'l H.S.

T6 - Mr. P. MacDonald <-> S4 - Midfield C.I. <-> S3 - The Toronto C.I.

T7 - Mr. W. Simpson <-> S10 - B. Leslie C.I. <-> S5 - Crispy College

T8 - Ms. L. Simpson <-> S8 - Woolburn C.I. <-> S9 - Warren Watt H.S.

T9 - Mr. T. Smith <-> S6 - JVC Int'l H.S. <-> S7 - Sir Charles C.I.

T10 - Ms. D. Tong <-> S7 - Sir Charles C.I. <-> S8 - Woolburn C.I.

The Maximized Value of the Combined Preferences From Teachers and Schools

(The Optimal Value) equals 336. This implies that the best assignment combination assigns teachers and

schools to their third highest preference on average (or ranking value of 8 [=336/40]).

Observations From The Test Data:

• One teacher is assigned to each school for each of the morning and afternoon period

• Each teacher is allocated to two different schools for the morning and afternoon period.

Conclusion:

• Thus, the core model satisfies all our specifications and criteria.

What Is The Results From Our Extended Model?

Teacher <->School in the Morning Period <-> School in the Afternoon Period <-> Distance between schools (km)

T1 - Ms. A. Bennett <-> S5 - Crispy College <-> S2- St. Thomas H.S. <-> 5

T2 - Mr. H. Burger <-> S2 - St. Thomas H.S. <-> S10 - B. Leslie C.I.<-> 5

T3 - Ms. C. Junior <-> S3 - The Toronto C.I. <-> S4 - Midfield C.I. <-> 5

T4 - Ms. I. Lee <-> S4 - Midfield C.I. <-> S1 - J. Campbell C.I. <-> 15

T5 - Mr. M. Levy <-> S9 - Warren Watt H.S. <-> S6 - JVC Int'l H.S. <-> 10

T6 - Mr. P. MacDonald <-> S7 - Sir Charles C.I. <-> S3 - The Toronto C.I. <-> 50

T7 - Mr. W. Simpson <-> S10 - B. Leslie C.I. <-> S5 - Crispy College <-> 30

T8 - Ms. L. Simpson <-> S8 - Woolburn C.I. <-> S9 - Warren Watt H.S. <-> 40

T9 - Mr. T. Smith <-> S6 - JVC Int'l H.S. <-> S7 - Sir Charles C.I. <-> 20

T10 - Ms. D. Tong <-> S1 - J. Campbell C.I. <-> S8 - Woolburn C.I. <-> 10

The Maximized Value of the Summation of All Preferences From Teachers and Schools

(Objective Value) equals 335. This implies that the best assignment combination assigns teachers and

schools to their third highest preference on average (or ranking value of 8 [=335/40]).

Observations From The Test Data:

• A maximum of one teacher is assigned to schools for each of the morning and afternoon period

• Teachers are allocated to two different schools which are within the school board's pre-defined limit of 50km on distance for the morning and afternoon periods.

• For teachers or schools which are given a preference ranking of zero by all schools or teachers, no assignment would be given.

Conclusion:

• Thus, the extended problem satisfies all craters and the two additional considerations.

Go To Step-by-Step Demo

 Go Back HOME

Sensitivity Analysis On Our Core Problem

What is it ?

• Sensitivity analysis is often useful in identifying the ranges of small changes in a constraint or in the objective coefficients (for instance, preferences in the teacher-school assignment problem) in the original problem for which the optimal results remain unchanged.

Effects of Changes in Preference Rankings:

• Impossible to perform meaningful analysis.

• Why? Each change in one preference ranking value will affect all other rankings on a preference ranking form.

Introducing a pair of new school and teacher:

• A different optimal solution to the original assignment problem will result.

• The optimal total preference value would increase with the extra preference rankings for the additional new pair of teacher and school. Yet, the average preference value could either increase or decrease.

Perturbations in Right-Hand Side (RHS) constraints:

Under MIP Model:

• Problem becomes infeasible by adding/ subtracting a fractional change to the RHS because of the use of binary variables

• If RHS is changed by 1, the problem no longer addresses the same specifications as in the core problem.

Under the relaxed LP Model:

• The existence of a logical constraint makes sensitivity analysis impossible to be performed, even if the binary variables are relaxed to become continuous variables within 0 to 1.

Under another setup of the problem:

• unable to re-model the problem in another network format.

Conclusion :

• Sensitivity analysis in the teacher-to-school assignment problem is not only difficult to perform, but also impossible to offer relevant information as demonstrated.

Go To Step-by-Step Demo

Go Back HOME

Other possible enhancements

• Teachers and schools may give equal preference ranking among some choices.

• Both teachers and schools could have some specific combination of preference for morning and afternoon period assignments to accommodate their various needs, such as reduction of preparation time by teachers because of similar syllabus.

• Priority preference is given to schools over teachers when a tie in the total preference of a school and a teacher occurs.

These additional features to the current proposal could be developed in the future.

Go To Step-by-Step Demo

Go Back HOME

 Preference Ranking Forms

• All preferences of the schools and teachers are to be collected via the use of the following 4 preference ranking forms intended for the specific model used (either the core or the extended) by the school board.

• Each teacher and each school are requested to fill one preference ranking form which considers both their morning and afternoon periods' preferences.

• If only one set of preferences are given, the model assumes the same set of preferences to be used for both the morning and afternoon periods.

• All completed forms are verified by the school board in order to ensure that they are filled out correctly before converting into the model data.

The 4 preference ranking forms are :

•  School Preference Ranking Form (to be used for the Core model)
• School Preference Ranking Form (to be used for the Extended model)

•  Teacher Preference Ranking Form (to be used for the Core model)
• Teacher Preference Ranking Form (to be used for the Extended model)

Go To Step-by-Step Demo

Go Back HOME

 The End !!