= Dummy-job reduction for sequence-dependent setup times
Add a dummy job $0$. Give the arc $0\to i$ cost equal to job $i$'s initial setup, the arc $i\to j$ its changeover cost, and every arc $i\to0$ zero cost. A <Hamiltonian cycle> through the dummy represents a schedule, starting just after $0$ and ending just before it. The total processing time is constant on a single machine, so minimizing cycle cost minimizes completion time. Dropping <subtour elimination constraints> gives an <assignment problem> lower bound.
Back to article page
