SIAM J. COMPUT.

c 1999 Society for Industrial and Applied Mathematics

Vol. 28, No. 4, pp. 1155–1166

APPROXIMABILITY AND NONAPPROXIMABILITY RESULTS

FOR MINIMIZING TOTAL FLOW TIME ON A SINGLE MACHINE∗
HANS KELLERER† , THOMAS TAUTENHAHN‡ , AND GERHARD J. WOEGINGER§
Dedicated to the memory of Gene Lawler
Abstract. We consider the problem of scheduling n jobs that are released over time on a single
machine in order to minimize the total flow time. This problem is well known to be NP-complete,
and the best polynomial-time approximation algorithms constructed so far had (more or less trivial)
worst-case performance guarantees of O(n).
In this paper, we present one positive and one negative result on polynomial-time approximations
for the minimum total flow time problem: The positive√result is the first approximation algorithm
with a sublinear worst-case performance guarantee of O( n). This algorithm is based on resolving the
preemptions of the corresponding optimum preemptive schedule. The performance guarantee of our
approximation algorithm is not far from best possible, as our second, negative result demonstrates:
Unless P = N P , no polynomial-time approximation algorithm for minimum total flow time can have
a worst-case performance guarantee of O(n1/2−ε ) for any ε > 0.

Key words. scheduling, approximation algorithm, worst-case analysis, total flow time, release
time, single machine

AMS subject classifications. 08C85, 68Q20, 05C38, 68R10, 90C35

PII. S0097539796305778

1. Introduction. Scheduling independent jobs on a single machine has been

studied extensively under various objective functions. We consider one of the basic
problems of this kind, which from a worst-case point of view also appeared to be
among the most intractable ones: There are given n independent jobs J1 , . . . , Jn
which have to be scheduled nonpreemptively on a single machine. Each job Ji has a
processing time pi and becomes available for execution at its release time ri , where
pi and ri are nonnegative real numbers. All job data are known in advance. Without
loss of generality we assume that the smallest release time is equal to zero. In a certain
schedule for these jobs, let Ci be the completion time of job Ji , let Si be its starting
time (i.e., Si + pi = Ci ), and let Fi = Ci − ri denote its flow time, respectively.
P The
objective is to determine a schedule that P minimizes the total flow time F i . This
problem is commonly denoted by 1|ri | Fi .
In case all job release times are identical, the problem can be solved in O(n log n)
time by applying the well-known shortest processing time (SPT) rule; see Smith [19].
For arbitrary release times, the problem becomes NP-complete (Lenstra, Rinnooy
Kan, and Brucker [15]). Several authors (Chandra [4], Chu [6], Deogun [7], and

∗ Received by the editors June 12, 1996; accepted for publication (in revised form) May 2, 1997;

published electronically March 19, 1999. A preliminary version of this paper appeared in Proc. 28th
Annual ACM Symp. on the Theory of Computing, 1997.
http://www.siam.org/journals/sicomp/28-4/30577.html
† Institut für Statistik, Ökonometrie und Operations Research, Universitätsstrasse 15, Universität

Graz, A–8010 Graz, Austria ([email protected]).

‡ Fakultät für Mathematik, Otto-von-Guericke Universität Magdeburg, D–39016 Magdeburg, Ger-

many ([email protected]). This research was supported by DAAD (German Academic Exchange
Service).
§ TU Graz, Institut für Mathematik B, Steyrergasse 30, A-8010 Graz, Austria (gwoegi@

opt.math.tu-graz.ac.at). The research of this author was supported by a research fellowship of the
Euler Institute for Discrete Mathematics and Its Applications and by START project Y43-MAT of
the Austrian Ministry of Science.
1155
1156 H. KELLERER, T. TAUTENHAHN, AND G. WOEGINGER

P
Dessouky and Deogun [8]) developed branch-and-bound algorithms for 1|ri | Fi .
Other papers (Bianco and Ricciardelli [3], Dyer and Wolsey [10],PHariri and Potts
[13], and Posner [18]) gave branch-and-bound algorithms for 1|ri | wi Fi , the prob-
lem of minimizing the total weighted flow time. Gazmuri [12] designed asymptotically
optimal algorithms for minimizing total flow time under very general probability dis-
tributions of the job data.
P
The preemptive version 1|pmtn, ri | Fi of the problem can be solved in poly-
nomial time by the shortest remaining processing time (SRPT) rule (see, e.g., Baker
[2]). The objective value of the optimum preemptive schedule clearly is a lower bound
on the objective value of the nonpreemptive problem. Ahmadi P and Bagchi [1] have
shown that it dominates six other lower bounds for 1|ri | Fi that had been used in
the scheduling literature.

