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

8 次查看（过去 30 天）

Mee 2017-9-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/357690-how-do-i-create-an-optimal-multi-day-work-schedule-using-mixed-integer-linear-programming

评论： Serien Ali 2018-9-14

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?

9 个评论
显示 7更早的评论隐藏 7更早的评论

Serien Ali 2018-9-5

Thank you!

Serien Ali 2018-9-14

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

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

David Ding 2017-9-27

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/357690-how-do-i-create-an-optimal-multi-day-work-schedule-using-mixed-integer-linear-programming#answer_283400

在 MATLAB Online 中打开

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

4 个评论
显示 2更早的评论隐藏 2更早的评论

David Ding 2017-9-28

在 MATLAB Online 中打开

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 2017-9-28

Thanks a lot David. I will try this.

Serien Ali 2018-8-30

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?

请先登录，再进行评论。