Domino sequencing: Scheduling with state-based sequence-dependent setup times

Abstract

We introduce the Domino Sequencing problem, a scheduling problem with special sequence-dependent setup times. For each job $j$ there are corresponding start and end states $a_j$ and $b_j$. When job $j$ is scheduled immediately before job $k$, a setup time of 1 is needed if $b_j\ne a_k$. We present polynomial-time algorithms for various versions. When jobs are partitioned into families, we show that the problem becomes $\mathsf{NP}$-hard and present a fixed-parameter tractable algorithm.