Approximation algorithms. For an instance I of 1|ri | Fi , let F H (I) denote

P
the total flow time obtained when algorithm H is applied to I, and let F ∗ (I) be the
objective value of an optimum solution for I. We usually write F H and F ∗ instead
of F H (I) and F ∗ (I), respectively, if the instance I is clear from the context. Now let
ρ : R+ → R+ and let H be an approximation algorithm. We say that algorithm H
has worst-case performance guarantee ρ if

sup{F H (I)/F ∗ (I) | I is an instance with n jobs } ≤ ρ(n)

holds for all integers n ≥ 1.

Chu
P [5] and Mao and Rifkin [17] investigated several “reasonable” algorithms for
1|ri | Fi , but none of them yielded a sublinear P worst-case performance guarantee.
For instance, a straightforward procedure for 1|ri | Fi is the earliest start time (EST)
algorithm: “Whenever the machine becomes free for assignment, take the shortest of
the (at that time) available jobs and assign it to the machine.” The following example
shows that the total flow time in an EST schedule can be a factor of n away from
the optimum: Let ε be a very small positive real number. Then choose p1 = 1,
p2 = · · · = pn = ε, r1 = 0, r2 = · · · = rn = ε. The EST schedule processes the jobs
in the ordering (1, 2, . . . , n) with total flow time Ω(n), whereas an optimum schedule
processes the jobs in the ordering (2, 3, . . . , n − 1, 1) with total flow time O(1).
Another direct approach is the earliest completion time (ECT) rule. An ECT
schedule is formed by scheduling jobs without any unnecessary idle time, where the
next job to be scheduled is the one with the earliest possible completion time of all
unscheduled jobs. Again, let ε be a very small positive real number. Then the job
data p1 = 1 + 2ε, p2 = · · · = pn = ε and ri = i − 1 for all i = 1, . . . , n yields an
ECT schedule of (2, 3, . . . , n − 1, 1) with total flow time Ω(n), whereas the optimum
schedule is (1, 2, . . . , n) with total flow time O(1). Again, we get a worst-case ratio
of n.

New results. The results of this paper are as follows. First we present a
polynomial-time
√ approximation algorithm with worst-case performance guarantee of
O( n). The algorithm starts from an optimum solution of the corresponding pre-
emptive instance. Then the preemptive schedule is transformed step by step into a
nonpreemptive one by successively resolving the preemptions. Our proof also demon-
strates that for any instance the minimum
√ total flow time of an optimum nonpreemp-
tive schedule is at most a factor of n larger than the corresponding minimum total
flow time of the optimum preemptive schedule.
 MINIMIZING THE TOTAL FLOW TIME 1157

In the second part of the paper, we prove that polynomial-time approximation

algorithms for minimum total flow time on a single machine cannot have a worst-
case performance guarantee of O(n1/2−ε ) for any ε > 0. This result is derived by an
appropriate reduction from the NP-complete numerical three-dimensional matching
problem.

Organization of the paper. Section 2 describes the approximation

√ algorithm
and proves the claimed worst-case performance guarantee of O( n). Section 3 gives
the nonapproximability result, and section 4 contains the discussion.

2. The approximation algorithm. In this section, we design a polynomial-

