Empowering the Configuration-IP - New PTAS Results for
Scheduling with Setups Times ∗

arXiv:1801.06460v1 [cs.DS] 19 Jan 2018

Klaus Jansen1 , Kim-Manuel Klein2 , Marten Maack1 and Malin Rau1
Department of Computer Science, University of Kiel, 24118 Kiel, Germany
Discrete Optimization Group, École polytechnique fédérale de Lausanne,1015
Lausanne, Switzerland
1
{kj,mmaa,mra}@informatik.uni-kiel.de
2
kim-manuel.klein@epfl.ch
1

2

January 22, 2018

Abstract
Integer linear programs of configurations, or configuration IPs, are a classical tool
in the design of algorithms for scheduling and packing problems, where a set of items
has to be placed in multiple target locations. Herein a configuration describes a
possible placement on one of the target locations, and the IP is used to chose suitable
configurations covering the items. Configuration IPs are especially useful for problems
in which the items and target locations are rather homogeneous, as is the case in the
classical problems of scheduling on identical machines and bin packing. However, when
considering, for instance, problems in which the items are partitioned into classes and
have some class dependent property, the configuration-IP quickly encounters its limits.
We give an augmented IP formulation, which we call the module configuration IP. This
IP cannot be solved efficiently using the classical algorithm of Lenstra and Kannan.
Instead, we show that it can be described within the framework of n-fold integer
programming and therefore be solved efficiently using the algorithm by Hemmecke,
Onn, and Romanchuk. Furthermore, we investigate how structural properties can
be applied to reduce the description of the IP and thereby speed up the resulting
algorithms. As an application, we consider scheduling problems with setup times,
in which a set of jobs has to be scheduled on a set of identical machines, with the
objective of minimizing the makespan. For instance, we investigate the case that jobs
can be split and scheduled on multiple machines. However, before a part of a job can
be processed an uninterrupted setup depending on the job has to be paid. For both
of the variants that jobs can be executed in parallel or not, we obtain an efficient
polynomial time approximation scheme (EPTAS) of running time f (1/ε) × poly(|I|)
with a single exponential term in f for the first and a double exponential one for
the second case. Previously only constant factor approximations of 5/3 and 4/3 + ε
respectively were known. Furthermore, we present an EPTAS for a problem where
classes of (non-splittable) jobs are given, and a setup has to be paid for each class of
jobs being executed on one machine.
∗

This work was partially supported by German Research Foundation (DFG) project JA 612/20-1

1

1

Introduction

In this paper, we present an augmented formulation of the classical integer linear program of configurations (configuration IP) and demonstrate its use in the design of efficient
polynomial time approximation schemes for scheduling problems with setup times. Configuration IPs are widely used in the context of scheduling or packing problems, in which
items have to be placed in multiple target locations. The configurations describe possible
placements on a single location, and the integer linear program (IP) is used to choose a
proper selection covering all items. Two fundamental problems, for which configuration
IPs have prominently been used, are bin packing and minimum makespan scheduling on
identical parallel machines, or machine scheduling for short. For bin packing, the configuration IP was introduced as early as 1961 by Gilmore and Gomory [10], and the recent
results for both problems typically use configuration IPs as a core technique, see, e.g.,
[11, 15]. In the present work, we consider scheduling problems and therefore introduce the
configuration IP in more detail using the example of machine scheduling.
Configuration IP for Machine Scheduling. In the problem of machine scheduling,
a set J of n jobs is given together with processing times pj for each job j and a number m of identical machines. The objective is to find a schedule σ : J → [m], such
that the makespan is minimized, that is, the latest finishing time of any job Cmax (σ) =
P
maxi∈[m] j∈σ−1 (i) pj . For a given makespan bound, the configurations may be defined as
multiplicity vectors indexed by the occurring processing times, where the overall length of
the chosen processing times does not violate the bound. The configuration IP is then given
by variables xC for each configuration C; constraints ensuring that there is a machine for
P
each configuration, i.e., C xC = m; and further constraints due to which the jobs are
P
covered, i.e., C Cp xC = |{j ∈ J | pj = p}| for each processing time p. In combination
with certain simplification techniques, this type of IP is often used in the design of polynomial time approximation schemes (PTAS). A PTAS is a procedure that, for any fixed
accuracy parameter ε > 0, returns a solution with approximation guarantee (1 + ε) that
is, a solution, whose objective value lies within a factor of (1 + ε) of the optimum. In the
context of machine scheduling, the aforementioned simplification techniques can be used
to guess the target makespan T of the given instance; to upper bound the cardinality of
the set of processing times P by a constant (depending in 1/ε); and to lower bound the
processing times in size, such that they are within a constant factor of the makespan T
(see, e.g., [3, 15]). Hence, only a constant number of configurations is needed, yielding
an integer program with a constant number of variables. Integer programs of that kind
can be efficiently solved using the classical algorithm by Lenstra and Kannan [19, 17],
yielding a PTAS for machine scheduling. Here, the error of (1 + ε) in the quality of the
solution is due to the simplification steps, and the scheme has a running time of the form
f (1/ε) × poly(|I|), where |I| denotes the input size, and f some computable function. A
PTAS with this property is called efficient (EPTAS). Note that for a regular PTAS a
running time of the form |I|f (1/ǫ) is allowed. It is well known, that machine scheduling
is strongly NP-hard, and therefore there is no optimal polynomial time algorithm, unless
P=NP, and also a so-called fully polynomial PTAS (FPTAS)—which is an EPTAS with a
polynomial function f —cannot be hoped for.

2

Machine Scheduling with Classes. The configuration IP is used in a wide variety of
approximation schemes for machine scheduling problems [3, 15]. However, the approach often ceases to work for scheduling problems in which the jobs have to fulfill some additional
requirements, like, for instance, class dependencies. A problem emerging, in this case, is
that the additional requirements have to be represented in the configurations, resulting
in a super-constant number of variables in the IP. We elaborate on this using a concrete
example: Consider the variant of machine scheduling in which the jobs are partitioned
into K setup classes. For each job j a class kj is given and for each class k a setup time
sk has to be paid on a machine, if a job belonging to that class is scheduled on it, i.e.,
P
P
Cmax (σ) = maxi∈[m]
k∈{kj | j∈σ−1(i)} sk . With some effort, simplification
j∈σ−1 (i) pj +
steps similar to the ones for machine scheduling can be applied. In the course of this, the
setup times as well can be bounded in number and guaranteed to be sufficiently big [16].
However, it is not hard to see that the configuration IP still cannot be trivially extended,
while preserving its solvability. For instance, extending the configurations with multiplicities of setup times will not work, because then we have to make sure that a configuration
is used for a fitting subset of classes, creating the need to encode class information into
the configurations or introduce other class dependent variables.
Module Configuration IP. Our approach to deal with the class dependencies of the
jobs is to cover the job classes with so-called modules and cover the modules in turn with
configurations in an augmented IP called the module configuration IP (MCIP). In the
setup class model, for instance, the modules may be defined as combinations of setup times
and configurations of processing times, and the actual configurations as multiplicity vectors
of module sizes. The number of both the modules and the configurations will typically be
bounded by a constant. To cover the classes by modules each class is provided with its
own set of modules, that is, there are variables for each pair of class and module. Since
the number of classes is part of the input, the number of variables in the resulting MCIP
is super-constant, and therefore the algorithm by Lenstra and Kannan [19, 17] is not the
proper tool for the solving of the MCIP. However, the MCIP has a certain simple structure:
The mentioned variables are partitioned into uniform classes each corresponding to the
set of modules, and for each class, the modules have to do essentially the same—cover the
jobs of the class. Utilizing these properties, we can formulate the MCIP in the framework
of n-fold integer programms—a class of IPs with variable dimensions, whose variables and
constraints fulfill certain uniformity requirements, and which can be efficiently solved via
the algorithm by Hemmecke, Onn, and Romanchuk [12]. For a detailed description of the
MCIP, the reader is referred to Section 3.
Using the MCIP, we are able to formulate an EPTAS for machine scheduling in the
setup class model described above. Before, only a regular PTAS with running time
5
nmO(1/ε ) was known [16]. To the best of our knowledge, this is the first use of n-fold
integer programing in the context of approximation algorithms.
Results and Methodology. To show the conceptual power of the MCIP, we utilize
it for two more problems: The splittable and the preemptive setup model of machine
scheduling. In both variants for each job j, a setup time sj is given. Each job may be
partitioned into multiple parts that can be assigned to different machines, but before any
part of the job can be processed the setup time has to be paid. In the splittable model,
3

constant
configurations
x0 x1 x2 x3 x4 x5
s.c. mult.

x0 x1 x2 x3 x4 x5

constant
module
sizes/c.
modules
per class

...

...

...

s.c. classes
with
c. sizes

constant
sizes
s.c. mult.

constant
configurations

p0 p1 p2 p3 p4 p5

s.c. mult.

...

...
p00

p01

p02

p03

p04

p05

p10

p11

p12

p13

p14

p15

p20

p21

p22

p23

p24

p25

Figure 1: On the left, there is a schematic representation of the configuration IP. There
are constant different sizes each occurring a super-constant number of times. The sizes are
directly mapped to configurations. On the right, there is a schematic representation of the
MCIP. There is a super-constant number of classes, each containing a constant number of
sizes which have super-constant multiplicities. The elements from the class are mapped
to a constant number of different modules, which have a constant number of sizes. These
module sizes are mapped to configurations.
job parts belonging to the same job can be processed in parallel, and therefore beside the
partition of the jobs, it suffices to find an assignment of the job parts to machines. This
is not the case for the preemptive model, in which additionally a starting time for each
job part has to be found, and two parts of the same job may not be processed in parallel.
In 1999 Schuurman and Woeginger [24] presented a polynomial time algorithm for the
preemptive model with approximation guarantee 4/3 + ε, and for the splittable case a
guarantee of 5/3 was achieved by Chen, Ye and Zhang [5]. These are the best known
approximation guarantees for the problems at hand. We show that solutions arbitrarily
close to the optimum can be found in polynomial time:
Theorem 1. There is an efficient PTAS with running time 2f (1/ε) poly(|I|) for minimum
makespan scheduling on identical parallel machines in the setup-class model, as well as in
the preemptive and splittable setup models.
The f (1/ε) part of the running time has the form poly(1/ε) in the splittable, 2polylog(1/ε)
in the setup class, and 2poly(1/ε) in the preemptive model. For more precise estimations
of the running time, we refer to the respective sections. Note, that all three problems are
strongly NP-hard, due to trivial reductions from machine scheduling.
For all three EPTAS results we employ the classical dual approximation framework
by Hochbaum and Shmoys [13] to get a guess of the makespan T . This approach is
introduced in Section 2 together with n-fold IPs and formal definitions of the problems.
In the following section, we develop the module configuration IP, in its basic form and
discuss how its description size can be reduced via a result by Eisenbrandt and Shmonin
concerning integer cones [9]. The EPTAS results follow the same basic approach described
4

above for machine scheduling: We find a schedule for a simplified instance via the MCIP
and transform it into a schedule for the original one. The simplification steps typically
include rounding of the processing and setup times using standard techniques, as well as,
the removal of certain jobs, which later can be reinserted via carefully selected greedy
procedures. For the splittable and preemptive model, we additionally have to prove that
schedules with a certain simple structure exist, and in the preemptive model, the MCIP has
to be extended. In Section 4 the basic versions of the EPTAS are presented and in the last
section, some non-trivial improvements of the running time for the splittable and the setup
class model are discussed. For the former, we develop an improved rounding and deal with
a problem that is derived from the fact that in the splittable case the number of machines
can be super-polynomial in the input size. For the latter, we reduce the number of module
variables using structural results for the configuration IP in the machine scheduling case
[15], and ideas developed by Goemans and Rothvoß in the context of bin packing [11].
While the main result of this work is the development of the module configuration
IP and its application to the problems at hand, we would like to emphasize two other
achievements: On the one hand, we present techniques on how novel structural insights
of the configuration IP can be applied to the MCIP to reduce the size of its description
remarkably. This results in a severe speedup in all three of the considered problems. On
the other hand, the simplification steps we developed to make the MCIP applicable in the
preemptive model, are non-trivial and interesting by themselves. We conclude the section
with a review of related results.
Related work. For an overview on n-fold IPs and their applications, we refer to the
book by Onn [22]. There have been recent applications of n-fold integer programming to
scheduling problems in the context of parameterized algorithms: Knop and Kouteckỳ [18]
showed, among other things, that the problem of makespan minimization on unrelated
parallel machines, where the processing times are dependent on both jobs and machines,
is fixed-parameter tractable with respect to the maximum processing time and the number
of distinct machine types. This was generalized to the parameters maximum processing
time and rank of the processing time matrix by Chen et al. [6].
There is extensive literature concerning scheduling problems with setup times. We
highlight a few closely related results and otherwise refer to the surveys [1, 2]. In the
following, we use the term α-approximation as an abbreviation for polynomial time algorithms with approximation guarantee α. The setup class model was first considered by
Mäcker et al. [20] in the special case that all classes have the same setup time. They
designed a 2-approximation and additionally a 3/2 + ε-approximation for the case that
the overall length of the jobs from each class is bounded. Jansen and Land [16] presented
a simple 3-approximation with linear running time, a 2 + ε-approximation, and the aforementioned PTAS for the general setup class model. As indicated before, Chen et al. [5]
developed a 5/3-approximation for the splittable model. A generalization of this, in which
both setup and processing times are job and machine dependent, has been considered by
Correa et al. [7]. They achieve a (1 + φ)-approximation, where φ denotes the golden
ratio, using a newly designed linear programming formulation. Moreover, there are recent
results concerning machine scheduling in the splittable model considering the sum of the
(weighted) completion times as the objective function, e.g. [23, 8]. For the preemptive
model, a PTAS for the special case that all jobs have the same setup time has been de5

