scieee Science in your language
[en] (orig)
FAKULT ¨
AT II
MATHEMATIK UND
NATURWISSENSCHAFTEN
Institut f ¨ur Mathematik
SCHEDULING PARALLEL JOBS
TO MINIMIZE MAKESPAN
by
BERIT JOHANNES
No. 723/2001
Scheduling Parallel Jobs to Minimize Makespan
Berit Johannes
November 11, 2001
Abstract
We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel ma-
chines to minimize the makespan. A parallel job requires simultaneously a pre-specified, job-dependent
number of machines when being processed. Our main result is the following. The makespan of a (non-
preemptive) schedule constructed by any listscheduling algorithm is within a factor of
2
of the optimal
preemptive makespan. This gives the best known approximation algorithms for both the preemptive and
the non-preemptive variant of the problem, improving upon previously known performance guarantees
of
3
. We also show that no listscheduling algorithm can achieve a better performance guarantee than
2
for the non-preemptive problem, no matter which priority list is chosen.
Since listscheduling also works in the online setting in which jobs arrive over time and the length of a
job becomes only known when it completes, the main result yields a deterministic online algorithm with
competitive ratio
2
as well. In addition, we consider a different online model in which jobs arrive one
by one and need to be scheduled before the next job becomes known. In this context, no listscheduling
algorithm has a constant competitive ratio. We present the first online algorithm for scheduling parallel
jobs with a constant competitive ratio. We also prove a new information-theoretic lower bound of
2
:
25
for the competitive ratio of any deterministic online algorithm for this model.
1 Introduction
Scheduling parallel jobs has recently gained considerable attention. The papers [2, 4, 5, 10, 13, 24, 25, 29,
31, 36] are just a small sample of work in this area. In fact, the study of computer architectures with parallel
processors has prompted the importance of the design and the analysis of good algorithms for scheduling
parallel jobs. Because of this background, parallel jobs are often alternatively called multiprocessor tasks.
While many different scheduling models and underlying computer architectures have been considered, we
focus on scheduling non-malleable parallel jobs on identical parallel machines to minimize the makespan.
We refer to [12] for a comprehensive introduction to the scheduling aspect of parallel computing, and to [9]
for an overview of results on computational complexity and approximation algorithms; [11] contains a good
collection of further references.
Model. We discuss the following class of scheduling problems. We are given
m
identical parallel machines
and a set of
n
independent, parallel jobs
j
= 1
;::: ;n
. Each job
j
has a positive integer processing time
p
j
,
which we also call its length. Job
j
simultaneously requires
m
j
6
m
machines at each point in time it
is in process. The positive integer
m
j
is also known as the width of job
j
. Note that we assume that
m
j
is part of the input; in particular, jobs are non-malleable. Moreover, each job
j
has a non-negative integer
release date
r
j
at which it becomes available for processing. Any machine can process at most one job at a
Institut f¨ur Mathematik, Technische Universit¨at Berlin, Germany, e-mail: joha[email protected]
1
time. The objective is to find a feasible schedule of minimal completion time; that is, the makespan is to be
minimized. We consider both the preemptive and the non-preemptive variant of this problem. If preemptions
are allowed, a job may be interrupted at any point in time and continued later, possibly on a different set of
machines. We denote the preemptive problem by P
j
m
j
; r
j
;
pmtn
j
C
max
and the non-preemptive problem
by P
j
m
j
; r
j
j
C
max
, following the three-field-notation introduced in [19]. We note that some authors use
“size
j
” instead of “
m
j
” as a symbol to refer to parallel jobs of the nature described before, see, e.g., [9].
¿From time to time, we shall also refer to the “ancestors” of the studied scheduling problems; they arise as
the special case in which
m
j
= 1
for all
j
= 1
;::: ;n
. Their short-form notation is P
j
r
j
;
pmtn
j
C
max
and
P
j
r
j
j
C
max
, respectively, and, in the absence of non-trivial release dates, P
j
pmtn
j
C
max
and P
j j
C
max
.
Since both parallel job scheduling problems are NP-hard, we are interested in approximation algorithms.
An
–approximation algorithm for a minimization problem is a polynomial-time algorithm that constructs
for any instance a solution of value at most
times the optimal value;
is also called the performance
guarantee of the algorithm. Motivated by the application context of parallel job scheduling, we also study
(deterministic) online algorithms. Whereas we shall consider different online scenarios, we always measure
the quality of an online algorithm in terms of its competitive ratio. An online algorithm is
–competitive if
it produces for any instance a solution of value at most
times the value of an offline optimum.
Related work. As mentioned earlier, there has lately been a considerable amount of work on parallel job
scheduling and we shall restrict ourselves to the subset most closely related to the topic of this paper. In
particular, we will not discuss problems with malleable jobs or dedicated machines. We start by pointing out
remarkable differences in the behavior of classic machine scheduling problems and parallel job scheduling
problems.
While preemptive scheduling of parallel jobs is NP-hard, even in the absence of release dates [8],
preemptive scheduling of non-parallel jobs (that is,
m
j
= 1
) can be solved in polynomial time [30, 23].
Graham [17] showed that every listscheduling algorithm is a
(2
1
=m
)
–approximation algorithm for the
strongly NP-hard problem of scheduling non-parallel jobs without release dates, P
j j
C
max
. Gusfield [20]
and Hall and Shmoys [21] observed that Graham’s result holds for non-parallel jobs with release dates,
P
j
r
j
j
C
max
, as well. If non-parallel jobs are scheduled in non-increasing order of their lengths, listschedul-
ing is a
((4
m
1)
=
3
m
)
–approximation algorithm for P
j j
C
max
, see [18], and a
3
=
2
–approximation algorithm
for P
j
r
j
j
C
max
, see [6]. Hochbaum and Shmoys [22] and Hall and Shmoys [21] gave polynomial-time ap-
proximation schemes for the problems P
j j
C
max
and P
j
r
j
j
C
max
, respectively. In contrast, there is no
approximation algorithm with performance guarantee better than
3
=
2
for P
j
m
j
j
C
max
, unless P
=
NP.
It follows from the work of Garey and Graham [15] on project scheduling with resource constraints that
listscheduling has performance guarantee
2
for scheduling parallel jobs without release dates, P
j
m
j
j
C
max
.
Turek, Wolf and Yu [36] presented a direct, simplified proof of this result. Feldmann, Sgall and Teng [13]
observed that the length of a non-preemptive listschedule is actually at most
2
1
=m
times the opti-
mal preemptive makespan. This implies that there is a
(3
1
=m
)
–approximation algorithm for both,
P
j
m
j
; r
j
;
pmtn
j
C
max
and P
j
m
j
; r
j
j
C
max
(see also [31]).
A problem closely related to P
j
m
j
j
C
max
is strip packing, sometimes also called orthogonal packing in
two dimensions. In contrast to the model considered here, machines assigned to a job need to be contiguous
in a solution to the strip packing problem. Turek, Wolf and Yu [36] pointed out that there is indeed advantage
to using non-contiguous machine assignments (in terms of the length of an optimal schedule). ¿From a
parallel computer architecture perspective, P
j
m
j
j
C
max
corresponds to scheduling on a PRAM, while strip-
packing is equivalent to scheduling on a linear array of processors [29]. The strip packing problem was
first posed by Baker, Coffman, and Rivest [3]. Various authors proposed approximation algorithms with
2
performance guarantees
3
[3, 7, 16],
2
:
7
[7],
2
:
5
[34], and
2
[35], respectively. Kenyon and Remila [27] gave
an asymptotic fully polynomial-time approximation scheme when
m
is fixed.
If no network topology is specified (PRAM) and the number
m
of machines is fixed, P
m
j
m
j
;
pmtn
j
C
max
can be solved as a linear programming problem in polynomial time [4]. Jansen and Porkolab [25] presented
an algorithm with running time O
(
n
) +
poly
(
m
)
for the same problem, thereby showing that it cannot be
strongly NP-hard, unless P
=
NP. They also gave a polynomial-time approximation scheme for the non-
preemptive problem with a fixed number of machines, P
m
j
m
j
j
C
max
, see [24]. Du and Leung [10] showed
that this problem is strongly NP-hard for
m
>
5
.
In scheduling, one typically distinguishes between three basic online models, each characterized by a
different dynamics of the situation (see, e.g., [32]). In the model “jobs arriving over time”, the characteristics
of a job become known when the job becomes known, which happens at its release date. In contrast, in the
model “unknown running times”, the processing time of a job remains unknown until it is completed. In the
third online model “scheduling jobs one by one”, jobs arrive one after the other, and the current job needs to
be (irrevocably) scheduled before the next job and all its characteristics become known.
Listscheduling complies with the requirements of both online models “unknown running times” and
“jobs arriving over time”. Therefore, listscheduling is a
2
–competitive algorithm for P
j
m
j
j
C
max
for the
model “unknown running times” without release dates, and its extension to P
j
m
j
; r
j
j
C
max
is
3
–competitive
for both models “unknown running times” and “jobs arriving over time”. Shmoys, Wein and Williamson [33]
showed that there is no deterministic online algorithm with a better competitive ratio than
2
1
=m
for the
online model “unknown running times”, even if every job requires only one machine and arrives at time zero.
Also for the non-parallel job case, Chen and Vestjens [6] proved a lower bound of
1
:
347
for the competitive
ratio of any deterministic non-preemptive online algorithm for the online model “jobs arriving over time”.
For the online model “scheduling jobs one by one”, the best-known competitive ratio for scheduling non-
parallel jobs is achieved by an algorithm of Albers [1], which is
1
:
923
–competitive. She also proved that
there is no deterministic online algorithm with a better competitive ratio than
1
:
852
. Fleischer and Wahl [14]
presented an algorithm with competitive ratio
1
:
9201
for
m
! 1
, which for
m
>
64
has a better competitive
ratio than Albers’ algorithm. No algorithm with constant competitive ratio was known for parallel jobs and
the online model “scheduling jobs one by one”. Of course, the lower bound by Albers applies to the setting
with parallel jobs as well.
Main results. Whenever a machine falls idle or a job is released, a listscheduling algorithm schedules the
first job from a given priority list that is already released and does not require more machines than are avail-
able. In preemptive listscheduling, jobs with lower priority can be preempted by jobs with higher priority. We
extend the study of this class of greedy-like algorithms, which was started for parallel-job scheduling in [36],
to the following directions. For P
j
m
j
; r
j
;
pmtn
j
C
max
, preemptive
m
j
–listscheduling, that is, preemptive
listscheduling where jobs are in order of non-increasing widths, constructs a schedule that is at most
2
1
=m
times as long as an optimal preemptive schedule. The analysis is presented in Section 3. In Section 4, we
show that for both P
j
m
j
; r
j
j
C
max
and P
j
m
j
; r
j
;
pmtn
j
C
max
, any non-preemptive listscheduling algo-
rithm produces a schedule with makespan at most twice the makespan of an optimal preemptive schedule.
Both results are obtained by a novel way of directly comparing the listschedule with the structure of an op-
timal preemptive schedule. Not only do they improve upon recent
3
–approximation algorithms by Mu’alem
and Feitelson [31], but we also provide an instance of P
j
m
j
; r
j
j
C
max
that is simultaneously bad for all
possible priority lists. That is, no variant of listscheduling can achieve a better performance guarantee than
2
for this problem.
While it is not difficult to see that all listscheduling algorithms with no specific ordering of the list
3
also work in the online settings “unknown running times” and “jobs arriving over time” with corresponding
competitive ratios, no listscheduling algorithm has a constant competitive ratio in the context of “scheduling
jobs one by one”. In Section 5, we present the first online algorithm with constant competitive ratio for
scheduling parallel jobs one by one. We also show that no deterministic online algorithm has a competitive
ratio smaller than
2
:
25
. These results are again in sharp contrast to non-parallel job scheduling for which it
already follows from Graham’s work [17] that listscheduling is
(2
1
=m
)
–competitive.
2 Preliminaries
In this section, we briefly discuss the limits of approximability for some parallel job scheduling problems as
well as the running time of listscheduling algorithms.
The problem of non-preemptively scheduling parallel jobs of length one to minimize makespan
(P
j
m
j
; p
j
= 1
j
C
max
) is equivalent to the strongly NP-hard BIN PACKING problem, as was observed
in [4]. It follows that there is no approximation algorithm for scheduling parallel jobs to minimize makespan
with performance guarantee better than
3
=
2
, unless P
=
NP. Moreover, in contrast to BIN PACKING, item
sizes (i.e., lengths of jobs) can be scaled. Therefore, we can state the following theorem.
Theorem 2.1. There is no polynomial-time algorithm that produces for every instance of P
j
m
j
j
C
max
a
schedule with makespan at most
C
max
+
with
<
3
=
2
and
constant, unless P
=
NP. Here,
C
max
denotes the optimal makespan.
Li [28] gave a polynomial-time algorithm with asymptotic performance guarantee of
31
=
18
for P
j
m
j
j
C
max
.
Drozdowski [8] observed that if all jobs have length one then the existence of a preemptive schedule of
length two implies the existence of a non-preemptive schedule of length two as well. Thus, preemptive
scheduling of parallel jobs with length one and therefore P
j
m
j
;
pmtn
j
C
max
does not have a better than
3
=
2
–approximation algorithm either, unless P
=
NP.
It is well-known that listscheduling algorithms for classic (i.e., non-parallel) job scheduling problems
can easily be implemented in polynomial time. However, one needs to be more careful for parallel job
scheduling problems because we may not assume that the number
m
of machines is at most the number
n
of jobs. Therefore, any polynomial-time scheduling algorithm that outputs job-machine assignments has to
find a compact way of encoding this output since not
m
, but
log
m
is part of the input size (as machines are
identical). The following lemma ensures that we may safely restrict ourselves to algorithms that specify the
starting times of jobs.
Lemma 2.2. Let
S
be a feasible schedule for an instance of the problem P
j
m
j
; r
j
j
C
max
, given by job
starting times. Then, there is a polynomial-time algorithm that computes a feasible assignment of jobs to
machines (without changing the starting times of jobs). In particular, the job-machine assignment can be
represented with polynomial size.
Sketch of proof. Let
t
1
< t
2
<