time approximation algorithm for the √ minimum total flow time problem that has
worst-case performance guarantee O( n). The main idea is to start with an optimum
solution of the corresponding problem, where preemption is allowed, and then to get
rid of the preemptions while increasing the total flow time by only some “moderate”
amount.
As already mentioned in the introduction, an optimum preemptive schedule can
be obtained by applying the SRPT rule, which is defined as follows: The remaining
processing time Pi (t) of job Ji is the amount of processing time of Ji which has not
been scheduled before time t. At any time t, the available job Ji with SRPT Pi (t) is
processed until it is either completed or until another job Jj with pj < Pi (rj ) becomes
available. In the second case, Ji is preempted and Jj is processed.
∗
We denote the total flow time in an optimum preemptive schedule by Fpmtn .
With every job Ji we associate the interval Ii = [Si , Ci ] in the preemptive schedule.
Note that due to possible preemptions, the length of Ii in general need not be equal
to pi . Let us observe some simple properties of the SRPT schedule: If a job Ji has a
preemption at time t, then the processing of some job Jj with pj < Pi (t) starts at this
time. Consequently, job Ji cannot return to the machine until job Jj is completed.
Observation 2.1. In the SRPT schedule, for any two jobs Ji and Jj either the
corresponding intervals Ii and Ij are disjoint or one of them contains the other one.
Furthermore, there is no machine idle time during Ii and Ij .
With the preemptive schedule we associate in the following way a directed ordered
forest that describes the containment relations of the intervals Ii . The jobs J1 , . . . , Jn
form the vertices of the forest. We introduce a directed edge going from job Ji to
Jj if and only if Ij ⊆ Ii and there does not exist a job Jk with Ij ⊆ Ik ⊆ Ii . For
every vertex Ji , its sons are ordered from left to right according to the ordering of
their corresponding intervals Ij . This yields a collection of ordered directed out-trees.
Out-trees that consist of a single vertex are called trivial out-trees. To complete the
definition of the forest, we also order the roots of these out-trees from left to right
according to the ordering of their corresponding intervals. By T (i) we denote the
maximal subtree of this forest rooted at Ji (hence, T (i) exactly contains those jobs
that are processed during [Si , Ci ]). A leaf is a job with out-degree zero. (Hence, it
does not have any preemptions.)
Since our approximation algorithm transforms the preemptive schedule into a
nonpreemptive one, the forest associated with the final schedule will be a collection
of n trivial out-trees. In sections 2.1, 2.2, and 2.3, we describe three procedures for
removing preemptions and simplifying the forest structure. Every procedure acts on
a certain subtree T (i) and removes all preemptions of the job Ji . Section 2.4 explains
how the approximation algorithm applies and combines these three procedures.
1158 H. KELLERER, T. TAUTENHAHN, AND G. WOEGINGER

J1 J2 J3 J4 J2 J1
-

J1 J2 J3 J4
-

Fig. 1. Illustration for Procedure SmallSubtree(i) with i = 1.

2.1. How√to handle small subtrees. A subtree T (i) is called small if it con-
tains at most n jobs. In this case we use the following procedure to resolve the
preemptions of job Ji and of all jobs contained in T (i).
Procedure SmallSubtree(i).
Let Si = Si0 < Si1 < · · · < Sik denote the starting times of the jobs in
T (i) in the current preemptive schedule. Remove all jobs and reinsert
them without preemptions in the ordering Ji , Ji1 , Ji2 , . . . , Jik .
For an illustration, see Figure 1. It is easy to see that SmallSubtree(i) does not
decrease the starting time of any job. Hence, the resulting schedule still obeys all
release times. Completion times of jobs outside of T (i) are not changed, and the
√ times of jobs in T (i) are all increased by less than Ci − ri . Since there are
completion
at most n jobs in T (i),
√
(1) ∆small (i) = nFi

is an upper bound on the increase of the objective function caused by SmallSubtree(i).

2.2. How to handle the last root. Now let Ji be the root of the rightmost
nontrivial out-tree. (Ji is preempted, but all jobs that are processed after Ci are
without preemptions.) Such a root Ji is called the last root and may be handled
according to the following procedure.
Procedure √ LastRoot(i).
Compute ⌈ n ⌉ + 1 time points t0 = Ci , t1 , . . . , t⌈√n ⌉ such that there
are exactly hpi units of idle√time between Ci and th √ in the current
schedule for all h ∈ {0, . . . , n}. Determine 0 ≤ k ≤ ⌈ n ⌉ − 1 so as
to minimize the value of k + |{j : tk ≤ Sj ≤ tk+1 }|.
In case there is a job processed during [tk , tk + pi ], shift it to the
right until its processing is disjoint from [tk , tk +pi ]. If necessary shift
also some later jobs to the right, but without changing their relative
orderings and without introducing any unnecessary idle time. Then
remove Ji and reschedule it in the interval [tk , tk + pi ].
For an illustration, see Figure 2. Since the job starting times are not decreased,
the resulting schedule is again feasible. Moreover, by definition of the numbers th ,
there are exactly pi units of idle time between tk and tk+1 . Hence, the shifting of jobs
takes place only within the interval [tk , tk+1 ], and no jobs outside of this interval are
affected by LastRoot(i).
Lemma 2.2. The value of k determined by Procedure LastRoot(i) satisfies
3√
k + |{j : tk ≤ Sj ≤ tk+1 }| ≤ n.
2
 MINIMIZING THE TOTAL FLOW TIME 1159

J1 J2 J3 J4 J1 J5 J6 J7 J8 J9 J10 J11
-

J2 J3 J4 J5 J6 J7 J8 J1 J9 J10 J11
-
t0 t1 t2 t3

Fig. 2. Illustration for Procedure LastRoot(i) with i = 1.

Proof. Define nh = |{j : th ≤ Sj ≤ th+1 }|. Then

