DFG Project "Algorithms for Complex Scheduling Problems"
within DFG Priority Programme 1307 "Algorithm Engineering"

Eulerian Extension Problem

In cooperation with Tobias Jacobs (Project Algorithm Engineering for Network Problems) and Nicole Megow (MPII Saarbrücken), we propose a new technique for considering the complexity of certain sequencing problems like the Gilmore-Gomory type Traveling Salesman Problem (GG-TSP) or the new flowshop problem we investigate [P4]. These problems have a natural interpretation as Eulerian Extension Problems. Briefly, in this approach for an instance of a sequencing problem, we build a Eulerian graph in which every tour corresponds to an optimal solution and vice versa. The main advantage of this approach is that instead of only one optimal solution, we obtain the entire set of optimal solutions, improving in that sense the original algorithm [1] for the GG-TSP.

The new objective function which we consider for no-wait flowshop scheduling is motivated by the process of strand casting in steel manufacturing. Since idle-times on the last machine, the strand casting machine, cause immense setup times, we aim to minimize the total number of idle times on the last machine in the process.

Production site for steel manufacturing.

Using the Eulerian Extension approach, we show that in case of only single-machine stages, this problem is solvable in polynomial time for two processing stages, and it is strongly NP-hard for more processing stages. Furthermore, we show that the problem can still be solved optimally when there are two machine stages and one machine in the first stage. For all other cases we show the strong NP-hardness, thus completely resolving the complexity status of this problem.

Back to main page.


[P4] Wiebke Höhn, Tobias Jacobs, and Nicole Megow.
On Eulerian Extensions and their Application to No-wait Flowshop Scheduling.
Journal of Scheduling, to appear. (Corresponding Tech-Report 008-2009)


[1] P. C. Gilmore and R. E. Gomory.
Sequencing a one state-variable machine: A solvable case of the traveling salesman problem.
Operations Research, 12:655-679, 1964.