MANAGEMENT SCIENCE

informs

Vol. 57, No. 4, April 2011, pp. 647–666
issn 0025-1909  eissn 1526-5501  11  5704  0647®

doi 10.1287/mnsc.1100.1302© 2011 INFORMS

Integrated Sequencing and Scheduling in
Coil Coating
Wiebke Höhn, Felix G. König, Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany{hoehn@math.tu-berlin.de, fkoenig@math.tu-berlin.de, rolf.moehring@tu-berlin.de}Marco E. Lübbecke
Department of Operations Research, RWTH Aachen University, 52056 Aachen, Germany,
marco.luebbecke@rwth-aachen.deW

e consider a complex planning problem in integrated steel production. A sequence of coils of sheet metalneeds to be color coated in consecutive stages. Different coil geometries and changes of colors necessitate
time-consuming setup work. In most coating stages one can choose between two parallel color tanks. This caneither reduce the number of setups needed or enable setups concurrent with production. A production plancomprises the sequencing of coils and the scheduling of color tanks and setup work. The aim is to minimize themakespan for a given set of coils. We present an optimization model for this integrated sequencing and scheduling problem. A core component is a graph theoretical model for concurrent setup scheduling. It is instrumental
for building a fast heuristic that is embedded into a genetic algorithm to solve the sequencing problem. The
quality of our solutions is evaluated via an integer program based on a combinatorial relaxation, showing that
our solutions are within 10% of the optimum. Our algorithm is implemented at Salzgitter Flachstahl GmbH, amajor German steel producer. This has led to an average reduction in makespan by over 13% and has greatly
exceeded expectations.
Key words: sequencing; scheduling; integrated steel production; coil coating; 2-union graphs; independent set;branch-and-priceHistory: Received March 12, 2010; accepted November 17, 2010, by Dimitris Bertsimas, optimization.

1.

Introduction

portfolio: The coils used for home appliances, forinstance, already have their typical white coatingwhen bought from the steel supplier, and the sheet
metal used for car bodies already has an anticorrosion coating before it arrives at the automotive
plant for pressing. Already in the 1960s, associations
were formed to promote the evolution of coil coating.1
Progress in the development of new and improved
coating materials and techniques fosters an ongoingdiversiﬁcation in precoated metal products, and inrecent years, coil coating has been investigated fromchemical and engineering perspective in several publications, e.g., Delucchi et al. (1999), Deﬂorian et al.
(2000), Duarte et al. (2005), and Zhang et al. (2009).
As is typical for paint jobs, the coil coating process may be subject to long setup times, mainly forthe cleaning of equipment, and thus very high setup
cost. To reduce this cost, modern coil coating lines areequipped with so-called shuttle coaters or quick (color)change coaters, offered by different manufacturers asstandard machinery; see, e.g., GFG Peabody, Bronx

Almost every stage in integrated steel production
requires solving a sequencing problem as subproblem, that is, deciding about a good order of steel slabs
or coils in which they should be processed, e.g., forthe melt in the blast furnace or when rolling slabs inthe hot and cold rolling mills to coils, to state only two
examples. In all of these problems, however, sequencing is only one part of devising a complete production
plan: For a given processing sequence, a schedule for
performing certain tasks on workpieces or machinery
also needs to be computed. The nature of this scheduling problem often depends largely on the processing
sequence; hence, the quest for good sequences can be
answered accurately only by taking into account thecost of the ensuing scheduling problem as well. In thispaper, we deal with the ﬁnal processing step in sheet
metal production, the coating of steel coils, which
may be seen as a prototype of such an integrated
problem: In addition to sequencing coils, a challenging concurrent setup scheduling (CSS) problem needs tobe solved, and both problems strongly interdepend.
The coil coating process plays an essential role inshaping steel producers’ extremely diverse product1647

http://www.coilcoating.org/; http://www.prepaintedmetal.eu/.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

648
Figure 1

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Coils of Different Widths as They Are Processed in the Coating Line (from Left to Right)(a) Solution for a classical coater with only one tank(b) Solution for a shuttle coater

Roller andcolor change
Tank 1
Tank 1
Roller changes

Color changes

Tank 2

Concurrent
roller andcolor change

Note. Setup work (such as color or roller changes to be deﬁned later) has to be performed whenever a coil has to be coated with a different coating or is wider
than its predecessor on that tank.

International, or SMS Siemag.2 Shuttle coaters possess
two separate tanks allowing for holding two different coating materials at the same time. The advantage is twofold: The shuttle can be used to switch
between two coatings on the same coater at (essentially) no setup cost, or alternatively the unused tankcan be set up while coating continues from the othertank in the meantime. We refer to this possibility toperform setup work during production, which is somewhat uncommon in scheduling literature, as concurrent setup; see Figure 1 for an illustrative example.
Literature regarding optimization in the planning
process for coil coating is scarce at best; to the bestof our knowledge, only Tang and Wang (2009) consider planning for a coil coating line. They apply tabu
search to a rather basic model without shuttle coaters.
The present work is the ﬁrst incorporating shuttles
and concurrent setup work in a thorough mathematical investigation.
Our work is concerned with a somewhat standard
coil coating line as operated by many major steel companies worldwide, consisting of a primer and a ﬁnisher, each comprising two coaters to coat the top
and bottom sides of a coil (cf. Meuthen and Jandel
2005, Delucchi et al. 1999). Each of the coaters may
or may not be a shuttle coater, whose introduction
signiﬁcantly changes the ﬂavor and the complexityof production planning: Which tank do we use forwhich coil, and how do we schedule concurrent setup
work without exceeding available work resources?
We aim to ﬁnd a sequence (the order of the coils)
and a schedule for that sequence (the tank assignmentand scheduling of setup work) that minimizes a joint
objective (the makespan).
To precisely capture the scheduling step, we introduce the concurrent setup scheduling problem, which
also ﬁts other applications involving concurrent setup.
By relating it to the independent set problem in certain generalized interval graphs called 2-union graphs,
we obtain a dynamic program running in polynomial
time for any ﬁxed number of shuttle coaters, while2

http://www.gfg-peabody.com/; http://www.bronxintl.com/; http://
www.sms-siemag.com/en/1577.html.

proving NP-hardness when this number is part ofthe input. Moreover, we prove corresponding results
for the independent set problem in special 2-uniongraphs, which are of interest in their own right.
The dynamic program inspires a fast and goodheuristic for concurrent setup scheduling, which weembed into a genetic algorithm for sequencing. Altogether, we develop a practical heuristic that solves theintegrated sequencing and scheduling problem andcomputes a detailed production plan for the coil coating line. The quality of our plans is assessed withthe help of an integer program, which we solve bybranch-and-price.
Our algorithm has been added to PSI Metals’ planning software suite,3 and is currently in use on a coilcoating line with shuttle coaters at Salzgitter Flachstahl GmbH,4 Germany (SZFG for short). There, ityields an average reduction in makespan by over
13% compared to the previous manual planning process. In addition, our lower bounds suggest that the
makespan of the solutions computed by our algorithm is within 10% of the optimal makespan for typical instances.5 Because most setup cost calculations
are incorporated into our methods as a black box, ouralgorithm can be adapted easily to other coil coatinglines with different setup rules and a different numberof shuttle coaters.

2.

Problem Formulation

Steel coils are a highly individualized product, andall nonproductive time in coil coating depends on
certain characteristics of coils. They usually have alength of 1–5 km, and their central attributes are naturally the coatings they receive in the four coatingstages, chosen from a palette of several hundreds,
and their width, usually 1–18 m. More intuitively, we
will henceforth refer to coating materials as colors.
We refrain from listing further coil attributes, because3

http://www.psimetals.de/en/.

4

http://www.salzgitter-ﬂachstahl.de/en/.

5This success has made this contribution a ﬁnalist of the 2009EURO Excellence in Practice Award.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

649

Management Science 57(4), pp. 647–666, © 2011 INFORMS

their list is very long; yet all relevant information is
included in our calculations.
For a concise description of the optimization task,
we shall brieﬂy familiarize the reader with some coilcoating terminology:• A coater comprises all machinery necessary for
applying one of the four layers of color to the coils,
primer and ﬁnish on top and bottom.
• A tank holds the color currently in use at a coater,and each tank has its own rubber roller for applying
the color to the coil.
• Naturally, a coater has at least one tank. A shuttle
coater has two tanks, each with its own roller, which
can be used alternatingly to apply color.
• A color change refers to cleaning a tank and ﬁlling
it with a new color. A roller change needs to be performed when a coil with smaller width is precedinga coil with larger width on the same tank: Because of
the wear the roller incurred at the edges of the former
coil, the coating of the latter would bear imperfections.
Before entering production, each coil is unrolled
and stapled to the end of its predecessor. To bridge
nonproductive time during setups, scrap coils areinserted in between actual coils, so essentially a neverending strip of sheet metal is continuously running
through the coil coating line. After undergoing somechemical conditioning of their surface, the coils run
through a top and bottom primer coater, an oven, a
top and bottom ﬁnish coater, and through a second
oven. In the ovens, the respective coating layers are
ﬁxed. After the coating process, the coils are rolled up
again, now ready for shipping. A schematic view of atypical coil coating line is depicted in Figure 2.
An instance of our optimization problem comprises
a set n = 1     n of coils to be coated. For theaccount in this paper, each coil j is characterized byk
its colors cj ∈  on coaters k = 1     m, its width
wj ∈ + , and its processing time pj ∈ + , the time it
Figure 2

