Document [original]

On Eulerian Extension Problems and their Application to

Sequencing Problems

Wiebke H¨

ohn ∗Tobias Jacobs †Nicole Megow ‡

February 2009, Update: July 2009

Abstract

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 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. For the new flowshop scheduling problem we give a full

complexity classification for any machine configuration.

1 Introduction

We present a new technique for analyzing sequencing problems such as no-wait flowshop scheduling prob-

lems and a variant of the Traveling Salesman Problem (TSP). We show that these problems have a natural

interpretation as Eulerian Extension Problems. This leads to new structural insights and new solution meth-

ods. On a high level view, for an instance of a sequencing problem we find a particular Eulerian graph in

which all existing Eulerian circuits represent sequencing solutions with the same cost. In fact, we provide the

entire set of optimal solutions, instead of just a single one. For a non-standard flowshop sequencing problem,

which has not been investigated from an information theoretic point of view, we gain new structural insights

which form the basis for fully settling the complexity status of any particular problem case.

A directed multi-graph G= (V,E)is called Eulerian if it contains a cycle visiting each edge exactly once.

AEulerian extension is a set of additional edges E0for a given (not necessarily connected) multigraph G=

(V,E)such that (V,E∪E0)is Eulerian. A Eulerian Extension Problem is, generally speaking, the problem of

finding a Eulerian extension minimizing the total cost of additional edges E0according to some cost function.

Notice that the classical Chinese Postman Problem (see e.g. [18]) is a special case in which the given graph

is strongly connected and the cost function is based on the cost of paths in the graph. Eulerian extension

problems are generally intractable as straightforward reduction from TSP shows. We investigate Eulerian

Extension Problems for special classes of cost functions arising in the context of the following classes of

sequencing problems.

The TSP is one of the most intensively studied optimization problems; see e.g. [9]. In its full generality

it is highly intractable, however special cases can be solved optimally in polynomial time. One of the

most famous solvable subclasses was studied already four decades ago by Gilmore and Gomory [4]. In

this problem variant, which we denote by G-TSP, each city iis associated with two numbers Aiand Bi

for i=1,...,n. The cost for traveling from city ito city jis RAj

f(x)dx if Aj≥Biand RBi

g(x)dx otherwise,

where f,gare integrable functions satisfying f(x)+g(x)≥0, for any x.

∗[email protected]. Technische Universit¨

at Berlin, Germany. Supported by the Deutsche Forschungsgemeinschaft

(DFG) as part of the Priority Program “Algorithm Engineering” (1307).

†[email protected]. Albert-Ludwigs-Universit¨

at Freiburg, Germany.

‡[email protected]. Max Planck Institute for Informatics, Saarbr¨

ucken, Germany.

Another classical sequencing problem is no-wait flowshop scheduling. In flowshop scheduling, we con-

sider a production process where njobs J1,...,Jnmust pass sproduction stages L1,...,Ls. Each job Jj

consists of soperations each of which is dedicated to a specific stage Lion which it must process for pi j time

units without preemption. Note that we consider operations with zero processing time as infinitely small

operations which require a free machine. Each stage Lihas miidentical parallel machines available. The

jobs pass the production stages L1,L2,...,Lsin exactly this order. In a feasible no-wait flowshop schedule,

there is no waiting time allowed between the execution of two consecutive operations of the same job. The

goal is to minimize the makespan Cmax, that is the completion time of the last job. Following the classical

three-field notation [5] we denote this problem by F|nwt|Cmax if there is only a single processor available

on each stage and by FF|nwt|Cmax in the multiprocessor case. In case that the number of stages is fixed to s,

we denote the corresponding processor environments by Fsand FFs, respectively.

In the single processor case, the no-wait condition implies the same job order on each machine stage.

Thus, idle times are uniquely determined by a job order which leads to a natural interpretation as an asym-

metric TSP. In fact, F2|nwt|Cmax is well-known to be a special case of G-TSP [4, 11]: each job jcan be

interpreted as a city with Aj=p1jand Bj=p2j, and the cost function is of Gilmore-Gomory type with f≡1

and g≡0.

A structurally quite different sequencing problem concerns no-wait flowshop scheduling with the objec-

tive of minimizing the number of interruptions, i.e., the number of continuous idle time intervals on the last

stage Ls. Here, we refer to idle time as time intervals where a machine is not processing any job during

the actual production process, i.e., the time before the first job and after the last job to be processed on the

particular machine is not considered as idle time. We denote this new objective by G.

This problem is motivated by a particular application in steel production, the continuous casting process,

in which ladles of melted steel have to pass several production stages. The final stage, the casting machine,

plays a special role: the steel must flow continuously into the casting machine. When the flow is broken (we

call it interruption), then the casting machine must be stopped for maintenance and extensive cleaning.

Therefore, practitioners call it their objective to minimize the number of interruptions.

Related work. Gilmore and Gomory [4] derived an algorithm to find an optimal solution for G-TSP. Its

computation time O(nlogn)matches the lower bound on the worst case time complexity for any optimal

algorithm solving this problem [13]. A slightly simplified variant of this algorithm has been presented by

Vairaktarakis [16].

Due to its practical importance in production planning, most of the existing literature on no-wait flow-

shops addresses the objective of minimizing the makespan. For an extensive survey on various occurrences

of no-wait constraints in production environments and previous theoretical work we refer to [6]. The special

case of two-stage scheduling F2|nwt|Cmax can be solved to optimality directly with Gilmore and Gomory’s

algorithm [4, 11]. The complexity status changes if there is more than one processor on one of the two

stages; then the problem becomes strongly NP-hard [15].

The particular problem of scheduling the continuous casting process is investigated from a practical point

of view e.g. in [7, 10, 14], where mathematical programming approaches as well as meta-heuristics and

simulation are considered. To the best of our knowledge, there is no literature on theoretical investigations

on the problem of minimizing the number of interruptions in a no-wait flowshop. The only related theoretical

work we are aware of, enforces the aim for interruption-free scheduling as a hard constraint. In [2, 3], the

authors give complexity and approximation results for openshop and flowshop problems with the objective

to minimize the makespan when no interruption is allowed on any machine. This restriction is much stronger

than what we aim for. In our application, idle times on other stages than the last one, the casting machine,

do not incur extra cost. A more restricted variant of the same problem is considered in [17] with only two

production stages and unit processing times on the first stage such that interruptions can occur only on the

second stage. Even though this processor environment is close to our setting, we do not see how results

could transfer between the makespan minimization problem and our problem of minimizing the number of

interruptions.

Our contribution. We interpret Gilmore and Gomory’s TSP as a Eulerian Extension Problem with a specific

cost function. We present an optimal algorithm which is much simpler than previously proposed ones [4, 16]

and which admits a much simpler and more intuitive analysis (Section 2). Its worst case computation time