veloped by Schuurman and Woeginger [24]. The mentioned (4/3 + ε)-approximation for
the general case [24] follows the same approach. Furthermore, a combination of the setup
class and the preemptive model has been considered, in which the jobs are scheduled
preemptively, but the setup times are class dependent. Monma and Potts [21] presented,
among other things, a (2 − 1/(⌊m/2⌋ + 1))-approximation for this model, and later Chen
[4] achieved improvements for some special cases.

2

Preliminaries

In the following, we establish some concepts and notations, formally define the considered
problems, and outline the dual approximation approach by Hochbaum and Shmoys [13],
as well as n-fold integer programs.
For any integer n, we denote the set {1, . . . , n} by [n]; we write log(·) for the logarithm
with basis 2; and we will usually assume that some instance I of the problem considered
in the respective context is given together with an accuracy parameter ε ∈ (0, 1) such that
1/ε is an integer.
Problems. For all three of the considered models, a set J of n jobs with processing times
pj ∈ Q>0 for each job j ∈ J and a number of machines m is given. In the preemptive and
the splittable model, the input additionally includes a setup time sj ∈ Q>0 for each job
j ∈ J ; while in the setup class model, it includes a number K of setup classes, a setup
class kj ∈ [K] for each job j ∈ J , as well as setup times sk ∈ Q>0 for each k ∈ [K].
We take a closer look at the definition of a schedule in the preemptive model. The
jobs may be split. Therefore, partition sizes κ : J → Z>0 , together with processing time
P
fractions λj : [κ(j)] → (0, 1], such that k∈[κ(j)] λj (k) = 1, have to be found, meaning
that job j is split into κ(j) many parts and the k-th part for k ∈ [κ(j)] has processing
time λj (k)pj . This given, we define J ′ = {(j, k) | j ∈ J , k ∈ [κ(j)]} to be the set of job
parts. Now, an assignment σ : J ′ → [m] along with starting times ξ : J ′ → Q>0 has to
be determined, such that any two job parts assigned to the same machine or belonging to
the same job do not overlap. More precisely, we have to assure that for each two job parts
(j, k), (j ′ , k′ ) ∈ J ′ with σ(j, k) = σ(j ′ , k′ ) or j = j ′ , we have ξ(j, k)+ sj + λj (k)pj ≤ ξ(j ′ ) or
ξ(j ′ , k′ )+ sj ′ + λj ′ (k)pj ′ ≤ ξ(j). A schedule is given by (κ, λ, σ, ξ) and the makespan can be
defined as Cmax = max(j,k)∈J ′ (ξ(j, k)+ sj + λj (k)pj ). Note that the variant of the problem
in which overlap between a job part and setup of the same job is allowed is equivalent to
the one presented above. This was pointed out by Schuurmann and Woeginger [24] and
can be seen with a simple swapping argument.
In the splittable model, it is not necessary to determine starting times for the job parts,
because, given the assignment σ, the job parts assigned to each machine can be scheduled
as soon as possible in arbitrary order without gaps. Hence, in this case, the output is of
P
the form (κ, λ, σ) and the makespan can be defined as Cmax = maxi∈[m] (j,k)∈σ−1 (i) sj +
λj (k)pj .
Lastly, in the setup class model the jobs are not split and given an assignment, the jobs
assigned to each machine can be scheduled in batches comprised of the jobs of the same
class assigned to the machine without overlaps and gaps. The output is therefore just an
P
assignment σ : J → [m] and the makespan is given by Cmax = maxi∈[m] j∈σ−1 (i) pj +
6

P

k∈{kj | j∈σ−1(i)} sk .

Note, that in the preemptive and the setup class model, we can assume that the
number of machines is bounded by the number of jobs: If there are more machines than
jobs, placing each job on a private machine yields an optimal schedule in both models and
the remaining machines can be ignored. This, however, is not the case in the splittable
model, which causes a minor problem in the following.
Dual Approximation. All of the presented algorithms follow the dual approximation
framework introduced by Hochbaum and Shmoys [13]: Instead of solving the minimization
version of a problem directly, it suffices to find a procedure that for a given bound T on the
objective value either correctly reports that there is no solution with value T or returns a
solution with value at most (1 + aε)T for some constant a. If we have some initial upper
bound B for the optimal makespan OPT with B ≤ bOPT for some b, we can define a
PTAS by trying different values T from the interval [B/b, B] in a binary search fashion,
and find a value T ∗ ≤ (1 + O(ε))OPT after O(log b/ε) iterations. Note that for all of the
considered problems constant approximation algorithms are known, and the sum of all
processing and setup times is a trivial m-approximation. Hence, we always assume that
a target makespan T is given. Furthermore, we assume that the setup times and in the
preemptive and setup class cases also the processing times are bounded by T , because
otherwise we can reject T immediately.
n-fold Integer Programs. We briefly define n-fold integer programs (IP) following the
notation of [12] and [18] and state the main algorithmic result needed in the following.
Let n, r, s, t ∈ Z>0 be integers and A be an integer ((r + ns) × nt)-matrix of the following
form:


A1 A1 · · · A1
A

 2 0 ··· 0 


0 A2 · · · 0 
A=

.. . .
. 
 ..

. .. 
 .
.
0

0

· · · A2

1
The matrix A is the so-called n-fold product of the bimatrix A
A2 , with A1 an r × t and
nt
r+ns
A2 an s × t matrix. Furthermore, let w, ℓ, u ∈ Z and b ∈ Z
. Then the n-fold integer
programming problem is given by:



min{wx | Ax = b, ℓ ≤ x ≤ u, x ∈ Znt }
Hemmecke, Onn and Romanchuk [12] showed that:
Theorem 2. Let ∆ be a bound on the absolute values occurring in A, and L the encoding
length of w, b, ℓ, u and ∆. The n-fold integer programming problem can be solved in time
O(∆3t(rs+st+r+s) Ln3 ).
The variables x can naturally be partitioned into bricks x(q) of dimension t for each q ∈
[n], such that x = (x(1) , . . . x(n) ). Furthermore, we denote the constraints corresponding
to A1 as globally uniform and the ones corresponding to A2 as locally uniform. Hence, r
is the number of globally and s the number of locally uniform constraints (ignoring their
n-fold duplication); t the brick size and n the brick number.
7

3

Module Configuration IP

In this section, we state the configuration IP for machine scheduling; introduce a basic
version of the module configuration IP (MCIP) that is already sufficiently general to work
for both the splittable and setup class model; discuss how a structural result by Eisenbrand
and Shmonin [9] can be employed to reduce the number of configuration variables; and
lastly show that the configuration IP can be expressed by the MCIP in multiple ways.
Before that, however, we formally introduce the concept of configurations.
Given a set of objects A, a configuration C of these objects is a vector of multiplicities
indexed by the objects, i.e., C ∈ ZA
given sizes Λ(a) of the objects a ∈ A, the size
≥0 . For
P
Λ(C) of a configuration C is defined as a∈A Ca Λ(a). Moreover, for a given bound B, we
define CA (B) to be the set of configurations of A that are bounded in size by B, that is,
CA (B) = {C ∈ ZA
≥0 | Λ(C) ≤ B}.
Configuration IP. We give a recollection of the configuration IP for scheduling on
identical parallel machines. Let P be the set of distinct processing times for some instance
I with multiplicities np for each p ∈ P , meaning, I includes exactly np jobs with processing
time p. The size Λ(p) of a processing time p is given by itself. Furthermore, let T be a
guess of the optimal makespan. The configuration IP for I and T is given by variables
xC ≥ 0 for each C ∈ CP (T ) and the following constraints:
X

xC = m

(1)

C∈CP (T )

X

Cp xC = np

∀p ∈ P

(2)

C∈CP (T )

Due to constraint (1), exactly one configuration is chosen for each machine, while (2)
ensures that the correct number of jobs or job sizes is covered.
Module Configuration IP. Let B be a set of basic objects (e.g. jobs or setup classes)
and let there be D integer values B1 , . . . , BD for each basic object B ∈ B (e.g. processing
time or numbers of different kinds of jobs). Our approach is to cover the basic objects
with so-called modules and in turn cover the modules with configurations. Depending on
the context, modules correspond to batches of jobs or job piece sizes together with a setup
time and can also encompass additional information like a starting time. Let M be a set of
such modules. In order to cover the basic objects, each module M ∈ M also has D integer
values M1 , . . . , MD . Furthermore, each module M has a size Λ(M ) and a set of eligible
basic objects B(M ). The latter is needed because not all modules are compatible with all
basic objects, e.g., because they do not have the right setup times. The configurations are
used to cover the modules, however, it typically does not matter which module exactly
is covered, but rather which size the module has, or, in the preemptive case, also which
starting time it has. Therefore, there is a partition of the modules Γ into groups G ∈ Γ
given. The modules belonging to a set G ∈ Γ have all the same size, i.e., Λ(M ) = Λ(M ′ )
for M, M ′ ∈ G, and the size of G is defined as the size of any contained module, i.e.
Λ(G) = Λ(M ) with M ∈ G. We consider a set of C of configurations of the module groups
Γ which are bounded in size by a guess of the makespan T in the considered problems,
i.e., C ⊆ CΓ (T ).
8

Since we want to chose configurations for each machine, we have variables xC for each
C ∈ C and constraints corresponding to (1). Furthermore, we chose modules with variables
yM for each M ∈ M and because we want to cover the chosen modules with configurations,
P
P
we have some analogue of constraint (2), say C∈C(T ) CG xC = M ∈G yM for each group
of modules G ∈ Γ. It turns out however, that to properly cover the basic objects with
modules, we need the variables yM for each basic object, and this is were n-fold IPs come
into play: The variables stated so far form a brick of the variables of the n-fold IP and
(B)
there is one brick for each basic object, that is, we have, for each B ∈ B, variables xC
(B)
for each C ∈ C, and yM for each M ∈ M. Using the upper bounds of the n-fold model,
(B)
variables yM are set to zero, if B is not eligible for M ; and we set the lower bounds of
all variables to zero. Sensible upper bounds for the remaining variables, will be typically
clear from context. Besides that, the module configuration integer program MCIP (for B,
M, Γ and C) is given by:
X X

(B)

xC = m

(3)

B∈B C∈C

X

(B)

X

CG xC =

X

Md yM = Bd

B∈B C∈C(T )

X X

(B)

yM

∀G ∈ Γ

(4)

∀B ∈ B, d ∈ [D]

(5)

B∈B M ∈G
(B)

M ∈M

It is easy to see that the constraints (3) and (4) are globally uniform. They are the
mentioned adaptations of (1) and (2). The constraint (5), on the other hand, is locally
uniform and ensures that the basic objects are covered.
Note that, while the duplication of the configuration variables does not carry meaning,
it also does not upset the model: Consider the modified MCIP that is given by not
duplicating the configuration variables. A solution (x̃, ỹ) for this IP gives a solution (x, y)
(B ∗ )
for the MCIP by fixing some basic object B ∗ , setting xC = x̃C for each configuration
C, setting the remaining configuration variables to 0, and copying the remaining variables.
Given a solution (x, y) for the MCIP, on the other hand, gives a solution for the modified
P
version (x̃, ỹ) by setting x̃C = B∈B xB
C for each configuration C.
Summarizing we get:
Remark 3. The MCIP is an n-fold IP with brick-size t = |M| + |C|, brick number n = |B|,
r = |Γ| + 1 globally uniform and s = D locally uniform constraints.
Moreover, in all the considered applications we will minimize the overall size of the
P
P
(B)
configurations, i.e., B∈B C∈C Λ(C)xC . This will be required, because in the simplification steps of our algorithms some jobs are removed and have to be reinserted later, and
we therefore have to make sure that no space is wasted.
Reduced Running Time. For the configuration IP, the number of distinct configurations is usually rather large (exponential in 1/ε), but it can be shown that there is a
solution that uses only few variables (polynomial in 1/ε) [14] via a result by Eisenbrandt
and Shmonin concerning integer cones [9]. Using this, the time it takes to find a feasible
solution can be drastically reduced by guessing the needed variables. If the set of modules

9

is rather small and the set of configurations is rather big, a similar strategy is worthwhile
for the MCIP. The result by Eisenbrandt and Shmonin is the following:
Theorem 4. Let b be an integral conical combination of a finite set of integer vectors
P
X ⊂ Zd , i.e., b ∈ { x∈X λx x | λx ∈ Z≥0 }. There is a subset X̃ ⊆ X bounded in size by
2d log(4d∆), where ∆ is the maximum value occurring in any of the vectors x ∈ X, such
that b is an integer conical combination of X̃.
(B) 

Given a solution (x, y) of the MCIP, we set b′ =
B∈B
M ∈G yM G∈Γ . It is easy
m
to see, that b = b′ is an integer conical combination of the extended configurations
P

(B)

P

C ′ = { C1 | C ∈ C} with multiplicities λC ′ = B∈B xC , with C ′ = C1 . Furthermore,
any other integer conical combination (λ′C ′ )C ′ ∈C ′ of b induces a feasible solution (z, y)
of the MCIP with the same objective value by fixing a basic object B ∈ B and setting
(B)
zC = λ′C ′ . Hence, there is a solution to the MCIP using at most 2|Γ| log(4|Γ| max C,G CG )
distinct configurations. If the remaining configuration variables are removed from this
solution, the brick size is bounded by |M| + 2|Γ| log(4|Γ| max C,G CG ).


P



