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.
Surely they should start before the rush-hour begins? :D
ReplyDelete