I have a scheduling problem with the following specifications:

  • A single machine is used.
  • $n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$.
  • Each job can be executed several times.
  • There is a cycle length $t = T_{max}$ and the scheduled jobs have to fit in $[0,T_{max}[$.
  • There are two types of constraints:
    1. $J_i$ must be executed $m$ spaces of time after $J_j$.
    2. $J_i$ must be executed after jobs $J \subset \mathbb{J}$ or $J_i$ mustn't be executed after jobs $J$.
  • The basic solution in $[0,T_{max}[$ satisfying the constraints, needs to satisfy the constraints when copied on to $[T_{max},2T_{max}[$, $[2T_{max},3T_{max}[$, $\ldots$. In particular, if $j_1 \ldots j_s$ is a solution (sequence of jobs satisfying constraints) with $j_i \in \mathbb{J}$, then $j_2 \ldots j_s j_1$, $j_3 \ldots j_s j_1 j_2 \ldots$ must also satisfy the constraints.

I want to find all possible schedules.

Is this problem solved? I would appreciate any pointers to the literature describing a solution or approximations to it.


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.