Is this another variant of Job Shop Scheduling Problem?

Question

The problem is as follows: there are $n$ jobs $\mathcal{J}=\{J_1,\ldots, J_n\}$, each of which could be done. There are $k$ machines $M_1,\ldots,M_k$ that work in parallel, independently of each other, and each of the jobs can be performed on any of the machines. Each of the jobs has a fixed execution time. Machine can do at most one job at any moment.

The set of jobs is partitioned into two subsets, $\mathcal{J} = \mathcal{J}_{\wedge}\cup \mathcal{J}_{\vee}$, and each of the jobs is assigned a set of prerequisites by a function $P\colon \mathcal{J}\to 2^{\mathcal{J}}$. The interpretation of prerequisites is the following: if $J\in \mathcal{J}_{\wedge}$, then all the jobs from $P(J)$ need to be finished before $J$ can be started. If $J\in \mathcal{J}_{\vee}$, then $J$ can be started as soon as at least one of the jobs from $P(J)$ is finished.

The goal is to schedule the jobs among the machines in such a way that the job $J_n$ is done as soon as possible, while respecting the prerequisites constraints. So, we only care about the job $J_n$ and want to perform only the jobs that enable doing $J_n$, while scheduling them in a way that minimizes the makespan.

I have spent some time looking, but I haven't found similarly formulated problem.

Question: could anyone point me to literature on similar problems? By similar I mean especially ones with the same type of prerequisites (both conjunctions and alternatives).

Answer 1

Without $\mathcal{J}_{\land}, \mathcal{J}_{\lor}$, the problem you described is called a Parallel machine scheduling problem in literature, and so not a Job shop scheduling problem.

If $J \in \mathcal{J}_{\land}$, then $P(J)$ are simply precedence constraints for $J$, or sometimes referred to as AND precedence constraints. There are a lot of papers on parallel machine scheduling problems with precedence constraints, that you should easily be able to find on the web.

If $J \in \mathcal{J}_{\lor}$, then $P(J)$ is referred to as OR-type constraints according to this paper: https://pdfs.semanticscholar.org/584b/292a3deb7c9ac1bdb753b0a3eb891338a0f3.pdf Personally, I could not find papers on parallel machine scheduling with AND, OR precedence constraints either, but I think you may be able to gather something useful from the papers that have cited the paper in the link above.

Answer 2

I can refer you to two papers that you may get some hints from. The first one is by Lee et al. (2012)¹, proposing an MILP for the flexible job-shop problem with ‘AND’/‘OR’ precedence constraints, and the second one is by van den Akker et al. (2006)², that studies a parallel machine scheduling problem with precedence constraints.

Apart from that, what comes to my mind is that you can force the last job to be scheduled in the following way ($\mathcal{J}$ is the set of jobs indexed by $j$ and $M$ is the set of machines indexed by $i$):

\begin{alignat}2\min&\quad z = C_{max}\\\text{s.t.}&\quad\sum_{i \in M} x_{ij} \leq 1, \quad \forall j \in \mathcal{J} \setminus n \tag1\\&\quad\sum_{i \in M} x_{in} = 1 \tag2\end{alignat}

where $x_{ij} = 1$ means that job $j$ is scheduled on machine $i$. Constraints (1) means each job can be processed by at most one machine, and constraint (2) implies the last job must be processed by one of the machines.

Although, probably due to the precedence constraints you need three-indexed variables.

---

_References:

_{[1] Lee, Sanghyup, et al. "Flexible job-shop scheduling problems with ‘AND’/‘OR’precedence constraints." International Journal of Production Research 50.7 (2012): 1979-2001.}

_{[2] Van den Akker, J. M., J. A. Hoogeveen, and Jules W. van Kempen. "Parallel machine scheduling through column generation: Minimax objective functions." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 2006.}