Division of Research
Graduate School of Business Administration
The University of Michigan
A NOTE ON SMITH'S SCHEDULE TO MINIMIZE THE
WEIGHTED SUM OF COMPLETION TIMES WITH
MAXIMUM ALLOWABLE TARDINESS
Working Paper No. 419
Suresh Chand
Purdue University
and
Hans M. Schneeberger
The University of Michigan
FOR DISCUSSION PURPOSES ONLY
None of this material is to be quoted or
reproduced without the expressed permission
of the Division of Research.
March 1985

ABSTRACT
This paper analyzes the Smith-heuristic for the single-machine scheduling
problem where the objective is to minimize the total weighted completion
time subject to the constraint that the tardiness for any job does not exceed
a prespecified maximum allowable tardiness. We identify several cases of
this problem for which the Smith-heuristic is guaranteed to lead to optimal
solutions. We also provide a worst-case-analysis of the Smith-heuristic;
the analysis shows that the fractional increase in the objective function
value for Smith-heuristic from the optimal solution is unbounded in the worst
case.

I

1. INTRODUCTION
The following single machine scheduling problem is considered in this paper.
Let N be the number of jobs available for scheduling and let T be the maximum
allowable tardiness. Further, let pi, ai, di, and Ci denote the processing
time, weight, due date and completion time, respectively, for job i. The problem
can the be stated as follows:
N
Minimize > aiCi
i=l
Subject to Ci - d < T
Note that the completion time Ci in a schedule is the sum of the processing time
of job i and all the jobs preceding job i. We will call this problem the
Constained Weighted Completion Time Problem (CWCT-Problem).
The CWCT-Problem was first considered by Smith [8] with T=O. He provided a
polynomial time algorithm for the case with equal weights al = a2 =... = aN.
He further proposed an extension for the case with unequal weights. Heck
and Roberts [4] generalized Smith's results for the case when T > 0. Smith [8]
and Heck and Roberts [4] conjectured that their algorithms for the CWCT-Problem
with unequal weights are optimal. Counter examples provided Emmons [3] and
Burns [1], however, show that these algorithms are not guaranteed to be optimal.
Lenstra et. al [5] and Chand and Schneeberger [2] show that this problem in
general is NP-hard; i.e., it is unlikely that a polynomial time algorithm could
be developed that would find optimal solutions to all instances of this problem.
Burns [1] and Miyazaki [6] recognized that the Smith-procedure is only locally
optimal in the sense that the pairwise interchange of any two adjacent jobs would
not improve the objective function. They then suggested some improvements over
the Smith-heuristic. Shanthikumar and Buzacott [7] proposed a Branch and Bound

2
algorithm and Chand and Schneebergur [2] developed a dynamic programming
algorithm with an inbedded Branch and Bound procedure to solve this problem.
In this paper, we identify several cases of the CWCT-Problem for which the
algorithm of Smith (Smith-heuristic) is guaranteed to give optimal solutions
(easy problems). The insights provided by these results can be very useful to
researchers in developing heuristics and optimal procedures for solving the
CWCT-Problem. In section 2, we briefly review and analyze the Smith-heuristic.
In section 3, we prove a new result: The CWCT-Problem with weights a, a2,..., aN
is equivalent to another CWCT-Problem with weights a1 + qp1, a2 + qP 22... aN + qPN'
where q is any known number. In section 4, we use the results from the previous
two sections in identifying the instances of the CWCT-Problem that can be solved
optimally in polynomial time. In section 5, we show that the worst - case -
performance of the Smith-heuristic can be made arbitrarily bad. The paper closes
in section 6 by summarizing the results. Throughout the rest of the paper, we
will assume T = 0. A CWCT-Problem with T > 0 can be converted into an equivalent
CWCT-Problem with zero maximum allowable tardiness simply by inflating all the
due dates by T.
2. REVIEW AND ANALYSIS OF THE SMITH-HEURISTIC
The following algorithm provided by Smith gives pairwise local optimal
schedule for the CWCT-Problem.
Algorithm (Smith):
(a) Arrange the jobs in the order of increasing due dates. It is
assumed that all jobs are on time in this schedule; if not, then the
problem does not have a feasible solution.