takes for j to pass any given point on the coatingline. Note that even though a coil passes the different
stages of the coating line one after the other, it is feasible to think of a coil as being processed at all stages
at once, because the time it takes a section of a coil toget from one stage to the next is negligible compared
to coil lengths.
The optimization goal is to minimize the makespanfor coating the given set of coils, i.e., the completiontime of the last coil in the sequence. This is essentiallyequivalent to minimizing nonproductive time, or cost,in the plan, which ensues for two reasons:Transition Coils. To satisfy certain technical restrictions, transition coils of different lengths, widths, etc.,
may be required in between two consecutive coils inthe sequence. The duration of transition coils necessary for each pair of coils i j ∈ n×n if run consecutively is explicitly speciﬁed in an instance as sloc i j ,and we refer to it as local cost.
Setups. Setups comprise color or roller changes.
Both require roughly the same amount of time,denoted by t. If coils i j ∈ n are run consecutively
on the same tank of a coater k, setups of total lengthkks k i j = scc i j + src i j have to be performed in
between, comprising the sum of durations of a possible color and roller change, wherekkt if ci = cj ,kscc i j =0 otherwise;(1)
t if wi < wj ,ksrc i j =0 otherwise.
Because of the dependency of consecutive coils on
a tank, it does not sufﬁce to consider pairs of consecutive coils in the sequence to quantify necessary
setup work. Larger sets of coils need to be taken into
account—the entire sequence in the worst case; see

Schematic View of a Coil Coating Line with Chemical, Primer, and Finish Coater

Oven

Finish coater

Sling buffer
Primer coater
Oven
Sling
bufferChem coater

Note. Here, the chemical (chem) and the bottom ﬁnish coaters are standard coaters; the remaining have shuttles.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

650
Figure 3
Tank 1

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Optimum Tank Assignment for a Fixed Sequence of Coils...

Tank 2Note. The setup right before the last coil—none, in this example—depends
on its predecessor on the tank, i.e., on the whole sequence.

Figure 3. Hence, we refer to nonproductive time ensuing because of setup work as global cost.
Finally, a plan for the coil coating process consistsof the following two parts:• a sequence ∈ n , i.e., a permutation stating theprocessing order of the coils;• a schedule S comprising a tank assignment T ∈1 2n×m stating for each coil from which tank it iscoated for each of the m shuttle coaters, and a feasible setup schedule for the set of setups W = W  T
deﬁned by and T as described above. We elaborateon the structure of feasible schedules in the following
section.
There is a strong interdependence among the different parts of a solution: A tank assignment T is only
meaningful in conjunction with a sequence , and theset W of setups to be scheduled depends on T and .
2.1. Concurrent Setup Scheduling
We will now focus on the subproblem of computing a schedule for a given sequence . Deciding
on a tank assignment T settles the predecessors ofcoils on the tanks, yielding the set W = W  T of
setups to be performed. These can be scheduled either
between coils during nonproductive time or concurrently to production on an idle tank. Whereas theformer results in an increase in makespan, the latterdoes not. Consequently, there are two possibilities tosave cost by good scheduling: On the one hand, thetank assignment can preserve used colors and/or arollers on an idle tank for later coils, thereby reducing the number of setups to be performed. On theother, setups can be performed concurrently with production on idle tanks, thereby keeping setups fromincreasing the makespan.
Setup schedules have to respect certain constraints
to be feasible: Although there may be several work
teams to perform setups, at most one team canwork on the same coater concurrently to production to ensure safety. Contrarily, during nonproductive time, the teams work together to ﬁnish work as
fast as possible. Moreover, concurrent setups are notallowed while transition coils are run, because transitions require careful monitoring. Finally, the execution of one concurrent setup may not be preemptedby another. Note that as a result of these restrictions,transition coils can be ignored when scheduling concurrent setups.
To capture this scheduling problem more formally,
we deﬁne the CSS problem as follows. Consider aproduction process comprising m cells, each of whichbeing equipped with two identical, interchangeable
tools. A sequence of n jobs needs to be processed ina ﬁxed order ∈ n , where each job j has to be processed for pj time units utilizing one tool on each of
the m cells simultaneously. If two jobs i and j are processed in consecution on the same tool of cell k, setup
work taking time s k i j ∈ ≥0 has to be performedon the tool after job i is completed and before job jstarts.
There are r setup resources available to perform
setup work in two distinct ways: If performed during
nonproductive time, all r resources work together as
one fast resource, achieving a speedup factor ≥ 1.
Alternatively, a setup can be performed concurrently
to production on an idle tool by one of the setup
resources, eliminating its impact on the makespan.
Partial concurrent setups are possible and remaining
setup work is ﬁnished during nonproductive time,
incurring a speedup as above.
A feasible solution to the CSS problem assigns oneof the two tools to each job for every cell and schedules all resulting setups such that at most r concurrent
setups are performed at a time during production, andonly one setup at once during nonproductive time.
Concurrent setups may only be preempted by setups
during nonproductive time. The objective is to determine a plan  S minimizing the makespan. Note that
because all setup resources work together during nonproductive time, the makespan of a solution is insensitive to deferring nonconcurrent setups to the latest
possible time. Hence, it sufﬁces to only schedule concurrent setups explicitly.
In our application, coaters resemble the cells, andtanks are our tools. The number of setup resources is
r = 1, i.e., there is one team of workers performing
setups. Also, setup times have a special structure; see
Equation (1). Nevertheless, all of our results hold for
CSS in general, i.e., arbitrary setup times and any r.
Moreover, our model and algorithms for CSS
remain valid even in a more general setting where
each setup task can only be performed by a subset ofthe resources. However, for the sake of a clear presentation and cleaner notation, we omit further comments on this case.
A natural generalization of the CSS problem would
be to consider t tools for some general t ∈ . However,
our results are strongly based on the number of tools
being two.
2.2. Cost Computation
The cost of a coil coating plan decomposes into time
for transition coils and setups during nonproductive

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

651

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Figure 4

Components of Cost and Tool Intervals(a)sloc( j, h)iTank 1j1ts(k)– t hTank 2
1 s(k ′)

Cost

(k)

predtank(h)(b)
I =[i, j ]...
pred(I )...
last(I)

succ(I )k

Notes. (a) A picture of a partial schedule on coater k is shown; sk is short for sk predtank h h in this ﬁgure. When coil j is ﬁnished, a period of nonproductive
time begins: The color and roller need to be changed on Tank 2 of this coater, and this is only in part done concurrently, then ﬁnished during nonproductive
time. Additionally, more setups before h have to be performed on a different coater k  , and this is done during nonproductive time as well. All setups that are
not concurrent incur speedup . Finally, a transition coil of length sloc j h needs to be run between coils j and h, and no setup can be performed during thistime. (b) Because transition coils do not allow concurrent setup, they can be ignored for scheduling. Thus, their length is not included in the length of intervals
in our model.

time. Because cost computation is quite complicated,
an illustrative example is given in Figure 4(a). Again,
concurrent setups incur no cost as they do not impact
the makespan, and no setup may be performed during transition coils.
More formally, consider a sequence ∈ n and akschedule S = S
for . Denote by predtank j the predecessor of coil j on the same tank of coater k in S,
and denote by C S the total amount of concurrent
setup in S. Then, formally, the cost of plan S isgiven by
n


sloc

j=2

+



j −1 

m n

1 

j



k

s k predtank j  j − C S

k=1 j=2

the sum of the duration of all transition coils andsetup performed nonconcurrently.
2.3. Related Work
Sequencing and scheduling problems with setup
times and makespan minimization constitute a widely
studied ﬁeld; see Allahverdi et al. (2008) for a recent
survey. In most of these problems, however, setups
are purely local, i.e., depend only on two successive
jobs on the same machine, and thus are closely related
to asymmetric traveling salesman problems; see Balaset al. (2008). Also, more general problems with setups
typically involve only local setups. One such example is scheduling problems with communication delays andprecedence constraints (see Bampis et al. 1997), where adelay occurs only between pairs of jobs with a nontransitive precedence constraint among them when
they are scheduled on different machines.

In contrast, our setup costs need to be calculated inview of several, possibly many preceeding jobs. Such
nonlocal setups have only sporadically been considered in scheduling, e.g., by Koulamas and Kyparisis(2008). They are more typical in multiproduct assembly lines. But here one no longer considers sequencing
problems with makespan minimization, but aims at
ﬁnding batches of products that minimize the cycle
time of the robotic cells; see, e.g., Rekieck et al. (2000).
Setups concurrent with production also occur inparallel machine scheduling problems with a common
server considered by Hall et al. (2000): Before processing, jobs must be loaded onto a machine by a single
server, which requires some time (the setup time forthat job) on that server. Good sequences of jobs on
the parallel machines minimize the time jobs have to
wait to be setup because of the single server being
busy on a different machine. In this model, too, setups
are purely local, and once sequences for the machines
have been determined, scheduling the server constitutes a trivial task.
Altogether, we are not aware of any papers onsequencing or scheduling problems that come close
to the combined sequencing and concurrent setup
scheduling problem studied here. Our model andresults may thus pave the way for other applications
involving sequencing and concurrent setup scheduling as they may occur in complex production environments such as the automotive industry.

3.

Interval Model for Concurrent
Setup Scheduling

In our solution approach, which we describe in §5,
we repeatedly solve instances of the CSS problem
resulting from different sequences of coils. Hence, anHöhn et al.: Integrated Sequencing and Scheduling in Coil Coating

652
Some Saving Rectangles, Appropriately Positioned in the Plane

Setup
intervals

Cell 1

Cell 2Cell mResource 2

Figure 5

Management Science 57(4), pp. 647–666, © 2011 INFORMS...
0

Conflicts
with R

Setup intervalof rectangle R

R

Resource 1...
Conflicts
with R0
0 Tool interval

0

Tool
intervals

0of rectangle R

Notes. Selecting rectangle R, i.e., running all jobs belonging to its tool interval on the same tool of cell 1 and performing concurrent setup during its setup
interval, prohibits the selection of any rectangle whose projection onto one of the axes intersects that of R. The selection of nondisjoint tool intervals preventsa proper tool assignment, whereas intersecting setup intervals violate resource constraints. For simplicity, only two resources are visualized.