is O(nlogn)which is best possible [13]. Moreover, our algorithm reveals a structural property that seems

to be inherent in this kind of sequencing problems. Typically, an optimal solution is not unique. With

our method we keep an implicit representation of the set of optimal solutions and defer the selection of a

particular tour to the final part of the algorithm. This gives us the opportunity of conveniently accessing all

optimal solutions. Besides the theoretical significance, this is meaningful to practical applications in which

often a secondary optimization criteria plays a role. In this case, one may choose accordingly from the set

of all optimal solutions regarding the first criteria.

Clearly, the optimality result for G-TSP applies directly to the classical two-stage flowshop schedul-

ing problem F2|nwt|Cmax since it is a special case of G-TSP. This is not the case for the new flowshop

problem F2|nwt|G. Nevertheless, we show an interpretation as a Eulerian Extension Problem with another

appropriate cost function and derive an elegant and fast optimal algorithm (Section 3). In this case, we obtain

an implicit representation of all optimal solutions in time O(nlogn), from which any particular optimum can

be extracted in linear time. The main computation effort lies in sorting all processing times once, and thus,

the algorithm runs in linear time if processing times are already sorted. Moreover, we solve optimally the

generalized problem FF2|nwt|Gwith a single machine on the first stage, m1=1. Notice, that this result is

a sharp contrast to the makespan variant of the same problem which is known to be strongly NP-hard [15].

In Section 4 we show that the problem on three machine stages F3|nwt|Gis NP-hard. Again an inter-

pretation as Eulerian Extension Problem is crucial. Finally, we complement our results with further findings

that fully reveal the computational complexity of FFs|nwt|Gfor each value of sand each machine config-

uration m1,...,ms.

2 Solving the Gilmore-Gomory Traveling Salesman Problem

We revisit the variant of the traveling salesman problem denoted by G-TSP in the previous section. Both

algorithms, the original one by Gilmore and Gomory [4] and the improved method proposed by Vairak-

tarakis [16], are based on an interpretation of the problem as a bipartite matching problem, where each city i

corresponds to an edge, the so-called city edge, from point Aiin the first partition to Biin the second parti-

tion. The goal is to find a minimum cost matching E0such that the union of E0and the city edges constitute

a cycle. Their algorithms first sort the vertices in both partitions, then compute a minimum cost matching

and finally transform it into a cyclic one using an involved patching algorithm.

Similarly to these approaches, we also model a city ias an edge (Ai,Bi)and call it city edge, and we also

seek to insert a minimum cost set E0of additional edges called extension edges such that the resulting graph

contains a Eulerian cycle. The conceptual difference is that we do not consider the graph as bipartite, i.e. we

allow E0to contain any possible edge.

Definition 1 (One-Dimensional Eulerian Extension Problem, 1DEE).Given a finite directed graph G =

(V,E)where vertices in V are labeled with real numbers, and given integrable functions f ,g:R→R

with f (x)+g(x)≥0for any x ∈R, the problem 1DEE denotes the task of finding a Eulerian Extension E0

minimizing ∑(u,v)∈E0c(u,v), where

c(u,v) = 









f(x)dx u ≥v

g(x)dx v >u.

To avoid overloaded notation, we refer to a vertex by its label.

Theorem 1. G-TSP is equivalent to 1DEE. The reductions can be done in polynomial time.

Proof. Given an instance Iof G-TSP, we construct the directed multigraph G= (V,E)of a 1DEE instance I0

as follows: let V=Sn

i=1{Ai,Bi}and E=Sn

i=1{(Ai,Bi)}. A tour Tfor Ican be directly translated into a

Eulerian extension E0for I0having the same cost: For any city jthat is visited immediately after city i, add

an extension edge (Bi,Aj)to E0. The total cost of E0equals the cost of the tour Tby definition of the cost

functions.

Conversely, given a 1DEE instance I0with the graph G= (V,E), we construct the G-TSP instance Iby

converting each edge (u,v)∈Einto a city jwith Aj=u,Bj=v. Consider a solution E0for I0, and find an

arbitrary Eulerian tour T0in V= (G,E∪E0). We show that by interpreting the order of the city edges in T0

as the order of the cities, gives a solution Tto the G-TSP instance Iof the same cost as E0.

Let (w1,w2,...,wm)be a sub-path of T0traversing only extension edges. We assume w.l.o.g. that w1<

wm; the reverse case works analogously. Moreover, we can assume that wi<wi+1for i=1,...,m−1.

Suppose there exists values wi<wi+1and wi+1>wi+2. Then simple calculations show that replacing

edges (wi,wi+1),(wi+1,wi+2)∈E0by (wi,wi+2)does not increase the cost of the Eulerian extension.

With this observation and the linearity of integrals, the total cost of extension

edges (w1,w2),(w2,w3),...,(wm−1,wm)between successive city edges (∗,w1)and (wm,∗)equals c(w1,wm).

This implies by definition of the cost function that the costs of solutions Tand T0are equal.

Motivated by the cost function of 1DEE that is defined on vertex labels, we introduce the concept of

minimal edges. Consider a linear ordering of vertices in non-decreasing order of labels. Then we call an

edge (u,v)minimal, if uand vare direct neighbors in this ordering.

Lemma 1. Given a Eulerian extension E0for an instance of 1DEE, there is a Eulerian extension E00 satisfy-

ing the following properties: E00 contains only minimal extension edges, E0and E00 have the same cost, and

for each Eulerian cycle in E ∪E0there is one in E ∪E00 where the city edges occur in the same order.

Proof. Let (u,v)be a non-minimal edge in E0, i.e., there is a vertex wwith u<w<vor u>w>v. We

replace (u,v)by (u,w)and (w,v)to obtain E00. This preserves the balance of indegree and outdegree for

each vertex, and due to the linearity of the integral the overall cost does not change. Repeatedly performing

this kind of operation for each non-minimal edge we obtain a Eulerian extension that contains only minimal

edges. Analogously, we can replace each edge of a Eulerian cycle in E∪E0by the corresponding path of

minimal edges in E∪E00. This preserves the order of city edges in the cycle.

Let indeg(v)and outdeg(v),v∈V, denote the indegree and outdegree of v, respectively. The following

sufficient condition for a Eulerian graph is well-known; see [18].

Lemma 2. A graph G = (V,E)is Eulerian if and only if it is connected and indeg(v) = outdeg(v), for

all v ∈V .

Let indeg(V0)denote the indegree of a subset V0⊆V, i.e., the number of edges (u,v)∈Ewith u/∈V0

and v∈V0. Let the outdegree outdeg(V0)be defined analogously. We state a necessary condition based on

indegree and outdegree of vertex subsets.

Lemma 3. If a graph G = (V,E)is Eulerian, then indeg(V0) = outdeg(V0)for any subset of vertices V0⊆V.

Proof. We prove the statement by showing a more general result.

