0

I am trying to understand part of the methematical model and answer posted in the following question: Linear Programming - Preventing Staff Scheduling Shift Overlap?

My question is concerning @Erwin Kalvelagen answer.

The M is just a constant e.g. 100. So if $δ_{i,j}=1$ we get $S_{i}≥E_{j}−100$ and since we want to minimize $S_{i}$ we get $S_{i}=0$?

Here is the question found in the other post:

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".

And the answer:

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

Let Si and Ei be the start and end-time of shift for driver i. Then we want to model: $S_{i}≥E_{j}$ or $S_{j}≥E_{i}$ (i.e. shift i is later than shift j or it is earlier). This can be formulated as:

$S_{i}≥E_{j}−M*δ_{i,j}$

$S_{j}≥E_{i}−M*(1−δ_{i,j})$

$δ_{i,j}∈{0,1}$

where M is a large enough constant (e.g. length of planning window), and δ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).

Georgios
  • 123
  • 5
  • You may wish to quote the question and answer you have referred to, so people don't have to click around, and also to preserve them if either question or answer gets deleted in the future – lioness99a Dec 21 '18 at 14:04
  • @ lioness99a Do you mean like that? – Georgios Dec 21 '18 at 14:24
  • Yes, although it may help readability if you only quote the parts which are directly relevant to your question – lioness99a Dec 21 '18 at 14:28
  • No. It just means this constraint is "disabled" when $\delta_{i,j}=1$. Note that $S_i$ is most surely subject to other constraints, so you cannot immediately conclude $S_i=0$. – Erwin Kalvelagen Dec 22 '18 at 14:29
  • @ErwinKalvelagen I think I got it. I guess $S_i$ should be in addition $/geq 0$ since it depicts the start time of a shift (0-24 hours?). The constraint gets "disabled" since $S_i$ should be greater or equal than a negative number when $\delta_{i,j}=1$ and this constraint is already included in the 0-24 constraint right? – Georgios Dec 22 '18 at 14:43
  • I am not so obsessed with $0$. The planning period can be $[30,100]$ or $[-10,50]$. – Erwin Kalvelagen Dec 22 '18 at 15:52
  • @Erwin Kalvelagen Now I am a bit confused. What would be the meaning of such intervals? I had in mind that $S_i$ depicts the start time of a shift. Thus, it can only take hour values which are between 00:00 and 24:00. So what would be the meaning of $S_i = -10?$ – Georgios Dec 22 '18 at 15:58

0 Answers0