## Wednesday, October 28, 2009

### A work sceduling problem

I saw this problem recently
A city authority is considering placing a toll booth on its new bridge. The beginning
times for the shifts are 8am, noon, 4pm, 8pm, midnight and 4am. A collector
beginning a shift at one of the above times works for the next 8 hours.
The following staffing levels during each of the 24-hour periods have been estimated

Hour.................... Minimum Collectors Needed
8am - Noon.............. . 5
Noon – 4pm ................6
4pm – 8pm .................10
8pm - Midnight........... .7
Midnight – 4am ...........4
4am – 8am .................6

Find the minimum number of collectors that need to be hired to begin the 8 hour shifts
at each of the six times.

A GLPK program to calculate this is
`var x1 >= 0, integer;var x2 >= 0, integer;var x3 >= 0, integer;var x4 >= 0, integer;var x5 >= 0, integer;var x6 >= 0, integer;/* objective function */minimize z: x1+x2+x3+x4+x5+x6;/* Constraints */s.t. ctr1:x1 + x6 >= 5;s.t. ctr2:x1+x2>= 6;s.t. ctr3:x2+x3>= 10;s.t. ctr4:x3+x4>= 7;s.t. ctr5:x4+x5>= 4;s.t. ctr6:x5+x6>= 6;data;end;`

The answer is 19 and no one starts working at 8am.
This is a simplified version of the program described here. Not a major revelation or anything but always find these puzzle solving programs cool.

#### 1 comment:

Barry M said...

Surely they should start before the rush-hour begins? :D