efﬁcient algorithm for CSS is of key importance. We
develop a representation of solutions as a family of
weighted two-dimensional intervals, where the ﬁrst
dimension is related to a tool assignment and the second to performing concurrent setup work. We call
two such intervals, or axis-parallel rectangles, independent, if their projections onto neither of the axes intersect. An optimal solution S to CSS will correspondexactly to a maximum weight subset of pairwise independent two-dimensional intervals; see Figure 5. Thissection essentially lays the groundwork for the designof both a fast heuristic algorithm and a dynamic
programming approach for our application, yielding optimal coil coating plans for ﬁxed sequences ofcoils in polynomial time for any constant number ofcoaters.
We model every possible assignment of a maximal
consecutive subsequence of jobs to the same tool of acell and every resulting possibility to perform concurrent setup work as weighted intervals called tool intervals and setup intervals, respectively. Then, we combine tool and setup intervals to form two-dimensional
intervals, i.e., axis-parallel rectangles. The weights ofintervals represent the reduction in cost (which may
be negative) achieved by the corresponding partial
tool assignment and the concurrent setup work performed, compared to processing all jobs on the same
tool without performing concurrent setup work.
Setup intervals of all cells compete for the r available resources for concurrent setup work; i.e., a chosen setup interval for one cell impacts the choiceof setup intervals on other cells. In contrast, we
can choose tool intervals of different cells independently. We position the rectangles in the plane accordingly, such that there is a one-to-one correspondence

between solutions to CSS on the one hand, and maximal independent sets of rectangles on the other. We
denote by pj the processing time of job j, and throughout this section we assume that the jobs are numbered
as they appear in the ﬁxed sequence, i.e., = id ∈ n .
3.1. Tool Intervals
A tool interval, always associated with a particularcell, represents a maximal consecutive subsequence ofjobs that are processed on the same tool. Thus, foreach cell, any two jobs i j ∈ n, i ≤ j, deﬁne a toolinterval I = i j containing all jobs i     j. Selecting
such an interval will correspond to running all jobs
in it on the same tool, and switching the tool directly
before i and directly after j; see Figure 4(b). Hence,a set of nonintersecting tool intervals, covering every
job, deﬁnes a unique tool assignment, and the processing time in I isp I =

j


px 

(2)

x=i

We call the last job before and the ﬁrst job after I
its predecessor pred I and successor succ I , respectively. Also, let last I denote the last job in I. Thekweight wtool I of a tool interval I of cell k comprises
the change in cost before succ I resulting from processing all jobs in I with one tool and pred I andsucc I with the other, compared to running all thesejobs from the same tool (and performing all necessary setup work before succ I during nonproductivetime). Thus, we havekwtool I =1s k last I  succ I− s k pred I  succ IHöhn et al.: Integrated Sequencing and Scheduling in Coil Coating

653

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Note that certain tool intervals may have negative weight, i.e., selecting them actually increases cost.
Because the requirement that all ofbe covered bytool intervals to obtain a well-deﬁned tool assignment, such intervals cannot be ignored. For computational purposes however, negative weights can easily
be eliminated, as we demonstrate in §3.4.
3.2. Setup Intervals
A setup interval Is is always associated with a toolinterval I = i j, hence also with a particular cell k.
Furthermore, it is tied to one of the r setup resources.
It represents concurrent setup work performed
from pred I to succ I on k’s idle tool during jobsi     j by a certain setup resource. A setup interval’s weight wsetup Is equals its length and describes
the amount of concurrent setup work performed. So
clearly, we always havewsetup Is ≤ minp I  s k pred I  succ I 
3.3. Saving Rectangles
We now deﬁne saving rectangles R = I Is as a combination of a tool interval I and a (possibly empty)
setup interval Is . The total weight of a saving rectangle R is1
w R = wtool I + wsetup Is 
As for tool intervals, this weight may be negative.
Recall that a feasible solution to CSS shall correspond to the selection of a maximum weight independent subset of all possible saving rectangles. Quite
naturally, both dimensions of a saving rectangle, i.e.,
tool and setup intervals, are associated with a senseof time; see Figure 5. We now make use of this fact
to position rectangles in the plane such that their projections onto one of the axes intersect, if and only if
the savings in makespan represented by their weightconﬂict, i.e., cannot be realized jointly.
Two saving rectangles conﬂict if and only if one of
the following holds:• They belong to the same cell and their tool intervals intersect—tool intervals of one cell, whose intersection contains a job j, lead to conﬂicting tool usage,
because both intervals assign j to a different tools.
• They belong to the same setup resource and theirsetup intervals intersect—each resource can perform
only one setup at a time.
Consequently, when positioning rectangles in theplane, all rectangles associated with the same cell
receive their own section of the x-axis, whereas allrectangles sharing the same setup resource are placedin a distinct section of the y-axis. Within sections, allrectangles are positioned in x and y direction according to their natural sense of time; see Figure 5 for an
illustration.

Now, any subset of pairwise independent saving
rectangles, whose tool intervals cover all jobs on allcells, naturally corresponds to a feasible concurrent
setup schedule with corresponding tool assignment.
Moreover, if such a subset has maximum weight,
the corresponding schedule is optimal: It realizes thegreatest savings possible compared to running all jobson the same tool.
By the construction above, saving rectangles also
have a very speciﬁc structure. We build upon theseproperties when analyzing the independent set problem ensuing from CSS in §4:• The projection of each rectangle onto the x-axis
is contained completely in one of the distinct sections
corresponding to the cells.
• If the projections onto the y-axis of two rectangles intersect, their projections onto the x-axis containcommon jobs.
The latter is because, timewise, a rectangle’s setup
interval is always contained in its tool interval. Notethat projections of rectangles onto the x-axis containing common jobs need not necessarily intersect when
positioned as in Figure 5—they may well belong todifferent cells and thus lie in different sections of thex-axis.
Finally, note that for general instances of CSS, it
may not be tractable to explicitly model all possibilities to perform concurrent setup work in an application, as the number of setup intervals could becomesuperpolynomially large. In the case where all setup
durations have a sufﬁciently large common divisor,
however, we can prove a polynomial bound on thenumber of setup intervals that need to be considered
for an optimal solution.
Lemma 1. Given an instance of CSS, let  denote thegreatest common divisor of all setup durations s k i j .
Then, there is a set D of at mostn−1 n−22points in time such that there exists an optimal selectionof saving rectangles , whose setup intervals all have end
points in D.
N =maxi∈n pi·

Proof. We explicitly construct a set of potential
start points sufﬁcient for an optimal solution and thenbound their number. In an optimal solution, setup
intervals may of course start with every but the last
job in the sequence, accounting for the ﬁrst n − 1points necessary. Given a potential start point for a
setup interval of length s, also the point exactly s
after it is a potential start point. Because preemption
is not allowed, any optimal selection of saving rectangles can be transformed to a solution where all setup
intervals start at a point of the above form by shifting every selected setup interval to the left as far as
feasibly possible.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

654

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Assuming without loss of generality (w.l.o.g.) thatthe ﬁxed sequence of jobs is= id ∈ n , we now
observe that, moving through the sequence in order,
the number of new potential start points during theprocessing of job i is bounded by i pi / . Thus, thetotal number of potential start points for setup intervals necessary in an optimal solution is

maxi∈n pi n − 1 n − 2
p
i i≤
·
= N


2
i∈n−1

Thereby, the number of savings rectangles that need
to be considered for an optimal solution is boundedby k · r · n2 N + 1 , the number of possibilities topair each of the n2 possible tool intervals of eachcell with no or one setup interval of every setup
resource. Note that N is polynomial in n, as long as
the ratio maxi∈n pi / is bounded polynomially in n.
This bound is also very coarse, because it takes into
account all possibilities to pair any setup interval witha tool interval, although only setup intervals completely contained in it are really relevant.
In our application the duration of all setups is amultiple of t, hence Lemma 1 applies with  = t. In
realistic instances, the maximum length of a coil isroughly twice t, so the number of setup intervals necessary for each cell is no more than 2n2 .
3.4.

Building Schedules from Maximal
Independent Sets
Given an independent set of saving rectangles suchthat every job is covered by a tool interval on
every cell, the construction of a feasible concurrent
setup schedule with corresponding tool assignmentis straightforward: The schedule for concurrent setup
work is given explicitly by setup intervals, interrupted by nonconcurrent setups and transition coils,
and at the end of each tool interval, we switch toolson the corresponding cell. By construction, there is a
one-to-one correspondence between the cost of thisschedule and the cost of the chosen saving rectangles , i.e.,


 1 k

sloc i i + 1 +s i i + 1c  =i∈n−1

−



k∈m

w R

R∈

where the ﬁrst part is the cost for running all jobs
from the same tool, depending only on = id.
Moreover, note that negative rectangle weights canbe eliminated by adding a sufﬁciently large constant to the weight of each rectangle, weighted by its
length. This does not change the structure of the problem, and we force any maximum weight independent
set to be maximal such that the selected rectangles
have tool intervals covering all jobs.

Finally, our model yields a fast algorithm for CSS
when sufﬁcient setup resources are available; i.e., concurrent setup can be performed simultaneously on
all cells.
Lemma 2. In the special case when r ≥ m, CSS can besolved in polynomial time.
Proof. By assigning a different resource to eachcell, we can assume that two saving rectangles conﬂict if and only if they belong to the same cell andtheir tool intervals intersect. Thus, an optimal solution
can be computed independently for each cell, and the
problem reduces to ﬁnding maximum weight subsetsof pairwise disjoint intervals (i.e., maximum weight
independent sets in classic interval graphs), which canbe done very efﬁciently (Gupta et al. 1982). We shall comment on the complexity status of CSS
for all other cases of r and m in §4.

4.

Independent Sets in Special
2-Union Graphs

