Capacity Planning for Cluster Tools in the
Semiconductor Industry
Martin Romaucha,∗, Richard F. Hartla
a Department of Business Administration
University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Wien

Abstract
This paper proposes a new model for Cluster-tools with two load locks. Clustertools are widely used to automate single wafer processing in semiconductor
industry. The load locks are the entry points into the vacuum of the Clustertool’s mainframe. Usually there are two of them available. Each lot being
processed, is dedicated to a single load-lock. Therefore at most two different
lots (with possibly different processing times and qualification) can be processed
simultaneously. This restriction is one of the major potential bottlenecks.
Capacity planning is one of the possible applications for the proposed model
and the paper demonstrates the integration into a more general framework that
considers different tool types and different operational modes.
The paper also generalizes an earlier model that is limited to three processing
chambers. The proposed modeling approach is based on makespan reductions
by parallel processing. It turns out that the performance of the new approach
is similar, when compared to the generalized model for three chambers, but the
new approach outperforms the generalized model for four and more chambers.
Keywords: Cluster-Tool , Capacity Planning, Semiconductor Industry, Linear
Programming , Duality

1. Introduction
This paper considers Cluster-Tools, a tool type that can be found in semiconductor fabrication front-end sites, also called wafer fabrication facilities. The
wafer is the substrate used for the fabrication of integrated circuits for semicon∗ Corresponding

author
Email addresses: martin.romauch@univie.ac.at (Martin Romauch),
richard.hartl@univie.ac.at (Richard F. Hartl)

Preprint submitted to —————–

3rd May 2016

2

Design,
Maskmaking
reticles

Wafermaking

wafer
starts

Epitaxy

Front-End
Process:
------Oxidation,
Deposition,
Diffusion

Photolitography
Photoresist
Exposure
Planarization
Etch

semiconductor
device

Test &
back-end

wafer
finishes

Cleaning

Inspection & Measurement

raw
silicon

Implantation

FRONT-END (WAFER FABRICATION)

Figure 1: front end fabrication as a re-entrant flow shop (based on Sorenson [24] and Mönch
et al. [19])

ductor devices. A wafer is a disc, usually a slice of mono-crystalline silicon with
a width between 150 and 300 mm, and a thickness between 0.5 and 1 mm.
The input of front-end facilities are containers of wafers (also called lots or
FOUPs, Front Opening Unified Pods). A lot usually consists of 20 or more
wafers that require the same processing. The fabrication is characterized by a
large number loops or layers (compare Hutcheson [15]). Each loop consists of
one or more processing steps; one of them is a lithographic process that allows
to cover parts of the wafer (photo resist) from the process that follows. Figure
1 gives a schematic view on wafer fabrication.
The flow diagram in Figure 1, is a representation of the fabrication process
as a re-entrant flow shop. According to Thiesse and Fleisch [25] the traversed
path of a single lot can be several kilometers long.
In semiconductor industry most of the equipment is automated and characterized by load/unload operations, robot handling, testing, alignment, cooling
and much more. Cluster Tools (compare Franssila [6]) for instance, have one or
more load locks and multiple processing chambers. Cluster-tools are used to automate several process types. The internal software defines the behavior of the
system. Cluster tools allow an automatic transfer of wafers between load ports
and process chambers with possibly different processes inside a vacuum. The
system can also be used for parallel processing to increase throughput and productivity. The wafers are transferred between chambers under a vacuum using a
robotic arm to prevent exposure to air to prevent oxidation and contamination.
Since a Cluster-tool may operate on different lots at the same time, the combination of lots is important and the Cluster-tool may show different operation
cycle times for the same type of lot. According to Mönch et al. [19] several researchers studied the optimization of internal scheduling, but the corresponding
models are not suitable to consider several Cluster-tools at the same time. One

3

L1

3

LL1

2

1

A
3

B

A

LL1

2

L1

B
1

L2

3
2

L2

1

3
2

LL2

LL2

C
(i) t = 0

3

LL1

A

1

C
(ii) t = 5

A

2

A

B

1

LL1

2

L1

B

L1

1

1

LL2

2

C

(iii) t = 6

L2

3

3

B

2
1

C

1

2

3

3

L2

3

LL1
1

LL2

2

C

(iv) t = 10

LL2
t = 1 2 3 4 5 6 7 8 9 10 11 12

Figure 2: A Cluster-tool with two load locks that is processing wafers in parallel. On left
hand side: four snapshots of the Cluster-tool for t = 0, 5, 6, 10 can be found. The thickness of
the outline of the wafers, indicates the processing progress. The corresponding Gantt-chart
can be found on the right hand side of the Figure.

of the major bottlenecks of a Cluster-tool are the load locks (see Christopher
[3]). The load locks are the entry point into the vacuum of the Cluster tool.
In order to describe a Cluster-Tool with respect to load locks and chambers, a
simplified schedule for a Cluster-tool that is working in parallel mode is discussed
in Example 1. The example is based on Figure 2.
Example 1. On the left hand side of Figure 2, a Cluster-tool that is working in
parallel mode with two load locks LL1 and LL2 is illustrated. In this example
the chambers are supposed to be identical. Later in the example, one of the
chambers will be less flexible than the others. In the beginning (t = 0), each
load lock is occupied by one lot (LL1 with lot L1 and LL2 with lot L2 ), and
each lot consists of three wafers. Each wafer needs to be processed in one of the
chambers. The load lock LL1 is occupied with the lot L1 that needs the longer
processing time. More precisely, each wafers from L1 need a processing time of
six time units. For L2 the processing time is five time units per wafer. In this
example the wafer handling time is neglected, therefore it is possible to start all
processes in each chamber at the same time.
In the first step (i) with t = 0, two wafers from lot L1 are assigned to
chambers A and B; and one wafer from L2 is assigned to chamber C. At t = 5
the wafer in chamber C is finished and it is passed back to L2 . Then, the second
wafer from L2 is assigned to chamber C. At t = 6 the wafers in A and B are
handed back to L1 and chamber A will be occupied by the last wafer of L1 ;
chamber B will be occupied by the last wafer of L2 .
The corresponding Gant-chart can be found on the right hand side of Figure
1
2. The make-span is 12 with an idle time percentage of 12
on average. If wafers
from L1 are excluded from chamber C then at least two wafers from L1 need to
be assigned to the same chamber (A or B), hence the schedule is optimal with

4

respect to the make-span.
Now, additionally suppose that the problem is scaled by thirty, and each lot
counts 90 wafers. Then the wafers can be distributed in such a way that the
idle time percentage vanishes. If this is possible, then the total processing time
is 90 · (6 + 5) = 990. Therefore it is sufficient to find a distribution where each
chamber finishes after 330 time units. Note that 330 is divisible by five and six:
A

B

