by
Gloria Au
Shirley Chan
Wendy Chan
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:
If you have any comments about this homepage, please email to:
s4chan@descartes.uwaterloo.ca
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.
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 ?
Ans.:- An assignment problem is a special case of the transportation problem where the binary variables Xij's are relaxed to continuous functions which range from 0 to 1.
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.
What are the requirements ?
How does the preference ranking work ?
How are the preferences being converted to modelling (GAMS) table ?
How to go about modelling the problem ?
How to incorporate the different schools requirement for the morning and afternoon periods ?
How to interpret the solution results?
In addition to the core requirements, there are two common concerns arising from the core problem:
An extended model is also developed to address these 2 concerns. They can be incorporated in the model by:
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: 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 ?
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:
Conclusion:
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:
Conclusion:
Sensitivity Analysis On Our Core Problem
What is it ?
Effects of Changes in Preference Rankings:
Introducing a pair of new school and teacher:
Perturbations in Right-Hand Side (RHS) constraints:
Under MIP Model:
Under the relaxed LP Model:
Under another setup of the problem:
Conclusion :
Other possible enhancements
These additional features to the current proposal could be developed in the future.
The 4 preference ranking forms are :
The End !!