10
$\begingroup$

Let us consider the following problem:

Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$ and a target start time $s_t$. No two tasks can be executed in parallel. The objective is to minimize the sum of the absolute deviation between the start time of a task and the target start time.

A possible way to model this problem would be the following:

$\forall t \in T$ let $e_t$ be a linear variable representing the absolute deviation between a task start time and its target start time.

$\forall t \in T$ let $a_t$ be a linear variable representing the actual start time of a task.

$\forall (t_1, t_2) \in T^2$ let $x_{t_1,t_2}$ be a binary variable representing if $t_1$ starts before $t_2$.

Let $M$ be a sufficiently large coefficient.

A possible model is then the following

\begin{align}\min\qquad &\sum_{t \in T}e_t\\\text{s.t.}\qquad&e_t \geq s_t - a_t, \forall t \in T\\&e_t \geq a_t - s_t, \forall t \in T\\&x_{t_1,t_2} + x_{t_2,t_1} = 1, \forall (t_1, t_2) \in T^2\\&a_{t_2} + d_{t_2} \leq a_{t_1} + M \cdot x_{t_1,t_2}, \forall (t_1, t_2)\in T^2\end{align}

Is there a way to deal with the non-overlapping constraints without adding a binary variable for each pair of task?

$\endgroup$
  • 1
    $\begingroup$ There are combinatorial algorithms for "assignment" problems (rather than by expressing them as linear programs). Would such as approach be of interest? $\endgroup$ – hardmath Jun 6 '19 at 10:06
  • 2
    $\begingroup$ @hardmath: to be fair it is not exactly a problem that I am currently facing, rather something looking like a variety of problems that I have faced in the past and for which I have used Constraint Programming technics rather than Mathematical Programming technics. I was more interested from a theoretical point of view if I was missing any obvious other more efficient MIP modeling. $\endgroup$ – Renaud M. Jun 6 '19 at 10:29
  • 1
    $\begingroup$ This is framed as a machine scheduling question, but sums of deviation without overlap come up quite a lot in chip design. You might find something, if you look up placement problems in chip design. Also: have you checked that this problem is NP-hard? Sorting jobs by target time and moving them, such that each move in either direction of a job makes as many jobs more expensive as it makes cheaper might already give you an optimal solution? $\endgroup$ – Luke599999 Jun 6 '19 at 11:55
  • $\begingroup$ @Luke599999: that is indeed a good remark. I have framed the question here with a scheduling terminology, but I have also those problematic encountered in cutting and packing problems. About your remark on whether sorting the jobs could lead to the optimal solution I have to think about it. $\endgroup$ – Renaud M. Jun 6 '19 at 12:33
7
$\begingroup$

I do not know of any way of handling this without some sort of variable that sorts out whether $i$ begins before $j$ or vice versa. Given the NP-completeness of the underlying problem, you will need some sort of binary variable in formulating, but there may be other ways than the method you give.

| improve this answer | |
$\endgroup$
7
$\begingroup$

One easy way to convince yourself that this is a non-convex problem - and hence can't be represented without integer constraints, or some other non-convex constraint - is to ask: "If X1 and X2 are both valid solutions, is their average always a valid solution?"

If the problem is convex, the answer must be yes, since that's the definition of convexity. In this case, it's clearly no: there might be valid solutions where task A begins before B, and others where B begins before A, but averaging the starting times results in overlap.

You can squeeze this into a MIP framework by adding some binary variables, but it may be worth considering a constraint solver e.g. Gecode, which specifically supports non-overlap constraints and is programmed to deal with them.

| improve this answer | |
$\endgroup$
5
$\begingroup$

If you have a finite set $I$ of start times, you can introduce a binary variable $y_{t,i}$ that indicates whether task $t \in T$ starts at time $i \in I$. Each task must be assigned exactly one start time: $$\sum_{i \in I} y_{t,i} = 1 \text{ for all } t \in T.$$ Conflicts are then prohibited by clique constraints: $$\sum_{t, i:\ i \le j < i+d_t} y_{t,i} \le 1 \text{ for all } j \in I.$$

| improve this answer | |
$\endgroup$
3
$\begingroup$

Perhaps its possible to solve as is then check the solution for "violations" of the one at a time constraint.

You could then push its start time by adding a constraint that enforces it to start after. Using the third constraint you defined. Plus another to set either $x_{t_1,t_2} = 1$ or $x_{t_2,t_1} = 1$.

This will be highly dependent on data and the solution will be of debatable quality.

| improve this answer | |
$\endgroup$
1
$\begingroup$

There is a nice in-depth review of different MIP formulations for machine scheduling problems by Queyranne and Schulz: https://pdfs.semanticscholar.org/a00d/f7ab46627debbfde11bfe2b019d4d3a5c72d.pdf It is dated, but still relevant today I think.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.