C

}|
{ z }| {
z }| { z
330 = 55 · 6 = 35 · 6 + 24 · 5 = 66 · 5
Therefore 55 wafers from L1 can be assigned to chamber A and 66 wafers
of L2 can be assigned to chamber C. The remaining wafers can be assigned to
chamber B.
This example shows that on a larger scale where larger quantities are considered, a continuous approximation - where it is allowed to computationally
“split” wafers - leads to reasonable results.
LP based Cluster-tool models can be directly integrated in capacity models
or in master planning like proposed in Ponsignon and Mönch [22] and Romauch
and Klemmt [23]. The combination of simulation and optimization (LP) as
discussed in Almeder et al. [1] Gansterer et al. [8] and Juan et al. [16] is also
suitable for the integration of LP based Cluster-Tools models.
Finally, real-time dispatching that integrates LP approaches can be found
in Doleschal et al. [4] and Ham et al. [11] which can be extended to LP based
Cluster-tool models. According to Duemmler and Wohlleben [5] there are also
various alignments necessary to achieve an effective WIP Flow Management
that assures that the planned capacity consumption (utilization) is coherent
with the dispatching reality. Therefore, improvements of LP based Cluster-tool
models are important to several areas.
The focus of this paper is on static capacity planning, but it is important to
note that the LP models introduced in this paper may also be useful to other
applications, like master planning, simulation and dispatching.
In the context of capacity planning for front-end facilities, a concise prediction of the equipment utilization is one of the major tasks. For given demands
- that is wafer starts for given product routes - a calculation needs to confirm
that the capacity restrictions are met. Furthermore it is necessary to identify
hard/soft bottlenecks that are limiting the throughput.
Depending on the purpose and time frame, there are several methods to
tackle this capacity planning problem - sometimes elementary MRP calculations are sufficient, but the large majority is covered by simulation and linear
programming. This paper is dedicated to linear programming formulations and
proposes a Cluster Tools model for multiple chambers and two load locks that
is performant, flexible and easy to analyze.
The contribution of this paper is threefold. First, we present a new model
that considers more than three chambers. Second we derive the model presented
in Ortner [21] in a more general way that also allows to handle than three chambers. Third, computational experiments are used to compare the performance
of the proposed methods.

5

2. Capacity Planning in Semiconductor Industry
In order to show the applicability of the proposed Cluster-Tool model, the integration into a basic capacity planning model will be presented. The discussed
model is static, the processing sequence is not considered and the quantities of
wafers are continuous. Aspects like multiple time-frames can be understood as
an elementary extension (cf. Romauch and Klemmt [23]), therefore the discussion (and the computational experiments) is restricted to a basic model to prove
the concept and to avoid a cumbersome notation.
The discussion of input and output of the basic capacity planning model
starts with an example that is depicted in Figure 3. The input for the capacity
planning model is the weekly going rate dp for each product p ∈ P on the basis
of lots for a given fixed lot size. That means, dp wafers of product product
p need to be produced in the following week. Each product corresponds to a
product route that consists of processing steps. Some of the processing steps
can be considered equivalent for different product routes and these equivalent
processing steps constitute the so called job classes (j ∈ J). The capacity
consumption (e.g. service times) and flexibility for members of the same job
class is the same. Analogous to Figure 3 the primary demand dp on basis
products infers a secondary demand λj on basis job classes. For instance job
class 1 has a demand λ1 = 30 because this job class occurs once in the product
routes for product one and product two (λ1 = d1 + d2 ).
The wafers λj are distributed among the available machines, i.e. yji wafers
from job class j are assigned to machine
i. In total, for each job class j the
P
demand λj needs to be satisfied, i.e. i∈{a,b,c,d} yij = λj . The distribution that
corresponds to yji infers a load on the corresponding machines that depends on
P6
the service time tji , i.e. ui = j=1 yji tji .
For the static capacity model the arrival rate λj on basis job class is distributed over the machines and results in a utilization profile, that corresponds
to the capacity usage. A proper distribution or resource allocation is therefore
a center piece of capacity planning, it will be used to judge if the demand can
be satisfied and to identify the bottlenecks. The capacity model selected for
the investigations is based on the idea of minimizing the maximum utilization
- that means, to minimize utilization on the bottleneck. This approach can be
extended to a lexicographic mini-max objective like in Ogryczak [20] to identify all levels of equally utilized equipment (cf. resource pool concept in Gold
[9, 10]). A solution that is optimal with respect to the lexicographic mini-max
objective has the property that only machines of the same level may share the
load of a common job class.
The LP defined in (1-4) is called the basic model, where the maximum load is
minimized. According to (3) ρ is an upper limit to the utilization ui for all tools
i ∈ I and the decision variable xji corresponds to the time invested in processing
lots from job class j on machine i. The service rate µji = t1ji corresponds to
number of lots that can be processed in one time unit. Therefore the number
of processed units of job class j on machine j is yji = xji µji . In order to satisfy
the demand, constraint (2) has to be satisfied.

6

product mix
(pP)

dp

d1=20

40

ua
utilization

job classes

j J 1
lj l1=30

a

wafer starts
per week

(pP)

d2=10

product routes

expected utilization
for each machine

demand for each
job class (given)

demand for each
product (given)

10

demand for each product

2

3

l2=80 l3=20

d3=40

4

5

l4=60 l5=10

ub

uc

b

c

6

l6=40

ud

d

(iI)
machines

Figure 3: A simplified capacity planning process - the Figure is adapted from Romauch and
Klemmt [23]. A given demand on the basis of products is decomposed into a demand for
each job class. Finally a distribution of the workload results in a forecast for the expected
utilization.

min ρ
s.t.

P

i∈I xji µji = λj
P
ui = j∈J xji ≤ ρ

xji ≥ 0.

(1)
(∀j ∈ J),

(2)

(∀i ∈ I),

(3)
(4)

3. Capacity Planning for Cluster Tools
The LP defined in (1-4) is a valid model for parallel single servers in heavy
traffic (see e.g. Harrison and Lopez [12]), where each machine is represented by
a queue with a given service rate.
The models presented in this paper are based on these assumptions and
extend the model to Cluster-Tools. According to Lopez and Wood [18] the
main operating modes are the serial and the parallel mode. A Cluster-Tool is
operated in serial mode if each wafer visits all chambers in a sequence and it is
working in parallel mode if each wafer visits only one chamber.
The serial mode can be approximated (lower bound) by separating the chambers of the Cluster-Tool from the mainframe. For instance, a Cluster-tool i with
three chambers {A, B, C} is represented by the mainframe i, and the chambers
(i, A), (i, B) and (i, C). An activity j calls chambers and mainframe at the same
time. The corresponding service rates for the chambers are µj,(i,A) , µj,(i,B) and

7

µj,(i,C) . Since the slowest process defines the throughput of the tool, hence
the service rate for the mainframe is defined by µj,i = minu∈A,B,C {µj,(i,v) }.
Therefore it is sufficient to add the following constraint to (1-4):

P

ui,v =

xji µji
j∈J µj,(i,v)

≤ ρ (∀i ∈ I, v ∈ {A, B, C})

(5)

The objective of this paper is to propose a similar approximation for ClusterTools in parallel mode. The corresponding models need a bit more explanation.
For Cluster-Tools in parallel mode the service rate depends on the selected
subset of chambers r∈ R ={A, B, C, AB, ...} that are selected to process a given
type of lot. The subset of chambers is also called a recipe. The service time µj,i,r
depends on the job class j, the Cluster tool i and the recipe r. The demand is
represented by the arrival rate λj .
The distribution of lots is determined by xj,i,r , which is the time invested
in activity (j, i) with recipe r. In Ortner [21] a parallel Cluster-Tool model for
two Load locks and three processing chambers is discussed. The basic idea is
the identification of categories for optimal schedules (see Figure 4) where the
makespan can be represented by a simple formula. Each formula is the
Pweighted
sums of the times
invested
in
a
given
recipes
amd
can
be
written
as
r wi,r xi,r
P
where xi,r = j xj,i,r .
For instance, if all possible processes are running in parallel which means that
x
+x
+x
+xi,A +xi,B +xi,C
the load locks are the limiting resource, then xi,ABC + i,AB i,AC i,BC
2
is the corresponding make-span. If this is not the case, then a single chamber
recipe exists that is too short or too long to run in parallel, which means that
the make-span must be larger than that.
It was shown, that the make-span can be represented by the maximum value
of five formulas. The corresponding proof in Ortner [21] is constructive and
generates feasible schedules for each case identified.
The LP (6-9) is an abstraction of the LP found in Ortner [21], where the
matrix B is defined in Table 1.
In (6-9) we present an extension of (1-4) that can be used to represent the
approach presented in Ortner [21]. For the three chamber case, the matrix B
represents the formulas given in Figure 4 and the corresponding values can be
found in Table 1.
One of the contributions of the paper is to derive matrices for more than
three chambers.

min ρ
P

(6)

xj,i,r µj,i,r = λj

(∀j ∈ J)

(7)

Bk,r xj,i,r ≤ ρ

(∀i ∈ I, k ∈ K)

(8)

(j, i, r) ∈ C

(9)

i ∈ I, r ∈ R :
(j, i, r) ∈ C

P

j∈J,r∈R

xj,i,r ≥ 0

8

xi,ABC + xi,AB + xi,AC + xi,A

A

xi,ABC

xi,AB

xi,AC

B

xi,ABC

xi,AB

xi,B

C

xi,ABC

xi,C

xi,ABC +

xi,A
xi,BC

xi,B

xi,AC xi,BC

A

xi,ABC

xi,AB

B

xi,ABC

xi,AB

C

xi,ABC

xi,C

xi,ABC + xi,AB + xi,BC + xi,B

A

xi,ABC

xi,AB

B

xi,ABC

xi,AB

xi,BC

C

xi,ABC

xi,C

xi,BC

xi,AB +xi,AC +xi,BC +xi,A +xi,B +xi,C
2

xi,A
xi,B

xi,B
xi,C

xi,ABC + xi,AC + xi,BC + xi,C

xi,A
xi,B

A

xi,ABC

xi,AC

xi,A

B

xi,ABC

xi,B

xi,BC xi,B

C

xi,ABC

xi,AC

xi,BC

xi,C

xi,ABC + xi,AB + xi,BC + xi,AC

A

xi,ABC

xi,AB

B

xi,ABC

xi,AB

C

xi,ABC

xi,C

xi,AC

xi,A

xi,B

xi,BC

xi,AC

xi,BC

Figure 4: Illuistration of different categories of optimal schedules. Five examples are given,
one for each representative schedule. Each Figure ia a Gantt-chart (x-axis: time) on basis
chambers. The formula in the header contains the formula to calculate the makespan, it
represents this category. Two-chamber-recipes are colored to highlight the joint usage of two
chambers.

Table 1: Matrix B = (Bk,r ) for the dual based model (6-9) when considering three chambers.

k=1
2
3
4
5

r=A
0.5
1

B
0.5

C
0.5

AC
0.5
1

1
1

1
1

BC
0.5
1
1
1

AB
0.5
1
1
1

ABC
1
1
1
1
1

3.1

An alternative modeling approach that exploits parallel processing

BC

AC

xi,BC

9

xi,AC
ξi,AC,B

A

B

ξi,A,BC

xi,A

ξi,A,B

xi,ABC

ABC
ξi,A,C

C

xi,B

ξi,B,C

xi,C
ξi,AB,C

AB

xi,AB

Figure 5: Parallel processing for three chambers, graph representation G(R, E). The vertices
R represent the recipes and the edges E represent possible parallelizations. The Figure on
the right hand side represents the parallelization opportunities for a given Cluster-tool i. For
instance, the variable ξi,AB,C defines the time invested in parallel processing of recipe AB
and recipe C.

Before tackling this problem, an alternative modeling approach that considers more than three chambers is presented.
3.1. An alternative modeling approach that exploits parallel processing
For a single equipment i, where the time invested in certain recipes xj,i,r
is given and P
no parallel processing is allowed (one load lock) the resulting
makespan is j,r xj,i,r . In case two load locks are available it is possible to
exploit parallel processing. Since xj,i,r cannot be changed, the time spent in
parallel processing is the only way to reduce the makespan. This parallelization
problem can be seed as a sub problem and will be explained in this chapter. A
similar idea was used in Tian et al. [26] for parallel processor scheduling.
In Figure 5 the graph representation G(R, E) of the parallelization problem
for three chambers can be found. The vertices R represent the recipes and the
edges E represent possible parallelizations. On the right hand side the parallelization opportunities for a given Cluster-tool i are illustrated. For instance,
when considering the parallelizations with recipe C, then there are three possible candidates {A, B, AB}. Each of these options is reflected by a variable
that defines the time used for this recipe combination, i.e. ξi,A,C , ξi,B,C and
ξi,AB,C . Also note that the time invested in parallel processing is limited by the
given values xj,i,r . For instance when considering ξi,AB,C two restrictions can
be found: ξi,AB,C ≤ xi,AB and ξi,AB,CP+ ξi,A,C + ξi,B,C ≤ xi,C . According to
that, a parallelization that maximizes (r1 ,r2 )∈E ξi,r1 ,r2 solves the sub-problem.
The prallelization graph that considers four chambers is depicted in Figure
6 and the number of vertices is already twice as large. The graph is also not
planar anymore, since it contains a K3,3 given by {A, B, AB} × {C, D, CD}.

The general formulation of the corresponding sub problem for optimal parallelization is represented by the following LP:

3.1

An alternative modeling approach that exploits parallel processing

xi,BC

10

xi,AD
xi,ABCD

xi,AC
xi,ACD

xi,ABC

xi,B

xi,D

xi,CD

xi,AB

xi,A

xi,C

xi,BCD

xi,ABD
xi,BD

Figure 6: Parallel processing for four chambers, graph representation G(R, E).

max
P

r2 :(r,r2 )∈E

P

(r1 ,r2 )∈E

ξi,r,r2 +

ξi,r1 ,r2

P

r1 :(r1 ,r)∈E

ξi,r1 ,r ≤ xi,r

ξi,r1 ,r2 ≥ 0

(10)
(∀r ∈ R)

(11)

(∀(r1 , r2 ) ∈ E)

(12)

The sub-problem (10-12) be integrated in the master LP as follows:

min ρ
P

(13)
j∈J

(14)

i ∈ I, r ∈ R

(15)

i ∈ I, r ∈ R

(16)

i∈I

(17)

xj,i,r ≥ 0

(j, i, r) ∈ C

(18)

xi,r ≥ 0

i ∈ I, r ∈ R

(19)

i ∈ I, (r1 , r2 ) ∈ E

(20)

xj,i,r µj,i,r = λj

i ∈ I, r ∈ R :
(j, i, r) ∈ C
P
xi,r = j xj,i,r
P
P
r2 :(r,r2 )∈E ξi,r,r2 +
r :(r ,r)∈E ξi,r1 ,r ≤ xi,r
P
P 1 1
r∈R xi,r −
(r1 ,r2 )∈E ξi,r1 ,r2 ≤ ρ

ξi,r1 ,r2 ≥ 0

In order to count the number of variables xj,i,r , xi,r and ξi,r1 ,r2 it is sufficient
to count the vertices and edges in the parallelization graph. Suppose that n
chambers
are available, then |R| = 2n − 1 recipes are available. There are

n
k possibilities to choose a set of k chambers and each partition defines nonk
conflicting recipe pair, that makes 2 2−2 (= 2k−1 − 1) edges. Therefore, the
Pn
n
number of edges is |E| = k=0 (2k−1 − 1) = 3 2−1 − (2n − 1) in total. According
n
to that the coefficient matrix of (13-20) has 1+|C| + |I| 3 2−1 columns, |J| +
|I|(1 + 2|R|) rows and 2|C| + |I|(1 + 3|R| + 2|E|) nonzeros.

3.2

Analysis of the parallelization problem

11

3.2. Analysis of the parallelization problem
The second approach is based on investigating the dual of the sub-problem
(10-12). The problem (10-12) can be represented by a max-flow problem which
gives some insights about the structure of basic feasible solutions.
The corresponding max-flow problem is defined as follows, the set of vertices
e ∪ {s, t}, where R
e
and edges and the capacity limits are defined by: V = R ∪ R
e
is a copy of R. The arcs between R and R are a bipartite representation of E,
together with the links to the source, and the links to the sink, the set of arcs
e i.e Ee ={(r, re) ∈ R × R
e : (r, re) ∈ E} ∪ {(s, r) : r∈ R} ∪ {(e
is defined by E,
r, t) :
e The arc capacities are infinite for all arcs except the links to source
re ∈ R}.
and the links to the sink. In Figure 7 the max-flow version for three chambers
e ∪ {s, t}, E)
e is illustrated. The meaning
is depicted where the graph G(R ∪ R
of the flows ηi,r1 ,r˜2 and ηi,r2 ,r˜1 is directly linked to ξi,r1 ,r2 since the maximum
flow formulation can be understood as a duplication of the original problem.
The details will be elaborated in a transformation of the problem. Before that,
the LP of the corresponding max-flow problem will be defined in (21-26). The
objective (22) is to maximize the flow into the sink t. The constraints (22)
and (23) represent the flow balance equations. The capacities on the arcs are
formulated in (24) and (25).
P

e ηi,re,t
(e
r ,t)∈E
P
= ηi,s,r
e ηi,r,e
r
e
r : (r,e
r )∈E
P
= ηi,e
e ηi,r,e
r
r ,t
r: (r,e
r )∈E
xi,r
ηi,s,r ≤ 2
max

ηi,e
≤
r ,t

xi,r
2

ηi,e ≥ 0

(21)
(∀r ∈ R)

(22)

e
(∀e
r ∈ R)

(23)

(∀r ∈ R)

(24)

(∀r ∈ R)

(25)

e
(∀e ∈ E)

(26)

To see that the max-flow version is a suitable representation of the sub
problem, a transformation of solutions will be established.
If η is a feasible solution for (21-26), then ξ defined by ξi,r1 ,r2 ← ηi,r1 ,re2 +
ηi,r2 ,re1 is a feasible solution for (10-12) and the objective value is the same.
In order to prove this statement it is necessary to provePthat (11) is satisfied. The left hand side of (11) has the following form:
r2 :(r,r2 )∈E (ηi,r,re2 +
| {z }
(i.1)

(ii.1)

(ii.2)

P
z }| {
z }| {
ηi,r2 ,e
) + r1 :(r1 ,r)∈E (ηi,r1 ,e
+ ηi,r,re1 ). Note that (r, r2 ) ∈ E is represented by
r
r
| {z }
(i.2)

e Therefore the components (i.1) and (i.2)
two arcs (r, r˜2 ) ∈ Ee and (r2 , r̃) ∈ E,
can
by
P be combined andPbecause of (22,24) the
P corresponding part is bounded
xi,r
η
+
η
=
η
=
η
≤
.
Bei,s,r
r2 :(r,r2 )∈E i,r,re2
r1 :(r1 ,r)∈E i,r,re1
2
e i,r,e
r
e
r :(r,e
r )∈E
cause of (23,25) the part that corresponds to (ii.1) and (ii.2) is bounded by

3.2

Analysis of the parallelization problem

≤

s

12

ABC

]
ABC

