Scheduler model

I created a scheduler to schedule librarians at a reference desk, in two parts: the front end was an Excel spreadsheet that did basic consistency checking, and the back end ran on the GNU glpsol solver. The model for the back end was written in GMPL (GNU Mathematical Programming Language), which is similar to AMPL. I apologize for the line-wrapping that occurs in the blog layout:


###
### Library Reference Desk Scheduler
###
### by Wayne Folta (wdf61@mac.com)
###
### This is a GNU MathProg Language (GMPL) format model for input to glpsol (--math option).
###
### It will schedule employees for shifts at the reference desk. It has several parameters
### (of which you can see examples in the DATA section, below. Override this data with
### your own (--data option).
###
### NOTES:
###
### *1* Watch employee_min closely. If it is greater than the number of hours
### that the employee has employee_avail, the optimization will fail. This should
### be caught in the front end spreadsheet, and there is a CHECK for this.
###
### *2* Watch employee_max closely. If it is less than the number of hours
### that the employee has employee_req, the optimization will fail. This should
### be caught in the front end spreadsheet, and there is a CHECK for this.
###
### *3* employee_avail covers any reason that an employee is not available. If they
### take leave, for instance, you will need to adjust employee_min:
### see *1*, above.
###
### *4* employee_req covers shifts (evenings and weekends, mostly) where someone
### is at work specifically to take that shift. See *2*, above.
###
### I have added CHECK commands to check *1*, and *2*, but my front end to glpsol
### is a spreadsheet, which checks these and several other issues, and colors errors
### with conditional formatting.
###
###

set SHIFTS ; # Shifts that exist,
set DAYS ; # on these days
set EMPLOYEES ; # for these employees, who are to be scheduled.

param employee_min{EMPLOYEES} >= 0 ; # Minimum number of hours to serve this scheduling period *1*
param employee_max{EMPLOYEES} >= 0 ; # Maximum number of hours to serve this scheduling period *2*

param day_max{DAYS} >= 0 ; # Maximum number of hours any employee can serve on any one day

# Sched_form is the main form, where each entry is 0 if the employee is unavailable for that shift,
# 1 if the employee is available, and 2 if the employee is required to work that shift.
# These values are pulled apart into employee_avail and employee_req, for easy constraints. *3* *4*

param sched_form{DAYS, SHIFTS, EMPLOYEES} ;

param employee_avail{d in DAYS, s in SHIFTS, e in EMPLOYEES} binary := if sched_form[d, s, e] > 0 then 1 else 0 ;
param employee_req {d in DAYS, s in SHIFTS, e in EMPLOYEES} binary := if sched_form[d, s, e] > 1 then 1 else 0 ;

param req{d in DAYS, e in EMPLOYEES} := sum{s in SHIFTS} employee_req[d, s, e] ;
param employee_lim{d in DAYS, e in EMPLOYEES} := if req[d, e] > day_max[d] then req[d, e] else day_max[d] ;

param needed{DAYS, SHIFTS} >= 0 ; # Number of employees needed for each shift

var sched{DAYS, SHIFTS, EMPLOYEES} binary ; # The final schedule: 1 if employee scheduled, 0 if not

check {e in EMPLOYEES}: employee_min[e] <= sum{d in DAYS, s in SHIFTS} employee_avail[d, s, e] ; # *1*
check {e in EMPLOYEES}: sum{d in DAYS, s in SHIFTS} employee_req[d, s, e] = employee_req[d, s, e] ;

maximize total_hours: sum{d in DAYS, s in SHIFTS, e in EMPLOYEES} sched[d, s, e] ;

subject to needs {d in DAYS, s in SHIFTS}: sum{e in EMPLOYEES} sched[d, s, e] <= needed[d, s] ;

subject to employee_availability {d in DAYS, s in SHIFTS, e in EMPLOYEES}: sched[d, s, e] = employee_req[d, s, e] ;

subject to min_hours {e in EMPLOYEES}: sum{d in DAYS, s in SHIFTS} sched[d, s, e] >= employee_min[e] ;
subject to max_hours {e in EMPLOYEES}: sum{d in DAYS, s in SHIFTS} sched[d, s, e] <= employee_max[e] ;

subject to reasonable_hours {d in DAYS, e in EMPLOYEES}: sum{s in SHIFTS} sched[d, s, e] 0} OUT "CSV" "Schedule Out CSV.csv":
d~Day, s~Shift, e~Employee ;

printf "Managed to schedule %d shifts of %d requested\n\n",
sum{d in DAYS, s in SHIFTS, e in EMPLOYEES} sched[d, s, e], sum{d in DAYS, s in SHIFTS} needed[d, s] ;