We now make a connection from the CSS problem
to the independent set problem for a special classof multi-interval intersection graphs. Although various notions of multi-intervals and their intersection
graphs have been studied in literature (e.g., Gyárfás
and Lehel 1970, Kaiser 1997, Butman et al. 2010),
we are mainly concerned with the following class ofgraphs.
Deﬁnition 1. An undirected graph G = V  E iscalled a t-union graph if it is the edgewise union of tinterval graphs with common node set V .
Recall that an interval graph G = V  E is a graphwhose node set can be represented as a family ofV  intervals where two intervals contain a common
point, if and only if the corresponding nodes sharean edge in G. As is common in literature, we assume
that a suitable interval representation for G is given
and use the notion of a node in G and its interval in
the given representation interchangeably. In a t-uniongraph, we denote by vi the interval associated with anode v in its ith interval graph.
Tool and setup intervals as deﬁned in §3 deﬁne twointerval graphs, and their edgewise union is the graphon the set of savings rectangles where two rectangles share an edge exactly if their savings cannot berealized jointly. Hence a maximum pairwise nonconﬂicting subset of savings rectangles corresponds to a
maximum weight independent set in a 2-union graph.
This problem is studied by Bar-Yehuda et al. (2006),
and the authors prove it to be APX-complete, even for
2-union graphs that have a representation where allintervals are half open and have length two, and allof their end points are integral. On the positive side,Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

655

Management Science 57(4), pp. 647–666, © 2011 INFORMS

they give a 2t-approximation algorithm based on alinear programming relaxation of the problem for the
more general class of 2-interval graphs.
In this section, we demonstrate how the special
structure of the intervals in our application can be
exploited to partially circumvent the hardness result
above. To precisely deﬁne this special class of 2-uniongraphs, we ﬁrst introduce a certain notion of afﬁnity among the disjoint sections of the tool interval’s
dimension corresponding to the m different cells.
Deﬁnition 2. Let V  be a family of intervals contained in a section L = sL  eL  of the real line. For aninterval v = sv  ev  ∈ V  , we denote byvL = sv − sL  ev − sL 
the L-relative interval of v. When referring to some
canonical section of the real line, we call these intervals section relative.
Deﬁnition 3. Let G be a 2-union graph, i.e., theedgewise union of two interval graphs G1 and G2 . We
call G m-composite if G1 and G2 are the intersection
graphs of two families of intervals such that the following hold:
1. G1 has at least m connected components
C1      Cm .
2. Let L1      Lm denote the minimal sections of theline containing all intervals in C1      Cm , respectively,
and assume w.l.o.g. that, by scaling G1 ’s intervals,
all Li have equal length. Then, for any u v ∈ V G
with u1 ∈ Ci , v1 ∈ Cj ,u2 ∩ v2 =⇒ u1Li ∩ vL1 j = 

(3)Loosely speaking, when two nodes share an edgein G2 , their intervals in G1 would intersect if they
belonged to the same section. Note that 1-composite
and n-composite 2-union graphs are usual intervalgraphs: In the former case, G2 is a subgraph of G1 ,so G = G1 , whereas in the latter, G1 has no edges, so
G = G2 .
Considering the rectangles in CSS, property (3) isalways satisﬁed, because setup intervals are subintervals of their tool intervals according to the natural sense of time. Because of separate resource sections along the y-axis, this holds for any number ofresources.
First, we show that for variable m, the maximum independent set problem remains NP-hardfor m-composite 2-union graphs, even in theunweighted case. Afterward, we proceed to describe
an exact dynamic programming approach running in
polynomial time for any ﬁxed m. Finally, we describe
how both negative and positive results carry overto CSS.

Table 1

Intervals Associated with Literals in the Two Interval
Graphs G1 and G2

LiteralInterval in G1

Interval in G2

xi

2r · i − 1 2r · i − 12 

i − 1 i

xi

2r · i −  2r · ii − 1 i

1
2Theorem 1. For m part of the input, the maximum
independent set problem in m-composite 2-union graphs isstrongly NP-hard, even in the unweighted case.
Proof. We give a reduction from the satisﬁability
problem with exactly three literals per clause (3SAT)
which is well known to be NP-complete (Cook 1971).
Let I denote an arbitrary 3SAT instance with n variables x1      xn and r clauses c1      cr . We may
assume w.l.o.g. that no clause contains two literals of
the same variable. With m = 2n, we now construct
an m-composite 2-union graph G such that G admits
an independent set of cardinality n + r if and only ifthere is a truth assignment for the variables of I suchthat all clauses are satisﬁed.
We construct G as the edgewise union of two interval graphs G1 and G2 . We introduce a node for eachof I’s 2n literals (the intervals for the nodes in G1
and G2 are given in Table 1). Therefore, the intervals
belonging to literals of different variables are always
disjoint in both G1 and G2 , whereas the two literals of
one variable share an edge in G2 ; see Figure 6.
Furthermore, we introduce a node for each occurrence of a literal in a clause. Let y denote a literal in cj ,whereas s is the start point of the interval associatedwith y’s negation in G1 as in Table 1. These nodes’
intervals in G1 and G2 are deﬁned in Table 2.
Now all occurrences of literals in the same clause
are adjacent in G2 , whereas occurrences of literals in
different clauses are always independent in both G1and G2 ; again, see Figure 6.
Now suppose the graph G, i.e., the edgewise unionof G1 and G2 , admits an independent set S of cardinality at least n + r. Because the two literals of eachvariable are adjacent, S may contain at most n nodes
corresponding to literals. On the other hand, the threeoccurrences of literals in each clause form a triangle, so similarly, S may contain at most r of thesenodes. Consequently, S contains exactly one literal ofeach variable and one occurrence of a literal for each
Table 2

Intervals Associated with Occurrences of Literals in Clausesin the Two Interval Graphs G1 and G2 , Where s Denotes theStart Point of the Interval in G1 Associated with the Negationof the Occurring Literal According to Table 1

Occurrence in clause

Interval in G1


cj

s+

j −1 s+jrrInterval in G2
n + j − 1 n + j

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

656
Figure 6

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Two-Dimensional Interval Representation of the Graph Constructed from the 3SAT Instance with Four Variables and Clauses x2 ∨ x3 ∨ x4 ,
x2 ∨ x3 ∨ x4 , x1 ∨ x2 ∨ x3 , and x1 ∨ x3 ∨ x4 

G2

x4
x3
x2
x1

x4

x3

x2

x1
G1

Notes. The two intervals associated with the two literals of variable x3 are highlighted with dots, and those belonging to the fourth clause x1 ∨ x3 ∨ x4  withstripes. The adjacency of the occurrences of literal x2 in the ﬁrst two clauses with x2 is highlighted with squares.

clause. Let us interpret the choice of literals in S as atruth assignment X for the variables of I. Each occurrence of a literal in a clause is adjacent to its negationin G, so such occurrence being in S implies it is truein X, for S is an independent set. Hence, X fulﬁlls
at least one literal in each clause of I, which is consequently a yes-instance.
Conversely, suppose I is a yes-instance, and X is atruth assignment fulﬁlling all clauses. Then an independent set in G can be constructed in the same way,
picking n nodes corresponding to the literals in X andan occurrence of a literal true in X for each clause.
Finally, for m = 2n, the graph G is also m-composite:
First, no interval in G1 crosses the end points of theintervals corresponding to literals, so these intervals
deﬁne m disjoint sections of the line containing theconnected components of G1 . Second, edges in G2
either join two literals of the same variable, or two
occurrences of two literals in the same clause. In
both cases, the adjacent nodes’ intervals in G1 haveidentical section-relative intervals by our construction; hence G also satisﬁes property (3). Note that this reduction actually demonstrates thatthe maximum independent set problem is even NPhard in 2-union graphs of a very speciﬁc structure:
The graph constructed is the edgewise union of acollection of pairwise disjoint triangles and edges on
the one hand, and a collection of disjoint stars on
the other. It is not immediately clear, however, that
hardness of this problem entails hardness of CSS: itremains to show that the reduction can be performed
such that the resulting interval representation is theinterval model of a CSS instance. We give the proofof the following theorem in the appendix.
Theorem 2. For the number of cells m part of the
input, CSS is NP-hard for any ﬁxed number r < m of setup
resources.
Let us now turn to positive results. We propose
the following dynamic programming algorithm tocompute a maximum weight independent set in
m-composite 2-union graphs, which runs efﬁciently
when m is a constant.
Theorem 3. For any constant m, a maximum weight
independent set in m-composite 2-union graphs can becomputed in polynomial time by dynamic programming.
Proof. Let the graph G again be represented as theedgewise union of two interval graphs G1 and G2 . We
deﬁne a state in our algorithm to be a m-tuple
Sv = v1      vm 
where vi is either a node whose interval in G1 lies incomponent Ci , or empty. Note that the nodes of one
state are thereby independent in G1 , and n + 1 m is arough upper bound on the number of states. We calla state feasible if its nodes also form an independent
set in G2 (and hence in G).
We now deﬁne a directed acyclic graph  on the setof feasible states and prove that a longest path fromthe empty state, whose components are all empty, tosome other state corresponds to a maximum weight
independent set in G. Because the number of states ispolynomially bounded, this will yield the result.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

657

Management Science 57(4), pp. 647–666, © 2011 INFORMS

We call two states Su , Sv compatible if Su ∪Sv forms an
independent set in G. As in Deﬁnition 3, we denote byL1      Lm the minimal sections of the line containing
all intervals in C1      Cm , respectively, and assume
again w.l.o.g. that all Li have equal length. For the ith
component vi of Sv , let sL vi and eL vi denote thestart and end point of the Li -relative interval of vi1
in G1 ; set sL vi  eL vi to zero when vi is empty. We
deﬁne the edge set of  asE  =  Su Sv  Su Sv compatible and eL ui ≤ eL vj∀ ij = 1m
So, in a sense, when following a path in  , thecorresponding intervals in all components of G1 aretraversed simultaneously and in a certain monotone
fashion.
Now  is clearly acyclic, and we argue that any
path P = Ss      St in  deﬁnes an independent set
Ss ∪ · · · ∪ St in G: First, the union of two subsequent
states in P is independent by deﬁnition of E  . Furthermore, the union of all states in P is independent
in G1 by construction. It remains to show that theunion of any two nonsubsequent states in P is independent in G2 as well.
For the sake of contradiction, assume there is a stateSu ∈ P and a node ui ∈ Su that, in G2 , shares an edge
with a node vj contained in a state succeeding Su on P .
Let Sv denote the ﬁrst such state. Because adjacentstates form independent sets by deﬁnition of E  ,there must be a state Sa in between Su and Sv on P
that contains neither ui nor vj , so in particular aj = vj .
Also, by our assumptions, Su ∪ Sa and Sa ∪ Sv form
independent sets.
Now, by property (3), we have sL vj ≤ eL ui ≤eL vj . On the other hand, from the deﬁnition of E  ,we get eL ui ≤ eL aj  and from the fact that Sa ∪ Sv
forms an independent set and aj = vj , eL aj < sL vj .
Finally, this results in eL aj < sL vj ≤ eL ui ≤ eL aj ,a contradiction. Consequently any path in  deﬁnes
an independent set in G.
We now deﬁne the length of an edge Su  Sv as
the weight gained by a path, i.e., an independent set,through its traversal:l Su  Sv =
wx −
wx 
x∈Su ∪Sv