indeg(V0)−outdeg(V0)

=µ∑

v∈V0

indeg(v)−|{(u,v)|u,v∈V}|¶−µ∑

v∈V0

outdeg(v)−|{(v,u)|u,v∈V}|¶

=∑

v∈V0

indeg(v)−∑

v∈V0

outdeg(v)

The basic idea for our algorithm solving 1DEE is as follows: We restrict ourselves to solutions consisting

only of minimal edges. First, we identify an edge set that any such feasible solution must contain. We obtain

a set of connected components each of which is Eulerian. In the second step, we add a minimum cost edge

set that connects all components while keeping them Eulerian.

Algorithm 1

1: Sort all vertices in Vin non-increasing order of their labels.

2: Let E0=/0. For i:=1 to n−1 do

Consider v, the i-th vertex in the ordering, and denote its direct successor by v0. Compute b(v) =

indeg(v)−outdeg(v)with respect to the graph (V,E∪E0).

If b(v)>0, then add b(v)copies of the minimal edge (v,v0)to E0, otherwise, add −b(v)copies of

the minimal edge (v0,v)to E0.

3: Let G1,...,Gkdenote the connected components of the graph (V,E∪E0). If k≥2, construct the undi-

rected, connected component graph Hby contracting each Gi,i=1,...,k, to a single vertex in H. For

any minimal edge (u,v)/∈E0with u∈Giand v∈Gjwe add an undirected edge (Gi,Gj)to Hwith

weight c(u,v)+c(v,u).

Compute a Minimum Spanning Tree (MST) Tin H. For each edge (u,v)∈T, add both associated

directed, minimal edges (u,v)and (v,u)to E0.

Lemma 4. Algorithm 1 chooses in Step 2 only edges that are necessary for any feasible Eulerian extensions

that consist only of minimal edges.

Proof. We prove that after any iteration of Step 2 in Algorithm 1, E0consists only of necessary edges. In

any iteration, the algorithm inserts |b(v)|edges between a vertex vand its direct successor v0in the given

ordering. Consider some iteration and the corresponding vertices vand v0. Let V0={u∈V|u≤v}. Lemma 3

provides the necessary condition that indeg(V0) = outdeg(V0)in the given graph when enhanced by any

Eulerian extension. Before inserting additional edges, we have indeg(u) = outdeg(u)for any u∈V0\ {v}

in the current graph (V,E∪E0). Since we are restricted to minimal extension edges, any Eulerian extension

must add |indeg(V0)−outdeg(V0)|appropriately oriented edges between vand v0. The algorithm inserts

exactly the required number of edges since |indeg(V0)−outdeg(V0)|=|indeg(v)−outdeg(v)|=b(v).

Theorem 2. Algorithm 1 solves 1DEE optimally in time O(nlogn).

Proof. By Lemma 1 we can restrict our attention to Eulerian extensions consisting only of minimal edges.

Let E1denote the set of extension edges chosen by Algorithm 1 by the end of Step 2. Each vertex i=

1,...,n−1 has equal in- and outdegree in the graph (V,E∪E1). By the handshaking argument this also

holds for the last vertex. If (V,E∪E1)is connected, then it is Eulerian by Lemma 2. Applying additionally

Lemma 4 we have proven that E1is a necessary and sufficient set of edges and thus optimal.

Otherwise, (V,E∪E1)consists of multiple strongly connected components G1,...,Gkeach of them being

Eulerian. By Lemma 4 any optimal solution must contain E1. The algorithm now finds a set of additional

minimal extension edges of minimum total cost that connects all components and ensures that the graph

is Eulerian. Notice, that if we add a single extension edge (u,v)to connect two components Giand Gj,

then by Lemma 3 and the restriction to minimal edges (Lemma 1), we additionally need to add the reverse

edge (v,u)to ensure that the resulting graph is Eulerian. Therefore our algorithm considers in Step 3 all

relevant edges to connect G1,...,Gkand assigns cost for adding both, forward and backward edge. Thus,

the MST solution on the accordingly constructed graph Hcorresponds to a minimum cost edge subset that

connects all components and keeps the graph Eulerian.

Concerning the runtime of the algorithm, we note that the connected component graph Hin Step 3 can

be constructed in O(n)because the vertices are already sorted by their labels (Step 1). Consider all vertices

in the given order starting from the vertex with smallest index. Suppose v∈Gi. If v’s direct successor v0

belongs to a different connected component Gj6=Gi, then add an undirected edge between the corresponding

vertices Giand Gjin H. With this observation, the runtime of our algorithm is dominated by sorting the

input and computing an MST which can be done in O(nlogn).

The reduction from G-TSP to 1DEE (Proof of Theorem 1) implies that for each solution to G-TSP there

is a Eulerian tour in a solution to the corresponding 1DEE instance. In this Eulerian tour, the city edges are

traversed in exactly the same order as the cities are traversed in the G-TSP solution. By Lemma 1 there is a

Eulerian extension consisting only of minimal edges which admits such a tour. This implies that we do not

loose any optimal G-TSP tour when restricting ourselves to minimal edge extensions.

If the minimum spanning tree computed in Step 3 of Algorithm 1 is unique, then the optimal set of

Eulerian extension edges E0is unique under the restriction to minimal edges. Since this does not restrict

the space of optimal solutions for the corresponding G-TSP instance, each Eulerian cycle in the extended

graph (V,E∪E0)corresponds to an optimal solution for G-TSP. If there is more than one MST, then each of

them represents a subset of all optimal G-TSP solutions.

3 Solving Two-Stage No-wait Flowshop Problems

While the makespan minimization problem F2|nwt|Cmax can be solved directly as a special case of G-TSP

with Gilmore-Gomory type cost functions f≡1, g≡0, there is no way to express the interruption related ob-

jective function Gas special functions fand gin G-TSP. Nevertheless, we show that the problem F2|nwt|G

has an interpretation as a Eulerian Extension Problem, which leads to a fast and elegant algorithm.

We define a cost function for a Eulerian Extension Problem in which extension edges (u,v)with u<

vaccount for interruptions on the second machine. We call such extension edges up edges. We denote

extension edges (u,v)with u>vas down edges.

Definition 2 (G-related One-Dimensional Eulerian Extension Problem, G-1DEE).Given a finite directed

graph G = (V,E)where the vertices in V are labeled with real numbers, the problem G-1DEE is to find a

Eulerian extension for G minimizing the number of up edges.

As in Section 2, we call a down edge (u,v)minimal if uand vare direct neighbors in a linear ordering

of Vby non-decreasing labels. Furthermore, we denote an up edge (u,v)as maximal if uhas the minimum

label and vhas the maximum label in V.

Lemma 5. Given a Eulerian extension E0for an instance of G-1DEE with G = (V,E), there is a Eulerian

extension E00 satisfying the following properties: E00 contains only minimal down edges and maximal up