√
⌈ n ⌉−1
X 1 √ √ 3√ √
(h + nh ) ≤ ⌈ n ⌉(⌈ n ⌉ − 1) + n ≤ n⌈ n ⌉.
2 2
h=0

Since k was chosen to√minimize k + nk , the value k + nk is bounded from above by

the average of these ⌈ n ⌉ numbers. Pn
Procedure LastRoot(i) increases the flow time of job Ji by at most kpi + j=1 pj .
Furthermore, the flow times of at most nk = |{j : tk ≤ Sj ≤ tk+1 }| other jobs are
increased by at most pi . By applying Lemma 2.2 one gets that LastRoot(i) increases
the value of the objective function by at most
n n
X 3√ X
(2) ∆last (i) = kpi + pj + n k pi ≤ n pi + pj .
j=1
2 j=1

Finally, observe that in the new schedule Ji is processed entirely after its completion
time in the old schedule.
2.3. How to handle fathers and sons. Procedure FatherSon(i, j) described
below may be applied only if the jobs Ji and Jj fulfill the following four conditions:
(C1) Jj is a son of Ji .
(C2) All sons of Ji in T (i) that lie to the right of Jj are leaves (i.e., jobs without
preemption). √
(C3) There are less than n jobs that lie to the right of Jj in T (i).
(C4) Just before executing FatherSon(i, j), job Ji is removed and rescheduled en-
tirely after its old completion time.
Condition (C4) may be fulfilled if Ji is rescheduled by LastRoot(i) or (as we will
see) if it is rescheduled by FatherSon(k, i), where k was the father of i at that time.
Condition (C4) has the following consequences: At the moment as SRPT decided to
start processing Jj instead of Ji , it did so because the remaining processing time of
Ji was larger than pj . Hence, the total time that Ji is processed during [Cj , Ci ] is
at least pj , and in case Ji is moved to some place after Ci , there is sufficient empty
space in [Cj , Ci ] to schedule all of Jj .
Procedure FatherSon(i, j).
All jobs that are processed during [Cj , Cj + pj ] are shifted to the
right until their processing is disjoint from [Cj , Cj + pj ]. If necessary,
also, some later jobs are shifted to the right but without changing
1160 H. KELLERER, T. TAUTENHAHN, AND G. WOEGINGER

J1 J2 J3 J4 J5 J6 J7 J2 J8 J1 J9 J1
-

J3 J4 J5 J6 J7 J2 J8 J9
-

Fig. 3. Illustration for Procedure FatherSon(i, j) with i = 1 and j = 2.

their relative orderings and without introducing any unnecessary idle

time.
Then remove Jj and reschedule it to the interval [Cj , Cj + pj ].
For an illustration, see Figure 3. Note that in the new schedule Jj is processed
entirely after its completion time in the old schedule. Furthermore note that Proce-
dure FatherSon(i, j) transforms all sons of Ji in T (i) that lie to the right of Jj into
trivial out-trees.
Procedure FatherSon(i, j) produces another feasible schedule where job Jj no
longer has preemption. Only jobs in the interval [Cj , Ci ] are shifted to the right, and
no other jobs are affected. All the shifted jobs are contained in√T (i), they lie to the
right of Jj , and, by condition (C3), their number is less than n. The completion
time of every moved job (including job Jj ) increases by at most pj . Hence, the total
increase in the value of the objective function that FatherSon(i, j) produces can be
bounded by
√
(3) ∆f son (j) = n pj .

2.4. Putting everything together. Finally, we describe our approximation al-

gorithm in detail. The algorithm starts with the optimum schedule for the preemptive
problem and determines the corresponding directed ordered forest.
In the first
√ phase, Procedure SmallSubtree(i) is applied to all jobs Ji for which
2 ≤ |T (i)| ≤ n holds. Afterward,√ every subtree T (i) either fulfills |T (i)| = 1 (and Ji
has no preemption) or |T (i)| > n holds.
In the second phase, the algorithm goes through a number of steps and repeatedly
modifies the rightmost nontrivial
√ out-tree. Every such step increases the number of
trivial out-trees by at least n. Every step consists of one call to LastRoot, possibly
followed by several calls to FatherSon. For a nonleaf vertex Ji in the forest, let
rmnls(i) denote the index of its rightmost nonleaf son and let leaf(i) denote the
number of sons of Ji lying to the right of rmnls(i). (Obviously, all these leaf(i)
sons must be leaves.) Every step of the second phase is performed as follows. Let Ji
be the root of the rightmost nontrivial out-tree.
LastRoot(i); √
While rmnls(i) exists and leaf(i)< n do
FatherSon(i,rmnls(i))
i :=rmnls(i)
EndWhile
Let Ji∗ denote the last
√ job whose preemptions are resolved in such a step. Then
either Ji∗ has more than n sons (that all are leaves) to the right of rmnls(i∗ ) or job
 MINIMIZING THE TOTAL FLOW TIME 1161

