0

I'm playing around with linear programming for schedule optimization, and I'm using ojAlgo although that shouldn't matter.

The scenario is I have several university classes each with variables start time S and end time E. Assume there is only one room I am scheduling against, and I just want to get possible S and E times for each one without overlap.

I need to express an additional rule that for given two consecutive classes, they must be 15 minutes (1 discrete interval) apart between the end time of the first class Ei and the start time of the second class Sj, or vice versa with Ej and Si.

I felt like I could use some binary tricks like I asked in this previous question, so I did something like this. b is a binary that can only be elements 1,0.

Ei - Sj >= 1 - 100000b Ej - Si >= 1 - 100000(1-b)

This seemed to work great for the following proofs:

Si=8, Ei=9, Sj=10, Ej=11, b=1, SUCCESS Si=8, Ei=9, Sj=10, Ej=11, b=0, FAIL Si=8, Ei=9, Sj=6, Ej=7, b=1, SUCCESS Si=8, Ei=9, Sj=6, Ej=7, b=0, FAIL Si=8, Ei=9, Sj=9, Ej=10, b=0, FAIL

But I got a false positive with this:

Si=8, Ei=9, Sj=6, Ej=7, b=1,SUCCESS

Is there a way I can alternate effectively with a binary between Ei - Sj >= 1 and Ej - Si >= 1 ?

tmn
  • 199
  • 7
  • Why not just set Ei - Si >= length of task i + 1 ? Then each class naturally takes up the extra break time after it. Then you just need the usual algorithm for no two overlapping classes. – Artimis Fowl Oct 26 '17 at 21:34
  • Well right now my model in ojAlgo is packing things together tightly when they don't have to. The result is huge blocks of empty space, and busy blocks packed back-to-back with classes. – tmn Oct 26 '17 at 21:44
  • Ah, I see what you are saying. Just hack it and manually chop off those extra 15 minutes later. – tmn Oct 26 '17 at 22:47
  • I'd still like to see how a binary would be used, because I have several problems of this nature. like limiting the working time each day. – tmn Oct 26 '17 at 23:02

1 Answers1

1

This fragment does not look correct at all:

Ei - Sj >= 1 - 100000b
Ej - Si >= 1 - 100000(1-b)

This means

$$\begin{align} &E_i \ge S_j+1\\&\text{or}\\ &E_j \ge S_i+1\end{align}$$

This has no practical physical meaning. It will allow something like:

enter image description here

I think you want:

$$\begin{align} &S_i \ge E_j+1\\&\text{or}\\ &S_j \ge E_i+1\end{align}$$

This will enforce:

enter image description here

Erwin Kalvelagen
  • 4,267