3
(b) Find jobs with due dates greater than or equal to the total processing
time of all jobs to be scheduled; these jobs are feasible candidates
for the last position in the sequence.
(c) Find the job with the largest p/a-ratio from the feasible jobs and
schedule it in the last position.
(d) Reduce the set of jobs yet to be scheduled by one, by removing the
job just scheduled in (c). Go to (b) until all jobs have been
scheduled by this method.
As reported in Lenstra et. al [5], the computational time for this algorithm
is bounded by O(NlogN).
Let [i] denote the job in position i in a given sequence. Miyazaki [6]
showed that the Smith-heuristic is globally optimal if C[+] < d[i]. Using
this result, he developed an improved algorithm with the computational time
bounded by 0(N). Burns [1] provided an algorithm (with computational time of
the order of 0(N3)) which finds a local optimum such that a pairwise interchange
of any two jobs would not improve the objective function.
The sufficient condition provided by Miyazaki for the optimality of the
Smith-heuristic is based on the characteristics of the final sequence. Such
conditions cannot be used, a priori, to find whether or not the heuristic is
optimal for the given class of problems. In this paper, our interest is to
find the characteristics of the problem data (due dates, weights, and processing
times) for which the Smith-heuristic is guaranteed to be optimal. One such
characteristic is given by the following theorem.

4
THEOREM 1: The Smith-heuristic is globally opitmal if the problem data is
such that
Pi > Pj - ai < aj for all jobs i and J, and ai > 0.
Proof: Note that steps (a) and (b) of the Smith-heuristic are needed to achieve
a feasible sequence. We only have to show that step (c) is optimal.
We prove the Theorem by contradiction. Assume that an optimal sequence
does not satisfy step (c) in the algorithm. This implies that there exist jobs
k and t with Pk/ak > pE/ai where both jobs are feasible candidates for the
last position of the sequence and job ~ is assigned to the last position. Job
k will then take a position earlier in the sequence. We show that in this case,
interchanging jobs k and ~ will always improve the objective function value.
Due to the specifications in the theorem, Pk/ak > pj/aE implies
Pk > PR and ak < at. Clearly, interchanging jobs k and t is feasible. Denote
the set of jobs between jobs k and t by Sk, with Z pi = P and Z ai = A. The
ieSk,t iCSk,z
decrease in the objective function value realized by interchanging jobs k and
L and rearranging the jobs in Sk, optimally is
AV > (pk-pt)A + (P+pk) a - (P+pa) a
- (Pk-P)A + P(.aQ-k) + PkaQ - ptak
>0 >0 >0
>0
Hence, AV is always positive which completes the proof.
Theorem 1 implies the following corollary.