< t
z
be the different starting times of the jobs in
S
. Let
i
1
< i
2
<

<
i
m
t
be the idle machines in
S
at time
t
and let
j
1
; j
2
;::: ;j
n
t
be the jobs that start at time
t
(
t
=
t
1
;::: ;t
z
)
.
We assign the jobs
j
1
;::: ;j
n
t
to the machines
i
1
;::: ;i
m
t
in the following way. Job
j
1
is assigned to the
first
m
j
1
machines in
f
i
1
;::: ;i
m
t
g
, job
j
2
is assigned to the next
m
j
2
machines in
f
i
1
;::: ;i
m
t
g
, and so on.
Then one can show that for every point
t
=
t
1
;::: ;t
z
in time there are no more than
n
+ 1
machine-intervals.
Here, a machine-interval is a set of consecutive machines (in the order
1
;
2
;::: ;m
) of maximal cardinality
such that all machines in this set are processing the same job. In particular, a machine-interval is completely
4
specified by (the index of) its first and its last machine. Hence, we will output for every
t
2 f
t
1
;::: ;t
z
g
the
set of machine-intervals with the corresponding jobs.
In particular, the non-preemptive listscheduling algorithm described in Section 1 computes a feasible sched-
ule (including job-machine assignments) in polynomial time. For preemptive listscheduling, it is not neces-
sary to invoke Lemma 2.2. At any event (release date or completion time of a job), one can simply interrupt
the processing of all jobs and then newly assign each job (highest priorities first) to consecutive machines.
Clearly, the total number of preemptions is bounded from above by
2
n
and the job-machine assignments can
again be compactly described. Note also that preemptive listscheduling only preempts at integer points in
time, whereas an optimal preemptive schedule may not.
3 Preemptive listscheduling of parallel jobs with release dates
We now present a
2
–approximation algorithm for scheduling parallel jobs with release dates when preemp-
tions are allowed. More specifically, we prove that preemptive
m
j
–listscheduling delivers for all instances
of P
j
m
j
; r
j
;
pmtn
j
C
max
a schedule that is at most
(2
1
=m
)
times as long as an optimal preemptive
schedule. The algorithm works as follows. At every decision point (i.e., release date or completion time) all
currently running jobs are preempted. Then, the already released, but not yet completed jobs are considered
in order of non-increasing widths
m
j
and as many of them are greedily assigned to the machines as feasibly
possible.
Theorem 3.1. For every instance of P
j
m
j
; r
j
;
pmtn
j
C
max
, the length of the schedule constructed by the
preemptive
m
j
–listscheduling algorithm is at most
(2
1
=m
)
times the optimal makespan
C
max
.
Proof. Let
e
be the job that determines the makespan in the preemptive listschedule, and let
C
e
be its com-
pletion time. We divide the time horizon
(0
; C
e
℄
into intervals
(
t; t
+ 1℄
of length one
(
t
= 0
;
1
;::: ;C
e
1)
.
We call such an interval time-slot. We distinguish two cases.
Case 1:
m
e
> m=
2
.
Let
r
z
be the minimal point in time after which every time-slot contains a wide job (i.e., a job
j
with
m
j
> m=
2
) in the
m
j
–listschedule. It follows from the definition of
m
j
–listscheduling that
r
z
is the min-
imal release date of all jobs with
m
j
> m=
2
that are scheduled in this last contiguous block of time-slots
with wide jobs. Hence,
r
z
plus the total processing time of wide jobs in this block is a lower bound for
C
max
.
Thus,
C
e
=
r
z
+ (
C
e
r
z
)
6
C
max
, and the listschedule is optimal in this case.
Case 2:
m
e
6
m=
2
.
Suppose
C
e
>
(2
1
=m
)
C
max
. Let
r
z
be the minimal point in time from which on every time-slot contains
a job
j
with
m
j
>
m
e
in the listschedule. By definition,
r
z
is the minimal release date of all jobs with
m
j
>
m
e
that are scheduled in this last contiguous block of time-slots containing jobs as least as wide as
e
.
Consequently, all these jobs have to be scheduled after
r
z
in the optimal schedule as well. Thus, the total
load of jobs to be processed in a space of
(
C
max
r
z
)
m
is strictly more than
(
r
e
r
z
)
m
e
+ (
C
max
(2
1
=m
)
r
e
p
e
) (
m
m
e
+ 1) +
p
e
m
e
:
The first term in the summation results from jobs
j
with
m
j
>
m
e
scheduled prior to the time at which
e
is released, and from the definition of
r
z
. The second term accounts for the time-slots after the release date
5
of job
e
in which
e
is not scheduled. Finally, the third term is the load produced by
e
itself. The following
calculation shows that this is too much load for so little space.
(
C
max
r
z
)
m >
(
r
e
r
z
)
m
e
+ (2
C
max
C
max
m
r
e
p
e
)(
m
m
e
+ 1) +
p
e
m
e
,
r
z
m > m
(
C
max
r
e
p
e
) + 2
m
e
(
C
max
+
r
e
+
p
e
) + (
C
max
r
e
p
e
) +
C
max
m
(
m
e
1)
r
z
m
e
,
r
z
(
m
m
e
)
<
(
C
max
r
e
p
e
)(2
m
e
m
)
(
C
max
r
e
p
e
)
C
max
m
(
m
e
1)
While the term on the left-hand side is non-negative because
m
e
6
m=
2
, the right-hand side is non-positive
because
C
max
r
e
p
e
>
0
. Therefore, we have a contradiction and
C
e
6
(2
1
=m
)
C
max
.
It is not hard to show that this approximation bound of
(2
1
=m
)
for (preemptive) listscheduling of (par-
allel) jobs to minimize makespan is tight. The following instance was already proposed by Graham [17]
to show that listscheduling for non-parallel jobs without release dates has no better performance guarantee
than
2
1
=m
.
Example 3.2. Consider an instance with
m
2
m
+1
unit-width jobs,
m
2
m
of length one, and the last job in
the list with length
m
. The resulting schedule will have no preemptions and has length
m
1 +
m
= 2
m
1
,
while the optimal (preemptive) schedule has makespan
m
.
4 Non-preemptive listscheduling of parallel jobs with release dates
The following result gives a universal performance guarantee of
2
for all non-preemptive listscheduling
algorithms, regardless which priority list is used. It holds for both the preemptive and the non-preemptive
version of the problem.
Theorem 4.1. For every instance of the problems P
j
m
j
; r
j
;
(pmtn)
j
C
max
, the length of the schedule con-
structed by any non-preemptive listscheduling-algorithm is at most twice the optimal preemptive makespan.
Proof. Let OPT be an optimal preemptive schedule for a given instance. Let
C
O P T
max
be the makespan of OPT.
We partition the time horizon into periods of same length, such that all jobs in OPT are started, preempted,
re-started and completed only at the beginning or the end of a period. By scaling, we may assume that such
a period starts at time
s
1
and ends at time
s
(for some non-negative integer
s
), and is of unit length. We
call it time-slot
s
. The part of job
j
in one time-slot is called slice of
j
. The release date of a slice is the
release date of its job. A slice of job
j
is wide if
m
j
> m=
2
, and it is called small, otherwise. The proof
will refer to slices of jobs instead of jobs since this is the level of granularity needed to prove the result. In
particular, we will also identify the slices of jobs in the listschedule. Let
LS
be the schedule constructed by
the listscheduling-algorithm, and let
C
LS
max
be its makespan.
Two disjoint sets of time-slots
E
1
and
E
2
of equal size (
j
E
1
j
=
j
E
2
j
) can be matched if the total load of
all slices in
E
1
[
E
2
exceeds
E
1
m
.
Among others, we make use of the following trivial lower bounds for the optimal makespan:
C
O P T
max
>
1
m
n
X
j
=1
p
j
m
j
;
(1)
6
C
O P T
max
>
r
j
+
p
j
, for all
j
= 1
;::: ;n :
(2)
Let
0 =
r
0
< r
1
< r
2
<

< r
z
be the different release dates of the given instance. For
k
= 0
;::: ;z
, let
D
(
r
k
)
be the set of time-slots in
LS
after
r
k
that contain wide slices, which are completed in OPT before
r
k
.
In particular,
D
(
r
0
) =
;
. These sets have the following three properties.
Observation 1.
D
(
r
h
)
\ f
r
k
+ 1
;::: ;C
LS
max
g
D
(
r
k
)
for
0
6
h < k
6
z
.
Observation 2. For every set
D
D
(
r
k
)
we define the bipartite graph
B
(
D
)
in the following way. For
every time-slot
h
2 f
(
r
k
j
D
j
+ 1)
;::: ;r
k
g
we introduce one node on the left side of the graph
B
(
D
)
. For
every time-slot
d
2
D
we introduce one node on the right side of the graph
B
(
D
)
. A node
h
on the left side
of
B
(
D
)
and a node
d
on the right side of
B
(
D
)
are adjacent if and only if the wide slice in the time-slot
d
is released before
h
, that is
r
d
6
h
1
. Then
B
(
D
)
contains a perfect matching.
Observation 3. The inequality
j
D
(
r
k
)
j
6
r
k
holds for all
k
= 0
;::: ;z
.
We denote by
S
(
r
k
)
the set of time-slots
f
1
;::: ;r
k
g [
D
(
r
k
)
, for each
k
= 1
;::: ;z
. Let
S
(
r
0
) =
;
and
let
S
(
C
LS
max
)
be the set of all time-slots in
LS
, thus
S
(
C
LS
max
) =
f
1
;::: ;C
LS
max
g
. We define the load of a set
of time-slots as the sum of the loads of all slices in these time-slots.
Observation 4. For all
0
6
h < k
6
z
we have
(
S
(
C
LS
max
)
n
S
(
r
k
))
\
(
S
(
r
k
)
n
S
(
r
h
)) =
;
. Moreover,
(
S
(
C
LS
max
)
n
S
(
r
k
))
[
(
S
(
r
k
)
n
S
(
r
h
)) =
S
(
C
LS
max
)
n
S
(
r
h
)
.
Observation 5. If there exists a
k
6
z
with
S
(
C
LS
max
)
n
S
(
r
k
) =
;
, then the claim of Theorem 4.1 is true.
Reason: If
S
(
C
LS
max
)
n
S
(
r
k
) =
;
for a
k
6
z
, then all time-slots between the time
r
k
and
C
LS
max
are part of
D
(
r
k
)
, therefore
C
LS
max
=
r
k
+
j
D
(
r
k
)
j
. On the other hand,
C
O P T
max
> r
k
and
C
O P T
max
>
j
D
(
r
k
)
j
. This implies
C
O P T
max
>
r
k
+
j
D
(
r
k
)
j
2
=
C
LS
max
2
.
Therefore, we assume henceforth that
S
(
C
LS
max
)
n
S
(
r
k
)
6
=
;
for all
k
6
z
.
We can also exclude for every release date
r
k
,
k
= 1
;::: ;z
, the case that the time-slot
r
k
is empty in
LS
,
since in this case all subsequent jobs would not be released before time
r
k
, and we could consider the re-
maining part of
LS
separately.
We consider the following two cases for
C
LS
max
: Either there is a release date
r
h
,
h
2 f
0
;::: ;z
g
, such that
there is more load than
j
S
(
C
LS
max
)
n
S
(
r
h
)
j
m
2
in
S
(
C
LS
max
)
n
S
(
r
h
)
, or there is no such release date.
Case 1. There is no release date
r
h
,
h
2 f
0
;::: ;z
g
, such that the load in
S
(
C
LS
max
)
n
S
(
r
h
)
is more than
j
S
(
C
LS
max
)
n
S
(
r
h
)
j
m
2
.
It follows that the load in
S
(
C
LS
max
)
n
S
(
r
z
)
cannot be more than
j
S
(
C
LS
max
)
n
S
(
r
z
)
j
m
2
. Together with Observa-
tion 5, this implies that there is a time-slot in
S
(
C
LS
max
)
n
S
(
r
z
)
f
r
z
+ 1
;::: ;C
LS
max
g
containing a small
job. Let
e
be a small job in
S
(
C
LS
max
)
n
S
(
r
z
)
that completes last. Let
r
e
be the release date,
s
e
the start time
and
C
e
the completion time of
e
. The load in
S
(
C
LS
max
)
n
S
(
r
e
)
is at most
j
S
(
C
LS
max
)
n
S
(
r
e
)
j
m
2
.
We partition the set
S
(
C
LS
max
)
n
S
(
r
e
)
into the disjoint sets
E
,
E
:=
E
1
[
E
2
, and
~
E
. Let
E
be the set
of time-slots in
S
(
C
LS
max
)
n
S
(
r
e
)
containing a slice of
e
. Let
E
1
be the set of time-slots in
E
before the
date
r
z
, and let
E
2
be the set of time-slots in
E
after
r
z
. Notice that
E
2
6
=
;
. Let
E
be the set of time-slots
in
S
(
C
LS
max
)
n
S
(
r
e
)
containing no slice of
e
and which are before
r
z
. Let
~
E
be the set of time-slots in
S
(
C
LS
max
)
n
S
(
r
e
)
, which do not contain a slice of
e
and which come after
r
z
. Finally,
D
e
r
e
is the set of all
7
time-slots between
r
e
and
r
z
that contain a slice of
e
, but which are not element of the set
S
(
C
LS
max
)
n
S
(
r
e
)
,
and hence not part of the set
E
.
Observation 6. More than
m
2
machines are busy in every time-slot in
E
. Moreover, any two time-slots
s
1
2
E
and
s
2
2
E
can be matched.
Reason: Job
e
with
m
e
6
m
2
is released at date
r
e
, but is started at time
s
e
only. Therefore, at least
m
m
e
+ 1
machines are busy at any time between
r
e
and
s
e
.
Observation 7. In every time-slot
s
1
2
~
E
more than
m
2
machines are busy. Any two time-slots
s
1
2
~
E
and
s
2
2
E
2
can be matched.
Reason: Since job
e
with
m
e
6
m
2
is released at time
r
e
, but started only at time
s
e
, the statement is clearly
true for all time-slots
s
1
before
s
e
. Each time-slot
s
1
2
~
E
after
C
e
contains a wide slice. We consider now a
time-slot
s
2
2
E
2
. Either
s
2
contains a slice of the wide job from
s
1
or the wide job could not be processed
in time-slot
s
2
although it was already released, because too many machines are busy in
s
2
. In both cases
the toal number of busy machines in both time-slots exceeds
m
.
Let us consider the set
S
(
C
LS
max
)
n
S
(
r
z
)
. We partition the time-slots between date
r
z
and
C
LS
max
, that are
part of the set
S
(
C
LS
max
)
n
S
(
r
e
)
, but not part of the set
S
(
C
LS
max
)
n
S
(
r
z
)
, and which are therefore part of the
set
D
(
r
z
)
, into two disjoint sets. The ones that contain a slice of
e
form the set
D
E
r
z
, and those without a slice
of
e
form the set
D
~
E
r
z
. Thus we have
D
E
r
z
=
E
2
\
D
(
r
z
)
and
D
~
E
r
z
=
~
E
\
D
(
r
z
)
. Each time-slot in
D
E
r
z
[
D
~
E
r
z
contains a wide slice. We have therefore partitioned the set
S
(
C
LS
max
)
n
S
(
r
z
)
into the disjoint sets
E
2
n
D
E
r
z
and
~
E
n
D
~
E
r
z
. All jobs in
S
(
C
LS
max
)
n
S
(
r
z
)
are released not later than
r
z
. Observation 7 implies the following
insight.
Observation 8.
j
E
2
n
D
E
r
z
j
>
j
~
E
n
D
~
E
r
z
j
.
We distinguish four further cases with respect to the relationship between the size of the sets
E
and
E
1
and
the relationship between the size of the sets
E
2
and
~
E
.
Case 1.A:
j
~
E
j
<
j
E
2
j
.
Case 1.A.1:
j
E
j
>
j
E
j j
~
E
j
.
Observation 7 implies that the set
~
E
and any set of
j
~
E
j
many time-slots in
E
2
can be matched. Because of
Observation 6, the set of the remaining
j
E
2
j j
~
E
j
many unmatched time-slots in
E
2
, together with the time-
slots in
E
1
, can be matched with any set of
j
E
2
j j
~
E
j
+
j
E
1
j
=
j
E
j j
~
E
j
many time-slots in
E
. The number
of busy machines in any remaining unmatched time-slot in
E
exceeds
m
2
. Thus the set
S
(
C
LS
max
)
n
S
(
r
e
)
contains in total more load than
(
j
~
E
j
+
j
E
j j
~
E
j
)
m
+
(
j
E
jj
E
j
+
j
~
E
j
)
m
2
=
(
j
E
j
+
j
E
j
+
j
~
E
j
)
m
2
=
j
S
(
C
LS
max
)
n
S
(
r
e
)
j
m
2
,
which contradicts the assumption of Case 1.
Case 1.A.2:
j
E
j
<
j
E
j j
~
E
j
.
In this case, we have
j
E
j
>
j
S
(
C
LS
max
)
n
S
(
r
e
)
j
2
. With the lower bound (2) and Observation 3 follows
C
O P T
max
>
r
e
+
j
E
j
> r
e
+
j
S
(
C
LS
max
)
n
S
(
r
e
)
j
2
=
r
e
+
C
LS
max
r
e
j
D
(
r
e
)
j
2
=
C
LS
max
2
+
r
e
j
D
(
r
e
)
j
2
>
C
LS
max
2
, and Theorem 4.1 is
proved in this case.
Case 1.B:
j
~
E
j
>
j
E
2
j
.
Case 1.B.1:
j
E
j
>
j
E
1
j
.
Observation 7 shows that we can match any set of
j
E
2
j
many time-slots in
~
E
with the set
E
2
. Using Observa-
tion 6, we can match any set of
j
E
1
j
many time-slots in
E
with the time-slots in
E
1
. In each of the remaining
8
unmatched time-slots in
~
E
and
E
, more than
m
2
machines are busy. Thus the load in
S
(
C
LS
max
)
n
S
(
r
e
)
exceeds
(
j
E
1
j
+
j
E
2
j
)
m
+
(
j
E
jj
E
1
j
)
m
2
+
(
j
~
E
jj
E
2
j
)
m
2
=
(
j
E
j
+
j
E
j
+
j
~
E
j
)
m
2
=
j
S
(
C
LS
max
)
n
S
(
r
e
)
j
m
2
. This is in contradiction
to the assumption of Case
1
.
Case 1.B.2:
j
E
j
<
j
E
1
j
.
We denote the set of the first
j
E
j
time-slots in
E
1
by
E
1
1
. Observation 6 implies that
E
1
1
can be matched
with
E
. With Observations 7 and 8 follows that any set of
j
~
E
n
D
~
E
r
z
j
many time-slots in
E
2
n
D
E
r
z
can
be matched with the time-slots in
~
E
n
D
~
E
r
z
. Furthermore,
j
D
E
r
z
j
<
j
D
~
E
r
z
j
because of
j
~
E
j
>
j
E
2
j
and
Observation 8. Therefore, the set
D
E
r
z
can be matched with any set of
j
D
E
r
z
j
many time-slots in
D
~
E
r
z
.
Since
j
E
2
j
6
j
~
E
j
, we obtain the following inequality:
j
D
~
E
r
z
j j
D
E
r
z
j
>
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
. Hence, there
are
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
many time-slots in the remaining
j
D
~
E
r
z
j j
D
E
r
z
j
many time-slots in
D
~
E
r
z
that can be
matched with the set of the remaining
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
many time-slots in
E
2
n
D
E
r
z
. Let
D
r est
be the set
of the
j
D
~
E
r
z
j j
D
E
r
z
j
(
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
)
many presently unmatched time-slots in
D
~
E
r
z
. By Observation 2,
there is a set
D
math
r est
of time-slots in
f
r
z
(
j
D
~
E
r
z
j j
D
E
r
z
j
(
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
)) + 1
;::: ;r
z
g
that can be
matched with
D
r est
. We combine the time-slots in
D
~
E
r
z
that are matched with a time-slot in
D
(
r
e
)
\
D
math
r est
,
thus with a time-slot in
D
e
r
e
, which is therefore not part of the set
S
(
C
LS
max
)
n
S
(
r
e
)
, in the set
D
spar e
. The load
in
S
(
C
LS
max
)
n
S
(
r
e
)
is at most
j
S
(
C
LS
max
)
n
S
(
r
e
)
j
m
2
. Since every time-slot in
D
spar e
contains more load than
m
2
,
it follows that the load in
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
is bounded from above by
j
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
j
m
2
.
If every time-slot in
E
1
n
E
1
1
has been matched with a time-slot in
D
r est
, then every time-slot in
E
has
been matched with another time-slot in
((
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
)
n
E
. Each of the remaining time-slots
in
((
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
)
n
E
contains more than
m
2
load. Thus,
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
contains
more load than
j
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
j
m
2
, which is a contradiction.
We may therefore assume that there is at least one time-slot in
E
1
n
E
1
1
that has not been matched with
a time-slot in
D
r est
. Consequently,
j
D
spar e
j
6
j
D
e
r
e
j
. Furthermore,
j
E
j
>
j
E
j
+
j
~
E
n
D
~
E
r
z
j
+
j
D
E
r
z
j
+
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
+ (
j
D
~
E
r
z
j j
D
E
r
z
j
(
j
E
2
n
D
E
r
z
j j
~
E
n
D
~
E
r
z
j
))
j
D
spar e
j
=
j
E
j
+
j
~
E
j j
D
~
E
r
z
j
+
j
D
E
r
z
j
+
j
E
2
j j
D
E
r
z
j j
~
E
j
+
j
D
~
E
r
z
j
+
j
D
~
E
r
z
j j
D
E
r
z
j j
E
2
j
+
j
D
E
r
z
j
+
j
~
E
j j
D
~
E
r
z
j j
D
spar e
j
=
j
E
j
+
j
~
E
j j
D
spar e
j
.
It follows that
j
E
j
>
j
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
j
2
, and with (2) we conclude that
C
O P T
max
>
r
e
+
j
E
j
+
j
D
e
r
e
j
>
r
e
+
j
D
e
r
e
j
+
j
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
j
2
=
r
e
+
j
D
e
r
e
j
+
C
LS
max
2
r
e
2
j
D
(
r
e
)
j
2
j
D
spar e
j
2
>
C
LS
max
2
+
r
e
j
D
(
r
e
)
j
2
+
j
D
e
r
e
jj
D
spar e
j
2
>
C
LS
max
2
, and herewith the correctness of Theorem 4.1 in this case.
A schematic illustration of the relevant part of the listschedule
LS
for this case is given in Figure 1. The red
bar underneath the picture indicates the time-slots from the set
S
(
r
e
)
(that are visible in this part of
LS
). The
blue bar marks the time-slots in
S
(
C
LS
max
)
and the green bars mark the time-slots from the set
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
. The red bar within
LS
corresponds to the job
e
. Sets of hatched time-slots with same color
have been matched.
9
00
00
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
11
11
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
0000
0000
0000
1111
1111
1111
0000
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
1111
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
0000
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
1111
000
000
000
000
000
000
000
000
000
000
000
111
111
111
111
111
111
111
111
111
111
111
0000
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
1111
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
00
00
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
11
11
0000
0000
0000
1111
1111
1111
0000
0000
0000
1111
1111
1111
00
00
00
11
11
11
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
000
000
000
000
000
000
000
000
000
000
000
111
111
111
111
111
111
111
111
111
111
111
00
00
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
11
11
00
00
00
11
11
11
000
000
000
111
111
111
| {z }
D
math
r est
r
z
r
e
s
e
C
e
e
C
LS
max
E
z}| {
| {z }
E
1
1
E
1
z}| {
| {z }
D
e
r
e
E
2
z}| {
~
E
z }| {
| {z }
D
E
r
z
|{z }
D
~
E
r
z
D
spar e
| {z }
D
r est
|{z }
E
2
n
D
E
r
z
|{z }
~
E
n
D
~
E
r
z
(
S
(
C
LS
max
)
n
S
(
r
e
))
n
D
spar e
S
(
r
e
)
S
(
C
LS
max
)
Figure 1: Illustration of Case 1.B.2.
Case 2. There is a release date
r
h
< C
LS
max
such that
S
(
C
LS
max
)
n
S
(
r
h
)
contains more load than
j
S
(
C
LS
max
)
n
S
(
r
h
)
j
m
2
.
Let
r
k
be the smallest release date of this kind. If
r
k
= 0
, the theorem follows from (1). Let us therefore
assume that
r
k
>
0
.
Observation 9.
S
(
r
k
)
n
S
(
r
h
)
6
=
;
, for every release date
r
h
< r
k
.
Reason: If
S
(
r
k
)
n
S
(
r
h
) =
;
for
r
h
< r
k
, Observation 4 implies
S
(
C
LS
max
)
n
S
(
r
h
) = (
S
(
C
LS
max
)
n
S
(
r
k
))
[
(
S
(
r
k
)
n
S
(
r
h
)) =
S
(
C
LS
max
)
n
S
(
r
k
)
. Since
S
(
C
LS
max
)
n
S
(
r
k
)
contains more load than
j
S
(
C
LS
max
)
n
S
(
r
k
)
j
m
2
,
it follows that the set
S
(
C
LS
max
)
n
S
(
r
h
)
contains more load than
j
S
(
C
LS
max
)
n
S
(
r
h
)
j
m
2
, a contradiction to the
definition of
r
k
.
Observation 10. The load of the set
S
(
r
k
)
n
S
(
r
h
)
is at most
j
S
(
r
k
)
n
S
(
r
h
)
j
m
2
, for every release date
r
h
< r
k
.
Reason: If the load in
S
(
r
k
)
n
S
(
r
h
)
was more than
j
S
(
r
k
)
n
S
(
r
h
)
j
m
2
, we would be able, with the help of
Observation 4, to merge the loads in
S
(
r
k
)
n
S
(
r
h
)
and
S
(
C
LS
max
)
n
S
(
r
k
)
. The cumulated load in
S
(
C
LS
max
)
n
S
(
r
h
)
would then exceed
j
S
(
C
LS
max
)
n
S
(
r
h
)
j
m
2
, a contradiction to the definition of
r
k
.
Observation 11. Every wide slice in
S
(
C
LS
max
)
n
S
(
r
k
)
is processed in OPT after
r
k
.
Reason: The wide slices, which are processed in OPT before
r
k
, but in
LS
after
r
k
, are included in
D
(
r
k
)
and therefore not part of the set
S
(
C
LS
max
)
n
S
(
r
k
)
.
If all small slices in
S
(
C
LS
max
)
n
S
(
r
k
)
are not released before
r
k
, Observation 11 and the assumption of Case 2
imply
C
O P T
max
> r
k
+
j
S
(
C
LS
max
)
n
S
(
r
k
)
j
2
>
C
LS
max
2
, and we are done.
10
We henceforth assume that there is at least one small job in
S
(
C
LS
max
)
n
S
(
r
k
)
which has been released
before
r
k
. We call such small jobs, which are released before
r
k
but completed by the listscheduling-
algorithm after
r
k
out-jutting jobs.
Let
~
j
be the minimum of the number of slices after
r
k
of an out-jutting job
j
and the number of time-slots
between
r
j
and
r
k
that contain no slice of
j
. Thus,
~
j
is an upper bound of the number of slices of job
j
, which
are processed in
LS
after
r
k
, but in OPT possibly before
r
k
. Let
u
be an out-jutting job for which this bound
is maximal among all out-jutting jobs. Let
~
D
bef or e
r
u
be the set of time-slots in
D
(
r
u
)
\ f
r
u
+ 1
;::: ;r
k
g
which contain no slice of
u
. Let
D
bef or e
r
u
be the set of time-slots in
D
(
r
u
)
\ f
r
u
+ 1
;::: ;r
k
g
that contain a
slice of
u
. Let
D
af ter
r
u
:=
D
(
r
u
)
\ f
r
k
+ 1
;::: ;C
LS
max
g
. We partition the time-slots between date
r
u
and
r
k
into the disjoint sets
U
,
U
,
~
D
bef or e
r
u
, and
D
bef or e
r
u
. Let
U
be the set of time-slots in
f
r
u
+ 1
;::: ;r
k
g n
D
bef or e
r
u
that contain a slice of the job
u
. Let
U
be the set of time-slots in
f
r
u
+ 1
;::: ;r
k
g n
~
D
bef or e
r
u
that do not
contain a slice of the job
u
. Hence, the set
f
r
u
+ 1
;::: ;r
k
g [
(
D
(
r
k
)
n
D
af ter
r
u
)
is composed of the disjoint
sets of time-slots
U
,
U
,
~
D
bef or e
r
u
,
D
bef or e
r
u
, and
D
(
r
k
)
n
D
af ter
r
u
.
Observation 12. The term
j
U
j
+
j
~
D
bef or e
r
u
j
is an upper bound for
~
u
.
Observation 13. We have
~
u
+
j
D
(
r
k
)
j
< r
k
.
Reason: Because of Observation 10, the set
S
(
r
k
)
n
S
(
r
u
)
contains at most
j
S
(
r
k
)
n
S
(
r
u
)
j
m
2
load. Together,
more than
m
machines are busy in each pair of time-slots
s
1
2
U
and
s
2
2
U
since there is no slice of
job
u
in
s
1
although job
u
was already released. Moreover, more than
m
m
u
>
m
2
machines are busy in
each time-slot in
U
and
~
D
bef or e
r
u
. Since each time-slot in
D
(
r
k
)
n
D
af ter
r
u
contains a wide slice, more than
m
2
machines are busy in each of them. Because of Observation 2, for every time-slot
s
1
2
D
(
r
k
)
n
D
af ter
r
u
there
exists another time-slot
s
2
2 f
r
k
j
D
(
r
k
)
n
D
af ter
r
u
j
+ 1
;::: ;r
k
g
such that
s
1
and
s
2
can be matched. This
way at most
j
D
bef or e
r
u
j
many time-slots from
D
(
r
k
)
n
D
af ter
r
u
are matched with a time-slot in
D
bef or e
r
u
. We
combine those time-slots to the set
D
spar e
. We have
j
D
spar e
j
6
j
D
bef or e
r
u
j
. Since
S
(
r
k
)
n
S
(
r
u
)
contains at
most
j
S
(
r
k
)
n
S
(
r
u
)
j
m
2
load, it follows that
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
contains at most
j
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
j
m
2
load,
because every time-slot in
D
spar e
is loaded by more than
m
2
. The set
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
decomposes
into the disjoint sets
U
,
U
, and
(
D
(
r
k
)
n
D
af ter
r
u
)
n
D
spar e
. If
j
U
j
6
j
U
j
+
j
(
D
(
r
k
)
n
D
af ter
r
u
)
n
D
spar e
j
, we could
match every time-slot in
U
with another time-slot in
((
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
)
n
U
. The remaining time-slots
in
((
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
)
n
U
contain each more than
m
2
load. Thus the load in
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
would exceed
j
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
j
m
2
, in contradiction to our earlier observations regarding this set. We
conclude that
j
U
j
>
j
U
j
+
j
D
(
r
k
)
n
D
af ter
r
u
j j
D
bef or e
r
u
j
. Combining this inequality with Observation 12
and 3 results in
~
u
+
j
D
(
r
k
)
j
<
j
U
j
+
j
~
D
bef or e
r
u
j
+
j
D
bef or e
r
u
j
+
j
D
af ter
r
u
j
6
j
U
j
+
j
D
(
r
u
)
j
6
j
U
j
+
r
u
6
r
k
.
Observation 14. The sum of the widths of all out-jutting jobs is at most
m
2
.
Reason: If this would not be the case, the sum of the widths of all small jobs between
r
k
1
and
r
k
would
exceed
m
2
. But then there would be no time-slot between the release dates
r
k
1
and
r
k
that is filled with at
most
m
2
load. Using Observation 9, this is in contradiction to Observation 10 since it would follow that the
load in
S
(
r
k
)
n
S
(
r
k
1
)
exceeds
j
S
(
r
k
)
n
S
(
r
k
1
)
j
m
2
.
Let us consider the set
S
(
C
LS
max
)
n
S
(
r
k
)
. The load between
r
k
and
C
LS
max
, excluding the load in the time-slots
in
D
(
r
k
)
, is more than
(
C
LS
max
r
k
j
D
(
r
k
)
j
)
m
2
. It follows from Observations 11 and 14 that at most an amount
of
~
um
2
of this load can be processed in OPT before
r
k
. Therefore, the load in
LS
that has to be processed in
OPT after
r
k
exceeds
(
C
LS
max
r
k
j
D
(
r
k
)
j
)
m
2
~
um
2
. Consequently,
C
O P T
max
> r
k
+
C
LS
max
r
k
j
D
(
r
k
)
j
2
~
u
2
>
C
LS
max
2
.
11
A schematic illustration of the relevant part of the listschedule
LS
for this case is given in Figure 2. The
red bar underneath the picture indicates the time-slots from the set
S
(
r
u
)
, the blue bars mark the visible
time-slots in
S
(
r
k
)
, and the green bars mark the time-slots from the set
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
. The sets
of hatched time-slots with same color have been matched.
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
00
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
11
000
000
000
000
000
000
000
000
000
000
111
111
111
111
111
111
111
111
111
111
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
1111
1111
1111
1111
1111
1111
1111
1111
1111
1111
0000
0000
1111
1111
00
00
11
11
00
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
11
00
00
00
00
00
00
00
00
00
00
11
11
11
11
11
11
11
11
11
11
0000011111
0000011111
r
u
r
k
s
u
C
u
u
~
u
C
LS
max
U
z}| {
U
z }| {
|{z }
D
bef or e
r
u
|{z }
~
D
bef or e
r
u
|{z }
D
af ter
r
u
D
(
r
k
)
z}| {
D
spar e
(
S
(
r
k
)
n
S
(
r
u
))
n
D
spar e
S
(
r
u
)
S
(
r
k
)
Figure 2: Illustration of Case 2.
Therefore, the length of
LS
is less than two times the length of the optimal preemptive schedule OPT.
An immediate implication on the power of preemption is stated in the following corollary.
Corollary 4.2. For all instances of P
j
m
j
; r
j
;
pmtn
j
C
max
, an optimal non-preemptive schedule is at most
twice as long as an optimal preemptive schedule. This bound is tight.
Chen and Vestjens [6] proved the existence of a priority order that shows that listscheduling according to this
job order achieves a performance guarantee better than
2
for the problem with non-parallel jobs P
j
r
j
j
C
max
.
If longer jobs are considered first, the resulting
p
j
–listscheduling algorithm (also called LPT rule) is a
3
=
2
–
approximation algorithm for P
j
r
j
j
C
max
. In contrast, the following example shows that for non-preemptive
scheduling with parallel jobs and release dates, no listscheduling-algorithm has a performance guarantee
smaller than
2
, no matter which priority list is chosen.
Example 4.3. Let
m
be the number of machines. Let
m
3
jobs
d
= 1
;::: ;m
3
of length
p
d
= 1
and
width
m
d
=
m
be given. We call these jobs big jobs. The release date of each big job
d
= 1
;::: ;m
3
is
r
d
:=
d
. Let there also be
m
small jobs
k
= 1
;::: ;m
with length
2
and width
1
. The release date of a small
job is
r
k
:=
k
1
,
k
= 1
;::: ;m
. An optimal schedule has length
m
, by filling the time-slots
2
to
m
2
12
completely with big jobs and the last two time-slots with the small jobs. The first time-slot remains empty.
Each listscheduling-algorithm receives at time
0
only one job, namely the first small job to schedule. This job
thus starts at time
0
. At time
1
the listscheduling algorithm receives the second small job and the first big job.
Since there are not enough idle machines left to schedule the big job, it assigns the second small job to start
at time
1
. The same happens at the following point in times, one small job is still running, thus preventing
the start of big jobs and causing the next small job to be started. At time
m
+ 1
all small jobs are completed
and the big jobs can be started. The resulting schedule has length
m
+ 1 +
m
3 = 2
m
2
. Therefore, the
ratio between the makespan of any listscheduling algorithm and the optimal makespan is
2
2
=m
.
Note that the variant of listscheduling in which jobs are assigned to machines in order of their priorities
(sometimes called serial or job-based listscheduling) does not lead to improved performance guarantees
either, even if jobs are in order of non-increasing widths (Example 3.2) or non-increasing processing times
(Example 4.3). Job-based listscheduling for parallel job scheduling is further discussed in [26, 36].
5 Online scheduling of parallel jobs
In this section, we consider online scheduling of parallel jobs. In an online environment, parts of the input
data are not known in advance. We consider the following three models. In the model “scheduling jobs
one by one”, all jobs are given in a list and only the first job in the list is known to the scheduler. The next
job from the list becomes visible only after the pevious job was scheduled. Once a job is scheduled, its
assignment cannot be changed. The jobs do not have release dates. In the model “unknown running times”,
the processing time of a job becomes only known at its completion time. This model has two sub-variants,
with and without release dates. In the latter case, no information on jobs is known before their release dates.
In the model “jobs arriving over time”, jobs become fully known at their release date, but no information on
them is known beforehand.
Since listscheduling (without special ordering of the list) complies with the requirements of the online
model “unknown running times”, it follows from the work of Garey and Graham [15] that listscheduling is
2
–competitive in the context of the online model “unknown running times” for parallel jobs without release
dates. For the same model with release dates and for the online model “jobs arriving over time”, Theo-
rem 4.1 implies that listscheduling is
2
–competitive. Theorem 3.1 yields the
(2
1
=m
)
–competitiveness of
preemptive
m
j
–listscheduling for the preemptive versions of the online models “unknown running times”
and “jobs arriving over time”. Shmoys, Wein and Williamson [33] showed for all versions of the online
model “unknown running times” that there is no deterministic online algorithm with a better competitive
ratio than
2
1
=m
, even if all jobs are non-parallel.
For the online model “scheduling jobs one by one”, listscheduling achieves a competitive ratio of
2
1
=m
for non-parallel jobs [17]. In contrast, listscheduling of parallel jobs does not have a constant competitive
ratio, which follows, for example, from the instance given in the proof of Theorem 5.1 below. In fact, for
parallel jobs and the online model “scheduling jobs one by one” no algorithm with constant competitive ratio
was known heretofore, to the best of the author’s knowledge. We present in this section a deterministic
12
–
competitive algorithm. We show first, that
2
:
25
is a lower bound for the competitive ratio of any deterministic
online algorithm for the model “scheduling jobs one by one” with parallel jobs. This result shows again
that scheduling parallel jobs is significantly harder than scheduling non-parallel jobs. For non-parallel job
scheduling, deterministic online algorithms are known with a competitive ratio smaller than
2
[1, 14].
Theorem 5.1. No deterministic online algorithm for the online model “scheduling jobs one by one” of the
scheduling problem P
j
m
j
j
C
max
has a competitive ratio smaller than or equal to
2
:
25
.
13
Proof. Let
A
be any deterministic online algorithm for the model “scheduling jobs one by one” of P
j
m
j
j
C
max
with competitive ratio
2
:
25
. We construct an instance with a list in which jobs of width
1
and jobs of width
m
alternate. The length of each job is set in a way that it can start only after the completion time of the previous
job in the list. Let the number of machines be
m
:= 10
. The total number of jobs is at most
20
.
More specifically, let
k
i
be the
i
–th job of width
1
in the list, and let
d
i
be the
i
–th job of width
m
,
i
= 1
;::: ;m
. Let
z
k
i
be the delay introduced by
A
prior to starting job
k
i
. Similarly, let
z
d
i
be the delay
before
d
i
. Then, the job lengths are defined as follows:
p
k
1
:= 1
,
p
k
i
+1
:=
z
k
i
+
p
k
i
+
z
d
i
+ 1
, and
p
d
i
:= max
j <i
f
z
k
j
; z
d
j
; z
k
i
g
+ 1
.
The length of the schedule produced by algorithm
A
after the completion of job
k
i
is therefore
z
k
i
+
p
k
i
+
P
i
1
j
=1
(
z
k
j
+
p
k
j
+
z
d
j
+
p
d
j
)
, and it is
P
i
j
=1
(
z
k
j
+
p
k
j
+
z
d
j
+
p
d
j
)
after the completion of job
d
i
.
The length of an optimal schedule including all jobs from the list up to (and including) job
k
i
is at
most
p
k
i
+
P
i
1
j
=1
p
d
j
. If the instance ends with the
i
–th d-job, the length of an optimal schedule is at most
p
k
i
+
P
i
j
=1
p
d
j
.
We prove the lower bound of
2
:
25
for the competitive ratio by complete enumeration over the possible
delays
z
k
i
and
z
d
i
,
i
= 1
;::: ;
10
, introduced by algorithm
A
. Note that no delay can be too large because
the competitive ratio
2
:
25
must be satisfied at any time during the run of the algorithm (i.e., for every sub-
instance). A computer program showed that there is no way for
A
to create delays in such a manner that its
competitive ratio is
2
:
25
for all sub-instances.
Note that due to limited computational power (and/or poor design of the complete enumeration algorithm)
we could not improve this bound. We are certain that it can be strengthened. The following algorithm is the
first algorithm with a constant competitive ratio for scheduling parallel jobs one by one.
Algorithm 5.2.
1. Partition the time axis into the intervals
I
i
:= [2
i
;
2
i
+1
℄
,
i
= 0
;
1
;:::
.
2. Schedule the arriving job
j
of length
p
j
and width
m
j
in the earliest interval
I
i
that is more than twice as
long as
p
j
and in which job
j
can feasibly be scheduled, as follows:
2.1. If
m
j
> m=
2
, schedule job
j
as late as possible within
I
i
.
2.2. If
m
j
6
m=
2
, schedule job
j
as early as possible within
I
i
.
Theorem 5.3. The competitive ratio of Algorithm
5
:
2
for the online version “scheduling jobs one by one”
of the scheduling problem P
j
m
j
j
C
max
is smaller than
12
.
Proof. Let
S
be the schedule constructed by Algorithm 5.2. We denote by
C
S
max
the length of
S
and by
C
max
the optimal offline makespan. Let
I
`
= [2
`
;
2
`
+1
℄
be the last and therefore the longest non-empty interval
of
S
. Hence,
C
S
max
6
2
`
+1
1
.
We distinguish two cases depending on whether
I
`
contains a job
j
with
p
j
>
2
`
=
4
or not, in which case
I
`
contains only jobs that are shorter, but did not fit into the preceding interval.
Case 1: There is
j
2
I
`
with
p
j
>
2
`
2
.
An optimal schedule cannot be shorter than the longest job of the instance. Thus, the optimal makespan is at
least
C
max
>
2
`
2
. Consequently
C
S
max
=C
max
6
(2
`
+1
1)
=
2
`
2
<
8
.
Case 2: For all jobs
j
2
I
`
we have
p
j
<
2
`
2
.
In this case, every job
j
2
I
`
did not fit anymore into the interval
I
`
1
. We consider the interval
I
`
1
. Its
length is
2
`
1
. We partition the set of time-slots of the interval
I
`
1
into the disjoint sets
K
,
H
,
L
, and
D
.
Let
K
be the set of time-slots that are filled to more than
m=
2
with small jobs, i.e. jobs with
m
j
6
m=
2
.
14
These time-slots had been filled during Step 2.2. of Algorithm 5.2 and are located at the beginning of the
interval. Let
H
be the set of time-slots that contain only small jobs, but in which at most
m=
2
machines are
busy. These time-slots are located right after the time-slots in
K
. All jobs in
H
start no later than in the first
time-slot of
H
. Let
L
be the set of empty time-slots. They are located between the time-slots of
H
and the
time-slots belonging to
D
. Let
D
be the set of time-slots that contain a wide job, i.e. a job with
m
j
> m=
2
.
These time-slots were filled during Step 2.1. of Algorithm 5.2 and are the last time-slots of the interval
I
`
1
.
The sets
K
,
H
,
L
, and
D
are disjoint and we have
j
K
j
+
j
H
j
+
j
L
j
+
j
D
j
= 2
`
1
. The time-slots in
K
and
D
are filled to more than half. Note that there cannot be more time-slots in
H
than in the rest of the
interval since all jobs in
H
start no later than in the first time-slot of
H
and all jobs are no longer than half
of the length of the interval they belong to.
We consider a job
j
that could have been processed within the interval
I
`
1
(since
I
`
1
is more than twice as
long as job
j
), but was forced into the next interval
I
`
because there was insufficient space. We distinguish
two further cases depending on whether job
j
is wide or small.
Case 2.1:
m
j
> m=
2
.
Obviously,
p
j
>
j
L
j
since otherwise
j
would have fitted into the empty time-slots in
I
`
1
. The total load of
job
j
and of jobs scheduled in the interval
I
`
1
is more than
(
j
K
j
+
j
D
j
)
m
2
+
j
L
j
m
2
=
m
2
(
j
K
j
+
j
D
j
+
j
L
j
) =
m
2
(2
`
1
j
H
j
)
. It follows that
C
max
>
(2
`
1
j
H
j
)
=
2
. We also have
C
max
>
j
H
j
. These facts combined
lead to
C
max
>
2
`
1
=
3
. It follows that
C
S
max
=C
max
6
3(2
`
+1
1)
2
`
1
<
12
.
Case 2.2:
m
j
6
m=
2
.
This time
p
j
>
j
H
j
+
j
L
j
since otherwise
j
could have been assigned to time-slots in
H
and
L
. Thus,
C
max
>
p
j
>
j
H
j
+
j
L
j
. Moreover, the time-slots in
K
and
D
together contain more load than
(
j
K
j
+
j
D
j
)
m
2
= (2
`
1
(
j
H
j
+
j
L
j
))
m
2
, leading us to
C
max
>
(2
`
1
(
j
H
j
+
j
L
j
))
=
2
. We combine both lower
bounds for the optimum to obtain
C
max
>
2
`
1
=
3
. This results in
C
S
max
=C
max
6
3(2
`
+1
1)
2
`
1
<
12
.
The following table gives an overview of the best known results for scheduling parallel jobs to minimize
makespan, offline and online. The first row contains for each model the best known performance guaran-
tee or competitive ratio, respectively. The second row contains for each model the complexity or the best
known lower bound for the performance guarantee. The lower bounds for the performance guarantee of
approximation algorithms for offline problems are under the assumption that P
6
=
NP.
model release dates preemptive non-preemptive
6
2
1
=m
[13]
6
2
1
=m
[13]
without
r
j
NP-hard [8]
>
3
=
2
6
2
1
=m <
2
offline
with
r
j
NP-hard [8]
>
3
=
2
online model —
<
12
“scheduling jobs one by one” —
>
2
:
25
6
2
1
=m
[13]
6
2
1
=m
[13]
without
r
j
>
2
1
=m
[33]
>
2
1
=m
[33]
6
2
1
=m <
2
online model
with
r
j
>
2
1
=m
[33]
>
2
1
=m
[33]
“unknown running times”
online model
6
2
1
=m <
2
“jobs arriving over time” with
r
j
open
>
1
:
347
[6]
15
Acknowledgments. I am grateful to Martin Skutella for directing me to this interesting research area, and
for several useful comments and discussions. In particular, he was the advisor of my Diploma thesis from
which the results presented here originated [26].
References
[1] S. Albers, Better bounds for online scheduling, SIAM Journal on Computing 29 (1999), 459–473.
[2] A. K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, Scheduling independent multiprocessor
tasks, in R. Burkard and G. Woeginger (eds.), Algorithms — ESA’97, Lecture Notes in Computer
Science 1284, Springer-Verlag, Berlin, 1997, 1–12.
[3] B. S. Baker, E. G. Coffman, Jr., and R. L. Rivest, Orthogonal packings in two dimensions, SIAM
Journal on Computing 9 (1980), 846–855.
[4] J. Bła˙zewicz, M. Drabowski, and J. We¸glarz, Scheduling multiprocessor tasks to minimize schedule
length, IEEE Transactions on Computers 35 (1986), 389–393.
[5] J. Chen and A. Miranda, A polynomial time approximation scheme for general multiprocessor job
scheduling, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, 418–
427.
[6] B. Chen and A. P. A. Vestjens, Scheduling on identical machines: How good is LPT in an on-line
setting?, Operations Research Letters 21 (1997), 165–169.
[7] E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan, Performance bounds for level-oriented
two-dimensional packing algorithms, SIAM Journal on Computing 9 (1980), 808–826.
[8] M. Drozdowski, On complexity of multiprocessor task scheduling, Bulletin of the Polish Academy of
Sciences, Technical Sciences, 43 (1994), 437–445.
[9] M. Drozdowski, Scheduling multiprocessor tasks — an overview, European Journal of Operational
Research 64 (1996), 215–230.
[10] J. Du and J. Y-T. Leung, Complexity of scheduling parallel task systems, SIAM Journal of Discrete
Mathematics 2 (1989), 473–487.
[11] D. G. Feitelson, A survey of scheduling in multiprogrammed parallel systems, Research Report RC
19790 (87657), IBM T. J. Watson Research Center, October 1994, revised August 1997.
[12] D. G. Feitelson, L. Rudolph, U. Schwiegelshohn, K. C. Sevcik, and P. Wong, Theory and practice in
parallel job scheduling, in D. G. Feitelson and L. Rudolph (eds.), Job Scheduling Strategies for Parallel
Processing, Lecture Notes in Computer Science 1291, Springer, Berlin, 1997, 1–34.
[13] A. Feldmann, J. Sgall and S.-H. Teng, Dynamic scheduling on parallel machines, Theoretical Computer
Science 130 (1994), 49-72.
[14] R. Fleischer and M. Wahl, On-line scheduling revisited, Journal of Scheduling 3 (2000), 343–353.
16
[15] M. R. Garey and R. L. Graham, Bounds for multiprocessor scheduling with resource constraints, SIAM
Journal on Computing 4 (1975), 187–200.
[16] I. Golan, Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM
Journal on Computing 10 (1981), 571–582.
[17] R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal 45 (1966),
1563–1581.
[18] R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal of Applied Mathematics
17 (1969), 416–426.
[19] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approximation
in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5 (1979), 287–
326.
[20] D. Gusfield, Bounds for naive multiple machine scheduling with release times and deadlines, Journal
of Algorithms 5 (1984), 1–6.
[21] L. A. Hall and D. B. Shmoys, Approximation schemes for constrained scheduling problems, Proceed-
ings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, 134–139.
[22] D. S. Hochbaum and D. B. Shmoys, Using dual approximation algorithms for scheduling problems:
Theoretical and practical results, Journal of the Association for Computing Machinery 34 (1987), 144–
162.
[23] W. A. Horn, Some simple machine scheduling algorithms, Naval Research Logistics Quarterly 21
(1974), 177–185.
[24] K. Jansen and L. Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks,
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 490–498.
[25] K. Jansen and L. Porkolab, Preemptive parallel task scheduling in
O
(
n
) +
pol y
(
m
)
time, in D. T. Lee
and S.-H. Teng (eds.), Algorithms and Computation, Lecture Notes in Computer Science 1969,
Springer-Verlag, Berlin, 2000, 398–409.
[26] B. Johannes, Obere und untere Schranken f¨ur die G¨ute von Heuristiken und Relaxierungen im Maschi-
nen Scheduling, Diplomarbeit, Institut f¨ur Mathematik, Technische Universit¨at Berlin, Germany, June
2001.
[27] C. Kenyon and E. Remila, Approximative strip packing, Proceedings of the 37th IEEE Symposium on
Foundations of Computer Science, 1996, 31–36.
[28] K. Li, Analysis of an approximation algorithm for scheduling independent parallel tasks, Discrete
Mathematics and Theoretical Computer Science 3 (1999), 155–166.
[29] W. Ludwig and P. Tiwari, Scheduling malleable and nonmalleable tasks, Proceedings of the 5th ACM-
SIAM Symposium on Discrete Algorithms, 1994, 167–176.
[30] R. McNaughton, Scheduling with deadlines and loss functions, Management Science 6 (1959), 1–12.
17
[31] A. W. Mu’alem and D. G. Feitelson, Preemptive bicriteria scheduling for parallel jobs: Off-line and
on-line algorithms, Technical Report 99-36, Leibniz Center for Research in Computer Science, Hebrew
University, Jerusalem, Israel, December 1999.
[32] J. Sgall, On-line scheduling, in A. Fiat and G. J. Woeginger (eds.), Online Algorithms, Lecture Notes
in Computer Science 1442, Springer-Verlag, Berlin, 1998, 197–231.
[33] D. B. Shmoys, J. Wein, and D. P. Williamson, Scheduling parallel machines on-line, SIAM Journal on
Computing 24 (1995), 1313–1331.
[34] D. Sleator, A
2
:
5
times optimal algorithm for packing in two dimensions, Information Processing Let-
ters 10 (1980), 37–40.
[35] A. Steinberg, A strip-packing algorithm with absolute performance bound
2
, SIAM Journal on Com-
puting 26 (1997), 401–409.
[36] J. Turek, J. L. Wolf, and P. S. Yu, Approximate algorithms for scheduling parallelizable tasks, Proceed-
ings of the 4th ACM Symposium on Parallel Algorithms and Architectures, 1992, 323–332.
18
Reports from the group
“Combinatorial Optimization and Graph Algorithms”
of the Department of Mathematics, TU Berlin
716/2001 Christian Liebchen: The Periodic Assignment Problem (PAP) May Be Solved Greedily
711/2001 Esther M. Arkin, Michael A. Bender, S´
andor P. Fekete, Joseph S. B. Mitchell, and Martin Skutella: The
Freeze-Tag Problem: How to Wake Up a Swarm of Robots
710/2001 Esther M. Arkin, S´
andor P. Fekete, and Joseph S. B. Mitchell: Algorithms for Manufacturing Paperclips and
Sheet Metal Structures
705/2000 Ekkehard K¨
ohler: Recognizing Graphs without Asteroidal Triples
704/2000 Ekkehard K¨
ohler: AT-free, coAT-free Graphs and AT-free Posets
702/2000 Frederik Stork: Branch-and-Bound Algorithms for Stochastic Resource-Constrained Project Scheduling
700/2000 Rolf H. M¨
ohring: Scheduling under uncertainty: Bounding the makespan distribution
698/2000 S´
andor P. Fekete, Ekkehard K¨
ohler, and J¨
urgen Teich: More-dimensional packing with order constraints
697/2000 S´
andor P. Fekete, Ekkehard K¨
ohler, and J¨
urgen Teich: Extending partial suborders and implication classes
696/2000 S´
andor P. Fekete, Ekkehard K¨
ohler, and J¨
urgen Teich: Optimal FPGA module placement with temporal
precedence constraints
695/2000 S´
andor P. Fekete, Henk Meijer, Andr´
e Rohe, and Walter Tietze: Solving a “hard” problem to approximate
an “easy” one: heuristics for maximum matchings and maximum Traveling Salesman Problems
694/2000 Esther M. Arkin, S´
andor P. Fekete, Ferran Hurtado, Joseph S. B. Mitchell, Marc Noy, Vera Sacrist´
an and
Saurabh Sethia: On the reflexivity of point sets
693/2000 Frederik Stork and Marc Uetz: On the representation of resource constraints in project scheduling
691/2000 Martin Skutella and Marc Uetz: Scheduling precedence constrained jobs with stochastic processing times
on parallel machines
689/2000 Rolf H. M¨
ohring, Martin Skutella, and Frederik Stork: Scheduling with AND/OR precedence constraints
685/2000 Martin Skutella: Approximating the single source unsplittable min-cost flow problem
684/2000 Han Hoogeveen, Martin Skutella, and Gerhard J. Woeginger: Preemptive scheduling with rejection
683/2000 Martin Skutella: Convex quadratic and semidefinite programming relaxations in Scheduling
682/2000 Rolf H. M¨
ohring and Marc Uetz: Scheduling scarce resources in chemical engineering
681/2000 Rolf H. M¨
ohring: Scheduling under uncertainty: optimizing against a randomizing adversary
680/2000 Rolf H. M¨
ohring, Andreas S. Schulz, Frederik Stork, and Marc Uetz: Solving project scheduling problems
by minimum cut computations (Journal version for the previous Reports 620 and 661)
674/2000 Esther M. Arkin, Michael A. Bender, Erik D. Demaine, S´
andor P. Fekete, Joseph S. B. Mitchell, and Saurabh
Sethia: Optimal covering tours with turn costs
669/2000 Michael Naatz: A note on a question of C. D. Savage
667/2000 S´
andor P. Fekete and Henk Meijer: On geometric maximum weight cliques
666/2000 S´
andor P. Fekete, Joseph S. B. Mitchell, and Karin Weinbrecht: On the continuous Weber and
k
-median
problems
664/2000 Rolf H. M¨
ohring, Andreas S. Schulz, Frederik Stork, and Marc Uetz: On project scheduling with irregular
starting time costs
661/2000 Frederik Stork and Marc Uetz: Resource-constrained project scheduling: from a Lagrangian relaxation to
competitive solutions
Reports may be requested from: Hannelore Vogt-M¨oller
Fachbereich Mathematik, MA 6–1
TU Berlin
Straße des 17. Juni 136
D-10623 Berlin – Germany
e-mail: moeller@math.TU-Berlin.DE
Reports are also available in various formats from
http://www.math.tu-berlin.de/coga/publications/techreports/
and via anonymous ftp as
ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-number-year.ps