A scheduling problem on an oriented graph with multiple constraints

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.