rmnls(i∗ ) does not exist. In the latter case, all sons of Ji∗ are leaves
√ and, according
first phase, their number must be greater than n. In either case,
to the result of the √
there are at least n leaves that formerly were preempting Ji∗ , the father of Ji∗ ,
its grandfather, and so on—the whole chain of ancestors to the formerly “last root.”
Since the execution of the√step removes all preemptions from this chain of ancestors,
it turns all these at least n leaves into trivial out-trees.
In the second phase of the algorithm the step described above is repeated over
and
√ over until all preemption have been removed. Since every step produces √ at least
n new trivial out-trees, the second phase terminates after at most n steps. This
completes the description of our approximation algorithm. P
Theorem 2.3. The approximation algorithm √ described for the problem 1|ri | Fi
has a worst-case performance guarantee of O( n), and it can be implemented to run
in O(n3/2 ) time. Moreover, there √ exist instances for which the algorithm yields a
schedule whose objective value is Ω( n) from the optimum.
Proof. To analyze the worst-case behavior of the algorithm, we define job classes
S, L, and F. Class S contains the jobs Ji for which SmallSubtree(i) is executed, L the
jobs Ji for which LastRoot(i) is executed, and F the jobs Jj for which FatherSon(i, j)
is executed. Since every procedure removes all preemptions of the corresponding job, √
every job is contained in at most one of the classes S, L, and F. Moreover, |L| ≤ n
holds, since LastRoot(i)
√ is executed exactly once per step in the second phase, and
there are at most n steps.
The constructed nonpreemptive schedule has an objective value F H which satisfies
X X X
F H ≤ Fpmtn
∗
+ ∆small (i) + ∆last (i) + ∆f son (i)
i∈S i∈L i∈F
 
X√ n
∗
X 3 √ X X√
≤ Fpmtn + nFi +  n pi + pj  + n pi .
2 j=1
i∈S i∈L i∈F

Here we used (1), P

(2), and (3). If we also apply the straightforward
√ relations pi ≤ Fi ,
n ∗
for 1 ≤ i ≤ n and i=1 Fi = Fpmtn , together with |L| ≤ n, then we determine that
n
3√ 5√
X X  
(4) F H ≤ Fpmtn
∗
+ n Fi + |L| pj ≤ 1+ ∗
n Fpmtn
2 j=1
2
i∈S∪L∪F

∗ ∗
holds. Since Fpmtn√ ≤ F , this proves that the algorithm has a worst-case performance
guarantee of O( n).
What about the time complexity? The SRPT schedule can be computed in
O(n log n) time.
√ Procedure SmallSubtree needs to be run only on the vertices which
have
√ at most n descendants and whose father is either nonexistent or has more than
n descendants. All these vertices can be located in a single O(n) time traversal of
the forest. Hence, procedures SmallSubtree √ and FatherSon are both executed only
O(n) times and always consider only O( n) of the jobs. Procedure
√ LastRoot may
have to deal with up to O(n) jobs, but it is executed only O( n) times. Summarizing,
this yields a time complexity of
√ √
|S| · O( n) + |L| · O(n) + |F| · O( n) ≤ O(n3/2 ).
√
To see that the algorithm can be a factor of Ω( n) from the optimum, consider
the instance of n = x2 jobs: The jobs Ji with 1 ≤ i ≤ x − 1 all have processing
1162 H. KELLERER, T. TAUTENHAHN, AND G. WOEGINGER

J1 J1 J1 J1 J1
-
∗
optimum preemptive schedule: Fpmtn = Θ(n)

J1
-
optimum nonpreemptive schedule: F ∗ = Θ(n3/2 )

Fig. 4. Illustration for the lower bound example in Corollary 2.4.

