How do I create an optimal MULTI-day work schedule using mixed integer linear programming?

Hi,

In this blog by Loren Shure Generating an Optimal Employee Work Schedule Using Integer Linear Programming, she showed how to solve a complicated scheduling problem. I am trying to recreate this but I want to do a weekly optimization with the constraint that an employee can work maximum 40 hours a week and one can work only one shift a day. Sean de Wolski made a comment that I could just duplicate the constraints to look at a longer time period at once but I do not know how to formulate it. Can someone please help me?

[Serien Ali]

Hi Mee, I am trying to do the same thing. Were you able to formulate this for weekly optimization?

Thanks so much.

[Mai]

Hi Serien, Yes, i was able to solve this using David’s suggestions. :)

[Serien Ali]

Thanks for your reply! I am having some issues formulating it. Did you add the weekly constraints into the already made A and b matrix, or did you need to create an Aeq and beq matrix? When I tried adding the constraint into the A and b matrix, I get an error that the sizes do not match. Also, because I am creating a weekly model, I removed the circular loop that was in place (GALLERY). To which I get more errors. Did you keep gallery in place?

Thank you so much!

[Serien Ali]

Also, I used hourMatrix as the total hours worked for each employee, however I think this is wrong. I am new to matlab, sorry in advance!

[Serien Ali]

Hi again Mai, sorry to be a bother. I cant seem to formulate it for a weekly optimization. Could you please walk me through how you managed to formulate it? It would be a huge help to me. Thank you so much!

[Serien Ali]

Hi Mai, could you please help? I cant find any resources online. Thanks so much.

[Mai]

Hi, I will reply soon when I get access to my laptop. :)

[Serien Ali]

Thank you!

[Serien Ali]

Hi Mai, were you able to get a hold of your laptop? Thanks

Answer 1

[David Ding]

Hi,

As per the blog, the constraints are captured in A and b where: Ax <= b.

Now, you need to look at how to change the values of A and b to match your scenario. The call to the function "intlinprog" is likely still going to be the same:

[x, cost] = intlinprog(f,1:nVars,A,b,[],[],lb,ub);

The difference will be the values of the input arguments. For starters, just by quickly glancing your description and the blog, for the inequality matrix A:

"...There are two parts to the inequality constraint matrix A, which are clearly visible. The top portion has 24 rows (because there are 24 hours in a day) and each row represents the constraint that at a particular hour, you need a minimum number of staff..."

Now, perhaps, if you wish to extend this to a week and following the above example, you can make the top portion of A to be of 168 rows, since there are 168 hours in a week?

Best of luck,

David

[Mee]

Hi David, Thanks for the reply. This solution works. But what if I have different availability and different min/max hours per day for a certain employee, how would it affect the input arguments and how would I implement it? And what about the max hours per week constraint per employee, where should i add that part? Thank you so much.

[David Ding]

Hi Mee,

The workflow would be the same as for the extension of the problem from a day to a week. You would need to write out those inequality constraints line by line. Then, use algebraic manipulations to turn them into the form Ax <= b. The dimensions of A and b as well as their values would depend on what inequality constraints you have. The same is true for the equality constraints Cx = d.

The function "intlinprog", like other optimization functions such as "linprog" and "quadprog" only sees the inequality constraints as Ax <= b, so it is your job to convert your constraints into this form.

Just to give you an example, say you have the following constraints:

3x <= 6x + 7
x >= 0

And you want to convert it into Ax <= b form. First step is to move all the constants on the right hand side and the variable x on the left hand side of each inequality equation:

-3x <= 7
x >= 0

Next, make sure all the inequality signs are <=:

-3x <= 7
-x <= 0

Finally, we extract the coefficients into matrix A and the constants into vector b. Note that there are two inequalities, so A has 2 rows. Each row would have only one column since the number of columns represents the number of variables there are:

A = [-3; -1]
b = [7; 0]

If you multiply out A*x, you indeed get back the original linear equations which are <= to the corresponding elements in the vector b.

Hope this helps.

David

[Mee]

Thanks a lot David. I will try this.

[Serien Ali]

Hi David,

I am having trouble setting up weekly constraints. I have turned the example into 168 hours instead of 24, and have min/max hours per shift for each employee. However I am having trouble setting up min hours per week for each employee. How can I go about doing this? How can i add this constraint into the existing matrix that I am setting up?