Linear Programming - Preventing Staff Scheduling Shift Overlap?

I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc).

I've Googled for several hours looking at articles on this category of problem, but the documented problems are much more complicated than the one I am currently pondering, which I've contrived on my own as an exercise.

Here is the problem:

=======================

SCENARIO: You have three drivers to make deliveries.

Driver 1 costs $10 / hr

Driver 2 costs $12 / hr

Driver 3 costs $14 / hr

Each driver can only work 3-6 hours a day. Only one shift can be worked by a worker a day. Only one worker can be working at a given time. Operating day is 6:00 to 22:00, which must be fully covered.

Driver 2 cannot work after 11:00.

Create a schedule that minimizes the cost.

========================

Here is the work I have written out so far.

Solve Variables:

Tsx = shift start for Driver X

Tex = shift end for Driver X

Minimize: 10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)

Constraints:

4.0 <= Te - Ts <= 6.0

6.0 <= Ts, Te <= 22.0

(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)

Te2 <= 11

When I express these equations in my Kotlin code (which I can share if desired), I am getting shift overlaps. Here is the output:

OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]

It minimized the cost to $624, and it did correctly constrain to 16 hours worth of shifts. It also respected the max shift time allowed for each driver, and prevented Driver 2 from being scheduled beyond 11:00.

However, it scheduled the shifts to Driver 1 6:00-11:00, Driver 2 6:00-12:00, and Driver 3 6:00-11:00.

I've tried to research the solution to this problem, but I really cannot find a simple answer to my question. Can someone please share what mysterious linear functions I need to constrain to in order for my shifts to not overlap? I keep reading about binary constraints and I'm not sure how to use those to show a shift being "occupied".

Solution 1:

The continuous time no-overlap constraint cannot be modeled in a pure LP model. You need a discrete variable for that.

Let $S_i$ and $E_i$ be the start and end-time of shift for driver $i$. Then we want to model: $S_i\ge E_j \text{ or } S_j\ge E_i$ (i.e. shift $i$ is later than shift $j$ or it is earlier). This can be formulated as:

$$ \begin{align} &S_i\ge E_j - M\delta_{i,j} \\ &S_j\ge E_i - M (1-\delta_{i,j})\\ &\delta_{i,j}\in \{0,1\} \end{align} $$ where $M$ is a large enough constant (e.g. length of planning window), and $\delta_{i,j}$ is a binary variable.

However, usually shift scheduling is modeled with discrete time (i.e. time slots; e.g. personnel shifts start at whole hours). See the remarks in the cross-post for a link to some shift scheduling formulations. In these models, we do not prevent overlaps, but rather minimize cost. It is cheaper to have as few unnecessary overlaps as possible (having more employees than needed is wasteful -- at least from a direct cost perspective).