In a flexible job-shop scheduling problem, we are trying to minimize the makespan. We have $n$ jobs that need to run on $m$ machines. Each job $i$ consists of $n_{i}$ operations ($O_{i1},O_{i2},…,O_{in_{i}}$). For each operation $O_{ik}$, processing machine must be from the machine set $A_{ik}$.

Here is the formulation of variables and parameters:


$i, h$: job index; $i, h = 1,2.,...,n$

$j$: machine index, $j = 1,2,...,m$

$k,g$: operation index, $k,g= 1,2,...,n_{i}$


$n$: total number of jobs

$m$: total number of machines

$n_{i}$: total number of operations of job $i_{t}$

$t_{ikj}$: processing time of $k$th operation of job $i$

Decision variables :

$c_{ik}$: completed time of $O_{ik}$

$x_{ikj}$: machine $j$ is selected for $O_{ik}$


The last two constraints are intuitive, with the variable $x_{ikj}$ either being wrong or true, and the time needed for each operation always being positive. But I can't easily formulate the remaining three constraints.


The first constraint says that the elapsed time between starting and ending one of the operations ($k$) in a particular job ($i$) is at least the time required for that operation on machine $j$ ($t_{ikj}$) if the operation is done on machine $j$ ($x_{ikj}=1$) and at least 0 if not ($x_{ikj}=0$).

The second constraint prohibits jobs from overlapping on a machine. Note that the middle operator ($\vee$) means "or", so the constraint is satifisfied if either bracketed term is true. Also note that if either $x_{hgj}$ or $x_{ikj}$ is 0, the corresponding bracketed term is 0 ($0\ge 0$) and the constraint is satisfied. Now assume that $x_{hgj}=1=x_{ikj}$, meaning operation $g$ of job $h$ and operation $k$ of job $i$ are both being done on machine $j$. $c_{hg} - c_{ik} - t_{hgj} \ge 0$ means that operation $k$ of job $i$ ended before operation $g$ of job $h$ began. The other bracketed term being true means operation $g$ of job $h$ ended before operation $k$ of job $i$ began. So the only way to satisfy this constraint when the same machine is doing both operations is for the operations not to overlap.

The third constraint says that every operation of every job is assigned exactly once, on an eligible machine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.