3.1 Verbal Formulation of the Mathematical Model
Imagine that we have a set of 10 schools to be assigned to 10 teachers. In order to determine a mathematical model, we need to define the following variables:
assign (1, 1) = 1 if teacher 1 is assigned to school 1
= 0 otherwise
assign (1, 2) = 1 if teacher 1 is assigned to school 2
= 0 otherwise
etc.
Note that each of these variables can take on the value of 0 (if the assignment is not made) or 1 (if the assignment) is made.
In addition to the above variables, we need the following parameters:
utility (1,1) = the utility derived by assigning teacher 1 to school 1 expressed as a score determining by the scoring system. etc.
Max_school (i) = Maximum number of schools that teacher i may attend
Max_teacher (j) = Maximum number of teachers that school j may hire
3.2 Basic Formulation
Maximize:
utility(1,1) * assign(1,1) + utility(1,2) * assign(1,2) + .... + utility(10,10) * assign(10,10)
Subject to:
assign(i, 1) + assign(i,2) + ..... +assign(i,10) = Max_school (i)
No more than the maximum number of school are taught by teacher i
assign(1,j) + assign(2,j) + ..... +assign(10,j) = Max_teacher (j)
No more than the maximum number of teachers are hired by school j
Each variable assign(i,j) is (0 or 1)
3.3 Solution Summary
The optimal solution to the relaxed problem is:
|
school teacher |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
|
|
|
|
|
|
|
|
x |
|
|
2 |
x |
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
x |
|
|
|
4 |
|
|
|
|
|
x |
|
|
|
|
|
5 |
|
|
|
|
|
|
x |
|
|
|
|
6 |
|
|
x |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
x |
|
8 |
|
|
|
|
x |
|
|
|
|
|
|
9 |
|
|
|
x |
|
|
|
|
|
|
|
10 |
|
x |
|
|
|
|
|
|
|
|
With a total score of utility of 698.
3.4 Mathematical Model
3.4.1 Assumptions
3.4.2 Index Sets and Variables
I: The set of 10 teachers
J: The set of 10 schools
X(I,J) is the assignment of teacher I to school J
U(I,J) is the utility of teacher I with school J
Z: The objective function
3.4.3 Data
The following data is obtained by from the result of a survey, on which each teacher must rank the 10 schools according to their preferences, from 1 to 10, where 1 indicates the least preferred, and 10 indicates the most preferred. Similar data is also obtained by survey the 10 schools on these teachers. The results are then combined by multiplying the scores for each school-teacher pair, which forms the basis of the data of our study.
Preferences of Schools by Each Teacher:
Teacher
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
|
1 |
10 |
8 |
2 |
2 |
8 |
7 |
8 |
2 |
2 |
1 |
|
|
2 |
2 |
10 |
8 |
5 |
5 |
6 |
9 |
1 |
10 |
9 |
|
|
3 |
5 |
1 |
9 |
8 |
3 |
9 |
6 |
3 |
7 |
4 |
|
|
4 |
8 |
3 |
1 |
3 |
4 |
3 |
5 |
4 |
5 |
10 |
|
|
School |
5 |
4 |
4 |
7 |
6 |
7 |
8 |
1 |
9 |
8 |
3 |
|
6 |
7 |
6 |
5 |
9 |
10 |
5 |
7 |
8 |
3 |
2 |
|
|
7 |
3 |
5 |
4 |
4 |
9 |
2 |
4 |
5 |
1 |
5 |
|
|
8 |
6 |
7 |
6 |
10 |
2 |
1 |
3 |
10 |
6 |
6 |
|
|
9 |
9 |
9 |
10 |
1 |
1 |
10 |
2 |
6 |
4 |
8 |
|
|
10 |
1 |
2 |
3 |
7 |
6 |
4 |
10 |
7 |
9 |
7 |
Evaluation of Teacher's performance by Each School:
School
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
|
1 |
1 |
2 |
3 |
7 |
6 |
4 |
10 |
7 |
9 |
7 |
|
|
2 |
4 |
4 |
7 |
6 |
7 |
8 |
1 |
9 |
8 |
3 |
|
|
3 |
7 |
6 |
5 |
9 |
10 |
5 |
7 |
8 |
4 |
2 |
|
|
4 |
10 |
8 |
2 |
2 |
8 |
7 |
8 |
2 |
2 |
1 |
|
|
Teacher |
5 |
2 |
10 |
8 |
5 |
5 |
6 |
9 |
1 |
10 |
9 |
|
6 |
5 |
1 |
9 |
8 |
3 |
9 |
6 |
3 |
7 |
4 |
|
|
7 |
8 |
3 |
1 |
3 |
4 |
3 |
5 |
4 |
5 |
10 |
|
|
8 |
3 |
5 |
4 |
4 |
9 |
2 |
4 |
5 |
1 |
5 |
|
|
9 |
6 |
7 |
6 |
10 |
2 |
1 |
3 |
10 |
6 |
6 |
|
|
10 |
9 |
9 |
10 |
1 |
1 |
10 |
2 |
6 |
3 |
8 |
Combined score of the teachers' and schools' preference
School
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
|
1 |
10 |
4 |
15 |
56 |
24 |
28 |
30 |
42 |
81 |
7 |
|
|
2 |
32 |
40 |
7 |
18 |
28 |
48 |
5 |
63 |
72 |
6 |
|
|
3 |
14 |
48 |
45 |
9 |
70 |
25 |
28 |
48 |
40 |
6 |
|
|
4 |
20 |
40 |
16 |
6 |
48 |
63 |
32 |
20 |
2 |
7 |
|
|
Teacher |
5 |
16 |
50 |
24 |
20 |
35 |
60 |
81 |
2 |
10 |
54 |
|
6 |
35 |
6 |
81 |
24 |
24 |
45 |
12 |
3 |
70 |
16 |
|
|
7 |
64 |
27 |
6 |
15 |
4 |
21 |
20 |
12 |
10 |
100 |
|
|
8 |
6 |
5 |
12 |
16 |
81 |
16 |
20 |
50 |
6 |
35 |
|
|
9 |
12 |
70 |
42 |
50 |
16 |
3 |
3 |
60 |
24 |
54 |
|
|
10 |
9 |
81 |
40 |
10 |
3 |
20 |
10 |
36 |
24 |
56 |
3.4.4 Program
Objective Function
Maximize: S(i,j) uij*xij
Constraints
S(j) xij = 1 for all i
No more than 1 school is taught by teacher i
S(i) xij = 1for all j
No more than the 1 teacher assigned to school j
xij = 0 or 1 for all i, j
4.1 Verbal Formulation of the Mathematical Model
In the original problem, 10 teachers are assigned to two sessions at 10 different schools. Also, in this case, we take into account the requirement that each teacher must go to a different school in the morning and in the afternoon session.
Our goal is to develop a model which determines how to assign teachers to the different sessions at different schools, subject to the following requirements:
- Each teacher is assigned to no more than one school in each session
- Each session at a particular school is taught by exactly one teacher
- Each teacher must go to a different school in the morning and in the afternoon session
In this problem, a new index must be defined to indicate the two different sessions. Basically, we have a set of two sessions (a.m., p.m.) at 10 schools that must be assigned to 10 teachers. In order to determine a mathematical model, we need to define the following variables:
assign (1, am, 1) = 1 if teacher 1 is assigned to the morning session at school 1
= 0 otherwise
assign (1, am, 2) = 1 if teacher 1 is assigned to the morning session at school 2
= 0 otherwise
etc.
Note that each of these variables can take on the value of 0 (if the assignment is not made) or 1 (if the assignment) is made.
In addition to the above variables, we need the following parameters:
utility (1,am, 1) = the utility derived by assigning teacher 1 to school 1 expressed as a score determining by the scoring system.
etc.
Max_school_am (i, am) = Max. # of morning session teacher i may attend
Max_school_pm (i, pm) = Max. # of afternoon session teacher i may attend
Max_teacher_am (am, j) = Max. # of teacher assigned to each morning session
at school j
Max_teacher_pm (pm, j) = Max. # of teacher assigned to each afternoon session
at school j
4.2 Basic Formulation
Maximize:
utility(1, am, 1) * assign(1, am,1) + utility(1, am, 2) * assign(1, am, 2) + ....
+ utility(10, pm, 10) * assign(10, pm, 10)
Subject to:
assign(i, am, 1) + assign(i, am, 2) + ..... +assign(i, am, 10) = Max_school_am (i, am)
No more than the maximum number of morning session are taught by teacher i
assign(i, pm, 1) + assign(i, pm, 2) + ..... +assign(i, pm, 10) = Max_school_pm (i, pm)
No more than the maximum number of afternoon session are taught by teacher i
assign(1, am, j) + assign(2, am, j) + ..... +assign(10, am, j) = Max_teacher_am (am, j)
No more than the maximum number of teachers are assigned to the morning session at school j
assign(1, pm, j) + assign(2, pm, j) + ..... +assign(10, pm, j) = Max_teacher_pm (pm, j)
No more than the maximum number of teachers are assigned to the afternoon session at school j
assign (i, pm, j) £ 1- assign (i, am, j)
Ensure that each teacher attends the morning and afternoon sessions at different school.
Note that if teacher i is already assigned to the morning session at school j, the value for assign (i, am, j) will be 1. The above equation has the effect of enforcing assign (i, pm, j) to be 0 and hence ensures that the teacher is not assigned to the afternoon session at the same school
Each variable assign(i,k,j) is (0 or 1)
4.3 Solution Summary
The optimal solution to the original problem:
|
school teacher |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
|
|
|
A |
|
|
|
|
P |
|
|
2 |
|
|
|
|
|
|
|
P |
A |
|
|
3 |
|
|
P |
|
A |
|
|
|
|
|
|
4 |
|
|
|
|
|
A |
P |
|
|
|
|
5 |
|
|
|
|
|
P |
A |
|
|
|
|
6 |
P |
|
A |
|
|
|
|
|
|
|
|
7 |
A |
|
|
|
|
|
|
|
|
P |
|
8 |
|
|
|
|
P |
|
|
A |
|
|
|
9 |
|
A |
|
P |
|
|
|
|
|
|
|
10 |
|
P |
|
|
|
|
|
|
|
A |
With the optimal objective value of 1291.
4.4 Mathematical Model
4.4.1 Assumptions
4.4.2 Index Sets and Variables
I: The set of 10 teachers
J: The set of 10 schools
K: The set of two different sessions
X(I,K,J) is the assignment of teacher I to the session K at school J
U(I,K,J) is the utility of teacher I teaching session K at school
Z: The objective function
4.4.3 Data
See Data for the relaxed problem as outlined in subsection 3.4.3.
4.4.4 Program
Objective Function
Maximize: S(i,k,j) uikj*xikj
Constraints
S(k,j) xikj = 1 for all k,j
No more than 1 teacher is assigned to the k session at school j
S(i,k) xikj = 1 for all i,k
No more than 1 session at school j is assigned to the teacher i
x(i, pm, j) £ 1- x(i, am, j)
Ensure that teacher i is not assigned to the afternoon session at the same school
xikj = 0 or 1 for all i, k,j