Sequencing of jobs

Suppose we need to sequence $n$ jobs where each job has a cost $a_i$. In addition there is a changeover cost $c_{i,j}$ when job $i$ immediately precedes job $j$ (see this post). 

First observe that the cost $\sum_i a_i$ form just a constant (we need to execute each job exactly once), so we can leave them out of the model.

For some the remaining problem may look like a TSP (Traveling Salesman Problem), except we don’t need to return to the city where we started from. We can also look at it differently.

The task of assigning jobs to periods is just like an assignment problem:

$$\boxed{\begin{align}  &x_{i,t} \in \{0,1\} \\                           &\sum_t x_{i,t} = 1 \>\>\forall i\\                           &\sum_i x_{i,t} = 1 \>\>\forall t \end{align}}$$

This was the easy part. To see if a job $j$ immediately follows a job $i$, we can do something like:

$$\boxed{\begin{align}  &y_{i,j} \in \{0,1\} \\                           &y_{i,j} = \sum_{t} x_{i,t} x_{j,t+1} \end{align}}$$

The sum gives us either 0 or 1 for feasible integer solutions. A slightly different formulation turns out to be easier to handle:

$$\boxed{\begin{align}  &y_{i,j} \in \{0,1\} \\                           &y_{i,j} \ge x_{i,t} x_{j,t+1}\>\> \forall t \end{align}}$$

We let $y_{i,j}$ float unrestricted if $j$ is never a successor to $i$. In that case, we leave it to the objective to choose $y_{i,j}=0$ when needed.

We can linearize the last inequality by $y_{i,j} \ge x_{i,t} + x_{j,t+1} –1$. Once we have $y_{i,j}$ the objective is obvious: minimize $\sum_{i,j} c_{i,j}y_{i,j}$.

The complete model can look like:

In the model we paid some attention to excluding cases where $i=j$. Note that with $c_{i,i}=0$ we just could leave out this exclusion, but I always prefer to model these things a bit more precise. The results for random $c_{i,j}$ are: