A scheduling problem on an oriented graph with multiple constraints

Question

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

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.