First Example. We conclude the section by pointing out several different ways to replace the classical configuration IP for scheduling on identical machines with the MCIP,
thereby giving some intuition for the model. The first possibility is to consider the jobs
as the basic objects and their processing times as their single value (B = J , D = 1);
the modules are the processing times (M = P ), and a job is eligible for a module, if
its processing time matches; the partition into groups is the trivial partition into single
elements; and the configurations are all the configurations bounded in size by T . Another
option is to chose the processing times as basic objects, keeping all the other definitions
essentially like before. Lastly, we could consider the whole set of jobs or the whole set of
processing times as a single basic object with D = |P | different values. In this case, we
can define the set of modules as the set of configurations of processing times bounded by
T , and partition the modules by size into groups.

4

EPTAS results

In this section, we present approximation schemes for each of the three considered problems. Each of the results follows the same approach: The instance is carefully simplified,
a schedule for the simplified instance is found using the MCIP, and this schedule is transformed into a schedule for the original instance. For each problem, we first discuss how the
instance can be sensibly simplified, and how a schedule for the simplified instance can be
transformed into a schedule for the original one. Next, we discuss how a schedule for the
simplified instance can be found using the MCIP, and lastly, we summarize and analyze
the taken steps.
For the sake of clarity, we have given rather formal definitions for the problems at hand
in Section 2. In the following, however, we will use the terms in a more intuitive fashion
for the most part, and we will, for instance, often take a geometric rather than a temporal
view on schedules and talk about the length or the space taken up by jobs and setups on
machines rather than time. In particular, given a schedule for an instance of any one of
the three problems together with an upper bound for the makespan T , the free space with
10

respect to T on a machine is defined as the summed up lengths of time intervals between 0
and T in which the machine is idle. The free space (with respect to T ) is the summed up
free space of all the machines. For bounds T and L for the makespan and the free space,
we say that a schedule is a (T, L)-schedule if its makespan is at most T and the free space
with respect to T is at least L.
When transforming the instance we will increase or decrease processing and setup times
and fill in or remove extra jobs. Consider a (T ′ , L′ )-schedule, where T ′ and L′ denote some
arbitrary makespan or free space bounds. If we fill in extra jobs or increase processing or
setup times, but can bound the increase on each machine by some bound b, we end up
with a (T ′ + b, L′ )-schedule for the transformed instance. In particular we have the same
bound for the free space, because we properly increased the makespan bound. If, on the
other hand, jobs are removed times decreased, we obviously still have a (T ′ , L′ )-schedule
for the transformed instance. This will be used frequently in the following.

4.1

Splittable Model

The approximation scheme for the splittable model presented in this section is the easiest
one discussed in this work and therefore presented first. There is, however, one problem
concerning this procedure: Its running time is polynomial in the number of machines,
which might be exponential in the input size. We discuss, how this problem can be
overcome in Section 5.
Simplification of the Instance. In the following, we distinguish big setup jobs j with
setup time sj ≥ εT and small setup jobs with setup time sj < εT ; and denote the
P
corresponding subsets of jobs by J bst and J sst respectively. Let L = j∈J sst (sj + pj ).
Because every job has to be scheduled and every setup has to be paid at least once, L is
a lower bound on the summed up space due to small jobs in any schedule. Let I1 be the
instance that we get by removing all the small setup jobs from the given instance I.
Lemma 5. A schedule with makespan T for I induces a (T, L)-schedule for I1 , that is, a
schedule with makespan T and free space at least L; and any (T ′ , L)-schedule for I1 can be
transformed into a schedule for I with makespan at most T ′ + εT .
Proof. The first claim is obvious. Hence, consider a sequence consisting of the jobs from
J sst together with their set up times, where the setup up time of a job is the direct
predecessor of the job. We insert the setup times and jobs from this sequence greedily
into the schedule in a next-fit fashion: Given a machine we keep inserting the items from
the sequence on the machine at the end of the schedule until the taken up space on the
machine reaches T ′ . If the current item does not fit exactly, we cut it, such that the used
space on the machine is exactly T ′ . Then we continue with the next machine. We can
place the whole sequence like this without exceeding the makespan T ′ , because we have
free space of at least L which is the summed up length of the items in the sequence. Next,
we remove each setup time that was placed only partly on a machine together witch those
that were placed at the end of the schedule, and insert a fitting setup time for the jobs
that were scheduled without one, which can happen only once for each machine. This
yields a feasible schedule, whose makespan is increased by at most εT .

11

Next, we round up the processing times of I1 to the next multiple of ε2 T , that is, for
each job j ∈ J we set p̄j = ⌈pj /(ε2 T )⌉ε2 T and s̄j = ⌈sj /(ε2 T )⌉ε2 T . We call the resulting
instance I2 , and denote its job set by J ′ .
Lemma 6. If there is a (T, L′ )-schedule for I1 , there is also a ((1 + 2ε)T, L′ )-schedule for
I2 in which the length of each job part is a multiple of ε2 T , and any (T ′ , L′ )-schedule for
I2 yields a (T ′ , L′ )-schedule for I1 .
Proof. Consider a (T, L)-schedule for I1 . There are at most 1/ε jobs scheduled on each
machine, since each setup time has a length of at least εT . On each machine, we extend
each occurring setup time and the processing time of each occurring job part by at most
ε2 T to round it to a multiple of ε2 T . This step extends the makespan by at most 2εT .
Since now each job part is a multiple of ε2 T , the total processing time of the job is a
multiple of ε2 T too.
In the last step, we check for each job j ∈ J bst if the total processing time is now
larger than the smallest multiple of ε2 T , which is larger than its original processing time.
If this is the case, we discard the spare processing time. Lastly, there is at least as much
free space in the resulting schedule as in the original one, because we properly increased
the makespan bound. The second claim is obvious.
Based on the two Lemmata, we define two makespan bounds T̄ = (1 + 2ε)T and
T̆ = T̄ + εT = (1 + 3ε)T . We will use the MCIP to find a (T̄ , L)-schedule for I2 in which
the length of each job part is a multiple of ε2 T . Using the two Lemmata, this will yield a
schedule with makespan at most T̆ for the original instance I.
Utilization of the MCIP. At this point, we can employ the module configuration IP.
The basic objects in this context are the (big setup) jobs, i.e., B = J bst = J ′ , and they
have only one value (D = 1), namely, their processing time. Moreover, the modules are
defined as the set of pairs of job piece sizes and setup times, i.e., M = (q, s) s, q ∈
{xε2 T | x ∈ Z, 0 < x ≤ 1/ε2 }, s ≥ εT , and we write sM = s and qM = q for each
module M = (q, s) ∈ M. Corresponding to the value of the basic objects the value of a
module M is qM , and its size Λ(M ) is given by qM + sM . A job is eligible for a module,
if the setup times fit, i.e., BM = {j ∈ J ′ | sj = sM }. We group the modules by size, i.e.,
Γ = {G ⊆ M | M, M ′ ∈ G ⇒ Λ(M ) = Λ(M ′ )}. In order to ensure integral values, we
establish ε2 T = 1 via a simple scaling step. Furthermore, the configurations C are all
the configurations of Γ that are bounded in size by T̄ , i.e., C = CM (T̄ ). For the sake of
readability, we state the constraints of the MCIP for the above definitions with adapted
notation and without duplication of the configuration variables:
X

xC = m

(6)

C∈C

X

CG xC =

(j)

yM

∀G ∈ Γ

(7)

∀j ∈ J ′

(8)

j∈J ′ M ∈G

C∈C

X

X X

(j)

q M y M = pj

M ∈M

Note that we additionally minimize the summed up size of the configurations, via the
P
objective function C Λ(C)xC .
12

Lemma 7. With the above definitions, there is a (T̄ , L)-schedule for I¯ in which the length
of each job piece is a multiple of ε2 T , iff MCIP has a solution with objective value at most
mT̄ − L.
¯ the schedule on each machine corresponds to exactly
Proof. Given such a schedule for I,
one configuration G that can be derived by counting the job pieces and setup times with
the same summed up length a and setting CG accordingly, where G is the group of modules
with length a. The size of the configuration C is equal to the used space on the respective
(j)
machine. Therefore, we can fix some arbitrary job j and set the variables xC to the
′
(j )
number of machines whose schedule corresponds to C (and xC = 0 for j ′ 6= j and C ∈ C).
Since there is at least a free space of L for the schedule, the objective value is bounded
by mT̄ − L. Furthermore, for each job j and job part length q, we count the number of
(j)
times a piece of j with length q is scheduled and set y(q,sj ) accordingly. It is easy to see
that the constraints are satisfied.
Now, let (x, y) be a solution to the MCIP with objective value at most mT̄ − L. We
(j)
use the solution to construct a schedule: For job j and configuration C we reserve xC
machines. On each of these machines we create CG slots of length Λ(G), for each G ∈ Γ
Note that because of (6) there is the exact right number of machines for this. Next,
(j)
consider each job j and possible job part length q and create y(q,sj ) split pieces of length
q and place them together with a setup of sj into a slot of length sj + q on any machine.
Because of (8) the entire job is split up by this, and because of (7) there are enough slots
for all the job pieces. Note that the used space in the created schedule is equal to the
objective value of (x, y) and therefore there is at least L free space.
Result. Summing up, we can find a schedule of length at most (1 + 3ε)T or correctly
determine that there is no schedule of length T with the following procedure:
Algorithm 8.
1. Generate the modified instance I2 :
⊲ Remove the small setup jobs.
⊲ Round the setup and processing times of the remaining jobs.
2. Build and solve the MCIP for this case.
3. If the IP is infeasible, or the objective value greater than mT̄ − L, report that I has no
solution with makespan T .
¯
4. Otherwise build the schedule with makespan T̄ and free space at least L for I.
5. Transform the schedule into a schedule for I with makespan at most T̆ :
⊲ Use the original processing and setup times.
⊲ Greedily insert the small setup jobs.
To assess the running time of the procedure, we mainly need to bound the parameters
of the MCIP, namely |B|, |Γ|, |M|, |C| and D. By definition, we have |B| = |J ′ | ≤ n and
D = 1. Since all setup times and job piece lengths are multiples of ε2 T and bounded
by T , we have |M| = O(1/ε4 ) and |Γ| = O(1/ε2 ). This yields |C| ≤ |Γ|(1/ε+2) =
2O(1/ε log 1/ε) , because the size of each module is at least εT and the size of the configurations bounded by (1 + 2ε)T . By Theorem 4, there is a solution that uses at most
13

2|Γ| log(4|Γ| max C,G CG ) = O(log(1/ε)/ε2 ) many configurations. These can be deter2
3
mined in 2O(1/ε log 1/ε) guessing steps. According to Remark 3 and Theorem 4 we now
have brick-size t = |M| + 2|Γ| log(4|Γ| max C,G CG ) = O(1/ε4 ), brick number |B| = n,
r = |Γ| + 1 = O(1/ε2 ) globally uniform and s = D = 1 locally uniform constraints. Because of the scaling step, all occurring numbers in the constraint matrix of the MCIP
are bounded by 1/ε2 and therefore ∆ ≤ 1/ε2 . The last step is to bound the encoding
length L of the objective function, the right hand side, and the lower and upper bounds
on the variables. Each of the entries of these vectors is lower bounded by 0 and upper bounded by O(m/ε2 ). Taking into account the dimension of the vectors, we get
L = O(nt log(m/ε2 )) = O((n log(m/ε2 ))/ε4 ). Hence the MCIP, including the guessing
step for the configurations, can be solved in time:
3

2O( /ε
1

log2 1/ε)

8

O(∆3t(rs+st+r+s) Ln3 ) = 2O( /ε
1

log2 1/ε) 4

n log m

While the first step of the procedure is obviously dominated by the above, this is not
the case for the remaining ones. In particular, building the schedule from the IP solution
costs O((n + m)/ε2 ), if the procedure described in the proof of Lemma 7 is realized in a
straight-forward fashion. The last step of the algorithm is dominated by this, yielding the
running time stated in the Theorem below. Note that the number of machines m could be
exponential in the number of jobs, and therefore the described procedure is a PTAS only
for the special case of m = poly(n). However, this limitation can easily be overcome, as
we discuss in Section 5. In the same section, we additionally present a better but slightly
more complicated rounding procedure.
Theorem 9. The algorithm for the splittable model finds a schedule with makespan at
most (1 + 3ε)T or correctly determines that there is no schedule with makespan T in time
2
8
2O(1/ε log 1/ε) n4 m.

4.2

Setup Class Model

In the setup class model, we can essentially reuse the simplification steps that were developed by Jansen and Land [16] for their PTAS. The main difference between the two
procedures is that we solve the simplified instance via the MCIP, while they used a dynamic program. For the sake of self-containment, we include our own simplification steps,
but remark that they are strongly inspired by those from [16].
Simplification of the Instance. In this context the set of big setup jobs J bst is given
by the jobs belonging to classes with setup times at least ε3 T and the small setup jobs
J sst are all the others. Furthermore, we call a job tiny or small, if its processing time is
smaller than ε4 T or εT respectively, and big or large otherwise. For any given set of jobs
J, we denote the subset of tiny jobs from J with Jtiny and the small, big and large jobs
analogously. We simplify the instance in four steps, aiming for an instance that exclusively
includes big jobs with big setup times and additionally only a constant number of distinct
processing and setup times. For technical reason we assume ε ≤ 1/12.
We proceed with the first simplification step. Let I1 be the instance given by the
sst
sst , i.e.,
job set J \ Jsmall
and Q the set of setup classes completely contained in Jsmall
sst
Q = {k | ∀j ∈ J : kj = k ⇒ j ∈ Jsmall}. An obvious lower bound on the space taken up
14

sst in any schedule is given by L =
by the jobs from Jsmall
sst
pj +
j∈Jsmall
′
the instance I1 may include a reduced number K of setup classes.

P

P

k∈Q sk .

Note that