time 1/(x − 1) and release times 1 + (i − 1)/(x − 1). Job Jx has processing time x2
and release time 0. The remaining x2 − x jobs are dummy jobs, all with processing
times 0 and release times 0. The forest corresponding to the optimum preemptive
schedule has a single nontrivial tree with root Jx and J1 , . . . , Jx−1 as leaves. Hence,
our algorithm calls SmallSubtree(x) and produces a schedule with F H = x3 − x + 2,
∗
whereas F √ = x2 + 3 holds. As x tends to infinity, the ratio F H /F ∗ grows like
Θ(x) = Θ( n).
Corollary 2.4. For any instance √ of n jobs with release times on a single ma-
chine, the inequality F ∗ /Fpmtn
∗
≤ 52 n + 1 holds. Moreover, for√every sufficiently
large n, there exists an instance In such that F ∗ (In )/Fpmtn
∗
(In ) ≈ n.
Proof. The upper bound follows from (4) and F ≤ F H . The
∗
√ lower bound follows
from the instance with n jobs where r1 = 0, p1 = n, ri = (i − 1) n, and pi = ε = 1/n
∗
for i ≥ 2. Then Fpmtn ≈ n and F ∗ ≈ n3/2 holds. (See Figure 4.)
3. The nonapproximability result. In this section, we will prove that no
polynomial-time approximation algorithm for minimizing the total flow time may have
worst-case performance guarantee O(n1/2−ε ) for any ε > 0. The proof is done by a
reduction from the following version of the NP-complete numerical three-dimensional
matching problem (see Garey and Johnson [11]).
Problem. Numerical three-dimensional matching (N3DM).
Pk
Instance. Positive integers ai , bi , and ci , 1 ≤ i ≤ k, with i=1 (ai + bi + ci ) = kD.
Question. Do there exist permutations π, ψ such that ai + bπ(i) + cψ(i) = D holds
for all i?
This problem remains NP-complete even if the numbers ai , bi , and ci are encoded
in unary and the total size of the input is Θ(kD). In the following discussion, we will
make use of this unary encoding. Consider an arbitrary instance of N3DM and let
0 < ε < 21 be some real number. Define numbers

n = ⌈(20k)4/ε D2/ε ⌉, r = ⌈2Dn(1−ε)/2 ⌉, g = 100rk 2 .

Next we will construct from the N3DM instance and from the number ε a correspond-
ing scheduling instance with n jobs. For every number ai in the N3DM instance, we
introduce a corresponding job with processing time 2r + ai , for every bi we introduce
a job with processing time 4r + bi , and for every ci we introduce a job with processing
time 8r + ci . These 3k jobs are called the big jobs and they are all released at time 0.
Moreover, there will be a number of so-called tiny jobs. Tiny jobs occur only in
groups denoted by G(t; ℓ), where t and ℓ are positive integers. A group G(t; ℓ) consists
 MINIMIZING THE TOTAL FLOW TIME 1163

of ℓ tiny jobs with processing time 1/ℓ. They are released at the times t + i/ℓ for
i = 0, . . . , ℓ − 1. Note that it is possible to process all jobs in G(t; ℓ) in a feasible
way during the time interval [t, t + 1] with a total flow time of 1. We introduce the
following groups of tiny jobs.
(T1) For 1 ≤ i ≤ k, we introduce the group G((14r + D + 1)i − 1; rg).
(T2) For 1 ≤ i ≤ g, we introduce the group G((14r + D + 1)k + ri − 1; g).
In a pictorial setting, the groups of type (T1) occur at regular intervals from time
14r + D to time (14r + D + 1)k. They leave k holes, where each hole has length
14r + D. Similarly, the groups of type (T2) occur in a regular pattern after time
(14r + D + 1)k. They leave holes of size r − 1.
So far we have introduced 3k big jobs and k + 100rk 2 groups of tiny jobs, which
amounts to an overall number of

3k + krg + 100rk 2 g = 3k + 100r2 k 3 + 10, 000r2 k 4 < 11, 000r2 k 4 < n

jobs. In order to simplify calculations, we introduce a number of artificial jobs all

with processing time zero and release time zero such that the total number of jobs
becomes equal to n. This completes the construction of the scheduling instance.
Lemma 3.1. If the N3DM instance has a solution, then for the constructed
scheduling instance F ∗ ≤ 200rk 2 holds.
Proof. Consider the following feasible schedule. All tiny jobs are processed im-
mediately at their release times. Hence, their total flow time equals k + 100rk 2 . For
every triple (ai , bπ(i) , cψ(i) ) with sum D in the solution of the N3DM instance, we pack
the corresponding three jobs together into one of the holes of length 14r + D that are
left free by the groups of type (T1). The job corresponding to ai is processed first,
the job corresponding to bπ(i) is processed second, and the job corresponding to cψ(i)
is processed last in this hole. It is easy to see that this yields a total flow time of

(5)
k k k
X X X 3
k + 100rk 2 + 3 (ai + 2r) + 2 (bi + 4r) + (ci + 8r) + (14r + D + 1)k(k − 1).
i=1 i=1 i=1
2
Pk
Since i=1 (ai + bi + ci ) = kD and since D ≤ r, one easily gets an upper bound of

