0
$\begingroup$

The problem is the following :

Data

  • An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks
  • A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a discretized duration.
  • a couple $(p_0, p_1) \in \mathbb{N} \times \mathbb{N}$ : to be understood as an authorized time frame.
  • $(w_{max_1}, w_{max_2}) \in \mathbb{N} \times \mathbb{N}$ : to be understood as a maximum wait times between tasks inside a list (definition follows) and between the realisation of same task in each list.

Definition 1 : List

We call a list (to be understood as an instanciation of all the tasks) the following map $L : V \rightarrow [\![p_0; p_1]\!]$ such as

  1. $\forall t \in V, L(t) + d(t) \leq p_1$
  2. $\forall t \in V, L(t) \geq p_0$
    those two are the time frame conditions (the second one is obviously redondant with the target set of the function by here to clarify)
  3. $\forall (t_1, t_2) \in V$ such that $L(t_1) < L(t_2)$ then $L(t_1) + d(t_1) \leq L(t_2)$
    This condition means that no two tasks of a list can overlap
  4. $\forall (t_1, t_2) \in E, L(t_1) < L(t_2)$
    This condition means that some tasks must happen in a definite position
  5. For $t_1 \in V$ let $w = \displaystyle \min_{t_2, L(t_1) < L(t_2)}(L(t_2) - (L(t_1) + d(t_1))$ then $w \leq w_{max_1}$
    This condition means that the delay between the end of a task and the begin of the next one must be inferior to a known duration.

Definition 2: Compatible lists

Two lists $L_1$ and $L_2$ are said to be compatible iff :

  • $\forall t \in V$:
    • $L_1(t) < L_2(t) \implies L_1(t) + d(t) \leq L_2(t)$
    • $L_2(t) < L_1(t) \implies L_2(t) + d(t) \leq L_1(t)$

To be understood as two lists are compatible if the same task in those two lists does not happen in an overlapping time frame.

Definition 3: Correct set of lists

Let $X = \{L_i\}$ be an ensemble of compatible lists and $n = |X|$, we say that X is a correct set of lists iff :

  • For $L_i \in X$, $\forall t \in V$, let $w' = \displaystyle \min_{j, L_i(t) < L_j(t), L_j \in X}(L_j(t) - (L_i(t) + d(t))$ then $w' \leq w_{max_2}$

This condition on an ensemble of lists is to be understood as : the delay between the end of an occurence of a task in a list and of the begining of the same task in another list must be inferior to a know duration.

Goal

Maximize n

This is to be understood as : pack as many lists as possible inside a time frame as long as they define a correct set (def 3) of compatible (def 2) lists (def 1).

Questions

My questions are the following :

  1. Do you see any incoherence (or improvement in the formulation) between the maths and the text ?
  2. What kind of known problem is this (if this one, i'm guessing some variant of job-scheduling) ?
  3. If this is not a known problem what simplification can be made to reach one ?
  4. If pertinent, what are the method to solve this (or the simplification of this) ? I know an optimal solution might not be achievable but something approaching might be and I'm guessing constraint programming might be something to look at.
$\endgroup$
  • $\begingroup$ As a complement of information. I believe this is some sort of no-wait open-shop with partial order problem. And I'm currently looking at Constraint programming with reified constraints. $\endgroup$ – FollowK Mar 29 at 15:56
  • $\begingroup$ What does $L : V \rightarrow [\![p_0; p_1]\!]$ mean? I'm not familiar with the notation $[\![p_0; p_1]\!]$. $\endgroup$ – D.W. Mar 29 at 16:51
  • $\begingroup$ Oh sorry this an "interval" of $\mathbb{N}$ so it could be replaced by $\mathbb{N}$ and a constraint $\forall t \in V, p_0 \leq L(t) \leq p_1$ $\endgroup$ – FollowK Mar 29 at 17:07
  • $\begingroup$ Please edit the question so its clear. Next: why both $L(t) \le p_1$ (from the constraint on the signature of $f$) and $L(t)+d(t) \le p_1$ (your item 1) -- that seems dubious, and I wonder if one of those is wrong. $\endgroup$ – D.W. Mar 29 at 20:38
  • $\begingroup$ This site probably isn't the best place to review your work on formalizing this, as such a question is unlikely to be useful to anyone else in the future. I suggest seeing if you can formulate a specific algorithmic question that is as simple as possible. $\endgroup$ – D.W. Mar 29 at 20:39

Your Answer

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

Browse other questions tagged or ask your own question.