edges, E0and E00 have the same cost, and for each Eulerian cycle in (V,E∪E0)there is one in (V,E∪E00)

where the edges from E appear in the same order.

Proof. Non-maximal up edges (u,v)are can be replaced with the edges (u0,v0),(v0,v),(u,u0), where (u0,v0)

is the maximal up edge. The two other new edges point downwards, so the total number of up edges

is preserved. As soon as all up edges are maximal, non-minimal downward edges can be replaced with

minimal ones as described in the proof of Lemma 1.

Theorem 3. F2|nwt|Gcan be reduced to G-1DEE in polynomial time.

Proof. We construct an instance I0= (V,E)of G-1DEE from an F2|nwt|Ginstance Iby defining V=

i=1{p1i,p2i}and by adding a job edge (p1i,p2i)to Efor each job Ji,i=1,...,n. We add another maximal

up edge, serving as a dummy job between the first and last job in the tour.

In the following we show that an optimal solution to I0contains kup edges (in addition to the dummy

edge above) if and only if an optimal solution to Icauses kinterruptions.

Consider a schedule for I. For simplicity, we assume that jobs are scheduled in increasing order of their

indices. We add an extension edge (p2i,p1i+1)to E0for i=1,...,n−1. This way we obtain a number of

up edges equal to the number of interruptions caused by the schedule. Let (u,v)be the maximal dummy

up edge of the instance I0. Adding the down edges (p2n,u),(v,p11), we obtain an extension admitting the

Eulerian cycle p11,p12,p21,p22,...,p2n,u,v,p11.

Consider an optimal solution E0to I0. We employ Lemma 5 assuming that all down edges are minimal

and all up edges are maximal. We convert the set E0into a solution to Iby scheduling the jobs in the order

in which the corresponding job edges appear in some Eulerian cycle in (V,E∪E0), starting with the first job

after the dummy job edge. By construction, any job edge can be reached from the dummy edge by down

edges only, and conversely, we can reach the dummy from any job edge also by using only down edges.

Whenever an interruption appears between two consecutive jobs, there is at least one other up edge

between the corresponding job edges in the cycle. There is also at most one up edge between two consecutive

job edges as otherwise up edges could be removed from the extension together with a sequence of down

edges. Therefore, the number of interruptions is k.

Intuitively, our algorithm for solving G-1DEE proceeds as follows: first, it determines the minimum

number of up edges that are necessary and sufficient for achieving balanced indegree and outdegree at each

vertex. They are inserted together with the suitable set of down edges. Then, the algorithm checks if the

resulting graph is strongly connected. If not, one additional up edge and the respective sequence of down

edges suffice to achieve the desired connectivity.

Algorithm 2

1: Sort all vertices in Vin non-decreasing order of their labels.

2: Let vibe the i-th vertex in the ordering and let Vi:={u∈V|u≤vi}. Compute bmax :=

maxi=1,...,n−1{0,b(vi)}, where b(vi):=indeg(Vi)−outdeg(Vi).

3: Initialize E0as the set containing bmax copies of the maximal up edge (v1,vn).

4: For i:=1 to n−1, add bmax −b(vi)minimal down edges (vi+1,vi)to E0.

5: If (V,E∪E0)is not strongly connected, add one further maximal up edge (v1,vn)and minimal down

edges {(vi+1,vi)|1≤i≤n−1}to E0.

With similar techniques as in the previous section we prove the following result.

Lemma 6. Algorithm 2 chooses in Step 3 and 4 only edges that are necessary for any feasible Eulerian

extension that consist only of minimal down edges and maximal up edges. The two steps effectuate that

indeg(v) = outdeg(v)for each v ∈V in (V,E∪E0).

Proof. Let vibe the vertex maximizing b(vi)in Step 2 of the algorithm. Lemma 3 states that there must

be max{0,b(vi)}=bmax edges from Vito V\Viin any feasible Eulerian extension. As these edges are up

edges, they have to be maximal due to our restriction. They are inserted by the algorithm in Step 3.

After Step 3, we have indeg(Vi)−outdeg(Vi) = b(vi)−bmax ≤0 in the graph (V,E∪E0)for each i=

1,...,n−1. So from Lemma 3 follows that for the graph to be Eulerian there must be b(vi)−bmax additional

edges from V\Vito Vi. Such edges are down edges, and due to our restriction to minimal ones, they must

be copies of the edge (vi+1,vi). Inserting them is exactly what Algorithm 2 does in Step 4.

As soon as Step 4 has been executed, we have indeg(Vi) = outdeg(Vi)for 1 ≤i≤n, and in partic-

ular indeg(v1) = outdeg(v1). Since indeg(Vi)−outdeg(Vi) = ∑i

j=1indeg(vj)−outdeg(vj)(see proof of

Lemma 3), it follows inductively that indeg(vi) = outdeg(vi)for all i.

Theorem 4. Algorithm 2 solves G-1DEE optimally in time O(nlogn). Steps 2-5 take only linear time.

Proof. By Lemma 5 it suffices to consider only maximal up edges and minimal down edges as extension

edges. Let E1be the set of edges chosen by the algorithm by the end of Step 4. By Lemma 6, E1is a subset

of any feasible Eulerian Extension for G, and we know that the indegree and outdegree of each node is

balanced in (V,E∪E1). If this graph is strongly connected, it is Eulerian (Lemma 2), and thus, Algorithm 2

is optimal.

Otherwise, at least one additional extension edge, i.e., either a maximal up edge or a minimal down edge,

must be added. Suppose, we add a minimal down edge, say (vi+1,vi), then we have indeg(Vi)−outdeg(Vi) =

1 in the resulting graph. From Lemma 3 follows that we need an additional up edge for re-establishing

balanced indegree and outdegree for each node. Thus, to establish connectivity in (V,E∪E1)it is necessary

to add an up edge. It is easy to see that with one additional up edge the set of minimal down edges inserted

in Step 5 of the algorithm is necessary and sufficient to re-establish the balancedness of each node’s indegree

and outdegree. The resulting graph (V,E∪E0)contains the cycle v1,vn,vn−1,...,v1and is therefore strongly

connected.

The runtime of the algorithm is dominated by the time for sorting, O(nlogn), in Step 1. The remaining

steps require linear computation effort; in particular, values b(vi)can be computed in Step 2 as b(v1) =

indeg(v1)−outdeg(v1)and b(vi) = b(vi−1)+indeg(vi)−outdeg(vi)in linear time. Although E0can contain

up to O(n2)edges after Step 4, the number of distinct edges is linear. For this reason it also takes linear time

to determine whether the graph is strongly connected or not in Step 5.

We remark that the optimal solution to G-1DEE is always unique, because the objective function only

depends on the number of up edges, and – assuming that all up edges are maximal – the set of down edges is