x∈Sv

Because for any independent set in G its nodes canbe ordered by the end points of their section-relativeintervals in G1 , any maximum weight independent set
also has a representation as a path in  , concluding
our argument. Note that in view of the hardness result for variable m (Theorem 1), this approach may well be thebest possible in terms of efﬁciency. Moreover, ourinterval model for CSS always leads to m-composite
2-union graphs. Hence, together with Lemma 1, we
immediately obtain the following.
Corollary 1. For an instance of CSS, let  denote thegreatest common divisor of all setup durations s k i j .
When the number of cells m is ﬁxed in advance, allinstances of CSS wheremaxi∈n piis polynomial in the size of the input can be solved in polynomial time, even if the number of setup resources r is partof the input.

5.

Algorithm

We now describe how we produce fully detailed production plans for the entire coil coating problem.
Because of the enormous complexity of the task, an
optimal solution is currently out of reach. On top of
that, quick computation times are indispensable forthe practical usability of our algorithms: Planners at
SZFG require a plan covering 24–72 hours to be computed within 180 seconds. This is why we propose
a special purpose heuristic, which is based on theinsights gained in the previous sections.
Mainly because of global cost, an effective algorithm cannot rely on local decisions or optimal substructures alone. Instead, meta heuristics generating many complete solutions quickly are a natural
approach. In their course, the cost of many sequences
needs to be evaluated, so the scheduling needs to be
performed very often as well. Hence, fast algorithms
for this subproblem are required.
5.1. Sequencing
We utilize a genetic algorithm for sequencing, whichby its nature combines solutions, or individuals, insuch a way that beneﬁcial characteristics of solutions persist, and costly characteristics are eliminated (Aarts and Lenstra 1997). The set of solutions iscommonly referred to as population. In a crossover, thecombination of two parents from the current population brings forth a new individual, whereas a mutation
creates a new individual by modifying one alreadypresent. In an iteration, or generation, the population
is ﬁrst enlarged through crossovers and mutations,
before a subset of all these individuals is selected forsurvival. See Meloni et al. (2003) for a recent successful application to a different production sequencing
problem.
A key to the success of our algorithm lies in theconstruction of its initial population, which is highly
diverse with respect to (w.r.t.) different beneﬁcial
aspects. Recall that the cost of a solution essentiallycomputes as the sum of local and global cost, whereHöhn et al.: Integrated Sequencing and Scheduling in Coil Coating

658

Management Science 57(4), pp. 647–666, © 2011 INFORMS

the former only depends on the sequence, whereas
the latter is greatly affected by the scheduling. In asense, we would like to eventually avoid global costby switching tanks smartly, so we focus on transition
coils for the initial population.
Transition coils need to be inserted into thesequence to bridge differences in certain criteria r ofsubsequent coils, like their weight per meter, thickness, etc. For simplicity, we have omitted these criteria in our problem formulation in §2. This local cost
incurred between two coils i and j has the following
structure:sloc i j = maxr i j rwhere r denotes the length of transition coils necessary to bridge the difference between i and j in criterion r.
When considering only one single criterion, we
may be able to avoid local cost completely by sorting the set of coils according to it, minimizing thelargest occurring difference between subsequent coils.
On the other hand, by the deﬁnition of sloc , one setof transition coil can be used to bridge differences inseveral criteria at the same time, making the most ofsome unavoidable transition coils, in a sense. These
two ideas are the essence of the algorithm generating
our initial population.
To create an individual ∈ n , we ﬁrst pick a criterion r1 by which we sort the set of coils to be coated.
To break ties, which occur frequently for some criteria, we pick a second criterion r2 . If in the ensuingsequence, call it 12 , transition coils becomes necessary because of some other criterion r3 , we know we
could have used them to bridge differences in any
other criterion at the same time, in particular differences in r1 and r2 .
This suggests the following algorithm to build asmarterfrom 12 : We choose a ﬁxed criterion, r3 ,different from r1 and r2 . Then, we add coils to in theorder of 12 , skipping those that would cause local
cost inbecause of differences in r3 . After reaching
the end of 12 , we add the ﬁrst unused coil from 12
to the end of and repeat the process regarding only
the coils in 12 that have not been added to yet.
We can now create different individuals for the initial population by different choices of r1 , r2 , and r3 ,and each individual is likely to avoid local cost due
to these criteria within certain parts of the sequence,
while utilizing unavoidable transition coils to bridge
differences in multiple criteria at once. Therefore, we
obtain a broad variety of completely different individuals, each composed of sections that are attractive
regarding their own part of the objective.
Finally, optimizing a sequence w.r.t. local cost only
amounts to solving an asymmetric traveling salesman problem, for which we use the Lin–Kernighan–Helsgaun heuristic (Helsgaun 2000). We add an

individual corresponding to an often optimal tour tothe initial population as well, before completing itwith a number of random sequences.
During a run of our algorithm, we maintain a constant population size across generations. For eachindividual, we solve the scheduling subproblem as
described in the next section to assess its cost. Individuals with better makespans survive. Mutations are
conducted by inverting a random consecutive subsequence of an individual. For crossovers, we implement a classic mechanism for sequencing problems
originally proposed by Mühlenbein et al. (1988).
Upon the selection of two individuals from the current population, a donor d and a receiver r, a random
consecutive subsequence of random length is takenfrom the donor to form the basis for the constructionof the new individual, or offspring s. We complete s bycontinuing from its last element i with the elements
following i in the receiver, until we encounter an element already contained in s. Now we switch back to
the donor and continue completing s from d in thesame way, going back to r again when encountering
an element already added to the offspring. If we cancontinue with neither r nor d, we add to s the next
element from r that is not in s yet and try again.
5.2. SchedulingGiven an individual from our genetic algorithm, i.e.,
a ﬁxed processing order for coils, we now solve theresulting instance of CSS to obtain a complete solution
to the coil coating problem. Indeed, Corollary 1 yields
a polynomial algorithm for this subproblem in ourapplication. However, this approach is obviously not
feasible for practical use because of its runtime. Nevertheless, we can use its ideas to deﬁne a fast heuristic algorithm based on our independent set model for
concurrent setup scheduling.
5.2.1. Independent Set Heuristic. The complexityof our exact algorithm stems from the need to consider interval selections for all coaters simultaneously
to ensure that savings from all selected setup intervals can be realized by the scarce work resource. Intuitively, the probability that concurrent setup work on
different cells can be scheduled feasibly, i.e., one setup
at a time, increases with the length of the associatedtool interval. This is our heuristic’s core idea for computing good tank assignments.
Instead of considering all coaters at once, we consider them separately. Recall that savings from toolintervals for different coaters can be realized independently in any case. Now, instead of explicitly adding
a setup interval Is to each tool interval I, we limit
cost savings wsetup Is from I’s potential setup intervals according to how much concurrent setup workfor one coater we expect to be able to schedule during I and add this value to the weight wtool I of I.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

659

Management Science 57(4), pp. 647–666, © 2011 INFORMS

More precisely, we deﬁne the new weight of a coaterinterval asI = wtool I + minI Is 
wtool

where  ∈ 0 1 is a parameter. When choosing  = 0, concurrent setup work is assumed impossible. For  = 1, all potential concurrent setup work is
assumed to be scheduled for each tool interval.
With these new modiﬁed weights, it sufﬁces to consider tool intervals alone. As a consequence, similar
to the case of sufﬁcient work resources mentioned in§3.4, computing a tank assignment T reduces to ﬁnding a maximum weight independent set in an interval graph, which can be dealt with very efﬁciently.
To compute a feasible concurrent setup schedule forthis tank assignment, we use an earliest-deadline-ﬁrst
strategy as a simple scheduling rule. As before, each
setup w ∈ W  T is associated with the coil i it isperformed for. We deﬁne a release time and a deadline for w as follows. Job w is released at rw when
the tank on which i is run becomes idle for the lasttime before i in T ; its deadline dw is the start timeof coil i. Because only one concurrent setup may be
performed at a time, we are trying to schedule alltasks on a single work resource. Whenever the work
resource becomes available, say, at time t, we schedule the setup w with the earliest deadline for whicht ∈ rw  dw .
5.2.2. Online Rule: First In, First Out. Finally, we
have a look at the tank assignment rule that waspreviously in use at SZFG: Whenever subsequentcoils have different colors, switch the tank. If the
new tank does not contain the required color, a color
change on that tank becomes necessary. So whenevera third color besides the two in the shuttle tanks isrequired, the color which was in use earlier is discarded, i.e., we follow a ﬁrst-in, ﬁrst-out (FIFO) rule.
For scheduling the tasks in the resulting set W  T ,the same earliest-deadline-ﬁrst rule as above is used.
The advantage of this rule is its online character (andthus simplicity): the choice of tank depends only on
the current and the previous coils; but this rule may
produce suboptimal tank assignments.

6.

Lower Bounds from a
Combinatorial Relaxation

