Efficient formulation of flexible job-shop scheduling constraints

Question

I am working on a flexible job-shop scheduling problem, where indices are as follows:

• $i$: Index of operations
• $j$: Index of jobs
• $m$: Index of machines
• $p$: Index of operation sequences on a machine

The decision variables of this model are defined as follows:

• $x_{ijmp} \in \{0, 1\}$: If operation $O_{ij}$ is allocated to machine $m$ with sequence $p$, 1; otherwise, 0
• $t_{ij} \geq 0$: Start time of operation $O_{ij}$
• $t'_{pm} \geq 0$: Start time of machine $m$ in sequence $p$

Suppose $S_{ij}$ is the processing time of operation $O_{ij}$ (a preset parameter). If $a_{lm} \geq 0$, I need constraint sets that specify:

• $a_{lm} = S_{ij}$ if $\sum_{p} x_{ijmp} = 1$ and $l = t_{ij}$ (or $a_{lm} = S_{ij}$ if $x_{ijmp} = 1$ and $l = t'_{mp}$) $\forall l, m$
• $a_{lm} = 0$ if ($\sum_{i,j,p} x_{ijmp} = 0$) or ($\sum_{p} x_{ijmp} = 1$ and $l \neq t_{ij}$ for all operations) $\forall l, m$

Since the time set is large in my application (300+ time slots for real-sized instances), I think it might be better not to use a time-indexed formulation (i.e., $x_{ijmt}$). How do you efficiently formulate such a constraint set?

Answer 1

Whether you need to index on time depends on what you are trying to achieve, what's your objective. If you are trying to work on constraints involving $a_{lm} $ then

$ \sum_l l\delta_{lij} =t_{ij}$
$\sum_l \delta_{lij} =1 \ \ \forall i,j$ and $l$ is time index.

$S_{ij}(\sum_p x_{ijmp}+\delta_{lij} -1) \le a_{lm} \le S_{ij}(\sum_p x_{ijmp}+\delta_{lij}-1) + TS_{ij}(1-\delta_{lij}) $

$a_{lm} \le S_{ij}\sum_{ijp}x_{ijmp}$
where T could be 300.

Answer 2

Job shop scheduling problem is NP-hard in its essence and finding or developing a straightforward formulation to solve the large instance is really challenging work. If you would like to develop a math model I recommend having a look at the following papers to see how different formulations can solve the problem. Also, one of the best approaches to solving this kind of problem is by using either CP/SAT solver or some state-of-the-art heuristic algorithms like the shifting-bottleneck heuristic.

• Mixed Integer Programming Models for Job Shop Scheduling: A Computational Analysis
• Alan Manne, "On the job-shop scheduling problem", Operations Research vol 8, no 2 March-April 1960.

Answer 3

https://github.com/google/or-tools/blob/stable/examples/cpp/jobshop_sat.cc

It can parse most of standard jssp/fjssp problems. It has very good results. Make sure you have a beefy machine (8, and better 16 cores), and use the corresponding number of workers.