uniquely determined by their number. As a consequence of the reduction given in the proof of Theorem 3 and

Lemma 5, the extension E0computed by Algorithm 2 implicitly represents all optimal schedules. Since there

may be O(n2)many extension edges E0, computing an Eulerian tour in the graph obtained by Algorithm 2

may also require quadratic time.

Corollary 1. Any problem instance of F2|nwt|Gcan be solved optimally in time O(n2).

The above algorithm can be applied also to the two-stage flowshop problem to minimize the number of

interruptions with more than one machine on the second stage.

Theorem 5. Any problem instance I of FF2|nwt|Gwith a single processor on the first stage, m1=1, can

be solved optimally in time O(nlogn).

Proof. Given an instance Iof problem FF2|nwt|Gwith m1=1, we consider an instance I0which equals I

restricted to single machines on both stages, i.e., m0

1=m0

2=1. We find an optimal solution S0for I0with r0

interruptions. This can be done efficiently by Theorem 4 and gives a feasible solution for I. Now, we

construct an improved feasible schedule Sfor instance Iwith r=max{0,r0−m2+1}interruptions: if there

is an interruption in S0then we move the next block of interruption-free processing jobs to an unused machine

of the second stage; we repeat until all interruptions are resolved or until all m2machines are used in S. This

reduces the number of interruptions by m2−1 or less if r0<m2−1.

The solution Sis optimal for I. To see that, assume for the sake of contradiction there is an optimal

solution S∗with less interruptions r∗<r. Then the corresponding schedule can be transformed into a feasible

one for instance I0with r00 <r0interruptions. Run the set of jobs using machine miin S∗consecutively

for i=1,...,r∗−1 using only one processor at the second stage. This gives a feasible solution S00 for I0with

at most m2−1 interruptions more, i.e., r00 ≤r∗+(m2−1)<r+m2−1. This contradicts the optimality of

schedule S0for I0with r0≥r+m2−1 interruptions.

4 Complexity of Minimizing the Number of Interruptions

In contrast to the polynomial time solvable problems with two machine stages in Section 3, the problem

becomes strongly NP-hard in any other case.

Theorem 6. The problem FFs|nwt|Gis strongly NP-hard for any constant number of stages s ≥3and

arbitrary constant numbers of machines. The same is true for FF2|nwt|Gwith m1>1.

The proof follows by combining NP-hardness results for four particular problem classes (machine con-

figurations). The problem F3|nwt|G, which plays a key role, is considered in Section 4.1; to show hardness,

we utilize a two-dimensional generalization of the G-1DEE. The remaining problem classes are considered

in Section 4.2.

In the proofs, we actually give reductions to a decision variant of the problem under consideration,

i.e., we ask if an interruption-free solution exists. We denote the decision problem by E0(F3|nwt|G).

Obviously, the NP-completeness of the decision problem implies NP-hardness of the optimization variant.

Moreover, it rules out the existence of an approximation algorithm, unless P=NP. We remark here, that our

proofs can easily be extended to show that the optimization problem remains strongly NP-hard under the

assumption that every solution has at least one interruption.

4.1 Hardness for scheduling on three stages

We show that the problem F3|nwt|Gis strongly NP-hard. To show this result, we consider a natural two-

dimensional interpretation of G-1DEE in which each vertex has two labels which can be seen as points

in R2. We define the G-related two dimensional Eulerian Extension Problem (G-2DEE) as follows.

Definition 3 (G-2DEE).Given a directed graph G = (V,E)with vertices V ⊂R+

0×R+

0, determine whether

there exists a Eulerian extension E0for G using only down edges {(u,v)|u,v∈V,u≥v component-wise}.

We show that the problem G-2DEE is strongly NP-complete by reduction from the Three-Dimensional

Matching Problem (3DM).

Definition 4 (Three-Dimensional Matching, 3DM).Given a set U ⊆M1×M2×M3of triples, where M1, M2

and M3are pairwise disjoint and have the same number k of elements, decide whether U contains a sub-

set U0⊆U with |U0|=k and no two elements of U0agree in any coordinate.

Here we assume w.l.o.g. that any element of M1∪M2∪M3appears in at least one triple of U. The

problem 3DM is well-known to be strongly NP-complete [8]. Our reduction to G-2DEE borrows ideas from

the reduction of 3DM to a weighted tour problem given by R¨

ock [12] in order to show the NP-hardness of

the flowshop problem F3|nwt|Cmax .

Theorem 7. The problem G-2DEE is strongly NP-complete.

Proof. Denote the edges in a solution E0of G-2DEE as extension edges. Note, that in contrast to the

one-dimensional case, extension edges in this setting only contain down edges. We say that two points

u,v∈R+

0×R+

0are independent, if neither (u,v)nor (v,u)can be an extension edge due to the constraint

specified in Definition 3.

Consider two rectangles A= [xmin,xmax]×[ymin,ymax],A0= [x0

min,x0

max]×[y0

min,y0

max]in R+

0×R+

0. We

say that Aand A0are independent if any two points u∈A,v∈A0are independent. Formally, Aand A0are

independent if and only if either xmax <x0

min and ymin >y0

max, or xmin >x0

max and ymax <y0

min.

A point v= (vx,vy)is reachable from another point u= (ux,uy)if (u,v)is a down edge, and vis one-way

reachable from uif it is reachable from u, but uis not reachable from v. Formally, vis reachable from u

if ux≥vxand uy≥vy. One-way reachability is obtained by additionally demanding u6=v.

vmin

vmax

a|U|2

a33

a32

a23

a22

a13

a12

a11

A|U|

a21

a31

a|U|3

a|U|1

....

Figure 1: 2DEE representation of a 3DM instance.

Given an instance U⊆M1×M2×M3of 3DM with |M1|=|M2|=|M3|=k, we construct an equivalent

G-2DEE instance (V,E)as follows: Let {A1,...,A|U|}be a collection of pairwise independent rectangles.

For i=1,...,|U|, define three points ai1,ai2,ai3∈Aisuch that ai2is one-way reachable from ai1, and ai3

is one-way reachable from ai2. We define the set of vertices as V=Si=1,...,|U|{ai1,ai2,ai3}∪{vmin,vmax},

where vmin is such that it is one-way reachable from any other vertex in V, and vmax is such that any other

vertex in Vis one-way reachable from it. Formally, the vertex set can be implemented as vmin = (0,0),vmax =

(|U|+1,|U|+1), and ai j = (4i−j,4(|U|+1−i)−j)for 1 ≤i≤ |U|and j∈ {1,2,3}.

For constructing the edge set E, let U={U1,...,U|U|}be an arbitrary enumeration of the triples in U.

For any element b∈Mj,j=1,2,3, we add edges to (V,E)that constitute a directed cycle. That cycle,

called Cb, includes exactly all vertices ai j where bis the jth component of Ui. Consequently, Econtains 3k