Assessing the quality of heuristic solutions is not only
a theoretical contribution, but an important questionin practice: How much optimization potential is left?
In this section we describe a general way of computing an instance-dependent lower bound on the
optimal makespan, when an online tank assignment
rule is used (see §5.2.2). Ignoring the need for setups
altogether, we obtain the trivial lower bound as thesum of processing times of all coils, LBtriv = nj=1 pj .
A more elaborate idea is to relax the complicating
global cost only. This reduces the coil coating problem to determining an optimal sequence with respect
to local cost—which can be formulated as a (small)
asymmetric traveling salesman problem (TSP), thus
we denote the obtained bound by LBTSP .
Global cost for a coil j depends—in the extreme
case—on the entire solution, in particular on the entire
tank assignment, prior to running coil j. Our relaxation now limits this dependency in limiting the number of coils that are considered when computing
global cost, i.e., we “don’t look back too far.” Moreprecisely, we concatenate subsequences containing a
constant number of coils, say, , for which we exactly
compute the global cost. In between subsequences weconsider only local cost. By means of an integer linear program we ﬁnd a cheapest such concatenation.
A solution is a sequence of all coils, and the tankassignment is given implicitly.
6.1.

An Integer Program: Concatenating Short
Subsequences
The logic of the model is to assign subsequencesof  coils each to n/ time slots, each consistingof  consecutive positions, except the last, which
may possibly be shorter. For a subsequence , wedenote by t  ∈ 1     n/ its time slot, andby p  j ∈ 1     n the absolute position of coil j
in subsequence . We subsume all possible subsequences of  coils in the set  . We slightly abuse
the set notation j ∈  to express that coil j is contained in subsequence . Naturally, the cardinality of is exponential in n, and listing  explicitly in an
integer program is out of the question. The generalidea is to solve the linear relaxation of our model by
dynamically adding sequences, also known as column
generation, and embedding this into a branch-andprice framework (Barnhart et al. 1998, Desrosiers andLübbecke 2005).
We have binary variables xp j for deciding whether
coil j is assigned to position p or not. Variable z ∈0 1 indicates whether subsequence  ∈  is selected
or not. Each  ∈  has its local plus global cost c ,which is computed as if all coaters were entirely clean
and empty at the beginning of . Local cost sloc i jbetween coils i and j is abbreviated ci j .
Note that to compute global cost, we need to knowa tank assignment that we do not explicitly compute. For the optimal value of this model to deliver aguaranteed lower bound, it is essential that the tankassignment rule assumed within subsequences canbe concatenated to a tank assignment on the whole
sequence following the same rule. It is exactly the setof online assignment rules (see §5.2.2), which possess

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

660

Management Science 57(4), pp. 647–666, © 2011 INFORMS

this property. Hence, we use the FIFO rule in the integer program and thereby obtain lower bounds for thecase when the FIFO rule is used:
min c z +ci j yi j (4)

i j∈nxp j = 1 j ∈ n(5)

xp j = 1 p ∈ n(6)z = xp j

(7)

p∈n



j∈n



p j ∈ nj
p  j =pxlast t  i + xﬁrst t+1  j ≤ 1 + yi ji j ∈ n t = 1     n/ − 1 (8)xp j ∈ 0 1

p j ∈ n

(9)yi j ∈ 0 1

i j ∈ n(10)z ∈ 0 1

 ∈ 

(11)

The constraints are interpreted as follows. Each coilgets coated exactly once (Equation (5)), each position is ﬁlled exactly once (Equation (6)), and a subsequence  needs to have coil j in position p if and only
if the corresponding xp j indicates so (Equation (7)).
The precedence constraints (8) enforce that in between
two consecutive subsequences in time slots t and t + 1
we incur local cost between coil i in the last position
last t in t and coil j in the ﬁrst position ﬁrst t + 1
in t + 1. The binary variable yi j precisely takes careof that, because its use is penalized in the objectivefunction (4) accordingly. The optimal objective valueof the integer program is denoted LBIP .
We may alternatively use variables xp j ta ∈ 0 1,
which additionally decide about which tank to use
on every coater in each position of the sequence.
The index ta reﬂects the different combinations on
all coaters (in our case, eight essentially different
tank assignments because we have three shuttle
coaters). This way, we would obtain a lower boundon the makespan for any tank assignment rule. At the
moment, this idea is computationally intractable.
6.2. Pricing
Initially, the integer program (4)–(11) contains all xp j
and yi j variables, but only some z variables, namely,
those that correspond to subsequences derived froma solution produced by our sequencing algorithm (itis restricted to use the FIFO tank assignment rule inthat case). All other z variables are generated only
as needed. The coupling constraints (7) are the only
ones that contain these variables; as a consequence
the corresponding dual variables p j ∈  are the only
relevant ones for calculating their reduced cost (whichmust be negative to proﬁtably add the variable to the
problem). The reduced cost of z isc̄ = c − p  j j j∈and the pricing problem is to ﬁnd a subsequence ofminimum, or at least negative, reduced cost. To thebest of our understanding, there is no principal alternative to a brute force method because we are able
to evaluate the total cost of a subsequence only when
we see it in its entirety, thus we have to construct
it. This also rules out most of the traditionally useddominance criteria in dynamic programming. Therefore, a straightforward depth ﬁrst search enumerates
the O n subsequences to solve the pricing problem.
A pruning criterion based on the dual variable values of coils not yet added to a subsequence helps in
mildly reducing the search space without compromising optimality.
6.3. Branching
When we determine an integer solution for the xp jvariables, all other variables automatically assume
integer values as well, that is, a natural candidate fortaking branching decisions in the branch-and-boundtree is to branch onz  0 1j p  j =p

for a given coil j at position p. In fact, speaking
in terms of branch-and-price methodology, this isbranching on the so-called original variables xp j of the
problem, which are explicitly present in this extensive
column generation formulation as well. The branching itself can be realized as a modiﬁcation to the pricing problem instead of adding an explicit branching
constraint to the master problem: one simply eliminates the forbidden coil j from position p (on thedown branch) or enforces it by eliminating all othern \ j coils from position p (on the up branch). Notethat the master problem has to be updated according to branching decisions: variables corresponding tosubsequences that do not respect the branching constraint have to be eliminated (technically, via an upperbound of zero). To stay feasible after each branching decision, we further introduce artiﬁcial variables(with large costs) in constraints (5), one for each coil.

7.

Computational Study

Because the project was initiated with the explicit goal
to develop a tool to go live in an existing production
environment, we were provided with realistic data
right from the beginning. Planners at SZFG repeatedly
validated our solutions and addressed various issues
regarding the accuracy of cost calculations and theHöhn et al.: Integrated Sequencing and Scheduling in Coil Coating
Management Science 57(4), pp. 647–666, © 2011 INFORMS

Figure 7

Detail of the Visualization of an Integer Optimal Solution
to Our Integer Program with Subsequences with  = 4
Coils Each

Notes. Each block represents one shuttle coater with its two tanks; thedark rectangles reﬂect the coils in the coating sequence. It is clearly visiblethat the integer program ignores global cost in between subsequences. The
expert planner can also see where and when which type of setup has to be
performed.

practicability of work schedules, which were eventually solved. Visualizations of our solutions certainly
helped in that respect; see Figure 7.
The test instances fall in two categories. The ﬁrst
comprises sets of up to 120 coils for a planning horizon of up to 72 hours. These instances are solved wellahead of time for long-term planning. The second category is made up of 20–40 coils for a shorter time
horizon of at most 24 hours. These instances usuallyoccur when unplanned changes in demand or availability of coils necessitate short-term replanning.
For many test instances, SZFG provided a plan
devised by their expert planners for comparison with
our solutions. In most cases we were able to obtain
unexpected improvements over these plans. We cannot report on the precise numerical characteristics ofour data and results because of nondisclosure agreements, hence normalized numbers are presented.
7.1. Some Implementation Details
Parameters for the genetic sequencing algorithm were
determined by rigorous testing, with the goal to have
one ﬁxed parameter set yielding good performanceacross all data sets. For most short-term instances, ouralgorithm ﬁnds its best solutions after less than 30 seconds, whereas solutions keep improving toward theruntime limit of 180 seconds for long-term planning.
In the construction heuristic for the initial population (§5.1), we use some coil properties thatwere omitted in the problem formulation in §2 forsimplicity. All possible three-tuples of width, height,
processing speed, and temperature in primer and ﬁnish oven are taken as criteria r1 , r2 , and r3 , accounting for about one-third of our initial population of
200 individuals. In each generation we create 100 new

661
individuals each from both mutations of random individuals and crossovers of two randomly chosen parents. This results in a total population of 400, of which
we keep the 200 with the best makespan for the next
generation.
Especially on small instances, the population
quickly evolves to a set of individuals with almost
identical cost. When the makespan of all individuals
is within 5% of the best individual, we discard theworst 90% of the population and replace it with a
new initial population. This usually leads to further
improvement of the best individuals in subsequent
generations.
Regarding scheduling, we performed extensive
testing using the heuristics described in §§5.2.1
and 5.2.2. We report on results for the independent
set heuristic for different values of the parameter  ∈0 1 compared with the simpler FIFO rule.
For lower bound computations, we implemented
a branch-and-price algorithm to solve the integer
program (4)–(11) within the publicly available SCIP
framework (solving constraint integer programs)(Achterberg 2009). Its implementation is not tuned toperformance because we used it as a proof of concept
only, so we do not report computation times for lower
bounds (which were huge).
7.2. Interpretation of Results
Our algorithm produces plans with makespan reductions of up to 25%, on average over 13%, compared
to reference solutions actually gone to production inboth long-term and short-term planning; see Figures 8
and 10. Expert planners also assert that our solutions“look very different” from theirs while retaining operability. Together with the fact that signiﬁcant savings
are also realized over manual plans that “looked optimal,” we take this as evidence that our rigorous mathematical analysis of the savings potential of shuttle
coaters fully paid off. It should also be noted againthat indeed every detail of production is controlled byour plan, and that these plans were veriﬁed on-site at
SZFG’s coil coating line. Hence, cost savings are now
realized to their full extent in day-to-day production.
7.2.1. Long-Term Instances. As expected, our
independent set heuristic for setup scheduling proves
superior to the simpler FIFO online rule. We wereunable, however, to ﬁnd a uniform choice of theparameter  suitable for all instances alike. When
determining the best setting for  by trying all values in 01     08, the graph heuristic outperformed
FIFO on 12 of the 16 instances, reducing cost by up to
30% (over FIFO). This translates to makespan savingsof up to 6%; see Figure 8. When ﬁxing  to 05, theindependent set heuristic remains similarly superior
to FIFO on eight instances, while incurring an increasein makespan of at most 1% in four cases; see Figure 9.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