k + 100rk 2 + 25rk + 24rk(k − 1) < 200rk 2

for the expression in (5).

Lemma 3.2. If the N3DM instance does not have a solution, then for the con-
structed scheduling instance F ∗ ≥ 100r2 k 2 holds.
Proof. Consider an optimum schedule S ∗ and suppose that its total flow time is
strictly less than 100r2 k 2 . Our first claim then is that in S ∗ all tiny jobs in groups
of type (T1) are processed as soon as they are released: Since all these tiny jobs
have identical processing times, they are processed in S ∗ in order of increasing release
times. It is easy to see that there is no use in splitting one of the groups of type (T1)
by processing some larger jobs in between (since this would contradict the SPT rule).
Since all big jobs have integer processing times and since the total processing time in
every group is equal to 1, we may further assume that the starting time of every big
job and of every group G(t; ℓ) in S ∗ is an integer. When the processing of some group
G(t; rg) starts at time t + x, for x an integer, the total flow time of the rg tiny jobs
in G(t; rg) is rgx + 1 = 100r2 k 2 x + 1. This implies x = 0 and proves the claim.
1164 H. KELLERER, T. TAUTENHAHN, AND G. WOEGINGER

Our second claim is that in S ∗ none of the big jobs are processed during the time
interval that starts with release of the last group of type (T1) and ends with release of
the last group of type (T2). Suppose otherwise. The groups of type (T2) are released
at regular intervals of length r. Since big jobs all have processing times of at least 2r,
scheduling a big job somewhere between these groups would shift the jobs of at least
one group by at least r time units away from their release time. This would yield a
total flow time of at least gr = 100r2 k 2 and proves the second claim.
Our third claim is that in S ∗ one of the big jobs is processed after the last group
of tiny jobs. Suppose otherwise. There are two types of holes that are left free by the
tiny jobs for processing the big jobs: k holes of length 14r + D and 100rk 2 holes of
size r − 1. Since big jobs all have processing times of at least 2r, they must be packed
into the holes of size 14r + D ≤ 15r. Since two jobs corresponding to the numbers ci
and cj have total processing time at least 16r, every such hole must contain exactly
one job corresponding to some ci . By analogous arguments, we determine that every
hole of size 14r +D must contain exactly one job corresponding to some ai , bj , and ch ,
respectively. This implies that the corresponding three numbers fulfill ai +bj +ch ≤ D,
which in turn yields ai + bj + ch = D (since the total sum of these 3k numbers is
kD and the total size of the holes is kD). Hence, the N3DM instance would have a
solution; this contradiction shows that our third claim holds true.
Finally, observe that the last group of tiny jobs is processed at time t = (14r +
D + 1)k + 100r2 k 2 − 1. Hence, the big job that is processed after this last group has
a completion time of at least 100r2 k 2 , and since its release time is zero, its flow time
is at least 100r2 k 2 . This final contradiction completes the proof of the lemma.
Theorem 3.3. For all 0 < ε < 12 and 0 < α < 1, there does not exist a
polynomial-time approximation algorithm for the minimum total flow time problem
with worst-case approximation guarantee αn1/2−ε unless P = N P .
Proof. Suppose such an approximation algorithm H would exist for some fixed
0 < ε < 21 and 0 < α < 1. Take an instance of N3DM that is encoded in unary, and
perform the above construction. Since the instance is encoded in unary, the size of
the resulting scheduling instance is polynomial in the size of the N3DM instance.
Then apply algorithm H to the scheduling instance. In case the N3DM instance
has a solution, Lemma 3.1 and the worst-case performance guarantee of H imply that
r
F H ≤ αn1/2−ε · F ∗ < · 200rk 2 = 100r2 k 2 .
2
In case the N3DM instance does not have a solution, Lemma 3.2 implies that

F H ≥ F ∗ ≥ 100r2 k 2

holds. Hence, with the help of algorithm H we could distinguish between these two
possibilities in polynomial time, which would imply P = N P .
4. Concluding remarks. In this paper we investigated the problem of min-
imizing total flow time on a single machine. For this NP-complete problem, only
approximation algorithms with worst-case bounds of Ω(n) were known up to now.
We presented the first approximation algorithm with sublinear√ worst-case perfor-
mance guarantee. The algorithm has a tight worst-case of O( n). It is based on a
resolution of the interrupted jobs in the corresponding optimum preemptive sched-
ule. Moreover, we derived a lower bound on the worst-case performance guarantee
of polynomial-time approximation algorithms for this problem. We proved that no
 MINIMIZING THE TOTAL FLOW TIME 1165

polynomial-time approximation algorithm can have a worst-case performance guar-