pairwise vertex-disjoint cycles. The construction of Eis completed by adding kedges from vmin to vmax, see

Fig. 1.

In the following, we assume that E0is a solution to the G-2DEE problem instance (V,E). A Eulerian

tour (V,E∪E0)traverses (vmin,vmax)exactly ktimes. The following two points state crucial properties of

such a tour.

1. Let P=vmax,...,vmin be a path in (V,E∪E0)that is part of a Eulerian tour and does not include the

edge (vmin,vmax). Then all edges in P∩Eare contained in not more than three different cycles Cb1,Cb2

and Cb2.

2. Any Eulerian tour in (V,E∪E0)includes each cycle Cbas a contiguous sub-tour.

For showing the first property, consider some edge in Pthat belongs to a cycle Cbwith b∈Mj. There

are only three possibilities to continue Pafter the sink ai j of the edge has been reached. If Pcontinues using

another edge from E, then, due to the vertex-disjointness of the cycles, that edge also belongs to Cb. If P

continues with an edge from E0, then, due to the independence and reachability properties of V, that next

edge will be either (ai j,vmin)or (ai j,ai j0)with j0>j. In the former case, Pends. In the latter case, Pcan

enter a new cycle Cb0with b0∈Mj0, but j0is strictly larger than j. In other words, each time Penters a new

cycle Cb,b∈Mj, the index jstrictly increases. As j≤3, the first property follows.

Since there are kedges (vmin,vmax)and 3kcycles Cb, it follows from the first property that each cycle can

be entered at most once, because otherwise some cycles would remain not entered at all. Thus, in a Eulerian

tour each cycle must be completely traversed as soon at it is entered, yielding the second property.

Thus, a Eulerian tour leaves each cycle Cbat the same vertex it entered it. It follows that between

any two consecutive traversals of (vmin,vmax), three cycles Cb1,Cb2,Cb3are traversed, each time starting

and ending inside the same rectangle Ai. So the Eulerian extension of (V,E)has to have the form E0=

Sh=1,...,k{(vmax,aih1),(aih1,aih2),(aih2,aih3),(aih3,vmin)}, where i1,...,ikare such that each cycle Cbcan be

traversed. This is the case if and only if no two aihjand aih0jbelong to the same cycle, which is equivalent

to Ui1,...,Uikconstituting a matching.

Now we are ready to show NP-completeness for F3|nwt|Grespective its decision vari-

ant E0(F3|nwt|G).

Theorem 8. It is NP-complete to decide whether there is an interruption-free schedule for an instance of

F3|nwt|G.

Proof. We show the NP-completeness of the decision problem E0(F3|nwt|G)by reduction from G-2DEE.

Our proof has the following structure: We first give an interpretation of our scheduling problem as an

extension problem. Then we fix a set of properties that are only satisfied by G-2DEE instances representing

a scheduling problem instance in that way. Finally, we prove that any G-2DEE instance can be transformed

into an equivalent instance satisfying these properties.

Consider a set of jobs J1,...,Jn. A schedule without interruptions corresponds to a permutation

Jσ(1),...,Jσ(n)of the jobs, where for 1 ≤i<njob Jσ(i+1)can be scheduled after Jσ(i)without causing

an idle time on the third machine. This is the case if and only if p3σ(i)≥p2σ(i+1)and p3σ(i)+p2σ(i)≥

p2σ(i+1)+p1σ(i+1).

In terms of our extension problem, this means that the point (p2σ(i+1),p2σ(i+1)+p1σ(i+1))is reach-

able from the point (p3σ(i),p3σ(i)+p2σ(i)). We associate every job Jjwith an edge from (p2j,p2j+p1j)

to (p3j,p3j+p2j). In the consequence, there is an interruption-free schedule of J1,...,Jnif and only if the

induced graph (V0,E0)admits an extension E0such that there is a path traversing each edge exactly once.

This is the case if and only if there is a Eulerian extension of the graph (V,E)=(V0∪ {vmin,vmax},E0∪

{(vmin,vmax)}), where vmin (vmax) is such that it is smaller (greater) than all other elements of Vin both

coordinates.

We call a graph G∗= (V∗,E∗)with V∗⊂R+

0×R+

0legal, if it represents a scheduling instance in the

way we have just described. Respectively, an edge is called legal if it represents some job from a scheduling

instance. It is not hard to observe that for an edge to be legal it suffices that it has the form ((x,y),(x0,x+x0))

with x≤y. In other words, the source and sink vertex of a legal edge are above the bisectrix, and for a given

source there is only one degree of freedom for the choice of the sink. For a graph to be legal it suffices that

it is induced by ˆ

E∪{(vmin,vmax)}, where ˆ

Eis a set of legal edges, and vmin and vmax are like defined in the

preceding paragraph.

We complete our reduction by describing in Lemma 7 how to legalize an arbitrary instance G= (V,E)

of G-2DEE, that is, to transform it into a legal instance G∗= (V∗,E∗), where Gadmits a Eulerian extension

if and only if G∗does.

Lemma 7. Each instance of G-2DEE can be legalized in polynomial time.

Proof. First, we ensure that every vertex is above the bisectrix and no vertex has coordinates (0,0). This is

achieved by vertically shifting the whole graph by xmax =max{x|(x,y)∈V}+1. Technically, we obtain

the graph G1= (V1,E1)by adding xmax to the second coordinate of every vertex. As this does not change

the reachability relation between any pair of vertices, Gand G1are equivalent in the sense of G-2DEE.

In the second transformation step, we eliminate all illegal edges. Let edge (u,v) = ((ux,uy),(vx,vy)) ∈E1

be illegal. Let ymax =max{y|(x,y)∈V1}+1. We enhance V1by the vertices w1= (ymax −ux,ymax),w2=

(0,ymax),w3= (ymax,ymax)and w4= (vy−vx,ymax). Then, we replace (u,v)with the edges (u,w1),(w2,w3)

and (w4,v), see Fig. 2.

Straightforward observation shows that all new edges are legal and any possible tour in a Eulerian exten-

sion must traverse the path u,w1,w2,w3,w4,v. Thus, the modified graph admits a Eulerian extension if and

only if G1does.

We obtain the graph G2= (V2,E2)by iteratively eliminating every illegal edge from G1. Note that

each such elimination causes ymax to increase by one. Still G2does not necessarily represent a flow-

shop scheduling instance, as there has to be an edge (vmin,vmax). We take care of this requirement in

the last step of transformation. Let u= (ux,uy)∈V2be an arbitrary vertex. We insert vmin = (0,0)

and vmax = (ymax,ymax)into V2, where ymax =max{y|(x,y)∈V2}+1. Furthermore, we insert w1,w2

and w4defined like in the transformation from G1to G2. Note that w3has already been inserted as vmax.

