# 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 -> \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.
• 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. – FollowK Mar 29 at 15:56
• What does $L : V \rightarrow [\![p_0; p_1]\!]$ mean? I'm not familiar with the notation $[\![p_0; p_1]\!]$. – D.W. Mar 29 at 16:51
• 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$ – FollowK Mar 29 at 17:07
• 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. – D.W. Mar 29 at 20:38
• 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. – D.W. Mar 29 at 20:39