We introduce a new technique for solving several sequencing
problems. We consider Gilmore and Gomory's variant of the Traveling
Salesman Problem and two variants of no-wait two-stage flowshop
scheduling, the classical makespan minimization problem and a new
problem arising in the multistage production process in steel
manufacturing.
Our technique is based on an intuitive interpretation of sequencing
problems as Eulerian Extension Problems. This view reveals new
structural insights and leads to elegant and simple algorithms and
proofs for this ancient type of problems. As a major effect, we
compute not only a single solution; instead, we represent the entire
space of optimal solutions.