Then, the edges (u,w1),(w2,vmin),(vmin,vmax)and (w4,u)are added to E2.

As the new vertices are above the bisectrix, the new edges are legal, and the resulting graph G∗=

(V∗,E∗)contains an edge from vmin to vmax, it represents an instance of F3|nwt|G. Any Eulerian tour

traverses the cycle u,w1,w2,vmin,vmax,w4,uas a closed sub-tour. Hence, G2and G∗are equivalent G-2DEE

instances.

ymax

w1w4

Figure 2: The edge (u,v)is replaced with the legal edges (u,w1),(w2,w3), and (w4,v).

4.2 More hardness results

First we consider flexible flowshops with two machine stages. We show by reduction from 3-PARTITION

that minimizing the number of interruptions is strongly NP-hard if the first stage contains two machines and

the second stage only one.

Definition 5 (3-PARTITION).Given a set A of 3m elements from N+with B/4<a<B/2for all a ∈A,

where B :=1

m∑a∈Aa, decide whether A can be partitioned into m disjoint sets A1,...,Amwith ∑a∈Aia=B

for i =1,...,m.

It is well known that 3-PARTITION is NP-complete in the strong sense, see [1].

Theorem 9. The problem E0(FF2|nwt|G)with m1=2and m2=1is strongly NP-complete.

Proof. Given a 3m-element instance Aof 3-PARTITION, we construct an instance Iof E0(FF2|nwt|G)

with m1=2 and m2=1. For any a∈Awe choose a job in Iwith processing times 1 and aon the first and

second stage, respectively. To partition these jobs, we add m+1 auxiliary jobs having processing times B

on the first stage and 0 on the second stage.

We show that in a schedule without interruptions, there is no point in time at which two auxiliary jobs

are processed in parallel on the first stage. First notice, that two auxiliary jobs running fully in parallel must

cause an interruption (i) with any job scheduled before them, because no job in Ihas processing time Bon

the second stage, and (ii) with any job scheduled after them, because no job in Ihas processing time 0 on the

first stage. Now, assume that there are auxiliary jobs J1and J2with start times S1<S2<S1+B, which, as a

consequence, fully block the first stage during [S2,S1+B). Since all jobs in Ihave positive processing times

on the first stage, no job can start at S1+Bon the second stage, and thus, an idle time after J1is unavoidable.

Therefore, we may assume that in any schedule without interruptions all auxiliary jobs are processed on

the same machine in the first stage. This induces mgaps of length at least Bbetween the auxiliary jobs on

the second stage. These gaps can be filled with the remaining jobs if and only if Ais a yes-instance.

Now, we generalize this NP-completeness result and combine it with the single machine case in Theo-

rem 8. The following two lemmata show that E0(FFs|nwt|G)with any constant number of stages s≥2

and constant numbers of machines, except s=2 and m1=1, is also strongly NP-complete.

Lemma 8. Consider E0(FFs|nwt|G)with a constant number of stages s ≥2. Then any variant of this

problem with constant numbers of machines m1,...,mswhere ms=1can be reduced to any other problem

variant with constant numbers of machines m0

i, i =1,...,s, satisfying m0

i≥mi, m0

s=1, and m0

k>mkfor

some k <s.

Proof. We consider E0(FFs|nwt|G)with a constant number of stages s≥2 and constant numbers of

machines. Given an instance Iof a problem variant with numbers of machines mi,i=1,...,s, where ms=1,

we build an instance I0of a problem variant with numbers of machines m0

i, satisfying m0

i≥mi,m0

s=1,

and m0

k>mkfor some k<s. In addition to the original jobs Jof I, we choose auxiliary jobs for I0which

force the jobs from Jto use only mimachines on stage Li. For blocking a stage Liwith m0

i>miaccordingly,

we add 2m0

i−mijobs with processing time p=maxj∈J∑s−1

i=1pi j +∑j∈Jps j on stage Li, and 0 elsewhere. We

q∑n

j=1ps j

Figure 3: Arrangement of auxiliary jobs in a schedule without interruptions (Lem. 8). Original jobs have to

be processed in dotted slots.

Figure 4: Schedule without interruptions for I0. (Lem. 9)

denote the auxiliary jobs corresponding to Liby Ai. For an arbitrary auxiliary job Jmod ∈Ai, we modify the

processing time on the last stage to q=p−∑j∈Jps j.

Given a schedule without interruptions for I0, we consider the sub-schedule of auxiliary jobs. Observe,

that the idle times on the last stage in this sub-schedule sum up to at most ∑j∈Jps j, since otherwise they could

not be filled with the jobs Jin the total schedule. For an arbitrary but fixed k∈ {1,...,s}, we examine the

arrangement of jobs in Ak. By its cardinality, there is a machine in stage Lkthat processes a subset ˜

Ak⊆Ak

of at least two jobs. Due to the largest possible length of idle times on the only machine of the last stage, ˜

does not contain more than two jobs. Thus, the jobs from ˜

Akgenerate an idle time of length exactly pon

the last stage. Since no further idle times are allowed, the remaining jobs from Akand the other auxiliary

jobs must be scheduled such that they exactly meet the previous jobs on the last stage. In particular, the

job Jmod must be scheduled such that it is processed at the beginning of the idle time, produced by the two

jobs from ˜

Akthat are processed on the same machine on Ls. Thus, we can assume that the auxiliary jobs are

arranged as in Fig. 3.

By definition of pand qthere exists a schedule without interruptions for the instance I0if and only there

exists one for the instance I.

Lemma 9. Consider E0(FFs|nwt|G)with a constant number of stages s ≥2. Then any variant of this

problem with constant numbers of machines m1,...,mscan be reduced to any other problem variant with

constant numbers of machines m0

i, i =1,...,s, satisfying m0

s≥msand m0

i=mifor i =1,...,s−1.

Proof. We reduce the problem E0(FFs|nwt|G)with constant numbers of machines m1,...,msto another

variant of this problem with machine numbers m0

i,i=1,...,s, satisfying m0

s≥msand m0

i=mielsewhere.

Given an instance Iof the former problem with set of jobs J, we build an instance I0of the latter problem

by adding auxiliary jobs to the instance I: We choose msjobs with processing time q=maxj∈J∑s

i=1pi j

on the last stage, and 0 on all other stages. Furthermore, we add m0

1m0

sjobs with processing time p>

(ms+1)q+∑j∈Jps j on stage L1, and 0 elsewhere. We denote these jobs with Jq

aux and Jp

aux, respectively.

If there exists an interruption-free schedule Sfor I, then the schedule in Fig. 4 shows how to arrange the

jobs from I0without idle times on the last stages: The jobs from Jp

aux are scheduled in blocks of m0

1jobs which

are processed in parallel on the first stage and on the same machine in the last stage. With sufficiently long

idle times between these blocks, we can process after msof them first a job from Jq

aux and then a sub-schedule