AB

g
AB

xi,AB
2

≤
ηAB,Ce

ηC,AB
f

AC

g
AC

BC

g
BC

C

f
C

B

f
B

A

xi,AB
2

f
A

R

t

R̃

e ∪ {s, t}, Ee) of the maximum flow formulation of the
Figure 7: Graph representation G(R ∪ R
sub problem for three chambers. The flow can be interpreted as the time used for parallel
processing: ξAB,C ← η
+η
.
AB,C

C,AB

e

f

P

P
P
ηi,r2 ,e
+ r1 :(r1 ,r)∈E ηi,r1 ,e
= r:(r,e
= ηi,e
≤
r
r
e ηi,r,e
r
r ,t
r )∈E
ξ is feasible for (10-12).
r2 :(r,r2 )∈E

xi,r
2 .

Hence,

The dual is therefore a min-cut problem and for the solution space it is
sufficient to consider selecting arcs that are connected to the sink or to the
source - these cuts are called basic cuts. In other words, for every cut it is
possible to construct a basic cut that has a cut value that is smaller or equal.
The formulation of the dual of the maximum flow formulation (21-26) can be
found in (27-30). The dual variables are called πi,r and π
ei,r . The constraint
(28) reveals the vertex covering aspect of the problem.
min

P

r∈R

xi,r

πi,r +e
πi,r
2

πi,r1 + π
ei,r2 ≥ 1

(27)
∀(r1 , re2 ) ∈ Ee

(28)

πi,r ≥ 0

∀r ∈ R

(29)

π
ei,r ≥ 0

∀r ∈ R

(30)

This problem is totally uni-modular, because the columns can be partitioned
according to the criterion proposed in Heller and Tompkins [13].
For the search space, it is sufficient to consider basic cuts. A basic cut B can
e and
be represented by the corresponding nodes that are selected, B ⊂ R ∪ R
e
each arc (r1 , re2 ) between R and R is covered by B to satisfy (28). Furthermore,

3.2

Analysis of the parallelization problem

13

it is sufficient to consider basic cut that cannot be reduced by eliminating a
node, that means that by definition, removing one node of a minimal basic cut
leads to an infeasible solution.
e \ B) of a minimal basic cut is a maxTherefore the complement (B c = R ∪ R
imum independent set. Efficient algorithm for listing all maximum independent
sets are known (see Kashiwabara et al. [17]) and can be used to find all minimal
basic cuts.
k
k
Suppose that a listing {(πi,r
,π
ei,r
)}k∈K that represents all minimal basic cuts
is given, then the optimal value for (27-30) corresponds to the cut value with
the smallest value in the listing of all minimal basic cuts.
k
k
)}k∈K are given, then the
,π
ei,r
Suppose that all minimal basic cuts {(πi,r


k
k
P
πi,r
+e
πi,r
smallest value r∈R xi,r
defines the optimum.
2
In order to remove 
symmetric solutions,
 the solutions will be identified by
k
k
πi,r
+e
πi,r
, hence the optimum is defined by
vectors (Πi,r,k ) where Πi,r,k ←
2
P
mink r∈R xi,r Πi,r,k . The minimum of a set of numbers is defined as the largest
lower bound of these numbers, therefore the optimum can be represented by the
LP formulated in (31-32), where constraint (32) ensures that χ is a lower bound
of the cut values and the objective (31) defines that χ is the largest lower bound:
max χ
χ≤

P

r∈R

xi,r Πi,r,k

(31)
∀k ∈ K

(32)

Therefore the shortest possible makespan
for given xi,r can be obtained by
P
changing
the
the
objective
(32)
to
min
x
r∈R i,r − χ. A substitution of χ with
P
ρ ← r∈R xi,r − χ in (33-32) leads to the following equivalent LP:
ρ

min
P

r∈R

(33)

(1 − Πi,r,k ) xi,r ≤ ρ ∀k ∈ K

(34)

The new formulation of the sub problem will be integrated in the master problem
(13-20) by replacing the constraints (17,16) with (34). The resulting master LP
is formulated in (3540):
min ρ
P

(35)
j∈J

(36)

i ∈ I, r ∈ R

(37)

− Πi,r,k )xi,r ≤ ρ

i ∈ I, k ∈ K

(38)

xj,i ≥ 0

i ∈ I, r ∈ R

(39)

xj,i,r ≥ 0

(j, i, r) ∈ C

(40)

xj,i,r µj,i,r = λj

i ∈ I, r ∈ R :
(j, i, r) ∈ C
xi,r =
P

r∈R (1

P

j

xj,i,r

14

The problem (27-30) can be interpreted as a relaxation of the vertex cover
problem, therefore the basic solutions are half integral (compare Hochbaum [14],
type 2var).
If the number of chambers is fixed, the coefficients (1 − Πi,r,k ) only depend
on the number of chambers, therefore a representation by a R × K matrix
1−Π = (1−Πr,k ) can be used. In order to reduce the size of the matrix, all rows
of 1 − Π that are redundant will be removed. The details to the corresponding
Algorithm can be found in AppendixA.
For three chambers the model (3540) coincides with the model presented in
Ortner [21] (compare (6-9)) and the matrix (1 − Π) is equivalent to the matrix
presented in Table 1. Therefore, the presented methodology replaces (6-9) and
provides an alternative to the elementary proof given in Ortner [21].
More importantly, the approach reveals a generalization of the model in
Ortner [21] to more than three chambers. For instance, the matrix for four
chambers is given in Table 2. Note that line 1 corresponds to complete parallelization, while line 8 corresponds to the sum of all recipes that contain A and
line 12 corresponds to chamber B, line 18 represents the utilization for chamber
C and line 23 represents the utilization for chamber D. Note that the coeffin
cient matrix of (3540) has 1+|C| + |I| 3 2−1 columns, |J| + |I|(|R| + |K|) rows and
2|C| + |I|(|R| + 1 + |K| + |1 − Π|) nonzeros, where |1 − Π| denotes the number
of nonzeros in (1 − Πi,r,k ). Known values for |K| and |1 − Π| can be found in
Table 4. According to that, the generalized model for five chamber is already
getting fairly large.
In the next section a computational experiment will be used to compare the
new approach and the generalized model.
4. Computational Experiments
In this Section the computational results for the generalized formulation
(35-40) and the alternative model (13-20) for the a large set of benchmark
instances (http://www.univie.ac.at/prolog/research/Clustertool/) is presented.
The instances were solved with Gurobi 6.0 on a desktop computer with a i72670QM@2.2 GHz processor.
The structure of the generalized formulation (13-20) seems to be much simpler than the alternative model (35-40), but especially for more than three
chambers the coefficient matrix of the generalized formulation tends to grow
faster and therefore it is interesting to examine which model performs better.
The size of the problems is indicated in Table 5 and Table 7, where the number
of nonzero entries in the coefficient matrix of the alternative model and the
scaling factor for the generalized model are documented (all chamber released).
The number of nonzeros of the coefficient matrix for the generalized model is
nonzerogen = 2|C|+|I|(|R|+1+|K|+|Π|) and the for the alternative formulation
it is nonzeroalt = 2|C| + |I|(1 + 3|R| + 2|E|) . Therefore the difference of the
δ =nonzerogen − nonzeroalt can be calculated as follows:
δ = |I|(|K| + |Π| − 2(|R| + |E|)) = |I|(1 + |K| + |Π| − 3n )

15

Table 2: Matrix B for the dual based model (6-9) when considering four chambers.
A

AB

ABC

ABCD

ABD

AC

ACD

AD

B

BC

BCD

BD

C

CD

D

1

0.5

0.5

0.5

1

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

2

0.5

0.5

1

1

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

3

0.5

0.5

0.5

1

1

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

4

0.5

0.5

1

1

1

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

5

0.5

0.5

0.5

1

0.5

0.5

1

0.5

0.5

0.5

0.5

0.5

0.5

6

0.5

0.5

1

1

0.5

0.5

1

0.5

0.5

0.5

0.5

0.5

0.5

7

0.5

0.5

0.5

1

1

0.5

1

0.5

0.5

0.5

0.5

8

1

1

1

1

1

1

1

1

9

0.5

0.5

1

0.5

0.5

0.5

0.5

0.5

0.5

1

0.5

10

0.5

1

1

0.5

0.5

0.5

0.5

0.5

0.5

1

0.5

11

0.5

0.5

1

1

0.5

0.5

0.5

0.5

0.5

1

0.5

12

1

1

1

1

1

1

1

1

13

0.5

0.5

1

0.5

0.5

1

0.5

1

0.5

14

1

1

1

1

1

1

1

1

15

1

1

1

1

1

1

16

1

1

1

1

1

17

1

1

1

1

1

18

1

1

19

1

1

20

1

21
22
23

0.5
1

0.5
0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5
0.5

0.5

0.5

0.5

0.5

1

1

1
1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
1

1

1

1

1

1

1

1

1

1

1

1

1

1

Table 4: Known values for |K| and |1 − Π|

|K|
|1 − Π|

n=1
1
1

2
2
4

3
5
22

4
23
245

5
590
13740

Table 5: Number of nonzero entries in the coefficient matrix of the alternative model; unit:
thousands.
three chambers
four chambers
five chambers
density shape sizecat=0 1
2
3
0
1
2
3
0
1
2
3
1:1
3.4 11.3 40.9 156.8 8.0 25.7 90.6 341.7 18.9 57.7 196.3 724.4
1:4
2.2 8.7 32.9 123.7 5.1 19.4 71.8 267.9 11.6 42.4 153.0 562.8
1
16:1
6.2 17.2 54.1 188.2 16.1 42.5 127.3 425.8 42.5 106.0 299.5 953.0
4:1
4.4 13.8 46.7 171.7 10.8 32.3 105.8 379.2 26.8 75.9 236.9 820.2
1:1
4.3 15.3 59.2 232.5 9.9 34.2 129.8 504.0 22.7 75.3 277.3 1059.7
1:4
3.0 10.7 42.2 165.5 6.9 23.6 91.9 357.5 15.3 51.1 194.5 747.9
2
16:1
7.0 21.0 74.0 271.4 17.9 50.6 169.9 604.1 46.0 122.8 387.6 1321.4
4:1
5.3 18.4 66.6 256.1 12.7 42.2 148.3 560.0 30.7 96.3 324.8 1193.8
1:1
4.5 17.4 68.7 271.7 10.4 38.7 149.9 587.8 23.8 84.6 319.0 1233.0
1:4
3.2 11.5 46.0 181.4 7.2 25.4 99.9 391.4 16.1 54.8 211.0 818.1
3
16:1
7.1 23.9 85.4 318.7 18.0 56.8 194.4 705.4 46.4 135.6 438.2 1530.8
4:1
5.8 20.3 78.4 302.7 13.8 46.3 173.6 659.9 33.0 104.8 376.9 1400.2

16

Table 7: Scaling factor for nonzero entries in the coefficient matrix of the generalized model
relative to alternative model. An entry of 2 means that the number of nonzero elements is
twice as large.
three chambers
four chambers
five chambers
density shape sizecat=0 1
2
3
0
1
2
3
0
1
2
3
1:1
1.01
1.00 1.00 1.00 1.47 1.29 1.17 1.09 15.93 10.76 6.74
4.11
1:4
1.00
1.00 1.00 1.00 1.38 1.22 1.12 1.06 13.44 8.49 5.06
3.13
1
16:1
1.00
1.00 1.00 1.00 1.36 1.19 1.10 1.05 12.85 7.66 4.53
2.83
4:1
1.00
1.00 1.00 1.00 1.37 1.19 1.10 1.06 13.17 7.64 4.68
3.00
1:1
1.00
1.00 1.00 1.00 1.27 1.16 1.08 1.04 10.21 6.52 3.90
2.51
1:4
1.00
1.00 1.00 1.00 1.26 1.15 1.08 1.04 9.75 6.14 3.67
2.38
2
16:1
1.01
1.01 1.01 1.00 1.93 1.71 1.47 1.28 27.55 22.26 16.05 10.46
4:1
1.01
1.01 1.00 1.00 1.84 1.59 1.35 1.20 25.48 19.35 12.63 7.82
1:1
1.01
1.01 1.00 1.00 1.83 1.53 1.31 1.17 25.31 17.63 11.29 6.89
1:4
1.01
1.01 1.00 1.00 1.70 1.47 1.28 1.16 22.00 15.86 10.51 6.50
3
16:1
1.01
1.00 1.00 1.00 1.59 1.36 1.20 1.11 19.33 12.70 7.94
4.78
4:1
1.01
1.00 1.00 1.00 1.55 1.32 1.17 1.09 18.09 11.76 6.98
4.22

Table 9: Auxiliary parameters δn and γn for calculating δ = nonzerosgen − nonzerosalt =
|I|δn and nonzeroalt = 2|C| + |I|γn .
n=1
2
3
4
5
γn =

δn
3n+1 −2n+1 +1
2

0

-2

1

188

14088

3

10

33

106

333

17

In Table 9 some values for

δ
|I|

can be found.

The instances that were used in the computational experiment vary in size
and structure and the following four factors were controlling the construction:

• sizecat {0, 1, 2, 3}
where, |I| · |J| = 100 · 4sizecat = 400,1600, 6400, 25600

• shape {1 : 4, 1 : 1, 4 : 1, 8 : 1}
where |I| : |J| = shape, the proportion of tools and jobs

• locked {0, 3, 6, 9}
is the probability that a chamber is not available.
locked chambers: locked
10

• density {1,2,3}
1=sparse, 2=medium, 3=dense

For the three chamber model, the corresponding instances have up to 300.000
nonzeros and for four chamber up to 700.000 nonzeros for the case where all
chambers are available. According to Table 10 the alternative model is significantly faster for four chambers, but in average slower for three chambers.

18

Table 10: Speedup factor for alternative model versus generalized model (detailed results).
The bold entries represent cases were the generalized model is faster.
three chambers
four chambers
sizecat shape density locked=0 3
6
9
avg locked=0 3
6
9
avg
1
0.84 0.82 0.88 0.8 0.84
1.25
1.12 0.83 1.11 1.08
1:4
2
1.07
0.81 0.61 0.93 0.86
1.2
1.15 1.33 1.18 1.22
3
0.83 0.85 0.91 0.93 0.88
1.2
1.21 1.27 1.22 1.23
1
0.97 0.83 0.8 0.86 0.87
0.92 0.82 0.71 1.22 0.92
1:1
2
0.79 0.97 0.88 0.9 0.89
1.11
1.12 1.23 1.14 1.15
3
0.86
0.9 0.92 0.82 0.88
0.93
1.1 1.09 1.16 1.07
0
1
0.67 0.65 0.81 0.68 0.7
0.66 0.79 0.82 0.8 0.77
4:1
2
0.96 0.73 0.77 0.76 0.81
0.77 0.82 0.82 0.93 0.84
3
0.83 0.74 0.77 0.71 0.76
0.82
0.8 0.83 0.9 0.84
1
0.72
0.6 0.63 0.51 0.62
0.74
0.6 0.58 0.59 0.63
16:1
2
0.63 0.58 0.65 0.68 0.64
0.78 0.72 0.6 0.67 0.69
3
0.6
0.58 0.59 0.52 0.57
0.81 0.71 0.66 0.69 0.72
1
0.98 0.84 0.83 0.78 0.86
1.63
1.33 1.37 1.48 1.45
1:4
2
0.89 0.91 0.96 0.96 0.93
2.29
1.73 1.62 1.61 1.81
3
0.76 0.75 0.94 0.97 0.86
1.89
1.78 1.52 1.6 1.7
1
1.08
0.92 1.02 0.85 0.97
1.43
1.43 1.42 1.34 1.41
1:1
2
1.11
0.82 1.09 1.01 1.01
1.53
1.48 1.44 1.43 1.47
3
1.11
1.07 1.1 1.73 1.25
1.83
1.43 1.46 1.42 1.54
1
1
0.8
0.7 0.84 0.62 0.74
1.22
1.07 0.98 1.11 1.1
4:1
2
1.21
0.54 1.15 0.86 0.94
1.52
1.41 1.21 1.22 1.34
3
1.18
0.8 0.86 0.79 0.91
1.49
1.49 1.24 1.38 1.4
1
0.66 0.57 0.71 0.68 0.66
0.99
1.04 0.83 0.84 0.96
16:1
2
0.68
0.6 0.48 0.72 0.62
1.29
1.27 1.12 0.94 1.16
3
0.74 0.51 0.7 0.76 0.68
1.26
1.27 1.14 1.07 1.19
1
0.91 0.97 0.74 1.02 0.91
2.05
2.32 1.92 1.82 2.03
1:4
2
1.08
1.06 0.98 0.96 1.02
2.22
2.02 2.03 2.05 2.08
3
1.06
1.09 1.06 1.09 1.08
2.04
2.02 1.87 1.98 1.98
1
1.3
1.13 0.95 1.29 1.17
2.35
1.68 1.81 1.62 1.87
1:1
2
1.19
1.09 1.22 1.05 1.14
2.08
2.35 1.94 1.8 2.04
3
1.26
1.4 1.11 1.05 1.21
1.87
1.9 1.84 1.94 1.89
2
1
0.95 0.89 0.88 0.92 0.91
1.69
1.78 1.66 1.53 1.67
4:1
2
1
0.91 0.89 0.93 0.93
1.68
1.7 1.83 1.7 1.73
3
2.43
0.99 0.94 1
1.34
1.82
1.76 1.78 1.69 1.76
1
0.74 0.78 0.75 0.98 0.81
1.44
1.72 1.41 1.27 1.46
16:1
2
0.84 0.82 0.83 0.85 0.84
1.5
1.71 1.63 1.51 1.59
3
0.85
0.8 0.89 0.96 0.88
1.48
1.67 1.68 1.53 1.59
1
1.41
1.02 1.19 1.19 1.34
2.5
2.44 2.17
2
2.28
1:4
2
1.24
1.16 1.1 0.94 1.11
2.41
2.42 2.74 2.23 2.45
3
1.22
1.1 0.99 1.2 1.13
2.33
2.2 2.93 2.1 2.39
1
1.77
1.32 1.05 1.07 1.3
1.82
2.26 2.04 1.94 2.02
1:1
2
1.28
1.48 1.33 1.05 1.29
2.94
2.24 2.13 2.11 2.36
3
1.33
1.31 1.32 1.09 1.26
3.09
3.52 2.21 2.11 2.73
3
1
1.08
0.92 0.95 1.01 0.99
1.7
1.81 1.87 1.82 1.8
4:1
2
1.04
0.92 1
1.03
1
1.85
2
1.91 1.87 1.91
3
2.7
1.11
1
1.1 1.48
2.03
1.91 1.82 1.96 1.93
1
1.03
0.83 0.89 0.92 0.92
1.63
1.91 1.88 1.62 1.76
16:1
2
1.02
0.94 0.92 1.01 0.97
1.7
1.7 1.94 1.74 1.77
3
1.16
0.91 0.95 0.99 1
1.63
1.64 1.88 1.79 1.74
avg
1.11
0.9 0.91 0.93 0.97
1.55
1.59 1.52 1.47 1.54

19

Table 12: CPU time in milliseconds.
three
sizecat shape density locked=0 3
1
25
28
1:4
2
30
36
3
29
33
1
36
36
1:1
2
39
36
3
37
42
0
1
48
49
4:1
2
47
49
3
58
53
1
64
84
16:1
2
63
71
3
70
73
1
60
68
1:4
2
76
79
3
96
101
1
73
95
1:1
2
84
132
3
98
118
1
1
106
124
4:1
2
122
219
3
129
147
1
144
184
16:1
2
155
199
3
170
284
1
230
234
1:4
2
237
269
3
268
316
1
237
271
1:1
2
349
380
3
366
454
2
1
306
325
4:1
2
414
462
3
482
504
1
423
417
16:1
2
516
532
3
600
636
1
844.5 920
1:4
2
893
1171
3
1000 1270
1
783
1106
1:1
2
1498 1533
3
1749 2017
3
1
1097 1339
4:1
2
1751 2012
3
1823 2184
1
1216 1450
16:1
2
1820 2002
3
1998 2465

chambers
6
9
25
25
41
27
32
30
35
35
42
39
38
40
47
47
48
50
53
56
65
83
68
65
70
77
70
86
74
72
89
79
88
88
99 100
114 135
111 130
127 130
139 158
158 155
244 164
194 176
301 219
284 286
297 282
275 263
366 353
438 418
346 343
490 437
519 487
435 377
527 502
579 568
799 798
1048 1194
1318 1110
1010 932
1567 1470
1888 1705
1170 1077
1744 1632
2162 1816
1348 1229
1976 1715
2271 2057

four chambers
avg locked=0 3
6
9
25.75
48
41
48
35
33.50
60
60
55
55
31.00
70
66
59
58
35.50
72
85
95
67
39.00
97
82
80
80
39.25
109
94
90
83
47.75
129
138 107 98
48.50
149
144 131 115
55.00
164
158 145 127
74.00
219
233 203 169
66.75
230
249 238 192
72.50
241
263 245 190
71.00
166
175 153 128
75.25
175
200 181 159
91.25
190
213 202 174
86.00
221
225 206 185
103.75
267
285 262 243
116.25
273
319 313 275
117.75
301
329 333 282
149.50
372
376 378 343
143.25
395
381 418 407
160.25
615
513 507 459
190.50
538
549 552 533
206.00
583
606 586 542
246.00
498
491 518 468
269.00
643
717 663 585
290.75
727
778 734 620
261.50
581
801 693 627
362.00 1015 1010 940 849
419.00 1213 1226 1098 969
330.00
904
907 888 802
450.75 1428 1408 1189 1063
498.00 1460 1639 1398 1214
413.00 1467 1347 1242 1111
519.25 2049 1731 1540 1342
595.75 2373 2030 1731 1556
843.23 2574 2330 1912 1655
1076.50 3771 3387 2693 2244
1174.50 4066 3881 2970 2481
957.75 4401 3155 2750 2228
1517.00 6157 5217 3992 3243
1839.75 6818 5885 4755 3793
1170.75 5851 4490 3302 2538
1784.75 8029 6460 4972 3733
1996.25 8498 7921 6246 4475
1310.75 6815 4901 3794 3274
1878.25 10745 8655 5332 4430
2197.75 12061 10248 6514 5102

avg
43.00
57.50
63.25
79.75
84.75
94.00
118.00
134.75
148.50
206.00
227.25
234.75
155.50
178.75
194.75
209.25
264.25
295.00
311.25
367.25
400.25
574.33
543.00
579.25
493.75
652.00
714.75
675.50
953.50
1126.50
875.25
1272.00
1427.75
1291.75
1665.50
1922.50
2117.75
3023.75
3349.50
3133.50
4652.25
5312.75
4045.25
5798.50
6785.00
4696.00
7290.50
8481.25

20

5. Summary
The paper proposes a new model for representing Cluster-Tools with two
load locks and provides generalization of an existing Cluster-Tool model Ortner
[21] that was restricted to three chambers. A computational study indicates
that on average the generalized model for three chambers is a little faster than
the new model proposed in this paper, but for several instances the proposed
alternative model seems to have small but significant benefits.
For four chambers, the new model performs significantly better than the
generalized model. Except for very small instances, the new model out-performs
the generalized one.
Our future research will consider Cluster-tools with more than two load
locks and we will investigate the impact of conflicting recipes. We will also
work on sensitivity analysis and robustness with respect to recipe combinations
and availability.
References
[1] Almeder, C., Preusser, M., Hartl, R. F., 2009. Simulation and optimization
of supply chains: alternative or complementary approaches? OR spectrum
31 (1), 95–119.
[2] Chazelle, B., 1993. An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry 10 (4), 377–409.
[3] Christopher, J., 2008. Study of optimal load lock dedication for cluster
tools. In: Proceedings of the 40th Conference on Winter Simulation. Winter
Simulation Conference, pp. 2136–2140.
[4] Doleschal, D., Weigert, G., Klemmt, A., Lehmann, F., 2013. Advanced
secondary resource control in semiconductor lithography areas: from theory
to practice. In: Proceedings of the 2013 Winter Simulation Conference:
Simulation: Making Decisions in a Complex World. IEEE Press, pp. 3879–
3890.
[5] Duemmler, M., Wohlleben, J., 2012. A framework for effective wip flow
management in semiconductor frontend fabs. In: Simulation Conference
(WSC), Proceedings of the 2012 Winter. IEEE, pp. 1–6.
[6] Franssila, S., 2010. Introduction to microfabrication. John Wiley & Sons.
[7] Gale, D., 1989. The theory of linear economic models. University of Chicago
press.
[8] Gansterer, M., Almeder, C., Hartl, R. F., 2014. Simulation-based optimization methods for setting production planning parameters. International
Journal of Production Economics 151, 206–213.

21

[9] Gold, H., 2004. Dynamic optimization of routing in a semiconductor manufacturing plant. In: Hein Fleuren, Dick den Hertog, P. K. (Ed.), Operations
research proceedings 2004: selected papers of the annual international conference of the German Operations Research Society (GOR); jointly organized with the Netherlands Society for Operations Research (NGB). German Operations Research Society (GOR) and the Netherlands Society for
Operations Research (NGB), Tilburg, The Netherlands, pp. 76–83.
[10] Gold, H., 2008. Lastverbund, european patent ep1567921.
[11] Ham, M., Lee, Y. H., Fowler, J. W., 2009. Integer programming-based
real-time scheduler in semiconductor manufacturing. In: Winter Simulation
Conference. Winter Simulation Conference, pp. 1657–1666.
[12] Harrison, J. M., Lopez, M. J., 1999. Heavy traffic resource pooling in
parallel-server systems. Queueing Systems 33, 339–368.
[13] Heller, I., Tompkins, C., 1956. An extension of a theorem of Dantzig’s.
Linear inequalities and related systems 38, 247–254.
[14] Hochbaum, D. S., 1996. Approximating covering and packing problems:
set cover, vertex cover, independent set, and related problems. In: Approximation algorithms for NP-hard problems. PWS Publishing Co., pp.
94–143.
[15] Hutcheson, J. D., 2000. Introduction to semiconductor equipment. Handbook of Semiconductor Manufacturing Technology, 23–33.
[16] Juan, A. A., Faulin, J., Grasman, S. E., Rabe, M., Figueira, G., 2015. A
review of simheuristics: Extending metaheuristics to deal with stochastic
combinatorial optimization problems. Operations Research Perspectives 2,
62–72.
[17] Kashiwabara, T., Masuda, S., Nakajima, K., Fujisawa, T., 1992. Generation of maximum independent sets of a bipartite graph and maximum
cliques of a circular-arc graph. Journal of Algorithms 13 (1), 161–174.
[18] Lopez, M. J., Wood, S. C., 2003. Systems of multiple cluster tools: Configuration, reliability, and performance: Single-wafer manufacturing in the
nanochip era. IEEE transactions on semiconductor manufacturing 16 (2),
170–178.
[19] Mönch, L., Fowler, J. W., Dauzère-Pérès, S., Mason, S. J., Rose, O., 2011.
A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling 14 (6),
583–599.
[20] Ogryczak, W., 1997. On the lexicographic minimax approach to location
problems. European Journal of Operational Research 100 (3), 566–585.

22

[21] Ortner, A. M., 2008. capacity planning for cluster tools - a mathematical
model that reflects scheduling for parallel processing with two loadlocks.
Master thesis, Alpen-Adria-Universität Klagenfurt, Klangenfurt, Austria.
[22] Ponsignon, T., Mönch, L., 2012. Heuristic approaches for master planning
in semiconductor manufacturing. Computers & Operations Research 39 (3),
479–491.
[23] Romauch, M., Klemmt, A., 2015. Product mix optimization for a semiconductor fab: Modeling approaches and decomposition techniques. Computers & Operations Research 53, 338 – 352.
URL http://www.sciencedirect.com/science/article/pii/
S0305054814001087
[24] Sorenson, C. T., 1999. Basic principles of semiconductor manufacturing.
Microelectronics Manufacturing and the Environment Course Materials,
http://www.erc.arizona.edu/education/mme%20course%
20materials/MME%20Modules/Manufacturing%20Module/
Manufac%20Overview.ppt, accessed: 2016-04-07.
[25] Thiesse, F., Fleisch, E., 2008. On the value of location information to lot
scheduling in complex manufacturing processes. International Journal of
Production Economics 112 (2), 532–547.
[26] Tian, K., Jiang, Y., Shen, X., 2009. A study on optimally co-scheduling
jobs of different lengths on chip multiprocessors. In: Proceedings of the 6th
ACM Conference on Computing Frontiers. CF ’09. ACM, New York, NY,
USA, pp. 41–50.
URL http://doi.acm.org/10.1145/1531743.1531752

AppendixA. Algorithm to find a minimal representation for the dual
based model
With respect to (6-9) it is important to keep the set K as small as possible.
Therefore, the concept of redundant vectors (redundant minimal basic cuts) will
be introduced and different criteria for redundancy will be stated and proven.
According to (38), vectors Πk := (Πr,k ) ∈ RR are used as a lower bound on ρ,
i.e. h1 − Πk , xi ≤ ρ. Suppose for two vectors Πk , Πk0 the following condition
true: h1 − Πk , xi ≤ h1 − Πk0 , xi ≤ ρ. Then Πk0 dominates Πk and Πk can be
removed. The condition can be reformulated to hΠ, xi ≥ hΠk0 , xi and leads to
the following more general definition of redundancy:
Definition 2. Assuming that a set A of m vectors, A = {a1 , a2 . . . , am } with
ai ∈ Rn and ai ≥ 0 is given. Then a vector b is called redundant if the following
is true:
∀x ≥ 0 : hb, xi ≥ mini hai , xi

23

Or, in other words b is called redundant if ∀x ≥ 0∃i : hb, xi ≥ hai , xi. Note,
that it is sufficient to consider vectors x of unit length, therefore b is called
redundant if:
∀x ≥ 0, kxk = 1∃i : hb, xi ≥ hai , xi ⇔
∀x ≥ 0, kxk = 1∃i : h1 − b, xi ≤ h1 − ai , xi ⇔
∀x ≥ 0, kxk = 1∃i : kh1 − b, xi xk ≤ kh1 − ai , xi xk
Geometrically, h1 − b, xi x can be interpreted as the projection of 1 − b on x.
Also note that
i
i
h1 − b, xi x − 1−b
= 1−b
and h1 − ai , xi x − 1−a
= 1−a
for kxk =
2
2
2
2
1, therefore the statement is equivalent to:
S
i
U +1−b ( 1−b
) ⊂ i U +1−ai ( 1−a
)
2
k 2 k
k 2 k 2
where U+ (b) = {x ∈ Rn : x ≥ 0, kx − bk ≤ }.
Figure A.8 depicts an example in three dimensions. If the sphere U +1−b ( 1−b
)
k 2 k 2
S +
i
is contained in i U 1−ai ( 1−a
) then b is redundant. The geometric interprek 2 k 2
tation can be used to compute if a vector b is redundant or not:
) defines
If b is not redundant, then some part of the boundary of U +1−b ( 1−b
k 2 k 2
S +
i
the boundary of the union of spheres i U 1−ai ( 1−a
). The boundary of the
k 2 k 2
S +
1−ai
union of spheres i U 1−ai ( 2 ) can be described by transformed facets like
k 2 k
in Figure A.8 where the white region is touching three neighboring regions. If
it is possible to find two facets that belong to two spheres (i, j) that are neighboring to the sphere U +1−b ( 1−b
), then a hyperplane Hij exists that contains
k 2 k 2
the intersection of the boundaries of the spheres (in 3d it contains a circle).
Furthermore, if b is not redundant this hyperplane has a nonempty intersection
with the facet that corresponds to b. Therefore, a vector can be found that is on
the hyperplane and outside the union. If no such two spheres can be found then
the dominating part of the region intersects with at least one of the hyperplanes
that are defined by xi = 0.
Therefore, b is not redundant if:
S
i
U +1−b ( 1−b
)|Hij 6⊂ i U +1−ai ( 1−a
)|
or
2
k 2 k
k 2 k 2 Hij
S
i
U +1−b ( 1−b
)|
6⊂ i U +1−ai ( 1−a
)|
k 2 k 2 xi =0
k 2 k 2 xi =0
The dimension of the corresponding sub problems is n − 1, the method can
be reapplied until the dimension of all subproblems is one. Note that if b
i
is not redundant then it is possible to identify one or more spheres U +1−ai ( 1−a
)
k 2 k 2
that contain b, the set of the corresponding indices is called M , and M 6= ∅,
otherwise it is trivial that b is not redundant. Also suppose that U +1−b ( 1−b
) is
k 2 k 2
i
not fully contained in one of the U +1−ai ( 1−a
) (i ∈ M ), otherwise b is clearly
k 2 k 2
dominated. For the procedure it is not necessary to consider all possible Hij ,
it is sufficient to assume that i ∈ M . The corresponding procedure is not very
effective and the worst case time complexity is larger than O(mn ).

24

In the following, an alternative method, that is based on convex hulls is
presented:
Proposition 3. criterion for redundancy: A vector b is redundant with respect
to a set of vectors {ai }, if and only if it is contained in the convex hull h{ai }i.
Proof. the negation redundancy is the following:

∃x ≥ 0

∀i :

hb, xi > hai , xi

∃x ≥ 0

∀i :

hb − ai , xi > 0

(A.1)

According to Gale [7] (Theorem 2.10, p. 49, which is a corollary of Farkas’
Lemma) the corresponding elimination criterion has the form:

∃λ ≥ 0(λ 6= 0)
It is also possible to assume that

∃λi > 0

P

i6=j

P

i6=j

b≤

λi (b − ai ) ≤ 0

λi = 1 and therefore:

P

i6=j

λi ai

This condition states that b is contained in the convex hull of {ai }i6=j . Therefore the problem is solvable by calculating the convex hull; and according to
n
Chazelle [2], the convex hull is computable in O(m log(m) + m 2 ) time.
A further alternative that avoids the calculation of the convex hull ( see
Chazelle [2]) is presented in the following proposition. Among the presented
methods it is the most efficient one.
Proposition 4. criterion for redundancy: A vector b is redundant if and only
if the following LP is infeasible.

min

1t x
(b − ai )t x ≥ 1

∀i

(A.2)

x≥0
Proof. ⇒: A feasible solution x of the LP also satisfies (A.1) and therefore the
vector b is redundant - the objective is irrelevant.
⇒: On the other hand, b is redundant and satisfies (A.1), therefore a vector
x0 and a positive number  > 0 exist such that (b − ai )t x > . Hence, x is a
feasible solution of the LP and the proof is complete. The complexity is defined
by the complexity of linear programming algorithms. Algorithms with O(n3 L)
are known, where L is the bit length of the input data.

25

Figure A.8: A three dimensional example with four vectors, where the corresponding set of
vectors that is non-dominating is represented by the union of spheres.

cut
A
e B,
e AB}
g
Π1 :
{A, B, AB, A,
1
e B,
e C}
e
Π2 :
{A, B, C, A,
1
e
e
Π3 :
{A, B, C, AB, A, B}
1
1
(Π
+
Π
)
:
1
1
2
2

B
1
1
1
1

C

AB
1

AC

BC

1
1
2
1
2

1
2
1
2

Table A.14: minimal basic cuts and redundancy

Definition 5. Note, that a set of vectors A = {ai ∈ [0, ∞)n } is called minimal
if none of its members is redundant with respect to A \ {ai }, more precisely:
∀j∃x ≥ 0 ∀i 6= j : aj t x < ati x.
Finally, to show that not all minimal basic cuts are needed in the LP formulation, a simple example that considers three chambers is presented:
Example 6. For three chamber, Table A.14 lists three of the minimal basic cuts,
named Π1 , Π2 , Π3 . Obviously, Π3 = 21 Π1 + 12 Π2 , therefore the criterion formulated in Proposition 3 shows that Π3 is redundant with respect to {Π1 , Π2 }.