Lemma 10. A schedule for I with makespan T induces a (T, L)-schedule for I1 , and any
(T ′ , L)-schedule for I1 can be transformed into a schedule for I with makespan at most
(1 + ε)T ′ + 2ε3 T .
Proof. The first claim is obvious and we therefore assume that we have a (T ′ , L)-schedule
sst by setup classes and first consider the groups with
for I1 . We group the jobs from Jsmall
summed up processing time at most ε2 T . For each of these groups we check whether the
respective setup class contains a large job. If this is the case, we schedule the complete
group on a machine on which such a large job is already scheduled if possible using up
free space. Since the large jobs have a length of at least εT , there are at most T ′ /(εT )
many large jobs on each machine and therefore the schedule on the respective machine
has length at most (1 + ε)T ′ or there is free space with respect to T ′ left. If, on the other
hand, the respective class does not contain a large job and is therefore fully contained in
sst , we create a container including the whole class and its setup time. Note that the
Jsmall
overall length of the container is at most (ε2 + ε3 )T ≤ εT (using ε ≤ 1/12). Next, we
create a sequence containing the containers and the remaining jobs ordered by setup class.
We insert the items from this sequence greedily into the remaining free space in a next-fit
fashion, exceeding T ′ on each machine by at most one item from the sequence. This can
be done because we had a free space of at least L and the inserted objects had an overall
length of at most L. To make the resulting schedule feasible, we have to insert some setup
times. However, because the overall length of the jobs from each class in need of a setup
is at least ε2 T and the sequence was ordered by classes, there are at most T ′ /(ε2 T ) + 2
distinct classes without a setup time on each machine. Inserting the missing setup times
will therefore increase the makespan by at most (T ′ /(ε2 T ) + 2)ε3 T = εT ′ + 2ε3 T .
sst . Let I
Next, we deal with the remaining (large) jobs with small setup times j ∈ Jlarge
2
be the instance we get by increasing the setup times of the classes with small setup times
to ε3 T . We denote the setup time of class k ∈ [K ′ ] for I2 by s′k . Note that there are no
small setup jobs in I2 .

Lemma 11. A (T ′ , L′ )-schedule I1 induces a ((1+ε2 )T ′ , L′ )-schedule for I2 , and a (T ′ , L′ )schedule for I2 is also a (T ′ , L′ )-schedule for I1 .
Proof. The first claim is true because in a schedule with makespan at most T there can
be at most T ′ /(εT ) many large jobs on any machine, and the second claim is obvious.
bst with placeholders of size
Let I3 be the instance we get by replacing the jobs from Jtiny
P
More precisely, for each class k ∈ [K] we introduce ⌈( j∈J bst ,kj =k pj )/(ε4 T )⌉ many

ε4 T .

tiny

jobs with processing time ε4 T and class k. We denote the job set of I3 by J ′ and the
processing time of a job j ∈ J ′ by p′j . Note that I3 exclusively contains big jobs with big
setup times.

Lemma 12. If there is a (T ′ , L′ )-schedule for I2 , there is also a ((1 + ε)T ′ , L′ )-schedule;
and if there is a (T ′ , L′ )-schedule for I3 , there is also a ((1 + ε)T ′ , L′ )-schedule for I2 .

15

Proof. Note, that for any (T ′ , L′ )-schedule for I2 or I3 there are at most T ′ /(ε3 T ) many
distinct big setup classes scheduled on any machine. Hence, when considering such a
bst from the machines and
schedule for I2 , we can remove the tiny jobs belonging to Jtiny
instead fill in the placeholders, such that each machine for each class receives at most
as much length from that class, as was removed, rounded up to the next multiple of
ε4 T . All placeholders can be placed like this and the makespan is increased by at most
(T ′ /(ε3 T ))ε4 T = εT ′ . If, on the other hand, we consider such a schedule for I3 , we can
remove the placeholders and instead fill in the respective tiny jobs, again overfilling by at
most one job. This yields a ((1 + ε)T ′ , L′ )-schedule for I2 with the same argument.
Lastly, let I4 be the instance we get by rounding the setup and processing times of I3 to
the next multiple of ε4 T : We set p̄j = ⌈p′j /ε4 T ⌉ε4 T for each j ∈ J ′ and s̄k = ⌈s′j /ε4 T ⌉ε4 T
for each setup class k ∈ [K ′ ].
Lemma 13. A (T ′ , L′ )-schedule for I3 induces a ((1 + 2ε)T ′ , L′ )-schedule for I4 , and any
(T ′ , L′ )-schedule for I4 can be turned into a (T ′ , L′ )-schedule for I3 .
Proof. The second claim is obvious and the first one is true because there are at most
T ′ /(ε3 T ) many big setup jobs on any machine.
Based on the rounding steps, we define two makespan bounds T̄ and T̆ : Let T̄ be
the makespan bound that is obtained from T by the application of the Lemmata 10-13 in
sequence, i.e., T̄ = (1 + ε2 )(1 + ε)(1 + 2ε)T . We will find a (T̄ , L)-schedule for I4 utilizing
the MCIP and afterward apply the Lemmata 10-13 backwards, to get a schedule with
makespan T̆ = (1 + ε)2 T̄ + ε3 T . Note that T̆ = (1 + 5ε + 10ε2 + 12ε3 + 11ε4 + 7ε5 + 2ε6 )T ≤
(1 + 6ε)T , using ε ≤ 1/12 in the second step.
Let P and S be the sets of distinct occurring processing and setup times for instance
I4 . Because of the rounding and the minimum and maximum lengths of the setup and
processing times, we can bound |P | and |S| by O(1/ε4 ).
Utilization of the MCIP. The basic objects are the setup classes, i.e., B = [K ′ ], and
the different values are the numbers of jobs with a certain processing time, i.e., D = |P |.
We set nk,p to be the number of jobs from setup class k ∈ [K ′ ] with processing time
p ∈ P . The modules are used to cover the basic objects, which correspond to sets of
jobs in this context. Hence, we define the set of modules M to be the set of pairs of
configurations of processing times and setup times with a summed up size bounded by T̄ ,
i.e., M = {(C, s) | C ∈ CP (T̄ ), s ∈ S, s + Λ(C) ≤ T̄ }, and set Mp = Cp and sM = s for
each module M = (C, s) ∈ M. The values of a module M are given by the numbers Mp
P
and its size Λ(M ) by sM + p∈P Mp p. Like in the above case, a class is eligible for a
module, if the setup times fit, i.e., BM = {k ∈ [K ′ ] | sk = sM }; the groups are separated
by size, i.e., Γ = {G ⊆ M | M, M ′ ∈ G ⇒ Λ(M ) = Λ(M ′ )}; the configurations C are the
configurations of Γ that are bounded in size by T̄ , i.e., C = CΓ (T̄ ); we establish ε4 T = 1
by scaling; and we state the resulting constraints of the MCIP with adapted notation and

16

without duplication of the configuration variables:
X

xC = m

(9)

C∈C

X

CG xC =

X

(k)

yM

∀G ∈ Γ

(10)

∀k ∈ [K ′ ], p ∈ P

(11)

k∈[K ′ ] M ∈G

C∈C

X

X

(k)

Mp yM = nk,p

M ∈M

Note that the coefficients are all integral and this includes those of the objective function,
P
i.e. C Λ(C)xC ), because of the scaling step.

Lemma 14. With the above definitions, there is a (T̄ , L)-schedule for I4 , iff the MCIP
has a solution with objective value at most mT̄ − L.

Proof. Let there be a (T̄ , L)-schedule for I4 . Then the schedule on a given machine
corresponds to a distinct configuration C that can be determined by counting for each
possible group size a the batches of jobs from the same class whose length together with
the setup time adds up to an overall length of a. Note that the length of this configuration
is equal to the used up space on that machine. We fix an arbitrary setup class k and set
(k)
(k ′ )
the variables xC accordingly (and xC = 0 for k′ 6= k and C ∈ C). By this setting we
get an objective value of at most mT̄ − L because there was L free space in the schedule.
For each class k and module M , we count the number of machines on which the there
(k)
are exactly Mp jobs with processing time p from class k for each p ∈ P , and set yM
accordingly. It is easy to see that the constraints are satisfied by these definitions.
Given a solution (x, y) of the MCIP, we define a corresponding schedule: Because of
(9) we can match the machines to configurations such that each machine is matched to
exactly one configuration. If machine i is matched to C, for each group G we create CG
slots of length Λ(G) on i. Next, we divide the setup classes into batches. For each class k
(k)
and module M , we create yM batches of jobs from class k with Mp jobs with processing
time p for each p ∈ P and place the batch together with the corresponding setup time
into a fitting slot on some machine. Because of (11) and (10) all jobs can be placed by
this process. Note that the used space equals the overall size of the configurations and we
therefore have free space of at least L.
Result.

Using the above results, we can formulate and analyze the following procedure:

Algorithm 15.
1. Generate the modified instance I4 :
⊲
⊲
⊲
⊲

Remove the small jobs with small setup times.
Increase the setup times of the remaining classes with small setup times.
Replace the tiny jobs with big setup times.
Round up the resulting processing and setup times.

2. Build and solve the MCIP for I4 .
17

3. If the MCIP is infeasible, or the objective value greater than mT̄ − L, report that I has
no solution with makespan T .
4. Otherwise build the schedule with makespan T̄ and free space at least L for I4 .
5. Transform the schedule into a schedule for I with makespan at most T̆ :
⊲
⊲
⊲
⊲

Use the prerounding processing and setup times.
Replace the placeholders by the tiny jobs with big setup times.
Use the orignal setup times of the classes with small setup times.
Insert the small jobs with small setup times into the free space.