662
Figure 8

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Comparison of Normalized Makespans for Representative Long-Term Instances

1.40

1.20

Best alpha
FIFO
Expert planner

1.00

0.80

0.60

0.40

0.20

0.00
Note. From left to right, makespans are for our solutions using the independent set heuristic with optimal choice of parameter , our solutions using the FIFO
online rule, as well as for a reference solution devised by an expert human planner where it was available.

7.2.2. Short-Term Instances. For all short-term
instances, we succeeded in computing lower bounds
by our branch-and-price approach, proving our solutions to be within at most 10% of makespan optimality; see Figure 10. Yet, we did not solve all instances
to integer optimality and also used short subsequences only ( ≤ 6), so the lower bound is certainly
improvable.
If we concentrate on cost—in contrast to makespan—it can be seen from Figure 11 that the integer
programming lower bound is able to close much moreof the gap to the upper bound than the TSP bound,which is optimal w.r.t. local cost only.
Figure 9

Finally, the superiority of the independent set
heuristic to FIFO is less signiﬁcant in short-term planning. Although both heuristics were on a par for
most instances, small improvements over FIFO wereobserved in three cases.

8.

Summary and Conclusions

We have developed an exact mathematical model forthe complex integrated sequencing and schedulingtask in coil coating with shuttles and implemented
optimization software solving it in practice. Our
approach fulﬁlls all requirements regarding speed

Comparison of Normalized Nonproductive Time Included in Our Long-Term Solutions

1.20

Best alpha
Alpha= 0.5
FIFO

1.00

0.80

0.60

0.40

0.20

0.00
Note. From left to right, costs are for our algorithm when using the independent set heuristic with optimal choice of , with ﬁxed choice of = 0 5, and whenusing the FIFO online rule.

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

663

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Figure 10

Comparison of Normalized Bounds and Makespans for Representative Short-Term Instances When Restricted to FIFO Tank Assignment

1.60
Trivial lower bound
TSP lower boundIP lower bound
FIFO
Expert planner

1.40
1.20
1.00
0.80
0.60
0.40
0.20
0.00

Notes. Bounds displayed from left to right are LBtriv , the sum of coil processing times; LBTSP , the sum of processing times plus local cost in an optimal, local
cost-based TSP solution; and our IP bound LBIP . Makespans are given for our solutions obtained using the FIFO online rule for scheduling, as well as for areference solution devised by an expert human planner where it was available.

and robustness for its application in the production
environment. Our model takes into account all relevant aspects of production reality, including the subtasks of sequencing the coils and scheduling the color
tanks and the scarce work resources to perform setup
work. The integrity of the plans computed and thecorrectness of cost calculations have been veriﬁedby the planners in charge of the coil coating line at
Salzgitter Flachstahl GmbH, Germany.
Figure 11

Percentage of the Closed Relative Gap Between the
Respective Trivial Lower Bound and the Optimum
Nonproductive Time Included in Our Short-Term
FIFO Solutions

0.8
0.7

TSP lower boundIP lower bound

0.6
0.5
0.4
0.3
0.2

Compared to previous plans, the optimized solutions yield double-digit percentage reductions inmakespan, greatly exceeding what was deemed possible: After all, the careful analysis of the problem
necessary for devising the mathematical model has
lead to a deep understanding of structure and interdependencies in the planning task, which enabled therealization of hidden optimization potential.
For the scheduling subproblem, we have developed a graph theoretic model allowing for the fastcomputation of optimal solutions in an environment
where sufﬁcient work resources are available. For thepresent resource-constrained case, this model leads
to a heuristic algorithm that is signiﬁcantly superior
to the simpler FIFO rule, particularly for long-term
instances.
Finally, we have developed and implemented an
integer programming model of a combinatorial relaxation of the problem, which we are able to solve via
branch-and-price for short-term planning instances.
The solutions yield lower bounds on the optimal
makespan of our short-term instances when using
an online tank assignment rule, proving that ourheuristic solutions have an optimality gap of no morethan 10%. Our optimization module has been in
use for day-to-day planning at Salzgitter FlachstahlGmbH since December 2009.

0.1

Acknowledgments
0Note. Our bound from the branch-and-price approach respects global costand closes considerably more of the gap than the TSP-based bound, which
considers only local cost.

The authors thank Michael Bastubbe, Torsten Gellert, andOlaf Maurer for help in implementing the branch-and-priceand genetic algorithms. Furthermore, the authors appreciate
the patience of Frank Barcikowski, Andreas Holdinghausen,

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

664

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Sigurd Schwarz, and Meister Krake at SZFG for answering countless questions concerning the even more countlessdetails of setup cost, and for carefully verifying their solutions. The authors thank the referees for motivating themto put their work in a more general context, in particularfor suggesting to consider the case r > 1; these comments
also led to a lighter notation and improved presentation.
This work was supported by the German Research Foundation (DFG) as part of the Priority Program “Algorithm
Engineering.”

Appendix. Proof of Theorem 2
In this hardness proof, we follow the main ideas from theproof of Theorem 1. Recall, that in this proof, the reduction from 3SAT was leading to an instance of the maximum independent set problem in m-composite 2-uniongraphs with very few rectangles. However, it is no clear
how this instance corresponds to CSS. Hence, further investigations are necessary to show its hardness. Our proof isdivided into four major steps: In §A.1, we consider the special structure of m-composite 2-union graphs resulting from
CSS instances. In general, these graphs contain a very highnumber of rectangles. In §A.2, we investige a special CSS
instance with only one cell, for which we show that it is
sufﬁcient to concentrate on a very limited set of rectangles
in the corresponding 2-union graph. This graph will be ofsimilar structure as the one in the proof of Theorem 1. In
the main part of the proof in §A.3, we reduce 1-in-3-3SAT
to CSS with one resource. Finally in §A.4, we generalize ourresult to an arbitrary number of resources.
Throughout the proof, we speak of an interval being contained in another according to the natural sense of time, i.e.,referring to the time axis starting at the beginning of eachsection; see Figure 5.
Structure of m-Composite 2-Union Graphs
for CSS Instances
The m-composite 2-union graphs corresponding to instancesof CSS exhibit a special structure: All possible tool intervals
for the given sequence need to be considered for each of
the m cells. Moreover, for each tool interval I, we have totake into account all setup intervals of length
A.1.

wsetup I = minp I  s k pred I  succ I or shorter if the setup interval is started less that wsetup I
time units before I’s end. We also need to consider thecase of empty setup intervals. In fact, we can think of all
setup intervals belonging to a tool interval I as only one
rectangle, which can be moved along the setup interval’stime axis within the interval I. According to the number ofsetup resources r, we copy this rectangle representation of
the m-composite 2-union graph to r different sections along
the y-axis to obtain the ﬁnal graph for the CSS instance.
Note that all our argumentation also holds when considering only discrete start times of the setup intervals as given
in Lemma 1. Still, for simplicity, we assume them to bearbitrary.
As described in §3.4, by adding a sufﬁciently large constant to each tool interval, weighted by its length, we canassume that every maximum weight independent set covers
every job on every cell. For simplicity, we do not consider

these additional weights in the following. Still, we assume
that in every maximum weight independent set, all jobs arecovered by a tool interval on every cell.
A.2.

Zero-Cost Decision Variant for aSpecial Instance of CSS
We consider a zero-cost decision variant of CSS for a special instance with odd number of jobs n and m = r = 1.
Later, we will use our investigations on this simple instanceto construct a more elaborate one in our hardness proof.
We assume = id. For any even job j, we have processing
time pj = 1, and for odd j, arbitrary pj ≥ 1. Setup costs are
speciﬁed by⎧
0 if j = i + 1 and i = 1 n − 1
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
M if j = i + 1 and i = 1 n − 1
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨0 if j = i + 2 and i is evens i j =⎪⎪
1 if j = i + 2 and i is odd
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
C if i = 1 and j = n
⎪
⎪
⎪
⎪
⎪
⎩
M otherwise,with C > 0 and M > i pi . The variable M is chosen sufﬁciently large such that in any zero-cost schedule, no setup
of length M occurs; the length of any tool interval is simply
not long enough to perform this setup work concurrently.
In the following, we will rule out rectangles that are
sufﬁcient to be considered when searching for a zero-costschedule:• Because of the size of M, we cannot chose any toolinterval containing the jobs 1 and 2 or n − 1 and n.
Hence, every zero-cost solution chooses the tool intervals 1and n. The setup intervals are empty, because no setup
has to be performed at the beginning and at the end.
• The tool interval 2 n − 1 can only be chosen if all
resulting setup is performed concurrently, i.e., if its setup
interval has length C.
• Consider tool intervals j for j = 2 3     n − 1. For
odd j, no setup is necessary, and hence the setup interval isempty. If j is even, a setup interval of length 1 is required.
Because in this case pj = 1, there is no ﬂexibility in starting
the setup interval.
• All other tool intervals require setup work of length M,
and thus they do not occur in zero-cost solutions.
Summarizing, it sufﬁces to consider the tool interval 2 n − 1 and all intervals containing exactly one job,
where only 2 n − 1 provides some ﬂexibility for concurrent setup work; see Figure A.1(a). This leaves exactly two
possible tool assignments: either we switch the tool after
every job or we only switch after the ﬁrst job and before thelast job.
Finally, note that we can replace an even job i by pi unitsize jobs i1  i2      ipi without changing the set of rectangles
necessary to consider. We deﬁne the setup cost between consecutive replacement jobs to be 0, and transfer the setup costto and from i to i1 and ipi , respectively. All remaining setup
cost is set to M. With the same arguments as above, it is sufﬁcient to assume that the jobs i1  i2      ipi form one interval

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating

665

Management Science 57(4), pp. 647–666, © 2011 INFORMS

Figure A.1

Instances of CSS That Are Used in the Proof of Theorem 2(b) Setup
Empty setup intervals
intervals

(a)

Setup
intervals
n
n–1
n–2
n–3

Literal xi

Literal xi

Clause c5

Empty setup
intervals

Clause c4

Clause c1
3m′+2n′C3m′+2n′

5
4
3
2
1

...

Rectangle for variable xi

Rectangle for variable xi

...

...
1 2 3 4 5n–3 n–2 n–1 n Tool

2n′ jobs

intervalsn′(3m′+2n′)′ jobs

2m′ jobs

2n′ jobs

n′(3m′+2n′)′ jobs

2m′ jobs

Toolintervals

Notes. (a) Necessary saving the rectangles for one cell of the instance from §A.2 when considering the zero-cost decision variant of CSS are shown. For
simplicity, pj = 1 for all j. (b) Cells 2i − 1 and 2i in the CSS instance represent literals xi and xi from the instance of 1-in-3-3SAT. Grey rectangles markpositions of variable and clause rectangles on other cells. In this example, the clauses c1 and c5 contain literal xi , and c4 contains xi .

instead of, as previously, i. Thus, given a sequence of unitsize jobs, any subset S ⊂ 2 3     n − 1 with i − j ≥ 2 forany i = j ∈ S deﬁnes a CSS instance as described in this section. We interprete the jobs in S as formerly even jobs andcall them unit rectangle jobs.
A.3.

Reduction of 1-in-3-3SAT to CSS withOne Resource
We will now show the strong NP-hardness of CSS when henumber of cells m is part of the input and when there is
only one resource. We reduce from 1-in-3-3SAT, a variant of
3SAT where one asks for a variable assignment such thatin every clause exactly one variable is true. This problem
variant is known to be strongly NP-hard (Schaefer 1978).
The main ideas of the reduction are taken from the proof of
Theorem 1.
Consider an instance I  of 1-in-3-3SAT with n variables
x1      xn and m clauses c1      cm . We reduce it to an
instance I of CSS with n = 2 n + m + n 3m + 2n unitsize jobs and m = 2n cells, one for each literal. Literals xi
and xi , i ∈ 1     n correspond to cells 2i − 1 and 2i, respectively. For each cell, we deﬁne the setup cost by specifying
the unit rectangle jobs as in §A.2: For xi and xi , we choose
job 2i on the cells 2i − 1 and 2i. If literal l is contained in
the sth clause, then we choose job
2n + n 3m + 2n + 2s − 1on the cell corresponding to l̄; see Figure A.1. We refer to therelated rectangles as variable rectangles and clause rectangles,
respectively, and set the setup cost C to 3m + 2n . We willshow that there is a zero-cost schedule for I if and only if I 
is a yes-instance of 1-in-3-3SAT.
Assume, we are given a truth assignment for I  . For any
true literal we choose a rectangle based on the tool interval 2 n − 1 and arrange these n rectangles without setup
conﬂict from job 2n + 1 til 2n + 1 + n 3m + 2n . On all
remaining cells, we choose the variable rectangle and allclause rectangles. This does not lead to a conﬂict, because
all of these variable rectangles belong to different variables,
and in every clause exactly one literal is true. By §A.2, thechosen rectangles represent a zero-cost schedule for I.

Consider the rectangle representation  of a zero-cost CSS
schedule of I. By the amount of setup cost C,  cannot
contain more than n rectangles based on the tool interval 2 n − 1. Otherwise, not all setup work can be performed concurrently. Assume that there is a variable forwhich both such rectangles are chosen. Then, by the above,
there in another variable for which no such rectangle is chosen. Because at most one of the corresponding variable rectangles can be contained in , this leads to schedule withpositive cost. Hence, for each variable exactly one rectangle
based on 2 n − 1 is selected. We set the corresponding literals to true. On the remaining n cells, all variable and clauserectangles must be chosen to allow a zero-cost schedule. Thisis possible if and only if for each clause exactly one literal is
not covered by a 2 n − 1-rectangle.
A.4.

Generalization for an Arbitrary Number ofResources
We generalize the result of §A.3 for r > 1 resources byadding r − 1 cells to the reduction above. For these cells,
we deﬁne the setup costs as follows: Between consecutive
jobs, we have cost 0, except after the ﬁrst and before thelast job, where the cost is deﬁned to be M. Between job 1
and n, we set the cost to n − 2. In all remaining cases, thecost is set to M. The only option to schedule the jobs onsuch a cell without cost is to switch the tank after the ﬁrst
and before the last job and to perform concurrent setup in
the meantime, blocking one full resource.
Note that with a similar construction, we can argue thatthe hardness result of Theorem 1 holds even when there isan arbitrary constant number of independent sections along
the y-axis.

References
Aarts, E., J. K. Lenstra, eds. 1997. Local Search in Combinatorial Optimization. John Wiley & Sons, Hoboken, NJ.
Achterberg, T. 2009. SCIP: Solving constraint integer programs.
Math. Programming Comput. 1(1) 1–41.
Allahverdi, A., C. T. Ng, T. C. E. Cheng, M. Y. Kovalyov. 2008.
A survey of scheduling problems with setup times or costs.
Eur. J. Oper. Res. 187(3) 985–1032.

666
Balas, E., N. Simonetti, A. Vazacopoulos. 2008. Job shop scheduling with setup times, deadlines and precedence constraints.
J. Scheduling 11(4) 253–262.
Bampis, E., F. Guinand, D. Trystram. 1997. Some models forscheduling parallel programs with communication delays.
Discrete Appl. Math. 72(1–2) 5–24.
Barnhart, C., E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh,
P. H. Vance. 1998. Branch-and-price: Column generation forsolving huge integer programs. Oper. Res. 46(3) 316–329.
Bar-Yehuda, R., M. M. Halldórsson, J. Naor, H. Shachnai, I. Shapira.
2006. Scheduling split intervals. SIAM J. Comput. 36(1) 1–15.
Butman, A., D. Hermelin, M. Lewenstein, D. Rawitz. 2010. Optimization problems in multiple-interval graphs. ACM Trans.
Algorithms 6(2) 40:1–40:18.
Cook, S. A. 1971. The complexity of theorem-proving procedures.
Proc. 3rd Annual ACM Sympos. Theory Comput., ACM, New
York, 151–158.
Deﬂorian, F., L. Fedrizzi, S. Rossi. 2000. Effects of mechanical deformation on the protection properties of coil coating products.
Corrosion Sci. 42(7) 1283–1301.
Delucchi, M., A. Barbucci, G. Cerisola. 1999. Optimization of coilcoating systems by means of electrochemical impedance spectroscopy. Electrochimica Acta 44(24) 4297–4305.
Desrosiers, J., M. E. Lübbecke. 2005. Selected topics in column generation. Oper. Res. 53(6) 1007–1023.
Duarte, R. G., A. C. Bastos, A. S. Castela, M. G. S. Ferreira. 2005.
A comparative study between Cr(VI)-containing and Cr-freeﬁlms for coil coating systems. Progress in Organic Coatings 52(4)320–327.
Gupta, U. I., D. T. Lee, J. Y.-T. Leung. 1982. Efﬁcient algorithms forinterval graphs and circular-arc graphs. Networks 12(4) 459–467.
Gyárfás, A., J. Lehel. 1970. A helly type problem in trees. P. Erdős,
A. Rényi, V. T. Sós, eds. Combinatorial Theory and Its Applica-

Höhn et al.: Integrated Sequencing and Scheduling in Coil Coating
Management Science 57(4), pp. 647–666, © 2011 INFORMS

tions II, Vol. 4. Colloquia Mathematica Societatis János Bolyai.
North-Holland, Amsterdam, 571–584.
Hall, N. G., C. N. Potts, C. Sriskandarajah. 2000. Parallel machinescheduling with a common server. Discrete Appl. Math. 102(3)
223–243.
Helsgaun, K. 2000. An effective implementation of the LinKernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1)106–130.
Kaiser, T. 1997. Transversals of d-intervals. Discrete Computational
Geometry 18(2) 195–203.
Koulamas, C., G. J. Kyparisis. 2008. Single-machine schedulingproblems with past-sequence-dependent setup times. Eur.
J. Oper. Res. 187(3) 1045–1049.
Meloni, C., D. Naso, B. Turchiano. 2003. Multi-objective evolutionary algorithms for a class of sequencing problems in manufacturing environments. IEEE Internat. Conf. Systems, Man andCybernetics 1 8–13.
Meuthen, B., A.-S. Jandel. 2005. Coil Coating. Vieweg+Teubner,
Wiesbaden, Germany.
Mühlenbein, H., M. Gorges-Schleuter, O. Krämer. 1988. Evolution algorithms in combinatorial optimization. Parallel Comput.
7(1) 65–85.
Rekieck, B., P. D. Lit, A. Delchambre. 2000. Designing mixedproduct assembly lines. IEEE Trans. Robotics Automation 16(3)268–280.
Schaefer, T. J. 1978. The complexity of satisﬁability problems. Proc.
10th Annual ACM Sympos. Theory Comput., ACM, New York,
216–226.
Tang, L., X. Wang. 2009. Simultaneously scheduling multiple turns forsteel color-coating production. Eur. J. Oper. Res. 198(3) 715–725.
Zhang, W., R. Smith, C. Lowe. 2009. Confocal Raman microscopy
study of the melamine distribution in polyester-melamine coilcoating. J. Coatings Tech. Res. 6(3) 315–328.