Dgdrxrt

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 mathbbN$ : to be understood a function mapping tasks to a discretized start time.


• a couple $(p_0, p_1) in mathbbN times mathbbN$ : to be understood as an authorized time frame.


• 
  $(w_max_1, w_max_2) in mathbbN times mathbbN$ : 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.