printf {e in EMPLOYEES} "\t%s", e ;
printf "\n" ;

for {d in DAYS, s in SHIFTS}
{
printf "%s %s", d, s ;
for {e in EMPLOYEES}
{ printf "\t%s", if sched[d, s, e] then "X" else " " ; }
printf "\n" ;
}

printf "\n" ;

# for {d in DAYS, s in SHIFTS: needed[d, s] > 0}
for {d in DAYS, s in SHIFTS}
{
printf "%3s %-5s (%d): ", d, s, needed[d, s] ;
printf {e in EMPLOYEES : sched[d, s, e] == 1} "%s ", e ;
printf "\n" ;
}

printf "\n" ;

###
### You should specify your own data in a separate file, which (with glpsol --math foo --data bar) will
### override this data section. I've left this section in so that you can see what it might look like...
###

data ;

set SHIFTS := 9_am 10_am 11_am 12_pm 1_pm 2_pm 3_pm 4_pm 5_pm 6_pm 7_pm 8_pm ;

set DAYS := Sun Mon Tue Wed Thu Fri Sat ;

set EMPLOYEES := John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 ;

param day_max := Sun 4
Mon 4
Tue 4
Wed 4
Thu 4
Fri 4
Sat 4 ;

param needed (tr) : Sun Mon Tue Wed Thu Fri Sat :=
9_am 0 1 1 1 1 1 2
10_am 0 1 1 1 1 1 2
11_am 0 1 1 1 1 1 2
12_pm 0 1 1 1 1 1 2
1_pm 0 1 1 1 1 1 2
2_pm 0 1 1 1 1 1 2
3_pm 0 2 2 2 2 2 2
4_pm 0 2 2 2 2 2 2
5_pm 0 2 2 2 2 0 0
6_pm 0 2 2 2 2 0 0
7_pm 0 2 2 2 2 0 0
8_pm 0 2 2 2 2 0 0 ;

param employee_min := John 8
Maria 8
Mary 8
Nicole 8
Pat 8
Sandy 8
Raquel 8
Susan 8
Jose 6
Margret 1
Temp_1 4
Temp_2 9
Alex 2
Michelle 2
Temp_3 3 ;

param employee_max := John 10
Maria 10
Mary 10
Nicole 10
Pat 10
Sandy 10
Raquel 10
Susan 10
Jose 8
Margret 1
Temp_1 4
Temp_2 9
Alex 2
Michelle 2
Temp_3 3 ;

param sched_form :=
[Sun, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10_am 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11_am 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[Mon, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0
10_am 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
11_am 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
12_pm 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
1_pm 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0
2_pm 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
3_pm 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0
4_pm 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0
5_pm 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0
6_pm 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
7_pm 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
8_pm 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0

[Tue, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
10_am 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
11_am 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
12_pm 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
1_pm 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0
2_pm 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0
3_pm 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0
4_pm 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0
5_pm 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0
6_pm 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0
7_pm 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
8_pm 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0

[Wed, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
10_am 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0
11_am 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
12_pm 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
1_pm 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
2_pm 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
3_pm 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0
4_pm 1 0 2 1 0 1 1 0 0 0 0 0 1 0 0
5_pm 1 0 2 0 0 1 0 0 0 0 0 0 0 0 0
6_pm 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0
7_pm 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0
8_pm 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0

[Thu, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0
10_am 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0
11_am 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0
12_pm 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0
1_pm 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0
2_pm 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0
3_pm 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0
4_pm 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0
5_pm 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
6_pm 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
7_pm 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
8_pm 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0

[Fri, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0
10_am 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0
11_am 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0
12_pm 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0
1_pm 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0
2_pm 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0
3_pm 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0
4_pm 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0
5_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[Sat, *, *] : John Maria Mary Nicole Pat Sandy Raquel Susan Jose Margret Temp_1 Temp_2 Alex Michelle Temp_3 :=
9_am 0 0 0 0 0 0 0 0 1 0 0 2 0 0 0
10_am 1 0 0 0 0 0 0 0 1 0 0 2 0 0 0
11_am 0 0 0 0 0 0 0 0 1 0 0 2 0 0 0
12_pm 1 0 0 0 0 0 0 0 1 0 0 2 0 0 0
1_pm 1 0 0 0 0 0 0 0 1 0 0 2 0 0 0
2_pm 0 1 0 0 0 0 0 0 1 0 0 0 0 0 2
3_pm 0 1 0 0 0 0 0 0 1 0 0 0 0 0 2
4_pm 0 1 0 0 0 0 0 0 1 0 0 0 0 0 2
5_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8_pm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ;

end ;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s