How to schedule employees that only work continually one shift a day?

I stumbled across the blog article posted by Loren Shure Generating an Optimal Employee Work Schedule Using Integer Linear Programming and I am trying to understand how to schedule employees.

My goal is to schedule them under the constraint that they can only work continually one shift per day.

For an employee the following schedule is not optimal.

Example:

 Time:     0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 Work-time:  0 0 0 0 0 0 0 0 0 0 0  0  1  1  1  0  0  1  1  1  0  0  0  0  0

There is "dead-time" between 3pm and 5pm.

In the article mentioned above this constrain is somehow set and fulfilled. A step that I do not understand is the purpose of the columns of the matrix A provided. In this article it is stated that they represent every possible shift for every possible employee. Yet it is not clear for me what it is meant by that.

Any suggestions?

Answer 1

[Neil Guertin]

Each column of A corresponds to a potential shift for one employee. For example, find(A(:,1)) shows that column 1 has entries in rows 7, 8, 9, 10, 11, 12, and 25. This means that Employee #1 (because there is an entry in row 25, the first row of the bottom half of A) might work hours 7, 8, 9, 10, 11, and 12. Likewise, column 1000 (entries in rows 7, 8, 9, 40) tells us that Employee #16 might work hours 7, 8, and 9.

The blog post describes a decision vector x, with 1295 elements corresponding to the 1295 columns of A. If an employee is chosen to work a shift, the corresponding element of x will be 1. For example, when I run the example, x(24) = 1. This means that Employee #1 will work hours 13-20 (This is a different solution than in the blog post, but has the same total cost).

A shift with dead time will never be selected because there is no column of A that corresponds to a shift with dead time.

[Georgios Salonikidis]

Thank you for this answer. This was well explained.