1
$\begingroup$

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.

$\endgroup$

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.