N operations subject to precedence constraints are to be sequenced on a single machine. Each operation can be executed by exactly one of the machine’s grabs. The task is to find a schedule minimizing the number of grab’s changes. This ‘Robot Sequencing Problem’ was introduced and studied by K. Richter. Here the authors study its graph theoretical counterpart called ‘Acyclic Subdivision Problem’ and the complexity of a generalization called ‘Restricted Robot Sequencing Problem’.