5
Corollary 1: The Smith-heuristic is globally optimal when all ai's are equal,
i.e;, when a - a " -. a
1 2 N
Note that the result in Corollary 1 was proved by Smith also; thus,
Theorem 1 can be viewed as a generalization of this result of Smith.
In the next section we prove a result for finding equivalent CWCT-Problems.
3. EQUIVALENT CWCT-PROBLEMS
Two scheduling problems which differ from each other only by a constant in
the objective function will be considered equivalent. Clearly, any procedure
that solves a problem will also solve all the corresponding equivalent problems.
Let the notation (ai, Pi di)-problem denote the CWCT-Problem with weights
a, a2,..., aN; processing times pi, 2' '... PN; and due dates d1, d2,...,dN.
The following Theorem provides a way of finding equivalent problems to a given
CWCT-Problem.
THEOREM 2: The (ai, Pi' di)-problem is equivalent to the (ai+qpi, Pi' di)problem where q is any known constant.
Proof: Let p[i] denote the job in position i. Then C[i] can be expressed as
C[i] ZP[j]
j=l
The objective function for the (ai + qPi Pi' di)-problem can then be written
as:

6
N
V = (a + qpi)C
i=l
N N
N
= objective function for the (ai Pi, di)-problem + q ZpiC
i=l
Note that
N N i
q PiCi- q Z E P(]P[j]
i-l iil j=1
N i
= q SE pipj
i=1 j=l
= constant.
Thus, the objective function value for the (a,, Pi, di)-problem differs from
that for the (a + qPi, Pi, di)-problem only by a constant. This completes
the proof.
In.the next section, using the results in theorems 1 and 2, we identify
instances of the CWCT-problem where the Smith-heuristic is guaranteed to be
globally optimal.
4. SOME EASY PROBLEMS
To make the presentation easier, we assume that the weight assigned to a
job is a function of it's processing time; that is, ai f(pi), il,2,...,N.
This assumption implies that a = a when pi = pj. The results in this
section can be easily extended to the situation when this assumption does not
hold.

7
With this assumption, the result in Theorem 1 can be restated as follows:
the CWCT-Problem with the weight a = f(p) a non-increasing function of p and
f(p ) > 0 for i1l, 2,..., N is an easy problem. Using the result in Theorem 2
we can state that any (f(pi), Pi, di)-problem for which there exists a q such
that f(p) + qp is a non-increasing function of p and f(pi) + qPi > 0, for
il1, 2,...,N, is also an easy problem; the following result gives a necessary
and sufficient condition for the existence of such a q.
THEOREM 3: Let the jobs be numbered such that p < p2 <,... PN. Consider
a (f(pi), Pi' di)-problem. An equivalent (f(Pi) - qPi Pi' di)-problem with
f(Pi) - qP > 0 for i=l, 2,..., N can be found if and only if
f(PN/PN < f(Pi)/P for i1l, 2,..., N (1)
f(p i+) - f(pi+l)
and f(P > for il, 2,..., N-l. (2)
Pi -Pi
Proof: Let q - f(p )/PN. From (1) we have
q < f(pi)/Pi for i=l, 2,...,N
or f(Pi) qPi > ~ for iml, 2,..., N.
From (2), we have
q > (Pi+l) (i for i - 1, 2,..., N-1
Pi+l Pi
or f(p ) - f(Pi+) qPi+ for i=l, 2,..., N-1.
Thus, these conditions are sufficient. We now show that these conditions
are necessary also.
The requirement that f(pi) - qi > 0 for il, 2,...,N implies
q < f(Pi)/Pi for i-l, 2,...,N
(3)

8
The requirement that f(p) - qp be a non-increasing function of p implies
f(i) - q f(Pi+l) -qPi+ for i=l, 2,...,N-1
f(Pi) - f(pi)
or q > (4)
Pi+l Pi
From (3) and (4), we have
f(Pi) - f(Pi)
f(Pi )/Pi _ ----> for i-l, 2,..., N-1
or Pi+l f(Pi) Pi f(Pi) > Pi f(Pi+l) - Pif(pi)
or f(P)/Pi > f(Pi+l)/pi+ for i=l, 2,...,N-1
or fPN)/N < f(Pi)/Pi for i=l, 2.....N.
Thus, q < f(pN)/pPN From (4), we have
f(Pi+l) - f(Pi)
f(PN)/PN _ for i=l, 2.... N-1
i+l Pi
This completes the proof.
The following Corollary gives a simple procedure to determine if the given
(f(Pi)' Pi, di)-problem is an easy problem.
Corollary: Consider a (f(pi), Pi di)-problem. An equivalent
q- f(p )/p
q max /Pmax
I- rmr.-
1-11 ~~

9
The results in Theorems 1 and 3 imply that the following three problems
are easy problems.
Easy Problem 1: The (f(pi). Pi. di)-problem with f(p) a non-increasing function
of p and f(p) 0 for i=l, 2,...,N is an easy problem.
f(p)
p
Figure 1: Easy Problem 1
Easy Problem 2: The (f(pi), Pi' di)-problem with f(p) an increasing convex
function of p is an easy problem if the job with the largest processing time
has the largest p/f(p)-ratio.
f(p)
P P
Figure 2: Easy Problem 2
Easy Problem 3: The (f(p ), Ps di)-problem with f(p) an increasing concave
function of p is an easy problem if Ap/Af(p) for the smallest two jobs is
greater than or equal to the p/f(p)-ratio for the largest job.

10
f(p) /
P Pmax
It should be noted that Easy Problems 1, 2, and 3 can be solved optimally
using the Smith-heuristic.
5. WORST-CASE-ANALYSIS
We first give an example of a 3-job problem where the maximum fractional
increase in the objective function value for the Smith-heuristic (compared to
the optimal solution) can be made arbitrarily large. The data for this example
is given below. In this example x is a control variable with value > 1.7
(explained later).
Job
1
2
3
2
Processing Time 6x x 4
2 22
Due Date x + 6x + 4 x + 6x x+ 6x + 4
Weight 5x 14
The sequence found by the Smith-heuristic is 3-2-1
function value equal to S:
S = 5 x3 + 31 x2 + 20 x + 20
with the objective
The optimal sequence is 1-2-3 with the objective function value equal to V:
V = 35 x2 + 30 x + 16
we have V < S for x > 1.7.

11
S-V
Fractional Increase =
5x - 4 - 10/x + 4/x2
35 + 30/x + 16/x2
Clearly, the fractional increase can be made arbitrarily large by increasing
the control parameter x.
If we add Job 4 in the above example with processing time = p4, weight = w4
~~~~~~~~~and the due dated ~= w4
2
and the due date d4 = d3 + P4 = x + 6x + 4 + P4' then the fraction increase is
5x - 4 - 10/x + 4/x2
35 + 30/x + 16/x2 + (x2 + 6x + 4+ p )w4/x2
which can be made arbitrarily large by increasing x for any finite p4- and w4 -values. It is now easy to see that if we add (N-3) jobs, N > 4, in the above
example such that processing times and weights for these jobs are finite and
di+l = di +Pi+l for i = 3,4,...,N, then the fractional increase for the Smithheuristi- can be made arbitrarily large by increasing x. This proves that the
worst-case-performance of the Smith-heuristic can be made arbitrarily bad for
problems of any size.
6. SUMMARY
In this paper, we analyzed the Smith-heuristic for the single-machine
scheduling problem where the objective is to minimize the total weighted
completion subject to no tardiness. Several problems were identified which can
be solved optimally by using the Smith-heuristic. It was established that the
fractional increase in the objective function value for the Smith-heuristic
compared to the optimal solution can be made arbitrarily large in the worst
case for problems of any size.

12
REFERENCES
Burns, R. N., "Scheduling to Minimize the Weighted Sum of Completion Times
with Secondary Criteria," Naval Research Logistics Quarterly, Vol. 23,
No. 1 (1976), pp. 125-129.
Chand, S. and H. Schneeberger, "Single Machine Scheduling to Minimize
Weighted Completion Time with Maximum Allowable Tardiness," Working
Paper, Krannert Graduate School of Management, Purdue University.
Emmons, H., "Note on a Scheduling Problem with Dual Criteria," Naval
Research Logistics Quarterly, Vol. 22, No. 4 (1975), pp. 615-616.
Heck, H. and S. Roberts, "A Note on the Extension of a Result on Scheduling
with a Secondary Criteria," Naval Research Logistics Quarterly, Vol.
19, No. 3 (1972), pp. 403-405.
Lenstra, J. K., A. H. G. Rinnooy Kan, and P. Brucker, "Complexity of
Machine Scheduling Problems," Annals of Discrete Mathematics, 1,
1979, pp. 343-362.
Miyazaki, Shigeji, "One Machine Scheduling Problem with Dual Criteria,"
Journal of the Operations Society of Japan, Vol. 24, No. 1 (1981),
pp. 37-50.
Shanthikumar, J. G. and Buzacott, J. A., "On The Use of Decomposition
Approaches in A Single Machine Scheduling Problem," Journal of the
Operations Society of Japan, Vol. 25, No. 1 (1982), pp. 29-47.
Smith, W. E., "Various Optimizers for Single Stage Production," Naval
Research Logistics Quarterly, Vol. 3, No. 1 (1956), pp. 59-66.