antee of O(n1/2−ε ) with ε > 0. This also shows that our approximation algorithm is
almost “best possible.”
We finish the paper with some remarks and open problems.
(1) The open main problem concerns closing the gap between our upper bound
and our lower bound. For example, there might √ exist an approximation algorithm
with worst-case performance guarantee of O( n/ log n).
(2) Subsequent to and P inspired by our work, Leonardi and Raz [16] investi-
gated the problemP P m|r i | Fi with parallel machines. Since the preemptive problem
P m|pmtn, ri | Fi is NP-complete for m ≥ 2 machines [9], Leonardi and Raz [16] do
not have the optimum preemptive schedule as a starting point for their approximation
algorithm. Instead, they start with an approximative solution for this relaxation and
then resolve the preemptions.
(3) Another open problem consists in designing approximation algorithms for
the total weighted flow time problem on a single P machine. Also in this case, the
corresponding preemptive problem 1|pmtn, ri | wi Fi is NP-complete (Labetoulle et
al. [14]).
(4) The waiting time Wi of some job Ji in a schedule is defined by Wi = Si − ri ;
i.e., it is the time that the job spends in the system while waiting for being processed.
We are not aware of any positive results on approximating the total waiting time.

Acknowledgment. Gerhard Woeginger acknowledges helpful discussions with

Amos Fiat and Stefano Leonardi.

REFERENCES

[1] R.H. Ahmadi and U. Bagchi, Lower bounds for single-machine scheduling problems, Naval
Res. Logist., 37 (1990), pp. 967–979.
[2] K.R. Baker, Introduction to Sequencing and Scheduling, John Wiley, New York, 1974.
[3] L. Bianco and S. Ricciardelli, Scheduling of a single machine to minimize total weighted
completion time subject to release dates, Naval Res. Logist., 29 (1982), pp. 151–167.
[4] R. Chandra, On n|1|F dynamic deterministic problems, Naval Res. Logist., 26 (1979), pp.
537–544.
[5] C. Chu, Efficient heuristics to minimize total flow time with release dates, Oper. Res. Lett.,
12 (1992), pp. 321–330.
[6] C. Chu, A branch-and-bound algorithm to minimize total flow time with unequal release dates,
Naval Res. Logist., 39 (1992), pp. 859–875.
[7] J.S. Deogun, On scheduling with ready times to minimize mean flow time, Comput. J., 26
(1983), pp. 320–328.
[8] M.I. Dessouky and J.S. Deogun, Sequencing jobs with unequal ready times to minimize mean
flow time, SIAM J. Comput., 10 (1981), pp. 192–202.
[9] J. Du, J.Y.T. Leung, and G.H. Young, Minimizing mean flow time with release time con-
straint, Theoret. Comput. Sci., 75 (1990), pp. 347–355.
[10] M.E. Dyer and L.A. Wolsey, Formulating the single machine sequencing problem with release
dates as a mixed integer program, Discrete Appl. Math., 26 (1990), pp. 255–270.
[11] M.R. Garey and D.S. Johnson, Computers and Intractability, W. H. Freeman, San Francisco,
1979.
[12] P.G. Gazmuri, Probabilistic analysis of a machine scheduling problem, Math. Oper. Res., 10
(1985), pp. 328–339.
[13] A.M.A. Hariri and C.N. Potts, An algorithm for single machine sequencing with release
times to minimize total weighted completion time, Discrete Appl. Math., 5 (1983), pp.
99–109.
[14] J. Labetoulle, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, Preemptive schedul-
ing of uniform machines subject to release dates, in Progress in Combinatorial Optimiza-
tion, Academic Press, New York, 1984, pp. 245–261.
1166 H. KELLERER, T. TAUTENHAHN, AND G. WOEGINGER

[15] J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker, Complexity of machine scheduling
problems, Ann. Discrete Math., 1 (1977), pp. 343–362.
[16] S. Leonardi and D. Raz, Approximating total flow time on parallel machines, in Proc. 29th
Annual ACM Symposium on the Theory of Computing, El Paso, TX, 1997.
[17] W. Mao and A. Rifkin, On-line algorithms for a single machine scheduling problem, in The
Impact of Emerging Technologies on Computer Science and Operations Research, S. Nash
and A. Sofer, eds., Kluwer Academic Publishers, Norwell, MA, 1995, pp. 157–173.
[18] M.E. Posner, Minimizing weighted completion times with deadlines, Oper. Res., 33 (1985),
pp. 562–574.
[19] W.E. Smith, Various optimizers for single-state production, Naval Res. Logist. Quart., 3
(1956), pp. 56–66.