that corresponds to a last stage machine in S.

On the other hand, given a schedule for I0without interruptions, we can construct a schedule without

interruptions for I. In the following we call jobs with processing time 0 on the stages L1,...,Ls−1zero-jobs.

We claim that in any interruption-free schedule for I0every machine on the last stage processes first one or

more jobs from Jp

aux, second a zero-job and third an interruption-free sequence of jobs from J∪Jq

aux (which

may also include jobs from Jp

aux).

We consider a schedule for I0that does not contain an interruption. Then, the last stage idle times in the

sub-schedule induced by the jobs Jp

aux do not equal or exceed p, by definition of p. Thus, there is no pair of

jobs from Jp

aux that is processed on the same machine on the first and last stage. In particular, every first stage

machine processes exactly m0

sjobs from Jp

aux. Hence, given a machine on the first and last stage, there is a

unique job from Jp

aux which is processed on both machines. As a consequence, the m0

1jobs from Jp

aux, that

are processed on a particular machine Mon the last stage, use every machine in the first stage for processing

exactly one job.

Let cbe the first completion time of these jobs, and let J∈Jp

aux be a job completing at that time. Since

idle times on the last stage must be compensable with the jobs from I0, none of the jobs from Jp

aux on M

completes after d=c+msq+∑j∈Jps j. Thus, these jobs block the first stage during [d−p,c). This yields

two characteristics for schedules without interruptions: First, Jcan be followed on machine Monly by

zero-jobs. And second, by

¯¯[d−p,c)¯¯=p−msq+∑

j∈J

ps j >q=max

j∈J

∑

i=1

pi j,

no job can be processed before Jon M. Since the jobs from Jp

aux have processing time 0 on the last stage, all

further jobs from J∪Jq

aux on Mfollow the zero-job without idle time. This completes the proof of the claim.

Given a schedule for I0with the properties claimed above, we show how to construct an interruption-free

schedule for the instance I. Consider all machines on the last stage that process a job from J∪Jq

aux. If there

is a machine that processes more than one job from Jq

aux, then we move the sequence of jobs, starting with

the second job from Jq

aux (ignoring the jobs from Jp

aux), to a machine on the last stage, that processes no job

from Jq

aux. Since the jobs from Jq

aux are zero-jobs, this does not create an interruption on the new machine. If

there occur conflicts with other jobs, then we delay sub-schedules corresponding to some machines on the

last stage. In case that a machine processes only jobs from J, but no job from Jq

aux, then by our claim, the

first job is a zero-job. Hence, we can move the sequence of jobs from Jto another machine, which already

processes a job from Jq

aux. Thus, we may assume, that there are at most msmachines on the last stage that

process jobs from Jand each of these machines processes one job from Jq

aux. If the job from Jq

aux is not

the first one in the sequence of jobs from J∪Jq

aux, then we can move the subsequence starting with it to the

beginning. Since the first job in the sequence and the job from Jq

aux are zero jobs, this creates no interruption.

Finally, we obtain a schedule for I0, that uses only msmachines on the last stage, and in which the jobs of J

are processed without interruption. This yields an interruption-free schedule for the instance I.

Theorem 6 is proven by combining the results of this subsection with Theorem 8.

5 Further remarks

We introduced the concept of interpreting sequencing problems as Eulerian Extension Problems. This view

does not only lead to elegant and fast algorithms, it also allows an implicit representation of all optimal

solutions for particular problem classes. We believe that our technique influences also other algorithmic

frameworks for related problems, and moreover, it raises interesting potential for multi-criteria optimization.

As a first step towards multi-criteria optimization, consider both objective functions, Gand Cmax. Already

simple examples (even on two stages) show that schedules with optimal makespan may have the maximum

number of interruptions whereas there exist idle time free schedules. For the two-stage variants of these

problems, our technique provides us an implicit representation of all optimal solutions from which one

could choose accordingly. Referring to a full version of this paper, we only mention here, that an algorithm

that solves the interruption problem optimally, yields a schedule of makespan no greater than twice the

minimum makespan, giving a trivial (1,2)-approximation for the bicriteria objective (G,Cmax). Moreover,

it follows from the NP-completeness of F2|nwt,m2≥2|Cmax [15] that approximating such problems with

a(c,1)-guarantee is NP-hard for any constant c≥1.

References

[1] M. R. Garey and D. S. Johnson. Computers and intractability. Freeman, 1979.

[2] K. Giaro. NP-hardness of compact scheduling in simplified open shop and flowshop. European Journal of Opera-

tional Research, 130:90–98, 2001.

[3] K. Giaro and M. Kubale. Compact scheduling of zero-one time operations in multi-stage systems. Discrete Applied

Mathematics, 145:95–103, 2004.

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

[5] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in

deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287–326, 1979.

[6] N. G. Hall and C. Sriskandarajah. A survey of machine scheduling problems with blocking and no-wait in process.

Operations Research, 44(3):510–525, 1996.

[7] I. Harjunkoski and I. Grossmann. A decomposition approach for the scheduling of a steel plant production. Com-

puters and Chemical Engineering, 25:1647–1660, 2001.

[8] R. M. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of

Computer Computations, pages 85–103. Plenum Press, 1972.

[9] E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys. The Traveling Salesman Problem: A Guided Tour

of Combinatorial Optimization. John Wiley & Sons, 1985.

[10] D. Pacciarelli and M. Pranzo. Production scheduling in a steelmaking-continuous casting plant. Computers and

Chemical Engineering, 28(12):2823–2835, 2004.

[11] S. S. Reddi and C. V. Ramamoorthy. On the flow-shop sequencing problem with no wait in process. Operational

Research Quarterly, 23(3):323–331, 1972.

[12] H. R¨

ock. The three-machine no-wait flow shop is NP-complete. Journal of the Association for Computing Ma-

chinery, 31(2):336–345, 1984.

[13] G. Rote and G. J. Woeginger. Time complexity and linear-time approximation of the ancient two-machine flow

shop. Journal of Scheduling, 1(3):149–155, 1998.

[14] C. Schwindt and N. Trautmann. Scheduling the production of rolling ingots: industrial context, model, and solution

method. Int. Trans. Operational Research, 10(6):547–563, 2003.

[15] C. Sriskandarajah and P. Ladet. Some no-wait shops scheduling problems: complexity aspect. European Journal

of Operational Research, 24(3):424–438, 1986.

[16] G. L. Vairaktarakis. Simple algorithms for gilmore–gomory’s traveling salesman and related problems. J. of

Scheduling, 6(6):499–520, 2003.

[17] Z. Wang, W. Xing, and F. Bai. No-wait flexible flowshop scheduling with no-idle machines. Operations Research

Letters, 33:609–614, 2005.

[18] D. B. West. Introduction to Graph Theory. Prentice-Hall, 2nd edition, 2001.