Scheduling problem

[William Felixon]

Hello!

I am working on a scheduling problem in AMPL. The opening hours on the company I am doing it for is between 04:15 and 01:00. This means that I am supposed to schedule their personnel between those hours. Every employee has a different level of compentece, ranging from 1 to 3. For instance, to execute a certain job requires one employee with competene level 1, one with level 2, and two with level 3. I have divided each shift into 15 min. This means that there are 83 shifts between 04:15 in the morning and 01:00 in the middle of the night. All the parameters such as salaries, demand for each level of competence and so on are divided into these 15 min shifts. I am almost finnished, the only problem I have is that I can't come up with a constraint  so that they work 8 hours straight ergo 32 shifts. If anyone could help me with this I would be very greatful. 

This is my .mod file:

set arbetare;

set skift;

set dag;

set mittpadagen;

set niva;

param kompetenslevel{niva,arbetare};

param lonetillagg{arbetare};

param behov_i_skift_k2{dag,skift};

param behov_i_skift_k3{dag,skift};

param behov_i_skift_k5{dag,skift};

param kostnad_per_skift{dag,skift};

var x{dag,skift,arbetare} binary;

minimize mal:

sum{d in dag} sum{s in skift} sum{a in arbetare} x[d,s,a]*kostnad_per_skift[d,s]+sum{d in dag} sum{s in skift} sum{a in arbetare} x[d,s,a]*lonetillagg[a];

subject to  meet_demand_k2{d in dag, s in skift}:

sum{a in arbetare} kompetenslevel[1,a]*x[d,s,a]>=behov_i_skift_k2[d,s];

subject to  meet_demand_k3{d in dag, s in skift}:

sum{a in arbetare} kompetenslevel[2,a]*x[d,s,a]>=behov_i_skift_k3[d,s];

subject to  meet_demand_k5{d in dag, s in skift}:

sum{a in arbetare} kompetenslevel[3,a]*x[d,s,a]>=behov_i_skift_k5[d,s];

subject to work_load {d in dag, a in arbetare}:          This constraint is saying that every employee can not work more than 8 hours/day

sum{s in skift} x[d,s,a]<=33;

subject to work_load_5 {a in arbetare}:                     This constraint is saying that each employee can not work more than 5 days/week

sum{d in dag}sum{s in skift} x[d,s,a]<=160;

[Robert Fourer]

You could define additional zero-one variables y[d,s,a] that indicate the shift at which each employee starts working. Then you would need constraints like sum {s in skift} y[d,s,a] <= 1 and sum {t in 0..31} x[d,s+t,a] >= 32 * y[d,s,a].

This kind of scheduling formulation can get very complicated; also if many of the people are identical then this kind of formulation may be hard to solve due to the existence of many equivalent solutions (so-called symmetries). Of course you should use it if it works for you. But if not, the alternative is to generate all of the possible schedules and to define the variables as the number of people of each kind who work each schedule, and in the attached example (for a simple case). This can lead to a huge number of variables but often the constraints are a lot simpler and the solution is faster because symmetries are avoided.

Bob Fourer
am...@googlegroups.com

=======

[William Felixon]

Thanks mate, I adjusted to mod file so it now looks like this:

set arbetare;

set skift;

set dag;

set mittpadagen;

set sentpadagen;

set niva;

set sentsomfan;

param kompetenslevel{niva,arbetare};

param behov_i_skift_k1{dag,skift};

param kostnad_per_skift{dag,skift};

var x{dag,skift,arbetare}binary;

var y{dag,skift,arbetare}binary;

minimize mal:

sum{d in dag} sum{s in skift} sum{a in arbetare} x[d,s,a]*kostnad_per_skift[d,s];

subject to  meet_demand_k1{d in dag, s in skift}:

sum{a in arbetare} x[d,s,a]>=behov_i_skift_k1[d,s];

subject to work_load {d in dag, a in arbetare}:

sum{s in skift} x[d,s,a]<=32;

subject to work_load_5 {a in arbetare}:

sum{d in dag}sum{s in skift} x[d,s,a]<=160;

#subject to max_y {d in dag, a in arbetare}:

#sum{s in skift} y[d,s,a]<=1;

subject to work_8h_shift_1 {d in dag,m in sentsomfan, a in arbetare}:

x[d,m,a]<=y[d,m,a]+x[d,m-1,a];

subject to work_8h_shift_2 {d in dag,m in sentsomfan, a in arbetare}:

x[d,m-1,a]+y[d,m,a]<=1;

#subject to work_8h_shift_3 {d in dag, m in mittpadagen, a in arbetare}:

#32*y[d,m,a]<=sum{t in 0..31} x[d,m+t,a];

subject to work_8h_shift_3_1 {m in mittpadagen, a in arbetare}:

32*y[1,m,a]<=sum{t in 0..31} x[1,m+t,a];

subject to work_8h_shift_3_2 {m in mittpadagen, a in arbetare}:

32*y[2,m,a]<=sum{t in 0..31} x[2,m+t,a];

subject to work_8h_shift_3_3 {m in mittpadagen, a in arbetare}:

32*y[3,m,a]<=sum{t in 0..31} x[3,m+t,a];

subject to work_8h_shift_3_4 {m in mittpadagen, a in arbetare}:

32*y[4,m,a]<=sum{t in 0..31} x[4,m+t,a];

#subject to work_8h_shift_3_5 {m in mittpadagen, a in arbetare}:

#32*y[5,m,a]<=sum{t in 0..31} x[5,m+t,a];

#subject to work_8h_shift_3_6 {m in mittpadagen, a in arbetare}:

#32*y[6,m,a]<=sum{t in 0..31} x[6,m+t,a];

subject to work_8h_shift_4 {d in dag,a in arbetare}:

32*x[d,1,a]<=sum{t in 0..31} x[d,1+t,a];

subject to work_8h_shift_5 {d in dag,i in 0..30, a in arbetare}:

32*y[d,53+i,a]<=sum{t in 0..(30-i)} x[d,53+t,a];

As you can see I have made some simplifications. But I indeed still seem to have the same problem that you mentioned. I spoke to my professor aswell and he said that the exact same thing. I tried to set different costs on each individual but doesn't seem to work, do you have any tips how to solve this? If you want I can of course email the files to you. 

best rgds 

William

 

[Robert Fourer]

It's not so clear which problem you are having at this point. Do you think that the formulation is incorrect, or is it correct but taking a long time in the solver?

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of William Felixon
Sent: Friday, November 27, 2015 2:42 AM
To: AMPL Modeling Language