Solution Summary

 

The optimal solution to extended problem #4:

 

 

school

teacher

1

2

3

4

5

6

7

8

9

10

1

 

 

 

 

 

 

P

A

 

P

2

 

 

 

 

 

 

A

 

P

 

3

 

 

 

 

A

 

 

P

 

 

4

P

A

 

 

 

 

 

 

 

 

5

 

 

 

 

 

A

 

 

 

 

6

 

 

A

P

 

 

 

 

A

 

7

A

 

P

 

 

 

 

 

 

 

8

 

 

 

 

P

 

 

 

 

 

9

 

P

 

A

 

 

 

 

 

 

10

 

 

 

 

 

P

 

 

 

A

 

With the optimal objective value of 1425.

 

Note that the optimal objective value is greater than that of the core problem, since there is more flexibility in assigning the teachers to the schools.

 

 

Mathematical Model

 

Assumptions

Assume those teachers who are teaching in schools open on Monday and Wednesday only can also be assigned to those schools open on Tuesday and Thursday.

 

Index Sets and Variables

Two subsets must be defined to separate the schools that operates on different days of the week:

MW(J) includes set of schools that are open on Mondays and Wednesdays.

TT(J) includes set of schools that are open on Tuesdays and Thursdays.

 

Data

Scalars are introduced to specify the maximum number of classes that two types of teachers are willing to teach.

 

Also, as mentioned above, a indicator parameter Yi is introduced to indicate whether teacher I is willing to teach overtime. In specific, Yi = 1 if teacher I is willing to teach overtime, and Yi = 0 if teacher I is not willing to teach overtime. That is,

Y = (1, 0, 1, 0, 0, 1, 1, 0, 1, 0)t

 

Other data is the same as in the core problem.

 

 

Program

The objective function is the same as that of the core problem.

 

The additional constraint regarding the overtime flexibility is implemented as follows:

 

S(k,j) xikj £ ((Y(i)*overtime)+((1-Y(i))*regular)), for all i

 

where overtime denotes the maximum classes an overtime teacher is allowed to teach, and regular is the maximum classes a regular teacher will teach. In our case, they are assumed to be 3 and 2 respectively.

 

Note that the above constraint can be interpreted as follows:

 

If teacher i is willing to teach overtime, then Y(i) = 1, and the constraint will simplify to S(k,j) xikj £ overtime. If, however, teacher i is not willing to teach overtime, then Y(i) = 0, and the constraint becomes S(k,j) xikj £ regular.

 

To ensure that no teacher is assigned to two places at the same time of the same day of the week, an extra constraint is added:

 

S(j) xikj £ 1 for j Í MW, k = am, pm, for each i.

 

A similar constraint is added for j Í TT.