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.

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.

### Publication.

[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) |

### Reference.

[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. |