|
| From: | Harley Mackenzie |
| Subject: | Re: [Help-glpk] GLPK shift coverage example |
| Date: | Sun, 15 Mar 2009 23:27:29 +0300 |
Great example Larry. I was part of a project for creating a set of
shifts for airport check-in counters for Kai Tak (the old Hong Kong
airport) in the early nineties using simulated annealing (mainly due to
the complexity of the shift rules - a common issue in the airline
industries) that was also creating shift rosters based on projected
demands created from flight schedules. It is interesting to see an LP
formulation of a similar problem.
Could I ask everyone on this list to consider submitting examples for
inclusion on the GLPK distribution, as it really adds value to the
application to see the work of others and how people formulate LP
models?
Regards,
Harley
D'Agostino, Larry - TX wrote:
I #8217;ve been working on a
workforce shift coverage model
recently. The purpose is to find an optimal shift schedule given
various
shift schedule proposals. The example below is just one proposal.
This
is a very common problem among assigning crew members to a given shift
allotment to cover demand. I think this type of problem makes for a
great
example. Andrew, feel free to use this model as an example in GLPK (if
you feel it has not been used already). I #8217;m sure your going to have
to modify the formatting as I copied it over from GUSEK. And as always
I
would welcome critiques and (better yet) improvements.
File: shiftcover.mod
/* WORKFORCE SHIFT
COVERAGE assignment problem */
/* Written by Larry
D'Agostino <larrydag -at- sbcglobal
-dot- com>
Maximize
Productivity with
Industrial Engineer and Operations Research Tools
http://industrialengineertools.blogspot.com
/* The WORKFORCE SHIFT
COVERAGE is an assigment problem that
determines
the schedule of crew
given available time and
shifts.
The objective is to
cover the available time
given hourly demand with the minimum
number of crew
members.
This is a set
covering problem that is
very common among finding crew
and shift
allocations. */
/* ----- Model PARAMTERS
and SETS -----*/
param numhrs;
/* number of hours of
operations in a given day */
param dys;
/* number of days in a
week */
set S;
/* set of crew shifts */
set H := 1..numhrs;
/* set of hours of a day*/
set D;
/* set of days of a week*/
param dmnd{h in H, d in
D};
/* demand for crew
members given h hour and d day */
param shifts{d in D, h in
H, s in S};
/* shifts to assign to
crew members given d day, h hour, and
s shift schedule
/*----- Model VARIABLES
-----*/
var crew{s in S},
integer, >=0;
/* number of crew
assigned to shift S */
/*----- Model CONSTRAINTS
-----*/
s.t. Coverage{h in H, d
in D}: sum{s in S}
crew[s]*shifts[d,h,s] >= dmnd[h,d];
/* number of crew to
cover with a shift given hourly
demand and day */
/*----- Model OBJECTIVE
-----*/
minimize obj: sum{s in S}
crew[s];
/* minimize number of
crew to cover demand*/
solve;
display crew;
printf "\n";
printf "Total Crew:
%3d\n\n", sum{s in S} crew[s];
printf "\n\n";
printf "Weekly Crew
Schedule\n\n";
printf "Hour ";
printf{d in D} " %s ",
d;
printf "\n";
for {h in H} {
printf " %2s ",h;
printf{d in D} " %3d
", sum{s
in S} crew[s]*shifts[d,h,s];
printf "\n";
}
printf"\n";
data;
param numhrs := 16;
set D := SUN, MON, TUE,
WED, THU, FRI, SAT;
set S := Sh1, Sh2, Sh3,
Sh4, Sh5, Sh6, Sh7, Sh8, Sh9;
param dmnd : SUN
MON TUE WED
THU FRI SAT :=
1
0 3
3 4
3 2 0
2
0 14 14
16 14
12 12
3
0 24 24
27 24
20 15
4
0 28 28
32 28
23 15
5
0 33 33
37 33
24 16
6
0 34 34
38 34
24 15
7
0 35 35
39 35
25 11
8 0
35 35
40 35
27 0
9
0 34 34
39 34
25 0
10
0 31 31
35 31
24 0
11
2 24 24
27 24
25 0
12 3
19 19
21 19
21 0
13
2 24 24
27 24
13 0
14
2 16 16
18 16
0 0
15
0 7
7 7
7 0 0
16
0 5
5 5
5 0 0;
param shifts :=
['SUN',*,*]:
Sh1 Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8
Sh9 :=
1
0 0 0 0
0 0 0 0
0
2
0 0 0 0
0 0 0 0
0
3
0 0 0 0
0 0 0 0
0
4
0 0 0 0
0 0 0 0
0
5
0 0 0 0
0 0 0 0
0
6
0 0 0 0
0 0 0 0
0
7
0 0 0 0
0 0 0 0
0
8
0 0 0 0
0 0 0 0
0
9
0 0 0 0
0 0 0 0
0
10
0 0 0 0
0 0 0 0
0
11 0
0 0 0 0
0 0 0 1
12
0 0 0 0
0 0 0 0
1
13
0 0 0 0
0 0 0 0
1
14
0 0 0 0
0 0 0 0
1
15
0 0 0 0
0 0 0 0
0
16
0 0 0 0
0 0 0 0
0
['MON',*,*]:
Sh1 Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8
Sh9 :=
1
1 0 0 0
0 0 0 0
0
2
1 1 0 0
0 0 0 0
0
3
1 1 1 0
0 0 0 0
0
4
1 1 1 1
0 0 0 0
0
5
0 1 1 1
1 0 0 0 0
6
1 0 1 1
1 1 0 0
1
7
1 1 0 1
1 1 1 0
1
8
1 1 1 0
1 1 1 1
1
9
1 1 1 1
0 1 1 1
1
10 0
1 1 1 1
0 1 1 1
11
0 0 1 1
1 1 0 1
0
12
0 0 0 1
1 1 1 0
1
13
0 0 0 0
1 1 1 1
1
14
0
0 0 0 0
1 1 1 1
15
0 0 0 0
0 0 1 1
1
16
0 0 0 0
0 0 0 1
1
['TUE',*,*]:
Sh1 Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8
Sh9 :=
1 1
0 0 0 0
0 0 0 0
2
1 1 0 0
0 0 0 0
0
3
1 1 1 0
0 0 0 0
0
4
1 1 1 1
0 0 0 0
0
5
0 1 1 1
1 0 0 0
0
6
1 0 1 1
1 1 0 0
1
7
1 1 0 1
1 1 1 0
1
8
1 1 1 0
1 1 1 1
1
9 1
1 1 1 0
1 1 1 1
10
0 1 1 1
1 0 1 1
1
11
0 0 1 1
1 1 0 1
0
12
0 0 0 1
1 1 1 0
1
13
0 0
0 0 1 1
1 1 1
14
0 0 0 0
0 1 1 1
1
15
0 0 0 0
0 0 1 1
1
16
0 0 0 0
0 0 0 1
1
['WED',*,*]:
Sh1
Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8 Sh9 :=
1
1 0 0 0
0 0 0 0
0
2
1 1 0 0
0 0 0 0
0
3
1 1 1 0
0 0 0 0
0
4
1 1
1 1 0 0
0 0 0
5
0 1 1 1
1 0 0 0
0
6
1 0 1 1
1 1 0 0
1
7
1 1 0 1
1 1 1 0
1
8
1 1 1 0
1 1 1 1
1
9
1 1 1 1
0 1 1 1
1
10
0 1 1 1
1 0 1 1
1
11
0 0 1 1
1 1 0 1
0
12
0 0 0 1
1 1 1 0
1
13
0 0 0 0
1 1 1 1
1
14
0 0 0 0
0 1 1 1
1
15
0 0 0 0
0 0 1 1
1
16 0
0 0 0 0
0 0 1 1
['THU',*,*]:
Sh1 Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8
Sh9 :=
1
1 0 0 0
0 0 0 0
0
2
1 1 0 0
0 0 0 0
0
3
1 1 1 0
0 0 0 0
0
4
1 1 1 1
0 0 0 0
0
5
0 1 1 1
1 0 0 0
0
6
1 0 1 1
1 1 0 0
0
7 1
1 0 1 1
1 1 0 0
8
1 1 1 0
1 1 1 1
0
9
1 1 1 1
0 1 1 1
0
10
0 1 1 1
1 0 1 1
0
11
0 0
1 1 1 1
0 1 0
12
0 0 0 1
1 1 1 0
0
13
0 0 0 0
1 1 1 1
0
14
0 0 0 0
0 1 1 1
0
15
0 0 0 0
0 0 1 1
0
16
0 0 0 0
0 0 0 1
0
['FRI',*,*]:
Sh1 Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8
Sh9 :=
1
1 0 0 0
0 0 0 0
0
2
1
1 0 0 0
0 0 0 0
3
1 1 1 0
0 0 0 0
0
4
1 1 1 1
0 0 0 0
0
5
0 1 1 1
1 0 0 0
0
6
1 0 1 1
1 1 0 0
0
7
1 1 0 1
1 1 1 0
0
8
1 1 1 0
1 1 1 1
0
9
1 1 1 1
0 1 1 1
0
10 0
1 1 1 1
0 1 1 0
11
0 0 1 1
1 1 0 1
0
12
0 0 0 1
1 1 1 0
0
13
0 0 0 0
1 1 1 1
0
14
0 0
0 0 0 1
1 1 0
15
0 0 0 0
0 0 1 1
0
16
0 0 0 0
0 0 0 1
0
['SAT',*,*]:
Sh1 Sh2 Sh3 Sh4 Sh5 Sh6 Sh7 Sh8
Sh9 :=
1 0
0 0 0 0
0 0 0 0
2
0 0 0 0
0 0 0 0
1
3
0 0 0 0
0 0 0 0
1
4
0 0 0 0
0 0 0 0
1
5
0 0
0 0 0 0
0 0 1
6
0 0 0 0
0 0 0 0
1
7
0 0 0 0
0 0 0 0
1
8
0 0 0 0
0 0 0 0
0
9
0 0 0 0
0 0 0 0
0
10
0 0 0 0
0 0 0 0
0
11
0 0 0 0
0 0 0 0
0
12
0 0 0 0
0 0 0 0
0
13
0 0 0 0
0 0 0 0
0
14
0 0 0 0
0 0 0 0
0
15
0 0 0 0
0 0 0 0
0
16
0 0 0 0
0 0 0 0
0;
Larry
http://industrialengineertools.blogspot.com
_______________________________________________
Help-glpk mailing address@hidden://lists.gnu.org/mailman/listinfo/help-glpk
--
------------------------------------------------------------------
Dr. Harley Mackenzie ABN: 36 348 783 012
HARD Software Web: www.hardsoftware.comPO BOX 8004
Tel: +61 3 5222 3435
Newtown 3220, Australia Email: address@hidden