1

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

tmn
  • 199
  • 7
  • You can add $\infty(Te1-Ts2) + \infty(Te2-Ts1) + \infty(Te1-Ts3) + \infty(Te3-Ts1) + \infty(Te2-Ts3) + \infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself. – Abhiram Natarajan Oct 20 '17 at 00:17
  • How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try using Integer.MAX_VALUE although I'm not sure that would have the same effect. – tmn Oct 20 '17 at 00:29
  • Here is what I originally posted on SO. https://stackoverflow.com/questions/46823121/ojalgo-linear-optimization-preventing-work-shift-overlaps – tmn Oct 20 '17 at 00:30
  • It doesn't have to be infinity! It can just be a ridiculously large number like 99999999. – Abhiram Natarajan Oct 20 '17 at 01:00
  • That would be a numerical disaster. – copper.hat Oct 20 '17 at 01:37
  • You can't express what you want using a continuous LP. You probably need to go down the mixed integer LP route. – copper.hat Oct 20 '17 at 01:39
  • You may need to discretise time... – copper.hat Oct 20 '17 at 04:35

1 Answers1

3

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

Erwin Kalvelagen
  • 4,267
  • That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend – tmn Oct 20 '17 at 11:11
  • Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this... – tmn Oct 20 '17 at 13:58
  • 1
    Correct. $\delta_{i,j}=0 \Rightarrow S_i \ge E_j$ and $\delta_{i,j}=1 \Rightarrow S_j \ge E_i$. Note that for binary variables you need a MIP solver. – Erwin Kalvelagen Oct 20 '17 at 14:09
  • 1
    @ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.) – copper.hat Oct 20 '17 at 15:01
  • 2
    @copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts. – Erwin Kalvelagen Oct 20 '17 at 15:27
  • It looks like this worked beautifully. Thanks Erwin! I look forward to following your blog. https://stackoverflow.com/a/46852528/1373258 – tmn Oct 20 '17 at 15:35
  • @ErwinKalvelagen: Much appreciated. Have ordered both to have a look at. – copper.hat Oct 20 '17 at 16:14
  • @ErwinKalvelagen: The books look interesting. The modelling one has a spelling error in Section 13.27 (Hamiltoniam) :-). – copper.hat Oct 26 '17 at 05:03