The procedure is correct due to the above results. To analyze its running time, we first
bound the parameters of the MCIP. We have |B| = K ′ ≤ K and D = |P | by definition,
3
3
and |M| = |S||P |O(1/ε ) = 2O(1/ε log 1/ε) , because |S|, |P | ∈ O(1/ε4 ). This is true, due
3
to the last rounding step, which also implies |Γ| ∈ O(1/ε4 ), yielding |C| = |Γ|O(1/ε ) =
3
3
2O(1/ε log 1/ε) . According to Remark 3, the MCIP has a brick size of t = 2O(1/ε log 1/ε) , a
brick number of K, and O(1/ε4 ) globally and locally uniform constraints. All occurring
values in the processing time matrix are bounded in T̄ , and we have T̄ = O(1/ε4 ), due to
the scaling. Furthermore, the values of the objective function, the right hand side, and
the upper and lower bounds on the variables are bounded by O(n/ε4 ), yielding a bound
3
of O((Kt log(n/ε4 )) = 2O(1/ε log 1/ε) K log n on their encoding length L. Summing up, the
MCIP can be solved in time:
O(1/ε3 log 1/ε)
K 4 log n
22
3

From the IP solution the schedule can be build in time 2O(1/ε log 1/ε) Knm, using the procedure described in the proof of Lemma 14. It is not hard to see that all the remaining
steps are dominated by the bound given in the following:
Theorem 16. The algorithm for the setup class model finds a schedule with makespan at
most (1 + 6ε)T or correctly determines that there is no schedule with makespan T in time:
O(1/ε3 log 1/ε)

22

4.3

K 4 nm

Preemptive Model

In the preemptive model we have to actually consider the time-line of the schedule on
each machine instead of just the assignment of the jobs or job pieces, and this causes
some difficulties. For instance, we will have to argue that it suffices to look for a schedule
with few possible starting points, and we will have to introduce additional constraints in
the IP in order to ensure that pieces of the same job do not overlap. Our first step, in
dealing with this extra difficulty is to introduce some concepts and notation: For a given
schedule with a makespan bound T , we call a job piece together with its setup a block, and
we call the schedule X-layered, for some value X, if each block starts at a multiple of X.
Corresponding to this, we call the time in the schedule between two directly succeeding
multiples of X a layer and the corresponding time on a single machine a slot. We number
the layers bottom to top and identify them with their number, that is, the set of layers Ξ
is given by {ℓ ∈ Z>0 | (ℓ − 1)X ≤ T }. Note that in an X-layered schedule, there is at most
one block in each slot and for each layer there can be at most one block of each job present.
Furthermore, for X-layered schedules, we slightly alter the definition of free space: We
18

solely count the space from slots that are completely free. If in such a schedule, for each
job there is at most one slot occupied by this job but not fully filled, we additionally call
the schedule layer-compliant.
Simplification of the Instance
In the preemptive model we distinguish big, medium and small setup jobs, using two
parameters δ and µ: The big setup jobs J bst are those with setup time at least δT , the
small J sst have a setup time smaller than µT , and the medium J mst are the ones in
2
between. We set µ = ε2 δ and we choose δ ∈ {ε1 , . . . , ε2/ε } such that the summed up
processing time together with the summed up setup time is upper bounded by mεT , i.e.,
P
j∈J mst (sj + pj ) ≤ mεT . If there is a schedule with makespan T , such a choice is possible,
because of the pidgeon hole principle, and because the setup time of each job has to occur
at least once in any schedule. Similar arguments are widely used, e.g. in the context of
geometrical packing algorithms. Furthermore we distinguish the jobs by processing times,
calling those with processing time at least εT big and the others small. For a given set of
jobs J, we call the subsets of big or small jobs Jbig or Jsmall respectively. We perform three
simplification steps, aiming for an instance in which the small and medium setup jobs are
big; small setup jobs have setup time 0; and for which a εδT -layered, layer-compliant
schedule exists.
Let I1 be the instance we get by removing the small jobs with medium setup times
mst
Jsmall from the given instance I.
Lemma 17. If there is a schedule with makespan at most T for I, there is also such
a schedule for I1 , and if there is a schedule with makespan at most T ′ for I1 there is a
schedule with makespan at most T ′ + (ε + δ)T for I.
Proof. The first claim is obvious. For the second, we create a sequence containing the jobs
mst each directly preceded by its setup time. Recall that the overall length of the
from Jsmall
objects in this sequence is at most mεT , and the length of each job is bounded by εT . We
greedily insert the objects from the sequence, considering each machine in turn. On the
current machine we start at time T ′ + δT and keep inserting until T ′ + δT + εT is reached.
If the current object is a setup time, we discard it and continue with the next machine
and object. If, on the other hand, it is a job, we split it, such that the remaining space on
the current machine can be perfectly filled. We can place all objects like this, however the
first job part placed on a machine might be missing a setup. We can insert the missing
setups because they have length at most δT and between time T ′ and T ′ + δT there is free
space.
Next, we consider the jobs with small setup times: Let I2 be the instance we get by
sst and setting the setup time of the big
removing the small jobs with small setup times Jsmall
sst . Note that in the resulting
jobs with small setup times to zero, i.e., s̄j = 0 for each j ∈ Jbig
P
instance each small job has a big setup time. Furthermore, let L := j∈J sst pj +sj . Then
small
sst in any schedule.
L is an obvious lower bound for the space taken up by the jobs from Jsmall
Lemma 18. If there is a schedule with makespan at most T for I1 , there is also a (T, L)schedule for I2 ; and if there is a γT -layered (T ′ , L)-schedule for I2 , with T ′ a multiple of
γT , there is also a schedule with makespan at most (1 + γ −1 µ)T ′ + (µ + ε)T for I1 .
19

Proof. The first claim is obvious, and for the second consider a γT -layered (T ′ , L)-schedule
sst and their setups, such that
for I2 . We create a sequence that contains the jobs of Jsmall
each job is directly preceded by its setup. Remember that the remaining space in partly
filled slots is not counted as free space. Hence, since the overall length of the objects in
the sequence is L, there is is enough space in the free slots of the schedule to place them.
We do so in a greedy fashion guaranteeing that each job is placed on exactly one machine:
We insert the objects from the sequence into the free slots, considering each machine in
turn and starting on the current machine from the beginning of the schedule and moving
on towards its end. If an object cannot be fully placed into the current slot there are two
cases: It could be a job or a setup. In the former case, we cut it and continue placing it
in the next slot, or, if the current slot was the last one, we place the rest at the end of
the schedule. In the latter case, we discard the setup and continue with the next slot and
object. The resulting schedule is increased by at most εT , which is caused by the last job
placed on a machine.
To get a proper schedule for I1 we have to insert some setup times: For the large jobs
with small setup times and for the jobs that were cut in the greedy procedure. We do so by
inserting a time window of length µT at each multiple of γT and at the end of the original
schedule on each machine. By this, the schedule is increased by at most γ −1 µT ′ + µT .
Since all the job parts in need of a setup are small and did start at multiples of µT or at
the end, we can insert the missing setups. Note that blocks that span over multiple layers
are cut by the inserted time windows. This, however, can easily be repaired by moving
the cut pieces properly down.
We continue by rounding the medium and big setup and all the processing times. In
particular, we round the processing times and the big setup times up to the next multiple of
εδT and the medium setup times to the next multiple of εµT , i.e., p̄j = ⌈pj /(εδT )⌉εδT for
each job j, s̄j = ⌈sj /(εδT )⌉εδT for each big setup job j ∈ J bst , and s̄j = ⌈sj /(εµT )⌉εµT
mst .
for each medium setup job j ∈ Jbig
Lemma 19. If there is a (T, L)-schedule for I2 , there is also a εδT -layered, layer-compliant
((1 + 3ε)T, L)-schedule for I3 ; and if there is a γT -layered (T ′ , L)-schedule for I3 , there is
also such a schedule for I2 .
While the second claim is easy to see, the proof of the first is rather elaborate and
unfortunately a bit tedious. Hence, since we believe Lemma 19 to be fairly plausible by
itself, we postpone its proof to the end of the section and proceed discussing its use.
For the big and small setup jobs both processing and setup times are multiples of εδT .
Therefore, the length of each of their blocks in an εδT -layered, layer-compliant schedule is
a multiple of εδT . For a medium setup job, on the other hand, we know that the overall
length of its blocks has the form xεδT + yεµT , with non-negative integers x and y. In
particular it is a multiple of εµT , because εδT = (1/ε2 )εµT . In a εδT -layered, layercompliant schedule, for each medium setup job the length of all but at most one block
is a multiple of εδT and therefore a multiple of εµT . If both the overall length and the
lengths of all but one block are multiples of εµT , this is also true for the one remaining
block. Hence, we will use the MCIP not to find an εδT -layered, layer-compliant schedule
in particular, but an εδT -layered one with block sizes as described above and maximum
free space.
20

Based on the simplification steps, we define two makespan bounds T̄ and T̆ : Let T̄ be
the makespan bound we get by the application of the Lemmata 17-19, i.e., T̄ = (1 + 3ε)T .
We will use the MCIP to find an εδT -layered (T̄ , L)-schedule for I3 , and apply the Lemmata
17-19 backwards to get schedule for I with makespan at most T̆ = (1 + (εδ)−1 µ)T̄ + (µ +
ε)T + (ε + δ)T ≤ (1 + 9ε)T , using ε ≤ 1/2.
Utilization of the MCIP
Similar to the splittable case, the basic objects are the (big) jobs, i.e., B = Jbig , and their
single value is their processing time (D = 1). The modules, on the other hand, are more
complicated, because they additionally need to encode which layers are exactly used and,
in case of the medium jobs, to which degree the last layer is filled. For the latter we
introduce buffers, representing the unused space in the last layer, and define modules as
tuples of starting layer, job piece size, setup time and buffer size (ℓ, q, s, b). For a module
M = (ℓ, q, s, b), we write ℓM = ℓ, qM = q, sM = s and bM = b, and we define the size Λ(M )
of M as s+q +b. The overall set of modules M is the union of the modules for big, medium
and small setup jobs Mbst , Mmst and Msst that are defined in the following. For this let
Qbst = {q | q = xεδT, x ∈ Z>0 , q ≤ T̄ } and Qmst = {q | q = xεµT, x ∈ Z>0 , q ≤ T̄ } be the
sets of possible job piece sizes of big and medium setup jobs; S bst = {s | s = xεδT, x ∈
Z≥1/ε , s ≤ T̄ } and S mst = {s | s = xεµT, x ∈ Z≥1/ε , s ≤ δT } be the sets of possible big
and medium setup times; B = {b | b = xεµT, x ∈ Z≥0 , b < εδT } the set of possible buffer
sizes; and Ξ = {1, . . . , 1/(εδ) + 3/δ} the set of layers. We set:
Mbst = {(ℓ, q, s, 0) | ℓ ∈ Ξ, q ∈ Qbst , s ∈ S bst , (ℓ − 1)εδT + s + q ≤ T̄ }
Mmst = {(ℓ, q, s, b) ∈ Ξ × Qmst× S mst× B | x = s + q + b ∈ εδT Z>0 , (ℓ − 1)εδT + x ≤ T̄ }
Msst = {(ℓ, εδT, 0, 0) | ℓ ∈ Ξ}
Concerning the small setup modules, note that the small setup jobs have a setup time
of 0 and therefore may be covered slot by slot. We establish εµT = 1 via scaling, to
ensure integral values. A big, medium or small job is eligible for a module, if it is also big,
medium or small respectively and the setup times fit. We group the modules by size and
starting layer, i.e., Γ = {G ⊆ M | M, M ′ ∈ G ⇒ Λ(M ) = Λ(M ′ ) ∧ ℓM = ℓM ′ }. We have to
avoid that two modules M1 , M2 , whose corresponding time intervals overlap, are used to
cover the same job or in the same configuration. Such an overlap is given, if there is some
layer ℓ used by both of them, that is, (ℓM − 1)εδT ≤ (ℓ − 1)εδT < (ℓM − 1)εδT + Λ(M )
for M ∈ {M1 , M2 }. Hence, for each layer ℓ ∈ Ξ, we set Mℓ ⊆ M to be the set of
modules that use layer ℓ. Now, the set of configurations C is given by the configurations
of groups, such that for each layer at most one group using this layer is chosen, i.e.,
P
C = {C ∈ CΓ | ∀ℓ ∈ Ξ :
G⊆Mℓ CG ≤ 1}. With this definition we prevent overlap
conflicts on the machines. Note that unlike in the cases considered so far, the size of
a configuration does not correspond to a makespan in the schedule, but to used space,
and the makespan bound is realized in the definition of the modules instead of in the
definition of the configurations. To also avoid conflicts for the jobs, we extend the basic
MCIP with additional locally uniform constraints. In particular, the constraints of the
extended MCIP for the above definitions with adapted notation and without duplication

21

of the configuration variables is given by:
X

xC = m

(12)

C∈C

X

(j)

(13)

(j)

∀j ∈ J

(14)

(j)

∀j ∈ J , ℓ ∈ Ξ

(15)

yM

j∈J M ∈G

C∈C(T )

X

X X

∀G ∈ Γ

CG xC =

q M y M = pj

M ∈M

X

yM ≤ 1

M ∈Mℓ

Like in the first two cases we minimize the summed up size of the configurations, via the
P
objective function C Λ(C)xC . Note that in this case the size of a configuration does not
have to equal its height. It is easy to see that the last constraint is indeed locally uniform.
However, since we have an inequality instead of an equality, we have to introduce |Ξ| slack
variables in each brick, yielding:
Remark 20. The MCIP extended like above is an n-fold IP with brick-size t = |M|+|C|+|Ξ|,
brick number n = |J |, r = |Γ| + 1 globally uniform and s = D + |Ξ| locally uniform
constraints.
Lemma 21. With the above definitions, there is an εδT -layered (T̄ , L)-schedule for I3 in
which the length of a block is a multiple of εδT , if it belongs to a small or big setup job,
or a multiple of εµT otherwise, iff the extended MCIP has a solution with objective value
at most mT̄ − L.
Proof. We first consider such a schedule for I3 . For each machine, we can derive a configuration that is given by the starting layers of the blocks together with the summed up
length of the slots the respective block is scheduled in. The size of the configuration C is
equal to the used space on the respective machine. Hence, we can fix some arbitrary job
(j ′ )
(j)
j and set xC to the number of machines corresponding to j (and xC = 0 for j ′ 6= j).
Keeping in mind that in an εδT -layered schedule the free space is given by the free slots,
the above definition yields an objective value bounded by mT̄ − L, because there was free
space of at least L. Next, we consider the module variables for each job j in turn: If j is
(j)
a small setup job, we set y(ℓ,εδT,0,0) to 1, if the j occurs in ℓ, and to 0 otherwise. Now, let
(j)

j be a big setup job. For each of its blocks, we set y(ℓ,z−sj ,sj ,0) = 1, where ℓ is the starting
layer and z the length of the block. The remaining variables are set to 0. Lastly, let j be
(j)
a medium setup job. For each of its blocks, we set y(ℓ,z−sj ,sj ,b) = 1, where ℓ is the starting
layer of the block, z its length and b = ⌈z/(εδT )⌉εδT − z. Again, the remaining variables
are set to 0. It is easy to verify that all constraints are satisfied by this solution.
If, on the other hand, we have a solution (x, y) to the MCIP with objective value at
P (j)
most mT̄ − L, we reserve j xC machines for each configuration C. There are enough
machines to do this, because of (12). On each of these machines we reserve space: For each
G ∈ Γ, we create an allocated space of length Λ(G) starting from the starting layer of G,
(j)
if CG = 1. Let j be a job and ℓ be a layer. If j has a small setup time, we create y(ℓ,εδT,0,0)
pieces of length εδT and place these pieces into allocated spaces of length εδT in layer ℓ.
22

If, on the other hand, j is a big or medium setup job, we consider each possible job part
(j)
(j)
length q ∈ Qbst or q ∈ Qmst , create y(ℓ,q,sj ,0) or y(ℓ,q,sj ,b) , with b = ⌈q/(εδT )⌉εδT − εδT ,
pieces of length q, and place them together with their setup time into allocated spaces of
length q in layer ℓ. Because of (14) the entire job is split up by this, and because of (13)
there are enough allocated spaces for all the job pieces. The makespan bound is ensured
by the definition of the modules, and overlaps are avoided, due to the definition of the
configurations and (15). Furthermore, the used slots have an overall length equal to the
objective value of (x, y) and therefore there is at least L free space.
Result
Summing up the above considerations, we get:
Algorithm 22.
1. If there is no suitable class of medium setup jobs, report that there is no schedule with
makespan T and terminate the procedure.
2. Generate the modified instance I3 :
⊲ Remove the small jobs with medium setup times.
⊲ Remove the small jobs with small setup times, and decrease the setup time of big
jobs with small setup time to 0.
⊲ Round the big processing times, as well as the medium, and the big setup times.
3. Build and solve the MCIP for I3 .
4. If the MCIP is infeasible, or the objective value greater than mT̄ − L, report that I has
no solution with makespan T .
5. Otherwise build the εδT -layered schedule with makespan T̄ and free space at least L
for I3 .
6. Transform the schedule into a schedule for I with makespan at most T̆ :
⊲ Use the prerounding processing and setup times.
⊲ Insert the small jobs with small setup times into the free slots and insert the setup
times of the big jobs with small setup times.
⊲ Insert the small jobs with medium setup times.
We analyze the running time of the procedure, and start by bounding the parameters
of the extended MCIP. We have |B| = n and D = 1 by definition, and the number of
layers |Ξ| is obviously O(1/(εδ)) = O(1/ε2/ε+1 ) = 2O(1/ε log 1/ε) . Furthermore, it is easy to
see that |Qbst | = O(1/(εδ)), |Qmst | = O(1/(ε3 δ)), |S bst | = O(1/(εδ)), |S mst | = O(1/(ε3 )),
and |B| = O(1/ε2 ). This gives us Mbst ≤ |Ξ||Qbst ||S bst |, Mmst ≤ |Ξ||Qmst ||S mst ||B|
and Msst = |Ξ|, and therefore |M| = |Mbst | + |Mmst | + |Msst | = 2O(1/ε log 1/ε) . Since
their are O(1/(δε)) distinct module sizes, the number of groups |Γ| can be bounded by
O(|Ξ|/(εδ)) = 2O(1/ε log 1/ε) . Hence, for the number of configurations we get:
O(1/ε log 1/ε)

|C| = O((1/(εδ))|Γ| ) = 22

It is easy to see, however, that Corollary ?? still works for the extended MCIP. Therefore, we can reduce the number of configurations, like we did in the splittable case to
23

2|Γ| log(4|Γ| max C,G CG ) = 2O(1/ε log 1/ε) at the expense of
O(1/ε log 1/ε)

22
2O(1/ε log 1/ε)

!

O(1/ε log 1/ε)

= 22

guessing steps. Using the above considerations and Remark 20, we can infer that the
modified MCIP has r = 2O(1/ε log 1/ε) many global and s = 2O(1/ε log 1/ε) many local constraints; its brick number is n, and its brick size is t = 2O(1/ε log 1/ε) . All occurring values
in the matrix are bounded by T̄ and we have T̄ = 1/(εµ) + 1/µ = 2O(1/ε log 1/ε) , due to the
scaling step. Lastly, we consider the encoding length L of the objective function, the right
hand side, and the lower and upper bounds on the variables. Because of their dimension,
we get a factor of nt = n2O(1/ε log 1/ε) , and it is easy to see that all occurring values are
either bounded by 2O(1/ε log 1/ε) or O(m). Summing up, the extended MCIP including the
guessing step for the configuration variables can be solved in time:
O(1/ε log 1/ε)

22

O(1/ε log 1/ε)

O(∆3t(rs+st+r+s) Ln3 ) = 22

n4 log m

It is easy to see that the steps in the procedure preceding the third, where the MCIP is
build and solved, are dominated by this term. However, a straight-forward realization of
the procedure for the creation of the εδT -layered (T̄ , L)-schedule for I3 (the fifth step),
which is described in the proof of Lemma 21, will take nm2O(1/ε log 1/ε) time. All the
remaining steps can be bounded by the same term, yielding:
Theorem 23. The algorithm for the preemptive model finds a schedule with makespan at
most (1 + 9ε)T or correctly determines that there is no schedule with makespan T in time:
O(1/ε log 1/ε)

22

n4 m

Proof of Lemma 19
We divide the proof into three steps, which can be summarized as follows:
1. We transform a (T, L)-schedule for I2 into a ((1 + 3ε)T, L)-schedule for I3 in which the
big setup jobs are already properly placed inside the layers.
2. We construct a flow network with integer capacities and a maximum flow, based on the
placement of the remaining jobs in the layers.
3. Using flow integrality and careful repacking, we transform the schedule into a εδT layered, layer-compliant schedule.
More precisely the above transformation steps will produce a εδT -layered, layer-compliant
((1 + 3ε)T, L)-schedule with the additional properties, that too much processing time
may be inserted for some jobs or setup times are produced that are not followed by the
corresponding job pieces. Note that this does not cause any problems: We can simply
remove the extra setups and processing time pieces. For the medium jobs this results in a
placement with at most one used slot that is not fully filled, as required in a layer-compliant
schedule.

24

Figure 2: The stretching and rounding steps, for a small job part with big setup time
starting in the first layer of the schedule, depicted from left to right: The schedule and the
containers are stretched; the block is moved up; and the processing and the setup time are
increased. The hatched part represents the setup time, the thick rectangle the container,
and the dashed lines the layers, with ε = δ = 1/8.
Step 1. Remember that a block is a job piece together with its setup time placed in
a given schedule. Consider a (T, L)-schedule for I2 and suppose that for each block in
the schedule there is a container perfectly encompassing it. Now, we stretch the entire
schedule by a factor of (1 + 3ε) and in this process we stretch and move the containers
correspondingly. The blocks are not stretched but moved in order to stay in their container,
and we assume that they are positioned at the bottom, that is, at the beginning of the
container. Note that we could move each block inside its respective container without
creating conflicts with other blocks belonging to the same job. In the following, we use
the extra space to modify the schedule. Similar techniques are widely used in the context
of geometric packing algorithms.
Let j be a big setup job. In each container containing a block belonging to j, there is
a free space of at least 3εδT , because the setup time of j is at least δT and therefore the
container had at least that length before the stretching. Hence, we have enough space to
perform the following two steps. We move the block up by at most εδT , such that it starts
at a multiple of εδT . Next, we enlarge the setup time and the processing time by at most
εδT , such that both are multiples of εδT . Now the setup time is equal to the rounded
setup time, while the processing time might be bigger, because we performed this step for
each piece of the job. We outline the procedure in Figure 2.
We continue with the small setup jobs. These jobs are big and therefore for each of
them there is a summed up free space of at least 3ε2 T in the containers belonging to the
respective job—more than enough to enlarge some of the pieces such that their overall
length matches the rounded processing time.
Lastly, we consider the medium setup jobs. These jobs are big as well and we could
apply the same argument as above, however, we need to be a little bit more careful in
order to additionally realize the rounding of the setup times and an additional technical
step, we need in the following. Fix a medium setup job j and a container filled with a
block belonging to j. Since the setup time has a length of at least µT , the part of the
container filled with it was increased by at least 3εµT . Hence, we can enlarge the setup
time to the rounded setup time without using up space in the container that was created
due to the processing time part. We do this for all blocks belonging to medium setup
jobs. The extra space in the containers of a medium setup job due to the processing time
25

Layer

Jobs
1/0

α

nj

..
.

..
.

vj

uℓ

..
.

..
.

kℓ

ω

Figure 3: Flow network for layers and partially scheduled jobs.
parts is still at least 3ε2 T ≥ 3εδT . For each medium setup job j we spend at most εδT
of this space to enlarge its processing time to its rounded size and again at most εδT to
create a little bit of extra processing time in the containers belonging to j. The size of
this extra processing time is bounded by εδT and chosen in such a way that the overall
length of all blocks belonging to j in the schedule is also a multiple of εδT . Because of
the rounding, the length of the added extra processing time for each j is a multiple of
εµT . The purpose of the extra processing time is to ensure integrality in the flow network,
which is constructed in the next step.
Note that the free space that was available in the original schedule was not used in
the above steps, in fact it was even increased by the stretching. Hence, we have created
a ((1 + 3ε)T, L)-schedule for I3 —or a slightly modified version thereof—and the big setup
jobs are already well behaved with respect to the εδT -layers, that is, they start at multiples
of εδT , and fully fill the slots they are scheduled in.
Step 2. Note that for each job j and layer ℓ ∈ Ξ, the overall length qj,ℓ of job and setup
pieces belonging to j and placed in ℓ is bounded by εδT . We say that j is fully, or partially,
or not scheduled in layer ℓ, if qj,ℓ = 1, or qj,ℓ ∈ (0, 1), or qj,ℓ = 0 respectively. Let Xj
be the set of layers in which j is scheduled partially and Yℓ the set of (medium or small
P
setup) jobs partially scheduled in ℓ. Then aj = ℓ∈Xj qj,ℓ is a multiple of εδT and we set
P
nj = aj /(εδT ). Furthermore, let bℓ = j∈Yℓ qj,ℓ and kℓ = ⌈bℓ /(εδT )⌉.
Our flow network has the following structure: There is a node vj for each medium or
small setup job, and a node uℓ for each layer ℓ, as well as a source α and a sink ω. The
source node is connected to the job nodes via edges (α, vj ) with capacity nj ; and the layer
nodes are connected to the sink via edges (uℓ , ω) with capacity kℓ . Lastly, there are edges
(vj , uℓ ) between job and layer nodes with capacity 1, if j is partially scheduled in layer ℓ,
or 0 otherwise. In Figure 3 a sketch of the network is given.
P
The schedule can be used to define a flow f with value j nj in the network, by setting
f (α, vj ) = nj , f (uℓ , ω) = bℓ /(εδT ), and f (vj , uℓ ) = qj,ℓ /(εδT ). It is easy to verify that f is
a maximum flow, and because all capacities in the flow network are integral, we can find
another maximum flow f ′ with integral values.

26

Step 3. We start by introducing some notation and a basic operation for the transformation of the schedule: Given two machines i and i′ and a time t, a machine swap between i
and i′ at moment t produces a schedule, in which everything that was scheduled on i from
t on is now scheduled on i′ and vice versa. If on both machines there is either nothing
scheduled at t, or blocks are starting or ending at t, the resulting schedule is still feasible.
Moreover, if there is a block starting at t on one of the machines and another one belonging to the same job ending on the other we can merge the two blocks and transform the
setup time of the first into processing time. We assume in the following that we always
merge if this is possible, when performing a machine swap. Remember that by definition
blocks belonging to the same job cannot overlap. However, if there was overlap, it could
be eliminated using machine swaps [24].
If a given slot only contains pieces of jobs that are partially scheduled in the layer,
we call the slot usable. Furthermore, we say that a job j is flow assigned to layer ℓ, if
f ′ (vj , uℓ ) = 1. In the following, we will iterate through the layers, and create as many
usable slots as possible, reserve them for flow assigned jobs, and fill them with processing
and setup time of the corresponding slot later on. To do so, we have to distinguish different
types of blocks belonging to jobs that are partially placed in a given layer: Inner blocks,
which lie completely inside the layer and touch at most one of its borders; upper cross-over
blocks, which start inside the layer and end above it; and lower cross-over blocks, which
start below the layer and end inside it. When manipulating the schedule layer by layer, the
cross-over jobs obviously can cause problems. To deal with this, we will need additional
concepts: A repair piece for a given block is a piece of setup time of length less than εδT ,
with the property that the block and the repair piece together make up exactly one setup
of the respective job. Hence, if a repair-piece is given for a block, the block is comprised
completely of setup time. Moreover, we say that a slot reserved for a job j, has a dedicated
setup, if there is a block of j including a full setup starting or ending inside the slot.
In the following, we give a detailed description of the transformation procedure followed
by a high-level overview of the procedure. The procedure runs through two phases. In the
first phase the layers are transformed one after another from bottom to top. After a layer
is transformed the following invariants will always hold:
I1 A scheduled block either includes a full setup, or has a repair piece, and in the latter
case it was an upper cross-over block in a previous iteration.
I2 Reserved slots that are not full have a dedicated setup.
Note that the invariants are trivially fulfilled in the beginning. During the first phase, we
remove some job and setup parts from the schedule that are reinserted into the reserved
slots in the second phase. Let ℓ ∈ Ξ denote the current layer.
In the first step, our goal is to ensure that jobs that are fully scheduled in ℓ occupy
exactly one slot, thereby creating as many usable slots as possible. Let j be a job that is
fully scheduled in layer ℓ. If there is a block belonging to j and ending inside the layer at
time t, there is another block belonging to j and starting at t, because j is fully scheduled
in ℓ and there are no overlaps. Hence, we can perform a machine swap at time t between
the two machines the blocks are scheduled on. We do so, for each job fully scheduled
in the layer and each corresponding pair of blocks. After this step, there are at least kℓ
usable slots and at most kℓ flow assigned jobs in layer ℓ.

27

Repair piece

Removed pieces

Figure 4: The rectangles represent blocks, the hatched parts the setup times, and the
dashed lines layer borders. The push and cut step is performed on two blocks. For one of
the two a repair piece is created.
Next, we consider upper cross-over blocks of jobs that are partially scheduled in the
layer ℓ but are not flow assigned to it. These are the blocks that cause the most problems,
and we perform a so-called push and cut step (see Figure 4) for each of them: If q is the
length of the part of the block lying in ℓ, we cut away the upper part of the block of length
q and move the remainder up by q. If the piece we cut away does contain some setup time,
we create a repair piece for the block out of this setup time. The processing time part of
the piece, on the other hand, is removed. Note that this step preserves the first invariant.
The repair piece is needed in the case that the job corresponding to the respective block
is flow assigned to the layer in which the block ends.
We now remove all inner blocks from the layer, as well as the parts of the upper and
lower cross-over blocks that lie in the layer. After this, all usable slots are completely free.
Furthermore, note that the the first invariant might be breached by this.
Next, we arbitrarily reserve usable slots for jobs flow assigned to the layer. For this,
note that due to the definition of the flow network, there are at most kℓ jobs flow assigned
to the layer and there are at least as many usable slots, as noted above.
Using machine swaps at the upper and lower border of the layer, we then ensure, that
the upper and lower cross-over blocks of the jobs flow assigned to the layer lie on the same
machine as the reserved slot. This step might breach the second invariant as well.
However, for each job j flow assigned to the layer, we perform the repair steps in
order to restore the invariants: If there is an upper cross-over block for j, we reinsert the
removed part of the block at the end of the slot, thereby providing a dedicated setup for
the remaining free space in the slot. If there is a lower, but no upper cross-over block for
j, there are two cases: Either there was a repair piece for the block or not. In both cases
we reinsert the removed part of the block in the beginning of the slot and in the first we
additionally insert as much setup of the repair piece as possible. The possible remainder
of the repair piece is removed. Now the slot is either full, or a full setup is provided. If
there is neither an upper nor a lower block for j, there is an in inner block belonging to j.
This has to be the case, because otherwise the capacity in the flow network between j and
ℓ is 0 and j could not have been flow assigned to ℓ. Moreover, this inner block contains
a full setup and we can place it in the beginning of the slot, thus providing the dedicated
setup. The invariants are both restored.
28

After the first phase is finished, we have to deal with the removed pieces in the second
one. The overall length of the reserved slots for a job j equals the overall length aj of
its setup and job pieces from layers in which j was partially scheduled. Since, we did
not create or destroy any job piece, we can place the removed pieces corresponding to job
j perfectly into the remaining free space of the slots reserved for j, and we do so after
transforming them completely into processing time. Because of the second invariant, there
is a dedicated setup in each slot, however, it may be positioned directly above the newly
inserted processing time. This can be fixed by switching the processing time with the top
part of the respective setup time.
Lastly, all remaining usable slots are completely free at the end of this procedure, and
since the others are full they have an overall size of at least L. We conclude the proof of
Lemma 19 with an overview of the transformation procedure.
Algorithm 24.
Phase 1: For each layer ℓ ∈ Ξ, considered bottom to top, perform the following steps:
1. Use machine swaps to ensure that jobs fully scheduled in ℓ occupy exactly one slot.
2. For each upper cross-over block of a job partially scheduled but not flow assigned to ℓ
perform a push and cut step.
3. Remove inner blocks and parts of cross-over blocks that lie in ℓ.
4. Reserve usable slots for jobs flow assigned to the layer.
5. Use machine swaps to ensure, that cross-over blocks of flow assigned jobs lie on the
same machine as the reserved slot.
6. For each job j flow assigned to the layer, perform exactly one of the repair steps.
Phase 2:
1. Transform all removed pieces into processing time and insert the removed pieces into
the reserved slots.
2. If processing time has been inserted ahead of the dedicated setup of the slot, reschedule
properly.

5

Improvements of the running time

In this section, we revisit the splittable and the setup time model. For the former, we
address the problem of the running time dependence in the number of machines m and
present an improved rounding procedure, yielding a better strongly polynomial running
time. For the latter, on the other hand, we employ structural results by Jansen, Klein and
Verschae [15] to get a better running time.

5.1

Splittable Model

In the splittable model, the number of machines m may be super-polynomial in the input
size, because it is not bounded by the number of jobs n. Hence, we need to be careful
already when defining the schedule in order to get a polynomially bounded output. We
say a machine is composite if it contains more than one job, and we say it is plain if it
contains at most one job. For a schedule with makespan T , we call each machine trivial
if it is plain and has load T or if it is empty, and nontrivial otherwise. We say a schedule

with makespan T is simple, if the number of nontrivial machines is bounded by n2 .
29

Lemma 25. If there is a schedule with makespan T for I there is also a simple schedule
with makespan T .
Proof. Let there be a schedule
S with makespan T for I. For the first step, let us assume
n
there are more than 2 composite machines. In this case, there exist two machines M1
and M2 and two jobs a, b ∈ J , a 6= b such that both machines contain parts of both jobs
since there are at most n2 different pairs of jobs. Let tMx (y) be the processing time
combined with the setup time of job y ∈ {a, b} on machine Mx , x ∈ {1, 2}. W.l.o.g. let
tM1 (a) be the smallest value of the four. We swap this job part and its setup time with
some of the processing time of the job b on machine M2 . If the processing time of b on
M2 is smaller than tM1 (a), there is no processing time of b on M2 left and we can discard
the setup time
from b on this machine. We can repeat this step iteratively until there are
n
at most 2 machines containing more than one job.
In the second step, we shift processing time from the composite machines to the plain
ones. We do this for each job until it is either not contained on a composite machine or
each plain machine containing this job has load T . If the job is no longer contained on a
composite machine, we shift the processing time of the job such that all except one machine
containing this job has load T . Since this
job does not appear on any composite machines,

their number can be bounded by n−1
,
by
repeating the first step. Therefore, the number
2

n−i
of nontrivial machines is bounded by 2 + i ≤ n2 for some i ∈ {0, . . . , n}.

For a simple schedule a polynomial representation of the solution is possible: For each
job, we give the number of trivial machines containing this jobs, or fix a first and last
trivial machine belonging to this job. This enables a polynomial encoding length of the
output, given that the remaining parts of the jobs are not fragmented into too many parts,
which can be guaranteed using the results of Section 4.
To guarantee that the MCIP finds a simple solution, we need to modify it a little. We
have to ensure that nontrivial configurations are not used to often. We
can do this by

summing up the number of those configurations and bound them by n2 . Let C ′ ⊆ C be
the set of nontrivial configurations, i.e., the set of configurations containing more than one
module or one module with size smaller than T . We add the following globally uniform
constraint to the MCIP:
X

xC ≤

C∈C ′

!

|J bst |
2

(16)

Since this is an inequality, we have to introduce a slack variable increasing the brick
size by one. The constraint adds at most O(|J bst | + |J bst | log(|J bst |) + log(|J bst |)) ≤
O(n log m/(ε6 )) to the encoding length, and therefore does not affect the running time. We
still can guess the at most O(log(1/ε)/ε2 ) nontrivial configurations we need by Theorem
4 and add the trivial configuration containing just one module of size 1/ε2 + 2/ε and an
empty configuration. These additional configurations will affect the running time just by
2
8
a constant factor. Hence the MCIP still can be solved in 2O(1/ε log 1/ε) n4 log m.
The number of modules with maximum size denotes for each job in J bst how many
trivial machines it uses. The other modules can be mapped to the nontrivial configurations
and the jobs can be mapped to the modules.
We still have to schedule the jobs in J sst . We do this as described in the proof of Lemma
5. We fill the nontrivial machines greedily step by step starting with the jobs having the
30

smallest processing time. When these machines are filled, there are some completely empty
machines left. Now, we estimate how many machines can be completely filled with the
current job j. This can be done, by dividing the remaining processing time by T − si in
O(1). The remaining part is scheduled on the next free machine. This machine is filled up
with the next job and again the number of machines which can be filled completely with
the rest of this new job is determined. These steps are iterated until all jobs in J sst are
scheduled. This greedy procedure needs at most O(|J bst |(|J bst | − 1) + |J sst |) ≤ O(n2 )
operations. The following theorem is a direct consequence:
Theorem 26. The algorithm for the splittable model finds a schedule with makespan at
most (1 + 3ε)T or correctly determines that there is no schedule with makespan T in time
2
8
2O(1/ε log 1/ε) n4 log(m).
Another improvement, we can make, concerns the number of modules. To do this,
we change the rounding strategy from Lemma 6. Instead of arithmetic, we use geometric
rounding. To implement this, we have to introduce a new representation of a schedule.
We say a schedule covers an instance I if in total each job j ∈ J is processed at least
pj . Let k ∈ N such that 2k ≥ 1/ε ≥ 2k−1 and define ε′ := 1/2k . In stead of rounding
to multiples of ε2 T , we will round to multiples of ε′2 T . It holds trivially that 1/ε′ ≤ 2/ε
and ε′ ≤ ε. Let Q := {l2k−i ε′2 T |l ∈ {1, . . . , 1/ε′ }, i ∈ {0, . . . , k}}. It holds that |Q| ≤
1/ε′ (log(1/ε′ ) + 1) ≤ 2/ε(log(1/ε) + 2). We want to round each occurring processing time
to one of the values in Q.
Lemma 27. If there is a (T, L′ )-schedule for I1 , there is also a (T̄ , L′ )-schedule with
T̄ = (1 + 2ε′ )T which covers I1 and in which the length of each job part is a value out of
Q. Furthermore, any (T ′ , L′ )-schedule which covers I1 yields a (T ′ , L′ )-schedule for I1 .
Proof. Consider a (T, L)-schedule for I1 . First we scale the instance with (1 + ε′ ) and
consider each occurring setup time and job part with processing time larger than ε′2 T .
Let h be one of these setup or processing times with h ≥ T /2i . Since we scaled the
schedule by (1 + ε′ ) the new processing time is now h′ := h + ε′ h ≥ h + ε′ T /2i . Therefore,
we can round up h to the next larger multiple of ε′ T /2i = 2k−i ε′2 T , without exceeding h′ .
By this step we rounded the set up and processing times larger than ε′2 T to values form
Q.
In the next step we make sure, that each occurring setup or processing time is a
multiple of ε′2 T . There are at most 1/ε jobs scheduled on each machine, since each
setup time has a length of at least εT . On each machine, we extend each job part with
processing time smaller than ε′2 T to ε′2 T . This step extends the makespan by at most
ε′ T since ε′2 T /ε ≤ ε′ T . Now each job part is a multiple of ε′2 T and therefore the total
processing time of the job is a multiple of ε′2 T too. Obviously this new schedule covers
I1 , since we just enlarged the occurring processing times.
Lastly, there is at least as much free space in the resulting schedule as in the original
one, because we properly increased the makespan bound. The second claim is obvious.
In order to guarantee integrality in the MCIP we have to adjust the scaling step, such
that ε′2 T = 1. Note that each job part and each setup time has one of O(log(1/ε)/ε) sizes.
These sizes define the new sizes we use in the modules. As a consequence we have |M| ≤
O((log(1/ε)/ε)2 ). Since the rounded schedule covers the jobs instead of exactly match the
31

processing time, we have to add one slack variable to each locally uniform equation (8) in
the MCIP. Each of the slack variables is bounded by m(1+2ε)/ε′2 and therefore we increase
the encoding length by at most O(|J bst | log(m/ε)). The improvement on the number of
modules reduces the brick size to t = |M|+2|Γ| log(4|Γ| max C,G CG )+1 = O(log(1/ε)2 /ε2 )
while the encoding length is still bounded by L ≤ O(n log m/(ε6 )). Hence the MCIP can
6
4
be solved in time O(∆3t(rs+st+r+s) Ln3 ) = 2O(1/ε log 1/ε) n4 log m.
Theorem 28. The algorithm for the splittable model finds a schedule with makespan at
most (1 + 3ε)T or correctly determines that there is no schedule with makespan T in time
6
4
2O(1/ε log 1/ε) n4 log(m).

5.2

Setup Class Model

In the algorithm for the setup class model, we did not use the result by Eisenbrandt and
Shmonin [9] to reduce the number of configuration variables. The reason for this is that
there are essentially as many module variables as there are configuration variables in this
model, and therefore the gain would be negligible. In the following, however, we show
how we can reduce the number of module variables using a result by Jansen, Klein and
Verschae [15] concerning the configuration IP for scheduling on identical machines.
Before stating this result, we establish some notation. Consider an instance of the
problem of scheduling on identical machines, with a set of processing times P , np jobs
of processing time p ∈ P , m machines, a makespan bound T , and the corresponding
configuration IP as stated in Section 3. Furthermore, let both the processing times and
the makespan bound be integral. We call a configuration simple, if the number of used
basic objects—that is the number of non-zero entries in the vector—is at most log(T + 1),
and complex otherwise. The result by Jansen et al. [15], simplified for our needs, can be
stated as follows:
Theorem 29. If there is a feasible solution for the configuration IP, there is also a solution
in which at most 2(|P | + 1) log(4(|P | + 1)T ) distinct complex configurations are used and
each of them is used only once.
2

2

Furthermore, they argued that there are at most 2O(log (T )+log (|P |)) simple configurations. In the setup class model, the modules are pairs of setup times and configurations of
processing times. Now, the basic idea for the reduction of the modules is to redefine them
using only the simple configurations, and building the needed complex configurations using extra variables and constraints. We elaborate on this idea in the following, assuming
that an instance for the setup class model is given, and using the same notation as in
Section 4.
Let Q be the set of possible sizes of configurations of processing times bounded in size
by T̄ = (1 + ε2 )(1 + ε)(1 + 2ε)T , i.e., Q = {q | q = xε4 T, x ∈ Z≥0 , q ≤ T̄ }. Consider a
P
(k)
(k)
solution (x, y) of the MCIP. We set mq = (C,s)∈M,Λ(C)=q y(C,s), for each k ∈ [K ′ ] and
(k)

(k)

q ∈ Q; and nq,p = (C,s)∈M,Λ(C)=q Cp y(C,s) , for each k ∈ [K ′ ], q ∈ Q and p ∈ P , where P
is the set of (rounded) processing times. We fix a class k and a size q, and consider the
P

32

(k)

configuration IP given by mq
X

(k)

and the values nq,p :
zC = m(k)
q

C∈CP (q)

X

Cp zC = n(k)
q,p

∀p ∈ P

C∈CP (q)
(k)

Obviously (y(C,sk ) )C∈CP (q) is a feasible solution for this IP, and we can apply Theorem 29,
to get another solution z that uses at most 2(|P | + 1) log(4(|P | + 1)q) distinct complex
configurations (with respect to q) and each of them only once. Furthermore, all the
configurations used by z have size q, because this is the case for the first solution, and
therefore a used configuration of smaller size, implies that also another one with bigger
(k)
size is used, and this is not possible. We set set ỹ(C,sk ) = zC , and repeat this for each
type k and size q, yielding another solution (x, ỹ) of the MCIP. This solution is feasible
because the same number of jobs is covered for each class, and the same number of modules
P
P
(k)
(k)
from each group is chosen, i.e., M ∈M Mp yM = M ∈M Mp ỹM for each k ∈ [K ′ ] and
P
P
P
P
(k)
(k)
p ∈ P , and k∈[K ′ ] M ∈G yM = k∈[K ′ ] M ∈G ỹM for each G ∈ Γ. For the second
equality, note that Γ is a partition of the modules by size, and we replaced modules with
other modules of the same size. Note that configurations that are simple with respect
to q ∈ Q are also simple with respect to T̄ ≥ q. Hence, for each class k, the number
of used modules corresponding to complex configurations in (x, ỹ) is bounded by κ :=
|Q|2(|P | + 1) log(4(|P | + 1)T̄ ) = O(1/ε8 log(1/ε)). Based on these observations, we define
a modified version of the MCIP for the setup class model.
Let CP′ (T̄ ) be the subset of CP (T̄ ) containing the simple configurations, and let M′ =
{(C, s) | C ∈ CP′ (T̄ ), s ∈ S, s + Λ(C) ≤ T̄ }, be the corresponding set of modules. Let
Q∗ = {q | q = ε3 T + xε4 T, x ∈ Z≥0 , q ≤ T̄ } be the set of possible module sizes. We define
the modified set of configurations C ′ as the set of configurations of possible module sizes
bounded in size by T̄ , i.e., C ′ = CQ∗ (T̄ ). Our strategy is to construct up to κ extra modules
for each class, directly in the IP, thereby eliminating the necessity to include the modules
corresponding to the complex configurations. A similar idea was used by Goemanns and
Rothvoss in the context of bin packing [11]. On that account, we introduce additional
variables in each brick, given by a class k: For each processing time p ∈ P and ℓ ∈ [κ], a
(k)
variable uℓ,p corresponding to the number of jobs of size p used in the ℓ-th extra module;
(k)

and, for each module size q ∈ Q∗ and ℓ ∈ [κ], a decision variable vℓ,q expressing whether the
ℓ-th module has size q or not. Concerning the latter variables, there is a subtle distinction
we have to make: The size of the ℓ-th extra module for class k should equal the size of
P
(k)
the corresponding configuration of processing times, i.e., p∈P puℓ,p , plus the setup time
of class k, except if the size of the configuration is 0, which amounts to not using the
(k)
ℓ-th extra configuration. In the latter case, all variables from {vℓ,q | q ∈ Q∗ } should take
the value 0, and otherwise there should be exactly one taking the value 1. Extending the

33

constraints of the MCIP naturally with these variables, yields:
X

xC = m

(17)

C∈C

X

(k)

X

yM +

X X

(k)

vℓ,q =

X

(k)

Mp yM +

M ∈M

X

∀q ∈ Q∗

(18)

∀k ∈ [K ′ ], p ∈ P

(19)

Cq xC

C∈C

k∈[K ′ ] ℓ∈[κ]

k∈[K ′ ] M ∈M′ ,Λ(M )=q

X

(k)

uℓ,p = nk,p

ℓ∈[κ]

These constraints are similar to the constraints (9)-(11) for the MCIP in the setup class
model: They ensure that the right number of configurations is chosen, the setup classes are
covered by the modules—including the extra modules—and the modules by the configurations—
also including the extra ones. However, they obviously do not suffice. We additionally
need to bound the size of the extra modules, and ensure proper behaviour of the decision
variables. While the former can easily be realized, the latter is a bit more complicated.
Essentially, we have to express for each class k, size q and number ℓ the following logical
constraint in terms of linear constraints:
 X



(k)

puℓ,p > 0 ∧

p∈P

X

(k)

puℓ,p = q − sk

p∈P



(k)

⇒ vℓ,q = 1

(20)

(k)

We do so using one additional auxiliary variable wℓ , which is lower bounded by 0 and
upper bounded by sk , as well as the following constraints for each class k ∈ [K ′ ] and
number ℓ ∈ [κ]:
(k)

X

vℓ,q ≤ 1

X

vℓ,q ≤

(21)

q∈Q∗
(k)

q∈Q∗

X

(k)

(22)

uℓ,p

p∈P
(k)

wℓ

≤ T̄ (1 −

X

(k)

vℓ,q )

(23)

q∈Q∗
(k)

wℓ

+

X

(k)

qvℓ,q =

q∈Q∗

X

(k)

puℓ,p + sk

(24)

p∈P

The first two constraints (21) and (22) guarantee that we choose at most one size for the
ℓ-th extra module of class k, and that we choose none if the corresponding configuration
(k)
has size 0. If a size is chosen, the auxiliary variable wℓ will take the value 0 due to (23)
and otherwise this constraint has no effect. For the last constraint we consider two cases:
P
P
(k)
(k)
(k)
If p∈P uℓ,p = 0, we also have q∈Q∗ vℓ,q = 0 due to (22) and wℓ can take any value
(k)

between 0 and sk . Therefore, the constraint can be satisfied by wℓ = sk and has no
P
(k)
(k)
further effect. If, on the other hand, p∈P uℓ,p > 0, we have wℓ = 0, and because of (21)
at most one of the sizes can be chosen. Now, constraint (24) ensures that exactly one size
and, more precisely, the right one is chosen. Furthermore, it also bounds the size of the
extra modules implicitly. It is easy to see, that the new constraints are locally uniform.
For (21)-(23) we have to insert slack variables, and summarizing, we get:
34

Remark 30. The modified MCIP above is an n-fold IP with brick-size t = |M′ | + |C ′ | +
(|P | + |Q∗ | + 4)κ, brick number n = K ′ , r = |Q∗ | + 1 globally uniform and s = |P | + 4κ
locally uniform constraints.
We use the same objective function as always and argue that the modified MCIP can
be used as well in the algorithm for the setup class model:
Lemma 31. If there is a solution for the MCIP, there is also a solution for the modified
MCIP with the same objective value.
Proof. We already argued that, if there is a solution (x, y) for the MCIP, there is another one (x, ỹ), which obviously has the same objective value, because the configuration
variables have the same value, and which has the following property: For each class k
at most κ distinct modules corresponding to complex configurations are used and each
one of them is used at most once. Using this solution, we define a solution (x̆, y̆, ŭ, v̆, w̆)
(k)
(k)
for the modified MCIP and start by setting x̆ = x, and y̆M = ỹM for each class k
and module M ∈ M′ corresponding to a simple configuration. Now fix a class k and
let M∗ be the set of modules corresponding to complex configurations used in ỹ (k) , i.e.,
(k)
M∗ = |{M ∈ M \ M′ | ỹM > 0}|. We number the modules from M∗ in any order from
(ℓ)
(k)
1 to κ∗ = |M∗ |. For each ℓ ∈ [κ∗ ], let M (ℓ) be the ℓ-th module and we set ŭℓ,p = Mp
(k)

(k)

(k)

for each p ∈ P , v̆ℓ,Λ(M (ℓ) ) = 1, v̆ℓ,q = 0 for each q 6= Λ(M (ℓ) ), and w̆ℓ
for each ℓ ∈ {κ∗ , . . . , κ}, we set

(k)
ŭℓ,p

= 0 for each p ∈ P ,

(k)
v̆ℓ,q

= 0. Moreover,

= 0 for each q ∈ Q∗ , and

(k)

w̆ℓ = sk . It is easy to verify, that performing these steps for each class k yields a feasible
solution for the modified MCIP with the same objective value as (x, ỹ).
Lemma 32. If the modified MCIP has a solution with objective value at most mT̄ − L,
there is a (T̄ , L)-schedule for I4 .
Proof. Given a solution (x, y, u, v, w) of the MCIP, we define a corresponding schedule:
Due to (17) we can assign the chosen configurations to the machines, and if configuration
C is assigned to machine i, for each possible module size q ∈ Q∗ , we create Cq slots of
(k)
length q on i. For each class k and module M ∈ M′ , we create yM batches of jobs from
class k with Mp jobs with processing time p for each p ∈ P Furthermore, we create batches
(k)
corresponding to the extra modules: For each class k and ℓ ∈ [κ] with wℓ = 0 the batch
(k)
is comprised of the setup time sk as well as uℓ,p jobs of size p. Because of (24) and (21)
(k)

there is exactly one q ∈ Q∗ with vℓ,q = 1 and the constructed batch has length q. We
place the batches into fitting slots on the machines and because of (19) and (18) all jobs
can be placed by this process. The used space in the created schedule equals the overall
size of the configurations and therefore the free space bound is satisfied
2

2

2

In the modified MCIP, we have |S||CP′ (T̄ )| = O(1/ε4 )2O(log (T̄ )+log (|P |)) = 2O(log 1/ε)
many distinct modules, while the bound for the number of distinct configurations remains
3
the same, that is 2O(1/ε log 1/ε) . Hence, the number of configurations is much bigger than
the number of modules and using Theorem 4 to reduce the number of configurations
is worthwhile. Note that the theorem can be used essentially like before, to show that
there is a solution using at most 2|Q∗ | log(4|Q∗ | maxC,G CG ) = O(1/ε4 log(1/ε)) distinct
35

7

2

configurations. These can be found via 2O(1/ε log 1/ε) guessing steps, yielding a reduced
2
brick size of t = |M′ |+|C ′ |+(|P |+|Q∗ |+1)κ = 2O(log 1/ε) . This is the essential observation
for the reduced running time. Noting that both the number of globally and locally uniform
constraints is polynomially bounded in 1/ε, and that all new coefficients in the matrix are
bounded by T̄ , we can solve the modified MCIP in time:
O(log2 1/ε)

22

K 4 log n log m

Therefore, we get:
Theorem 33. The algorithm for the setup class model finds a schedule with makespan at
most (1 + 6ε)T or correctly determines that there is no schedule with makespan T in time:
O(log 2 1/ε)

22

6

K 4 nm

Conclusion

We presented a more advanced version of the classical configuration IP, showed that it can
be solved efficiently using algorithms for n-fold IPs, and developed techniques to employ
the new IP for the formulation of efficient polynomial time approximation schemes for
three scheduling problems with setup times, for which no such algorithms were known
before. Furthermore, we utilized structural insights on integer programs to get better
running times of the EPTASs.
For further research the immediate questions are whether the MCIP can be solved more
efficiently and to which other problems it can be reasonably employed. However, the results
of this paper are enabled by techniques for n-fold integer programs. Therefore, from a
broader perspective, it would be interesting to study further uses of these in approximation,
and of course to further study the techniques themselfs.
Acknowledgements.

We thank Syamantak Das for helpful discussions on the problem.

References
[1] Ali Allahverdi, Jatinder ND Gupta, and Tariq Aldowaisan. A review of scheduling
research involving setup considerations. Omega, 27(2):219–239, 1999.
[2] Ali Allahverdi, CT Ng, TC Edwin Cheng, and Mikhail Y Kovalyov. A survey of
scheduling problems with setup times or costs. European journal of operational research, 187(3):985–1032, 2008.
[3] Noga Alon, Yossi Azar, Gerhard J Woeginger, and Tal Yadid. Approximation schemes
for scheduling on parallel machines. Journal of Scheduling, 1(1):55–66, 1998.
[4] Bo Chen. A better heuristic for preemptive parallel machine scheduling with batch
setup times. SIAM Journal on Computing, 22(6):1303–1318, 1993.
[5] Bo Chen, Yinyu Ye, and Jiawei Zhang. Lot-sizing scheduling with batch setup times.
Journal of Scheduling, 9(3):299–310, 2006.
36

[6] Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and approximation results for scheduling with a low rank processing time matrix. In
LIPIcs-Leibniz International Proceedings in Informatics, volume 66. Schloss DagstuhlLeibniz-Zentrum fuer Informatik, 2017.
[7] José Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Leen Stougie, Ola
Svensson, Víctor Verdugo, and José Verschae. Strong lp formulations for scheduling
splittable jobs on unrelated machines. Mathematical Programming, 154(1-2):305–328,
2015.
[8] José Correa, Victor Verdugo, and José Verschae. Splitting versus setup trade-offs
for scheduling to minimize weighted completion time. Operations Research Letters,
44(4):469–473, 2016.
[9] Friedrich Eisenbrand and Gennady Shmonin. Carathéodory bounds for integer cones.
Operations Research Letters, 34(5):564–568, 2006.
[10] Paul C Gilmore and Ralph E Gomory. A linear programming approach to the cuttingstock problem. Operations research, 9(6):849–859, 1961.
[11] Michel X Goemans and Thomas Rothvoß. Polynomiality for bin packing with a
constant number of item types. In Proceedings of the twenty-fifth annual ACM-SIAM
symposium on Discrete algorithms, pages 830–839. SIAM, 2014.
[12] Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. N-fold integer programming in cubic time. Mathematical Programming, pages 1–17, 2013.
[13] Dorit S Hochbaum and David B Shmoys. Using dual approximation algorithms for
scheduling problems theoretical and practical results. Journal of the ACM (JACM),
34(1):144–162, 1987.
[14] Klaus Jansen. An eptas for scheduling jobs on uniform processors: using an milp
relaxation with a constant number of integral variables. SIAM Journal on Discrete
Mathematics, 24(2):457–485, 2010.
[15] Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the gap for makespan
scheduling via sparsification techniques. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy,
pages 72:1–72:13, 2016.
[16] Klaus Jansen and Felix Land. Non-preemptive scheduling with setup times: A ptas.
In European Conference on Parallel Processing, pages 159–170. Springer, 2016.
[17] Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of operations research, 12(3):415–440, 1987.
[18] Dušan Knop and Martin Kouteckỳ. Scheduling meets n-fold integer programming.
arXiv preprint arXiv:1603.02611, 2016.
[19] Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research, 8(4):538–548, 1983.
37

[20] Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören
Riechers. Non-preemptive scheduling on machines with setup times. In Workshop on
Algorithms and Data Structures, pages 542–553. Springer, 2015.
[21] Clyde L Monma and Chris N Potts. Analysis of heuristics for preemptive parallel machine scheduling with batch setup times. Operations Research, 41(5):981–993, 1993.
[22] Shmuel Onn. Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010.
[23] Frans Schalekamp, René Sitters, Suzanne Van Der Ster, Leen Stougie, Víctor Verdugo, and Anke Van Zuylen. Split scheduling with uniform setup times. Journal of
scheduling, 18(2):119–129, 2015.
[24] Petra Schuurman and Gerhard J Woeginger. Preemptive scheduling with jobdependent setup times. In Proceedings of the tenth annual ACM-SIAM symposium on
Discrete algorithms, pages 759–767. Society for Industrial and Applied Mathematics,
1999.

38

