The problem is the following :


  • An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks
  • A map $d: V \rightarrow \mathbb{N}$ : to be understood a function mapping tasks to a discretized start time.
  • 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.


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


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.

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.