Scheduling Employees Assignment Problem

I am working on a program right now to schedule employees for a shift, and then determine what jobs are not covered in order to determine the amount of overtime needed. I know this is a typical assignment problem, however I cannot wrap my head around how to set this problem up in Matlab. I haven't used this program in 5+ years and to say I'm rusty is an understatement. What I really need to learn is: how do I solve the cost matrix outlined below, and how can I have a final assignment matrix generated in order to see who is assigned to what job. I don't want someone to write the code for me, I just want to learn how a problem like this can be solved.

My problem statement is as follows: There are four crews working 12 hour shifts, with one crew assigned to each shift. There are a total of 21 possible jobs for a shift, while each crew has 15-16 employees. Not all jobs need to be performed each shift. Each employee is trained for certain jobs, and cannot perform a job they are not trained on. Each employee can only be assigned to one job per shift, and each job can only have one employee assigned to it. The schedule is created once a week with two shifts scheduled per day, and so a total of 14 shifts for a week.

• Indices:

- i = number of employees (62 total)

- j = number of jobs (21 total)

- k = number of shifts (14 total)

• 
• Constraints: for j=1 to 21 and for k= 1 to 14

I have created a cost matrix for each shift in the excel workbook attached. What I am planning to do with this is create a three dimensional matrix of 62 x 21 x 14 with these, and then what I would like to do is have the matrix solved and an assignement matrix created with which employee is assigned to which job per shift. If an employee is either not trained for a job, or is unavailable that day, I have set that element to infinity so the cost is too great to solve for.

I have been scouring through the blog posts and forums on here trying to understand how to input a problem like this, but I cannot understand how the programs I have found create their matrices or have an assignment matrix generated at the end. In particular I have been working with the following two posts in trying to modify their program to accomodate my problem, but with no luck.

https://blogs.mathworks.com/loren/2016/01/06/generating-an-optimal-employee-work-schedule-using-integer-linear-programming/

https://www.mathworks.com/matlabcentral/fileexchange/6543-functions-for-the-rectangular-assignment-problem

[Mohammad Sami]

I think your constraints are not fully defined. I would assume that employee can work one shift, 7 days a week.

Perhaps you want to try do it for one day first. Maybe you need four indices, i = employee, j = days, k = 2 shifts, l = 21 jobs.

You will need to add a constraint on the number of employee on each shift.

You will need to add a constraint that an employee is only doing one job on that shift.

You will need to add a constraint that a job is only done once a shift.

Maybe there is a constraint on how many times a job needs to be done in a week.

Maybe there is a constraint on how many times a week an employee can work.

Maybe there is a constraint on how many shifts employee can do in a day.

Maybe there is a constraint on which employees can do which jobs, (sum of that job for employee can be set to 0 if they cannot do it)

[Paul Ingram]

I was figuring I wasn't capturing all of the constraints, so thank you for pointing those out. I hadn't thought about making the constraint for the number of people per shift.

If I make this run for just one day though, could I keep only two indices i and j?

For the constraints I'm trying the understand how to input these. For instance, if an employee can only do one job a shift, and I kept just i and j, would that be something like: For i=n Sum(x_ij)≤ 1 for j=1 to 21

[Mohammad Sami]

I think if you do it for one day, you can perhaps use only two indexes.

but then you would have to account for same job can be done on both shift. so the for j = 1..21 Sum i=1to62 X_ij can be less then or equal to two.