PII: S0377-2217(98)00023-X
Theory and Methodology
A comparative study of dispatching rules in dynamic ¯owshops
and jobshops
Chandrasekharan Rajendran
a
, Oliver Holthaus
b,*
a
Industrial Engineering and Management Division, Department of Humanities and Social Sciences, Indian Institute of Technology,
Madras 600 036, India
b
Faculty of Business Administration and Economics, Department of Production and Operations Management, University of Passau,
Dr-Hans-Kap®nger-Str. 30, 94032 Passau, Germany
Received 1 December 1996; accepted 1 December 1997
Abstract
This paper presents a comparative study on the performance of dispatching rules in the following sets of dynamic
manufacturing systems: ¯owshops and jobshops, and ¯owshops with missing operations and jobshops. Three new
dispatching rules are proposed. We consider a total of 13 dispatching rules for the analysis of the relative performance
with respect to the objectives of minimizing mean ¯owtime, maximum ¯owtime, variance of ¯owtime, proportion of
tardy jobs, mean tardiness, maximum tardiness and variance of tardiness. First, we carry out the simulation study in
¯owshops with jobs undergoing processing on all machines sequentially and in jobshops with random routeing of jobs.
The results of the study reveal some interesting observations on the relative performance of the dispatching rules in
these two types of manufacturing systems. Next, we consider ¯owshops with missing operations on jobs and jobshops
with random routeing of jobs. We observe some interesting results in the sense that the performance of dispatching rules
is being in¯uenced by the routeing of jobs and shop¯oor con®gurations. Ó 1999 Elsevier Science B.V. All rights
reserved.
Keywords: Flowshop; Jobshop; Dispatching rules; Simulation study
1. Introduction
The problem of scheduling in dynamic job-
shops has been extensively studied for many years
and it attracts the attention of the researchers and
practitioners equally. The problem is usually
characterized as one in which a set of jobs, each
consisting of one or more operations to be per-
formed in a speci®ed sequence on speci®ed ma-
chines and requiring some process times, is to be
processed over a period of time. The objective is to
determine the job schedules that minimize a mea-
sure (or multiple measures) of performance. The
problem of scheduling in ¯owshops is usually
investigated with a static arrival of jobs and
hence, research is mostly directed towards the
European Journal of Operational Research 116 (1999) 156±170
*
Corresponding author. Tel.: 49 851 5 09 2454; fax: 49 851 5
09 2452; e-mail: holthaus@uni-passau.de.
0377-2217/99/$ ± see front matter Ó 1999 Elsevier Science B.V. All rights reserved.
PII: S 0 3 7 7 – 2 2 1 7 ( 9 8 ) 0 0 0 2 3 – X
development of exact and approximate solution
techniques (Baker, 1974; French, 1982; Pinedo,
1995). In many real-life situations, it is quite
common to encounter a dynamic and stochastic
arrival of jobs in manufacturing systems and hence
the scheduler makes use of dispatching rules to
derive the job schedules. While many studies have
concentrated on the problem of scheduling in dy-
namic jobshops (see the survey articles of Black-
stone et al., 1982; Haupt, 1989; Ramasesh, 1990
for a detailed discussion), there have been rela-
tively few studies on dynamic ¯owshops (e.g.
Scudder and Ho�mann, 1987; Hunsucker and
Shah, 1992; Hunsucker and Shah, 1994). We also
®nd that there appears to be no earlier study pre-
senting a comparative analysis of dispatching rules
in jobshops and ¯owshops. These observations
have been the motivation for the present work on
dynamic ¯owshops and jobshops.
This paper ®rst presents a literature review of
earlier research work on dynamic ¯owshops and
jobshops, followed by the identi®cation of the ex-
isting rules and the development of new dispatch-
ing rules for a performance analysis. The jobshop
and ¯owshop models are subsequently presented
with details of experimental set-ups. We consider
two types of ¯owshops: one in which all jobs un-
dergo processing on all machines and the other
one in which jobs have missing operations on some
machines. The results of the simulation experi-
ments are discussed for the two cases separately:
¯owshops and jobshops, and ¯owshops with
missing operations and jobshops. The interesting
aspects of the ®ndings are also brought out.
2. Literature review
A dispatching rule is used to select the next job
to be processed from a set of jobs awaiting service
at a facility that becomes free. The di�culty of the
choice of a dispatching rule arises from the fact
that there are n! ways of sequencing n jobs waiting
in the queue at a particular facility and the shop-
¯oor conditions elsewhere in the shop may in¯u-
ence the optimal sequence of jobs at the present
facility. Dispatching rules are normally intended to
minimize the inventory and/or tardiness costs. It is
a customary practice to minimize the ¯owtime-
related and tardiness-related measures of perfor-
mance since the associated inventory and tardiness
costs are assumed to be directly proportional to
the time periods of ¯owtime and tardiness of jobs,
respectively, for the sake of theoretical research
(Blackstone et al., 1982). The dispatching rules can
be classi®ed into ®ve categories: (1) rules involving
process times, (2) rules involving due-dates, (3)
simple rules involving neither process times nor
due-dates, (4) rules involving shop¯oor conditions
and (5) rules involving two or more of the ®rst four
classes. It has been observed that no single rule
performs well for all important criteria related to
¯owtime and tardiness of jobs. In general, it has
been noted that process-time based rules fare bet-
ter under tight load conditions, while due-date
based rules perform better under light load con-
ditions (Conway, 1965; Rochette and Sadowski,
1976; Blackstone et al., 1982). Of course, the
choice of a dispatching rule depends upon which
criterion is to be met with, viz. the minimization of
mean ¯owtime or mean tardiness or variance of
¯owtime or tardiness. A typical process-time based
rule is the famous SPT (shortest process time) rule
being used as a bench-mark quite often since this
rule is found to be very e�ective in minimizing
mean ¯owtime and also minimizing mean tardi-
ness under highly loaded shop¯oor conditions
(Conway, 1965; Rochette and Sadowski, 1976;
Blackstone et al., 1982; Haupt, 1989). As for the
due-date based rules, the earliest due-date (EDD)
rule is perhaps the most popular rule. The rules
such as the (®rst in, ®rst out) FIFO rule do not
make use of any information on the process time
or due-date of a job, and is often used as a bench-
mark since the FIFO rule is quite e�ective in
minimizing the maximum ¯owtime and variance of
¯owtime in many cases. The more complex rules
make use of both process time and due-date in-
formation, e.g. Least Slack rule, Critical Ratio,
etc. (see Blackstone et al., 1982; Haupt (1989), for
a detailed presentation of several rules). There
are some rules which load the jobs depending
on shop¯oor conditions rather than on the
characteristics of jobs. An example of this type
of rule is the WINQ rule (total work-content
of jobs in the queue of the next operation of a
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 157
job) (Haupt, 1989). Day and Hottenstein (1970),
Blackstone et al. (1982), Haupt (1989) and Ra-
masesh (1990) present excellent reports on some of
the widely used and popular dispatching rules for
jobshop scheduling.
It is a customary practice for researchers to as-
sume in the case of ¯owshop scheduling that all jobs
are available at the beginning of the scheduling
period (Baker, 1974; French, 1982; Pinedo, 1995). It
is therefore quite natural that many optimizing and
heuristic algorithms have been developed for min-
imizing makespan or total ¯owtime or both (e.g.
Ignall and Schrage, 1965; Campbell et al., 1970;
Dannenbring, 1977; Nawaz et al., 1983; Rajendran,
1994; Ho, 1995; Ishibuchi et al., 1995). However,
when job arrivals are dynamic and stochastic, and
job process times are not deterministic, the use of
dispatching rules is resorted to in the case of ¯ow-
shops (e.g. Hunsucker and Shah, 1992, 1994).
These studies have considered some simple dis-
patching rules such as the SPT, FIFO and LPT
(longest process time) rules, and have not consid-
ered the more e�cient rules such as the COVERT
rule (see Russell et al., 1987 for a detailed discussion
of this rule) or the rules by Anderson and Nyirenda
(1990), or Raghu and Rajendran (1993). Therefore,
we observe that the existing studies on dynamic
¯owshops are not quite exhaustive. For the case of
special operating conditions such as the pro®ts as-
sociated with jobs or lot splitting or di�erential job
speeds relative to due-dates, some problem-speci®c
dispatching rules have been developed (e.g. Scudder
and Ho�mann, 1987; Smunt et al., 1996). It is evi-
dent that the problem of scheduling in dynamic
¯owshops has not received the attention as much as
the problem of scheduling in dynamic jobshops. It is
also clear that there seems to be no prior research on
the comparative analysis of dispatching rules in
¯owshops and jobshops. Such a study assumes
signi®cance since the nature of routeings is di�erent
in ¯owshops and jobshops, viz. unidirectional
routeing and random routeing of jobs, respectively,
and this di�erence may in¯uence the relative per-
formance of various dispatching rules. These ob-
servations have been the motivation for the present
study. In Section 3, we identify the existing rules
that are quite e�ective with respect to several mea-
sures of performance and subsequently present the
development of new dispatching rules for mini-
mizing the ¯owtime-related performance measures.
3. Identi®cation of the best existing rules and
development of new dispatching rules
Before we present the dispatching rules con-
sidered in this study, we introduce the terminology
used in this paper. Let
A study of the existing literature on jobshop
scheduling reveals that the following rules are
quite e�ective for di�erent measures of perfor-
mance.
(1) FIFO (®rst in, ®rst out): This rule is often
used as a bench-mark. The job that has entered the
queue at the earliest is chosen for loading. The
FIFO rule is an e�ective rule for minimizing the
maximum ¯owtime and variance of ¯owtime.
(2) AT (arrival time): The job with the earliest
arrival time in the shop is chosen for loading. The
priority index of job i is given by
Zi � Ti: �1�
This rule seeks to minimize the maximum ¯owtime
and variance of ¯owtime.
(3) EDD (earliest due-date): This rule is often
used in industries for its simplicity of implemen-
tation in the shop¯oor. Since this rule performs
well with respect to minimizing maximum tardi-
s time at which the dispatching decision is
made;
tij process time for operation j of job i;
operation j of job i is performed on the
machine that becomes free at the current
instant s and this machine requires a job to
be o�-loaded from the queue;
o(i) total number of operations on job i;
Di due-date for job i;
Wi total work-content of jobs in the queue of
the next operation of job i. If operation j is
the last operation for job i, then Wi is zero;
Ti time of arrival of job i;
Zi priority value assigned to job i at the time
of decision of dispatching.
158 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170
ness and variance of tardiness in the single-ma-
chine scheduling problem (Baker, 1974), we have
chosen to include it in the present study. The pri-
ority index is given as follows:
Zi � Di: �2�
(4) S/OPN (slack per remaining operation): The
job with the least slack per remaining number of
operations is chosen for loading. This rule is often
used as bench-mark for evaluating the rules with
respect to the tardiness-related measures of per-
formance. The priority of job i is given as follows:
Zi �
si=�o�i� ÿ j� 1� if si P 0;
si � �o�i� ÿ j� 1� if si < 0;
�
�3�
where the slack, si, is given by
si � Di ÿ sÿ
Xo�i�
q�j
tiq
!
: �4�
(5) COVERT (cost over time): This rule has
been extensively investigated in the literature (e.g.
Russell et al., 1987) and is found to be e�ective
when the tardiness-related measures of perfor-
mance are of importance in jobshop scheduling.
The COVERT rule computes a penalty function, ci,
depending upon the slack of job i, si, and the sum of
expected waiting times for the job's uncompleted
operations, WTi, and hence determines the priority
index, Zi, of the job. Mathematically, the priority
index, Zi, given in the rule is expressed as follows:
Zi � ci=tij;
where
ci �
WTi ÿ si� �=WTi if 06 si < WTi;
0 if si P WTi;
1 if si < 0:
8><
>: �5�
The job with the largest Zi is chosen for loading
and ties are broken by the smallest tij. The method
of dynamic average waiting time (DAWT) has
been used in the present study since this method is
found to be quite e�ective (see Russell et al., 1987).
(6) RR (rule by Raghu and Rajendran, 1993):
This rule seeks to minimize both mean ¯owtime
and mean tardiness of jobs. The simulation study
of this rule has revealed that the rule outperforms
the SPT rule in minimizing mean ¯owtime in many
cases, and that it outperforms the ATC rule by
Vepsalainen and Morton (1987), and the CR +
SPT and S/RPT + SPT rules by Anderson and
Nyirenda (1990) in minimizing mean tardiness.
The RR rule is based on the premise that in the
computation of the priority index of a job, if
proper weights are given to the components of
process time and due-date of a job, depending on
the utilization level of the machine, we could ex-
pect a good performance under a variety of
shop¯oor conditions such as di�erent due-date
settings and utilization levels. The RR rule also
reckons the probable waiting time of the job at the
machine of job’s next operation. The priority in-
dex, Zi, of job i is given as follows:
Zi � si � exp�ÿg� � tij
ÿ �
=RPTi � exp�g� � tij
� Wnxt; �6�
where g refers to the utilization level of the ma-
chine on which the job is to be loaded, RPTi de-
notes the sum of process times of uncompleted
operations, including the current operation, on job
i, and Wnxt indicates the probable waiting time of
job i at the machine of its next operation. This
waiting time is computed by taking into account
the relative priority of job i, when the job enters
the queue at the machine of its next operation.
(7) SPT (shortest process time): This rule is
perhaps the most commonly used rule for jobshop
scheduling and is found to be very e�ective in
minimizing mean ¯owtime and also in minimizing
mean tardiness under highly loaded shop¯oor
conditions (Conway, 1965; Rochette and Sadowski,
1976; Blackstone et al., 1982; Haupt, 1989).
Moreover, this rule is the most e�ective in mini-
mizing the proportion of tardy jobs in jobshops if
the due-date setting is not too loose.
(8) PT + WINQ (process time plus work-in-
next-queue): This rule has been recently proposed
by Holthaus and Rajendran (1997) and is found to
be the most e�ective in minimizing mean ¯owtime.
The priority index by this rule is as given below:
Zi � tij � Wi : �7�
(9) PT + WINQ + AT (process time plus
work-in-next-queue plus arrival time): This rule is
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 159
also proposed by Holthaus and Rajendran (1997),
and is found to be quite e�ective in minimizing the
maximum ¯owtime and variance of ¯owtime. The
priority index is de®ned as follows:
Zi � tij � Wi � Ti: �8�
(10) PT + WINQ + SL (process time plus
work-in-next-queue plus negative slack): Again,
developed by Holthaus and Rajendran (1997), this
rule minimizes the maximum tardiness and vari-
ance of tardiness of jobs. The priority index is
expressed as follows:
Zi � tij � Wi �minfsi; 0g: �9�
In all the above cases, except for the COVERT
rule, the job with the least Zi is chosen for loading.
We now present three new rules that seek to
minimize the ¯owtime-related measures of per-
formance.
Proposed rule 1 ((PT + WINQ)/TIS rule): The
motivation for this rule is the observation that the
SPT and PT + WINQ rules tend to delay the
completion times of jobs that have relatively large
process times and hence these rules result in large
values of maximum ¯owtime and variance of
¯owtime. The study by Holthaus and Rajendran
(1997) introduces the PT + WINQ rule, that is
found to be the most e�cient rule for minimizing
mean ¯owtime of jobs. Combining these two ob-
servations, and introducing a term corresponding
to the resident time (or Time-In-Shop) of job i
upto the current time instant, we present the new
rule formally:
Zi � tij � Wi
ÿ �
= sÿ Ti� �: �10�
The job with the least Zi is chosen for loading.
This rule seeks to minimize not only the mean
¯owtime, but also the maximum ¯owtime and
variance of ¯owtime because a job that has spent a
longer resident time in the shop would be preferred
for loading.
Proposed rule 2 (PT/TIS rule): This rule is a
simpli®ed version of rule 1. It makes use of the
information only on the process time and resident
time of job i. It is given as follows:
Zi � tij= sÿ Ti� �: �11�
The job with the least Zi is chosen for loading.
Proposed rule 3 (AT-RPT rule): This rule makes
use of the information on the resident time (or
Time-In-Shop) and the total remaining process
time of a job. It seeks to minimize the maximum
¯owtime and the variance of ¯owtime of jobs. The
priority index Zi is given by
Zi � ÿ sÿ Ti� � ÿ
Xo�i�
q�j
tiq: �12�
Since the term s is common to two jobs when their
priority values are compared, the priority index
gets reduced to the following:
Zi � Ti ÿ
Xo�i�
q�j
tiq: �13�
The job with the least Zi is chosen for loading.
We have now identi®ed a total of 10 existing
rules, apart from the three new dispatching rules,
for a performance analysis in ¯owshops and job-
shops.
4. Experimental design for the simulation study
A jobshop could be classi®ed into an open shop
and a closed shop, depending upon the way in
which jobs are routed in the shop. In a closed
shop, the number of routeings available to a job is
®xed and an arriving job can follow one of the
available routeings. In an open shop, there is no
limitation on the routeing of a job and each job
could have a di�erent routeing. In this paper we
consider the open shop con®guration. The typical
standard assumptions such as the processing of
only one operation on a given machine at a given
instant, no job preemption, an operation of any
job to be performed after the completion of all
its previous operations, machines being the only
limiting resources, no machine breakdowns, no
assembly of jobs, and no parallel machines
(Haupt, 1989; Ramasesh, 1990) are also made in
this study. As for the ®rst experimental evaluation
in ¯owshops and jobshops, we assume the presence
of 10 machines. In case of the ¯owshop, all jobs
undergo processing on all 10 machines sequentially
160 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170
starting from the ®rst machine. In case of the
jobshop, a random permutation of 10 machines is
chosen and the entering job undergoes processing
in the chosen permutation order. It means that no
machine will be revisited and all machines are
visited. The reason for generating a random per-
mutation of 10 machines and setting this permu-
tation as the sequence of operations for a job in
the jobshop is that we would like to have the same
experimental settings in the jobshop and ¯owshop
(where we have a unidirectional routeing of jobs
over 10 machines). As for the second experimental
evaluation in ¯owshops with missing operations
and jobshops, we assume the presence of 10 ma-
chines. In case of the jobshop, the number of op-
erations for an entering job is randomly sampled
in the set 2; 3; . . . ; 9; 10f g and the corresponding
machine visitations are randomly generated with
no machine being revisited. For example, if we
have the number of operations for an entering job
as 6, we sample six di�erent machines to be visited
by the job, say, {6-1-7-10-8-3}. In case of the
¯owshop with missing operations, the machine
visitation order will be {1-3-6-7-8-10}, in order to
maintain the unidirectional routeing of jobs. In
our opinion, such an approach of generating the
machine visitations in ¯owshops and jobshops
helps us to have the same experimental settings in
both jobshops and ¯owshops, so that we could
draw a meaningful comparison of the relative
performance of dispatching rules in these two
types of manufacturing systems. In all experi-
mental setups, the process times are drawn from a
uniform discrete distribution ranging from 1 to 49.
The total work-content (TWK) method of due-
date setting (Blackstone et al., 1982) is used in all
experiments with the allowance factor, c� 4, 6 and
8. The job arrivals are generated using an expo-
nential distribution for inter-arrival times. Four
machine-utilization levels Ug are tested in the ex-
periments, viz. 80%, 85%, 90% and 95%. Thus, in
all, there are three di�erent due-date settings and
four di�erent utilization levels (i.e. four di�erent
mean inter-arrival times), making a total number
of 12 simulation experiment sets for every dis-
patching rule for ¯owshops and jobshops sepa-
rately. It is a customary practice for researchers to
conduct simulation experiments with di�erent pa-
rameter settings. We ®nd in the literature that the
allowance factors in the range 3±8, and utilization
levels in the range 80±95% are commonly consid-
ered (see Blackstone et al., 1982; and Haupt, 1989).
While the number of machines in a jobshop could
be theoretically anything, it is usually set in the
range 6±12. This setting follows from the obser-
vations of Baker and Dzielinski (1960), and Nanot
(1963) that the shop size is not a signi®cant factor
in a�ecting the relative performance of rules and
that a shop with about nine machines should ad-
equately represent the complexity involved in large
dynamic jobshop operations.
In our study, each simulation experiment con-
sists of 20 di�erent runs (or replications). In each
run, the shop is continuously loaded with job-or-
ders that are numbered on arrival. In order to
ascertain when the system reaches a steady state,
we have observed the shop parameters, such as
utilization level of machines, mean ¯owtime of
jobs, etc. It has been found that the shop reaches a
steady state after the arrival of about 500 job-or-
ders. Typically, the total sample size in simulation
studies of jobshop scheduling is of the order of
thousands of job completions (Conway et al.,
1960; Blackstone et al., 1982). For a given total
sample size, it is preferable to have a smaller
number of replications and a larger run length,
and the recommended number of replications is
about 10 (Law and Kelton, 1984). Following these
guidelines, we have ®xed the number of replica-
tions as 20, with the run length for every replica-
tion as 2000 completed job-orders. The statistical
analysis of the experimental data with single-factor
ANOVA with block design (Common Random
Numbers for one block) and Duncan’s Multiple
Range Test (Montgomery, 1991; Lorenzen and
Anderson, 1993) has shown that this sample size
yields a variance which results in a Type I error of
at most 1%. As for the computation of statistics
from a given replication, we have collected data
from orders numbering from 501 to 2500, and the
shop is further loaded with jobs, until the com-
pletion of these 2000 numbered job-orders. This
helps in overcoming the problem of `censored da-
ta’ (Conway, 1965). The simulation program has
been written in C++ and implemented on a Pent-
ium PC.
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 161
5. Results and discussion
The performances of the 13 rules under study
are evaluated with respect to mean ¯owtime of
jobs �F �, maximum ¯owtime Fmax� � and variance
of ¯owtime r2F
ÿ �
, percentage of tardy jobs (%T),
mean tardiness �T �, maximum tardiness �Tmax� and
variance of tardiness r2T
ÿ �
. The results of the sim-
ulation study for some sets of parameter values are
presented in Tables 1±4. These results are obtained
by taking the mean over 20 replications. The
complete set of results (corresponding to four
utilization levels and three allowance factor values)
could not be presented for want of space and also
due to the reason that the other results are not
substantially di�erent from what are currently
given. We now discuss some typical results of the
experimental analysis for the conventional ¯ow-
shops and jobshops, followed by the analysis for
¯owshops with missing operations and jobshops.
5.1. Flowshops and jobshops
Tables 1 and 2 present the values of F ; Fmax; r2F ;
%T, T ; Tmax and r2T yielded by the 13 dispatching
rules in conventional ¯owshops (Table 1) and in
jobshops (Table 2) using the utilization levels
Ug� 80% and Ug� 95% and the allowance factors
c� 4 and c� 6. For each combination of utiliza-
tion level, allowance factor and performance
measure, those mean values which are signi®cantly
smaller than the other mean values are marked
with an asterisk.
5.1.1. Mean ¯owtime
The rules SPT and PT + WINQ reduce to be
the same in the case of ¯owshops since the WINQ
component is the same for all jobs. For ¯owshops,
the SPT and PT + WINQ rules emerge to be the
best, while the RR rule performs very well with
utilization levels up to 90%. When the ¯owshop is
heavily loaded at 95% utilization level, the per-
formance of the RR rule improves as the due-date
setting becomes loose. At tight due-date settings,
the slack component of the RR rule serves to
hasten the tardy jobs and in the process, the per-
formance of the RR rule is very good with respect
to minimizing the mean tardiness at the expense of
an enhanced mean ¯owtime. Moreover, the look-
ahead component, Wnxt, of the RR rule does not
seem to be quite e�ective in ¯owshops since all
jobs have the same operation as the next one.
As for jobshops, the performance of the RR
rule is better at high utilization levels than at low
utilization levels due to the relative e�ectiveness of
its look-ahead component, Wnxt, whereas the per-
formances of the PT + WINQ and SPT rules are
consistent and good in the same order. The dif-
ference in the performance of the RR rule in
¯owshops and jobshops is due to the presence of
the look-ahead component, Wnxt, in it and this
component is more meaningful in the case of
jobshops (due to non-unidirectional routeing of
jobs) than in ¯owshops. It is also known that the
rules making use of the information on process
and waiting times of jobs perform quite well in
jobshops, and therefore we observe the good per-
formances of the PT + WINQ, SPT and RR rules.
5.1.2. Maximum ¯owtime and variance of ¯owtime
For minimizing maximum ¯owtime the per-
formances of the FIFO, AT, AT-RPT, PT/TIS,
(PT + WINQ)/TIS and PT + WINQ + AT rules
are almost comparable in the case of ¯owshops.
The reason for the similarity between the perfor-
mances of the PT + WINQ + AT and AT-RPT
rules on the one hand, and those of the FIFO and
AT rules on the other hand is that the WINQ and
RPT components in the former two rules do not
play a dominant role in the priority index com-
putations in ¯owshops since all jobs have the same
unidirectional routeing and the expected values of
the total remaining process times of di�erent jobs
will not substantially di�er. However, for job-
shops, the AT-RPT and PT + WINQ + AT rules
emerge to be the best for most of the cases. It is
noteworthy that the AT rule emerges to be better
than the FIFO rule. The reason is that the AT rule
hastens the job that has a larger resident time in
the entire shop¯oor rather than myopically con-
sidering resident time in the current queue.
With respect to the minimization of variance of
¯owtime the rules PT/TIS and (PT + WINQ)/TIS
are very e�ective in the case of ¯owshops, whereas
for jobshops, the AT-RPT and PT + WINQ + AT
162 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170
Table 1
Performance of rules in conventional ¯owshops
Ug(%) c Rule F Fmax rF 2 %T T Tmax rT 2
80 4 FIFO 636.5 �1237.7 39344.2 9.1 13.7 562.7 3207.4
AT 636.2 �1237.7 39260.9 9.0 13.6 560.8 3184.8
AT-RPT 645.4 �1256.4 40115.0 10.2 15.8 583.9 3780.4
EDD 607.5 1535.9 59307.2 4.2 4.5 �190.6 742.2
S/OPN 613.8 1533.6 58221.3 4.7 5.3 �204.9 920.4
COVERT 528.3 1549.0 49988.6 2.6 �1.0 �198.4 �161.7
RR 524.2 1525.6 41903.0 �1.6 �1.4 �227.3 �229.1
SPT �520.3 3665.0 87233.1 4.4 21.1 2610.4 23070.7
PT+WINQ �520.3 3665.0 87233.1 4.4 21.1 2610.4 23070.7
PT/TIS 540.6 �1275.2 �30107.3 2.5 2.8 355.1 568.6
(PT+WINQ)/TIS 553.4 �1236.4 �28624.5 3.0 3.2 374.9 589.8
PT+WINQ+AT 606.1 �1199.8 35243.0 6.8 9.6 492.8 2184.4
PT+WINQ+SL 524.3 1612.3 54542.6 6.7 6.4 �243.4 774.4
80 6 FIFO 636.5 �1237.7 39344.2 0.7 0.8 295.6 210.5
AT 636.2 �1237.7 39260.9 0.7 0.8 294.6 208.6
AT-RPT 645.4 �1256.4 40115.0 0.8 1.1 324.4 278.9
EDD 602.1 1741.3 76003.7 �0.0 �0.0 �0.0 �0.0
S/OPN 604.8 1718.8 73666.9 �0.0 �0.0 �0.0 �0.0
COVERT �520.9 2126.3 66332.9 �0.2 �0.1 26.5 �1.1
RR 524.2 1647.5 47365.7 �0.0 �0.0 �0.0 �0.0
SPT �520.3 3665.0 87233.1 1.3 7.8 2102.3 9892.0
PT+WINQ �520.3 3665.0 87233.1 1.3 7.8 2102.3 9892.0
PT/TIS 540.6 �1275.2 �30107.3 �0.1 �0.1 50.5 �8.1
(PT+WINQ)/TIS 553.4 �1236.4 �28624.5 �0.1 �0.1 90.9 �15.1
PT+WINQ+AT 606.1 �1199.8 35243.0 0.4 0.5 237.2 124.5
PT+WINQ+SL �521.3 2220.2 69707.4 1.7 1.6 204.2 198.8
95 4 FIFO 1998.8 �2974.4 �243347.6 94.2 1008.3 2309.3 220889.9
AT 1998.8 �2975.1 �243161.7 94.2 1008.2 2310.8 220788.4
AT-RPT 2006.1 �2976.5 �242573.2 94.5 1014.6 2332.2 224693.9
EDD 1977.8 3292.2 280154.9 94.7 984.5 1950.8 200524.4
S/OPN 1986.6 3293.4 280116.3 94.8 993.2 1969.8 205411.4
COVERT 1425.6 21425.7 2512371.2 76.2 �457.3 20311.0 2341636.3
RR 1628.3 4482.8 442143.8 76.2 687.5 3365.9 270522.1
SPT �1280.7 35988.8 6803343.8 �25.5 573.4 34922.6 6029416.4
PT+WINQ �1280.7 35988.8 6803343.8 �25.5 573.4 34922.6 6029416.4
PT/TIS 1401.3 �2954.0 �229385.5 74.3 �459.9 1923.2 �127902.2
(PT+WINQ)/TIS 1503.3 �2880.8 �196695.7 80.7 544.8 1883.0 �124081.1
PT+WINQ+AT 1926.4 �2912.9 �243068.8 92.6 939.5 2217.1 208227.4
PT+WINQ+SL 1715.2 �3024.0 293585.2 87.5 759.1 �1671.0 �155500.9
95 6 FIFO 1998.8 �2974.4 �243347.6 75.0 586.9 2034.5 155609.3
AT 1998.8 �2975.1 �243161.7 75.0 586.7 2036.0 155530.6
AT-RPT 2006.1 �2976.5 �242573.2 75.2 592.3 2055.9 157960.6
EDD 1953.6 3467.9 321699.1 72.9 536.4 1430.3 117890.6
S/OPN 1964.7 3466.4 318035.8 73.5 545.6 1443.8 119734.8
COVERT 1471.3 13711.1 974967.2 44.5 �186.8 12133.4 694286.3
RR 1370.0 3340.1 316480.8 38.2 �168.9 1326.5 �59862.6
SPT �1280.7 35988.8 6803343.8 �15.3 469.9 34389.4 5636553.9
PT+WINQ �1280.7 35988.8 6803343.8 �15.3 469.9 34389.4 5636553.9
PT/TIS 1401.3 �2954.0 �229385.5 40.3 �179.9 1522.1 �61857.6
(PT+WINQ)/TIS 1503.3 �2880.8 �196695.7 48.8 227.6 1513.4 �65108.1
PT+WINQ+AT 1926.4 �2912.9 �243068.8 71.4 532.1 1945.0 142990.2
PT+WINQ+SL 1472.4 �3005.0 386009.1 59.5 264.4 �934.5 �58037.4
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 163
Table 2
Performance of rules in jobshops
Ug(%) c Rule F Fmax rF 2 %T T Tmax rT 2
80 4 FIFO 839.1 1962.0 73655.1 27.1 62.4 1068.2 17985.2
AT 811.3 1536.8 46482.4 22.9 39.4 731.0 8533.8
AT-RPT 809.9 �1422.7 �38070.2 22.9 38.9 733.6 8263.7
EDD 785.3 1825.0 71070.5 15.0 21.3 485.2 4065.5
S/OPN 780.0 1606.8 62078.1 5.7 6.1 �305.1 1229.1
COVERT 651.4 1681.0 65733.0 �3.2 �1.9 �318.4 �449.0
RR 642.6 1592.3 54204.1 �2.2 �1.8 �272.8 �332.7
SPT �633.6 3777.6 122044.2 8.6 35.1 2626.0 31329.9
PT+WINQ �630.2 2703.2 74648.3 8.8 23.7 1604.5 12837.2
PT/TIS 684.1 1546.5 42018.0 7.8 9.9 510.4 2091.4
(PT+WINQ)/TIS 670.9 1762.0 43833.2 9.0 14.8 801.9 4205.1
PT+WINQ+AT 761.3 1479.2 41168.7 16.7 25.3 655.9 5385.7
PT+WINQ+SL �634.1 1669.4 58716.2 11.2 13.4 �373.4 1927.2
80 6 FIFO 839.1 1962.0 73655.1 4.1 7.7 698.6 2580.5
AT 811.3 1536.8 46482.4 2.0 2.7 452.5 642.8
AT-RPT 809.9 �1422.7 �38070.2 2.0 2.8 458.8 684.9
EDD 770.3 1949.2 91904.5 �0.1 �0.1 29.2 �4.2
S/OPN 812.0 2039.2 121691.2 �0.0 �0.0 �0.4 �0.0
COVERT �635.5 2162.0 94553.8 �0.1 �0.1 �4.8 �0.0
RR 684.7 1930.2 88172.3 �0.0 �0.0 �2.4 �0.1
SPT �633.6 3777.6 122044.2 2.3 10.9 2086.1 11901.9
PT+WINQ �630.2 2703.2 74648.3 1.6 4.6 1104.4 2952.0
PT/TIS 684.1 1546.5 42018.0 0.3 0.2 150.9 47.3
(PT+WINQ)/TIS 670.9 1762.0 43833.2 0.7 1.1 435.0 333.9
PT+WINQ+AT 761.3 1479.2 41168.7 1.2 1.3 365.9 300.8
PT+WINQ+SL �632.2 2052.1 70490.1 1.9 2.1 262.4 339.6
95 4 FIFO 2418.2 4452.4 389561.2 98.1 1419.4 3528.4 383376.4
AT 1958.0 2978.4 159891.9 98.0 958.6 2187.7 168511.5
AT-RPT 1956.8 2853.4 �144409.3 98.1 957.3 2190.1 162342.9
EDD 1936.0 3248.3 196001.2 98.3 936.1 1928.0 146660.8
S/OPN 2079.3 5420.6 690911.9 97.3 1079.0 4340.8 641894.2
COVERT 1530.5 21714.8 2216269.4 80.5 541.0 20645.7 2034123.3
RR �1347.7 3580.2 239339.2 74.7 �386.0 2274.2 123806.7
SPT 1466.8 25875.4 4817213.2 �38.6 660.4 24704.8 4079225.6
PT+WINQ 1428.8 12306.1 1320991.3 57.8 543.8 11183.8 1006503.7
PT/TIS 1556.8 3091.0 196891.1 88.8 572.3 2015.7 134509.2
(PT+WINQ)/TIS 1513.3 3937.2 261927.1 81.5 547.2 2955.4 199304.8
PT+WINQ+AT 1785.8 2862.1 �146081.1 95.7 790.1 2049.3 144365.1
PT+WINQ+SL 1493.2 �2714.4 161474.1 88.5 522.1 �1485.4 �83276.2
95 6 FIFO 2418.2 4452.4 389561.2 88.0 951.1 3123.9 314105.9
AT 1958.0 2978.4 159891.9 78.4 512.2 1908.8 121015.5
AT-RPT 1956.8 �2853.4 �144409.3 78.5 512.1 1933.2 118370.9
EDD 1925.9 3496.1 243087.0 78.8 470.1 1462.7 90536.6
S/OPN 1829.8 4420.8 335557.8 61.9 376.8 2676.1 195127.7
COVERT 1514.5 11302.6 643845.8 36.3 158.4 9629.0 430994.7
RR �1296.7 3063.2 194157.2 �24.2 �62.7 �1018.1 �19207.9
SPT 1466.8 25875.4 4817213.2 �22.4 504.8 24124.1 3705205.9
PT+WINQ 1428.8 12306.1 1320991.3 30.4 333.5 10623.6 803002.8
PT/TIS 1556.8 3091.0 196891.1 50.9 223.6 1570.1 69300.0
(PT+WINQ)/TIS 1513.3 3937.2 261927.1 45.1 241.4 2538.2 119471.9
PT+WINQ+AT 1785.8 �2862.1 �146081.1 68.9 376.9 1751.3 92919.0
PT+WINQ+SL 1416.2 �2862.6 239849.4 54.3 175.2 �889.6 �25100.3
164 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170
rules have the best performance. With respect to
all ¯owtime-related performance measures the PT/
TIS and (PT + WINQ)/TIS rules seem to o�er
good compromise solutions between the SPT,
PT + WINQ and AT rules. The reason is that we
reckon the process time as well as the resident time
of jobs in the PT/TIS and (PT + WINQ)/TIS
rules. Of course, the ®nal choice between the PT/
TIS, (PT + WINQ)/TIS, SPT, PT + WINQ, PT +
WINQ + AT and AT rules depends on the relative
importance that the decision maker assigns to the
measures of performance such as mean ¯owtime,
maximum ¯owtime and variance of ¯owtime.
5.1.3. Percentage of tardy jobs
Up to 85% utilization levels, the RR rule fares
better than the SPT rule. At 90% and 95% utili-
zation levels, the SPT rule emerges better than the
RR rule, while the RR rule fares well under loose
due-date settings. The reason is that at highly
loaded conditions with tight due-date settings, the
slack component of the RR rule is dominant and it
loses its contribution as the allowance factor in-
creases. At this stage, the look-ahead component
of the RR rule serves to enhance the throughput of
jobs and consequently renders a less number of
jobs tardy. It is also interesting to observe that the
RR rule is not e�ective in ¯owshops as much as in
jobshops. The reason is due to the relative e�ec-
tiveness of the look-ahead component, Wnxt, in
jobshops (due to random routeing of jobs) as
against the case in ¯owshops.
5.1.4. Mean tardiness
The RR rule continues to be the best (or not
signi®cantly worse than the best rule) for this ob-
jective except for one case where we encounter the
¯owshop with a high utilization level of 95% and a
tight due-date setting of c� 4. As discussed earlier,
the look-ahead component, Wnxt, in the RR rule is
not so e�ective in ¯owshops since all jobs have the
same unidirectional routeing. The relative perfor-
mance of the COVERT rule seems to be better in
¯owshops than in jobshops. The reason is due to a
better estimation of waiting time of jobs on ma-
chines, when there is a unidirectional routeing of
jobs in ¯owshops.
5.1.5. Maximum tardiness and variance of tardiness
The RR rule seems to be quite e�ective for many
cases of jobshops and ¯owshops at utilization levels
of 80% and 85%. However, at highly loaded con-
ditions (90% and 95% utilization levels) and tight
due-date settings (c� 4), we ®nd that the PT +
WINQ + SL rule emerges to be better than the RR
rule for both jobshops and ¯owshops. Also at 95%
utilization level and c� 6, the PT + WINQ + SL
rule is a very e�ective rule for minimizing maximum
tardiness and variance of tardiness. The reason is
that many jobs are likely to be more tardy under
high utilization levels than under low utilization
levels and hence, the component of negative slack,
SL, becomes dominant and it serves to enhance the
performance of the PT + WINQ + SL rule under
highly loaded conditions. In the case of the RR rule,
we reckon the slack, irrespective of its positive or
negative value, and hence, the rule performs well
under di�erent conditions.
5.2. Flowshops with missing operations and jobshops
Tables 3 and 4 present the values of F ; Fmax; r
2
F ;
%T, T ; Tmax and r2T yielded by the 13 dispatching
rules in ¯owshops with missing operations on jobs
(Table 3) and in jobshops (Table 4) using the uti-
lization levels Ug � 80% and Ug� 95% and the
allowance factors c� 4 and c� 6. For each com-
bination of utilization level, allowance factor and
objective, those mean values which are signi®-
cantly better than the other mean values are
marked again with an asterisk.
5.2.1. Mean ¯owtime
For both ¯owshops with missing operations on
jobs and jobshops, the PT + WINQ rule emerges
to the best (or not signi®cantly worse than the best
performing rule) in all cases except for one case
where we encounter the jobshop with a high uti-
lization level of 95% and a due-date setting of
c� 6. It is also interesting to note that at higher
utilization levels (85%, 90%, 95%) the PT + WINQ
rule performs signi®cantly better than the SPT
rule.
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 165
Table 3
Performance of rules in ¯owshops with missing operations on jobs
Ug(%) c Rule F Fmax rF 2 %T T Tmax rT 2
80 4 FIFO 471.5 1480.3 72195.4 26.2 38.7 751.5 7788.5
AT 470.2 �1058.5 �40843.9 30.9 55.3 757.4 11221.0
AT-RPT 479.3 �1034.2 �37203.4 34.0 65.0 781.8 13117.0
EDD 460.3 1633.5 107960.4 17.0 21.1 �386.4 3574.2
S/OPN 459.4 1559.2 87709.4 15.8 19.2 503.1 3427.7
COVERT 390.5 1735.7 69805.2 7.9 �5.4 721.6 1848.3
RR 368.3 1568.9 62956.3 �5.2 �4.2 �336.1 �651.8
SPT �362.3 3409.2 92662.4 8.7 29.5 2530.3 24075.2
PT+WINQ �361.4 3039.8 83326.4 9.2 25.7 2070.2 17638.4
PT/TIS 393.2 1146.0 �36325.2 17.9 21.6 654.6 4053.3
(PT+WINQ)/TIS 391.8 1162.3 �39426.8 16.3 20.3 704.4 4134.8
PT+WINQ+AT 433.0 �1015.5 �37437.6 24.9 38.2 693.1 7427.5
PT+WINQ+SL 369.2 1526.0 65343.7 13.9 12.2 �303.4 1362.1
80 6 FIFO 471.5 1480.3 72195.4 6.9 8.1 526.8 1664.4
AT 470.2 �1058.5 �40843.9 13.3 22.1 692.7 5318.0
AT-RPT 479.3 �1034.2 �37203.4 15.6 27.8 726.5 6829.6
EDD 460.3 1983.9 145356.2 �0.9 �0.6 �100.1 �100.0
S/OPN 450.9 1860.8 107613.3 �0.7 �0.4 �69.4 �58.1
COVERT 367.8 1961.3 75223.7 �0.5 �0.1 �45.3 �2.7
RR 367.0 1685.1 70812.0 �0.2 �0.1 �41.0 �3.3
SPT �362.3 3409.2 92662.4 3.2 13.1 2148.4 11940.2
PT+WINQ �361.4 3039.8 83326.4 3.2 10.3 1671.0 7616.1
PT/TIS 393.2 1146.0 �36325.2 5.7 5.9 513.1 1167.3
(PT+WINQ)/TIS 391.8 1162.3 �39426.8 4.9 5.8 567.4 1310.8
PT+WINQ+AT 433.0 �1015.5 �37437.6 9.6 13.9 613.6 3132.1
PT+WINQ+SL �363.7 2051.2 74165.5 4.0 3.2 261.7 373.7
95 4 FIFO 1353.1 3327.8 535203.7 92.1 763.0 2515.4 272115.0
AT 1358.2 2237.9 192813.3 93.7 768.8 1971.4 153425.6
AT-RPT 1358.8 2219.7 �181969.7 93.5 770.5 1993.0 153907.6
EDD 1328.6 2877.1 343178.6 93.1 737.1 1627.6 139014.9
S/OPN 1339.7 3889.0 313302.6 94.1 745.7 3498.5 224101.2
COVERT 1002.7 23227.5 3001687.6 70.4 �419.6 22313.2 2693328.9
RR 1070.5 5782.9 561990.1 75.0 502.6 4842.6 259677.4
SPT 928.0 29870.2 4795080.9 �28.4 485.8 29057.6 4208952.6
PT+WINQ �857.2 18450.7 2039522.5 35.8 �396.0 17594.2 1635856.6
PT/TIS 1011.2 2545.8 216605.3 83.5 �438.4 2025.0 116667.8
(PT+WINQ)/TIS 992.0 3310.6 264667.8 78.7 �424.5 2835.4 142564.1
PT+WINQ+AT 1204.9 �2142.6 199307.3 89.4 622.2 1814.3 132322.2
PT+WINQ+SL 1091.4 2603.2 313607.7 84.2 518.9 �1380.7 �102675.8
95 6 FIFO 1353.1 3327.8 535203.7 76.5 506.6 2189.4 175121.7
AT 1358.2 2237.9 192813.3 78.5 524.0 1910.3 136154.3
AT-RPT 1358.8 2219.7 �181969.7 78.4 527.7 1931.6 138920.9
EDD 1311.9 3199.8 459776.6 76.4 457.0 1280.2 87282.1
S/OPN 1316.0 3473.8 381495.2 76.3 450.1 2530.7 120969.0
COVERT 1034.4 16793.2 1656189.5 45.5 221.6 15417.6 1266981.0
RR 955.8 3550.2 425115.3 47.1 �196.4 1922.2 63602.1
SPT 928.0 29870.2 4795080.9 �17.6 409.5 28651.3 3964078.8
PT+WINQ �857.2 18450.7 2039522.5 21.7 308.6 17190.5 1470441.4
PT/TIS 1011.2 2545.8 216605.3 57.8 245.1 1850.8 79426.1
(PT+WINQ)/TIS 992.0 3310.6 264667.8 52.6 240.4 2684.2 103412.0
PT+WINQ+AT 1204.9 �2142.6 199307.3 70.4 397.5 1742.8 107777.3
PT+WINQ+SL 996.6 2848.8 394469.1 60.7 244.0 �981.2 �45103.1
166 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170
Table 4
Performance of rules in jobshops with missing operations on jobs
Ug(%) c Rule F Fmax rF 2 %T T Tmax rT 2
80 4 FIFO 516.2 1712.3 86475.9 32.4 53.4 896.2 11121.4
AT 501.7 1168.3 45856.2 33.8 54.3 665.4 9343.8
AT-RPT 502.1 �1042.1 �35690.3 35.9 64.5 733.9 11770.1
EDD 488.3 1702.2 115346.1 20.4 24.2 497.4 3886.2
S/OPN 474.0 1485.8 85788.5 10.6 8.1 �329.9 �1106.5
COVERT 411.0 1676.8 72698.8 6.1 �3.3 560.5 �828.1
RR 390.9 1514.9 68808.7 �4.8 �3.3 �342.4 �487.0
SPT �386.9 3570.3 106870.8 9.9 32.8 2694.4 28315.4
PT+WINQ �386.7 2396.2 77373.2 11.8 25.3 1606.3 12187.3
PT/TIS 426.3 1243.2 42144.1 20.3 23.3 621.1 3953.7
(PT+WINQ)/TIS 415.2 1457.4 48029.0 17.6 23.3 786.6 5267.5
PT+WINQ+AT 463.5 1184.2 44190.3 26.9 38.1 621.2 6668.2
PT+WINQ+SL 391.6 1510.3 66546.7 15.7 15.4 �383.2 1878.7
80 6 FIFO 516.2 1712.3 86475.9 9.2 11.9 616.2 2620.8
AT 501.7 1168.3 45856.2 12.8 19.0 595.0 4046.2
AT-RPT 502.1 �1042.1 �35690.3 15.6 26.1 691.5 5988.6
EDD 482.9 1994.1 149206.5 0.7 0.3 139.1 38.3
S/OPN 484.9 1927.9 124193.8 �0.1 �0.0 �17.8 �0.3
COVERT 391.3 2023.6 83858.1 �0.3 �0.0 �25.0 �0.6
RR 408.4 1850.5 91365.4 �0.1 �0.0 �23.4 �0.6
SPT �386.9 3570.3 106870.8 3.4 14.6 2309.8 14520.8
PT+WINQ �386.7 2396.2 77373.2 3.6 8.3 1324.7 4531.8
PT/TIS 426.3 1243.2 42144.1 6.0 5.7 483.7 1007.7
(PT+WINQ)/TIS 415.2 1457.4 48029.0 5.2 6.6 646.0 1639.8
PT+WINQ+AT 463.5 1184.2 44190.3 9.4 12.4 540.7 2527.3
PT+WINQ+SL �387.5 1954.4 73236.6 4.1 3.6 283.4 478.9
95 4 FIFO 1434.2 3994.3 629934.0 94.0 841.3 3108.9 342886.4
AT 1246.2 2251.8 171821.8 94.7 653.9 1738.1 118542.4
AT-RPT 1250.8 �2105.1 �145608.1 94.4 659.9 1804.7 120134.5
EDD 1214.3 2860.2 329951.6 93.5 621.1 1606.0 117838.4
S/OPN 1297.8 3901.0 400364.7 95.0 701.5 2929.8 274367.4
COVERT 1003.7 20655.2 2387068.7 69.5 419.0 19734.2 2068493.3
RR 917.4 4364.4 413092.3 76.1 �342.7 3246.2 160095.9
SPT 953.3 25105.7 3765178.7 �32.5 490.1 24244.4 3194334.2
PT+WINQ �886.1 12559.3 1140129.0 48.4 381.9 11758.0 791364.9
PT/TIS 1015.0 2587.2 211853.5 87.4 432.7 1908.2 109687.1
(PT+WINQ)/TIS 954.9 3731.0 336688.3 75.4 391.3 3082.4 188180.0
PT+WINQ+AT 1113.0 2366.7 188748.5 90.3 526.7 1792.3 109092.3
PT+WINQ+SL 982.9 2557.3 278247.4 83.9 408.7 �1441.2 �78475.8
95 6 FIFO 1434.2 3994.3 629934.0 81.2 573.9 2730.9 229657.9
AT 1246.2 2251.8 171821.8 76.7 407.6 1673.5 98775.1
AT-RPT 1250.8 �2105.1 �145608.1 76.2 419.4 1758.8 105183.9
EDD 1201.2 3202.0 450885.7 74.9 345.8 1295.8 72094.6
S/OPN 1183.1 3582.1 389178.7 71.0 316.7 2090.7 117733.2
COVERT 1003.4 13819.1 1118868.8 39.7 177.6 12405.3 760191.1
RR �856.0 3296.0 339012.0 36.7 �94.5 1423.5 �33234.3
SPT 953.3 25105.7 3765178.7 �19.6 402.3 23829.0 2959005.8
PT+WINQ 886.1 12559.3 1140129.0 28.5 261.7 11368.5 662724.9
PT/TIS 1015.0 2587.2 211853.5 59.0 229.7 1706.2 72438.7
(PT+WINQ)/TIS 954.9 3731.0 336688.3 47.3 221.1 2851.1 133587.1
PT+WINQ+AT 1113.0 2366.7 188748.5 66.7 304.4 1682.7 81594.3
PT+WINQ+SL 924.1 2815.8 363602.4 55.8 175.8 �1065.2 �33268.6
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 167
5.2.2. Maximum ¯owtime and variance of ¯owtime
In the case of ¯owshops, for minimizing maxi-
mum ¯owtime the PT + WINQ + AT rule has the
best performance, whereas for minimizing variance
of ¯owtime the AT-RPT rule emerges to the best
(or not signi®cantly worse than the best performing
rule) in all cases. For jobshops, the AT-RPT rule
has the best performance with respect to both ob-
jectives. Not only in jobshops, but also in ¯ow-
shops with missing operations the AT rule emerges
to be better than the FIFO rule. Once again, as in
the earlier study of conventional ¯owshops and
jobshops, the PT/TIS and (PT + WINQ)/TIS rules
perform quite well with respect to all ¯owtime-re-
lated measures of performance, and the choice
between the PT/TIS, (PT + WINQ)/TIS, SPT,
PT + WINQ, PT + WINQ + AT, AT and AT-
RPT rules depends on the preference structure used
by the decision maker.
5.2.3. Percentage of tardy jobs
Just as in the comparative study of jobshops
and conventional ¯owshops, up to 85% utilization
levels, the RR rule fares better (or not signi®cantly
worse) than the SPT rule. For 90% and 95% uti-
lization levels with tight due-date settings, the SPT
rule emerges better than the RR rule. These ob-
servations are similar to those in the case of the
comparative analysis of conventional ¯owshops
and jobshops, and the reasons for this trend are
also the same as discussed earlier.
5.2.4. Mean tardiness
Similar to the results observed earlier in the
study on jobshops and conventional ¯owshops,
the RR rule continues to be the best (or not sig-
ni®cantly worse than the best performing rule) for
this objective except for one case where we en-
counter the ¯owshop with a high utilization level
of 95% and a tight due-date setting of c� 4. As
discussed earlier, the look-ahead component in the
RR rule seems to be not so e�ective in ¯owshops
with missing operations as much as in jobshops.
The performance of the COVERT rule seems to be
better in ¯owshops than in jobshops. The reason
could be again attributed to a better estimation of
waiting time of jobs on machines, when there is a
unidirectional routeing of jobs in ¯owshops.
5.2.5. Maximum tardiness and variance of tardiness
Once again, the RR rule seems to be quite ef-
fective for many cases of jobshops and ¯owshops
under low utilization levels. However, at highly
loaded conditions (90% and 95% utilization levels)
and tight due-date settings (c� 4), we ®nd that the
PT + WINQ + SL rule emerges to be better than
the RR rule (or not signi®cantly worse than the
RR rule) for both jobshops and ¯owshops. Also at
95% utilization level and c� 6, the PT + WINQ +
SL rule continues to fare better. These observa-
tions are the same as in the case of the comparative
analysis of conventional ¯owshops and jobshops,
and the reasons for this trend are also the same as
discussed earlier.
5.3. Some general observations on dispatching rules
We wish to make some observations at this
stage. The objective of minimizing mean ¯owtime
leads to the minimization of mean waiting time of
jobs, and hence to the minimization of mean in-
process inventory. The objective of minimizing
mean tardiness leads to the minimization of mean
customer dissatisfaction level. Similarly, other
measures of performance are related to in-process
inventory and customer dissatisfaction. While
computing the mean or maximum or variance of
¯owtime/tardiness, we implicitly assume that all
jobs are equal in importance or that they have the
same holding/tardiness costs. In other words, we
assume that the holding/tardiness costs are directly
proportional to the ¯owtime/tardiness, respective-
ly. It can be seen that the chosen measures of
performance are surrogate measures of the mini-
mization of cost-based parameters. As for mini-
mizing a complex cost function consisting of in-
process inventory and tardiness (or penalty) costs,
we propose that a decision maker/manager could
make use of an additive function with appropriate
relative weights to the costs, and use the cost
function as the basis for choosing an appropriate
dispatching rule. It is to be noted that the relative
weights for di�erent costs would depend on the
utility function/preference structure that the deci-
sion maker employs, and hence the choice of a
dispatching rule would also vary accordingly. We
168 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170
would also like to mention here that Holthaus and
Rajendran (1997) have addressed the development
of new dispatching rules that seek to minimize the
mean and maximum ¯owtime of jobs, and maxi-
mum tardiness of jobs. These new rules and the
best existing rules have been evaluated through a
simulation study of a jobshop. The present study
addresses the development of a new dispatching
rule that seeks to minimize the maximum ¯owtime
of jobs, apart from the development of two new
dispatching rules that seek to simultaneously
minimize the mean and maximum ¯owtime of
jobs. In addition, we have now addressed the
evaluation of dispatching rules in dynamic ¯ow-
shops, which is perhaps the ®rst of its kind to be
reported in the literature, with a variety of mea-
sures of performance and experimental conditions.
A comparative analysis of the relative perfor-
mance of a number of dispatching rules in dy-
namic ¯owshops and jobshops has also been
reported, which is once again the ®rst of its kind.
We have also considered the ¯owshop with miss-
ing operations, and carried out the performance
analysis of dispatching rules in this type of ¯ow-
shop. The present study is therefore unique in view
of these considerations and it contributes to the
existing body of knowledge in the ®eld of jobshop
and ¯owshop scheduling.
6. Conclusion
While a lot of research work has been carried
out on the study of dispatching rules in jobshop
scheduling, there have been relatively few attempts
to study the relative performance of dispatching
rules in dynamic ¯owshops. Furthermore, a com-
parative study on the performance of dispatching
rules in dynamic ¯owshops and jobshops is inter-
esting and revealing because the job routeings in-
¯uence the relative performance of dispatching
rules. This study has been one such attempt to
compare the relative performances of dispatching
rules in two sets of manufacturing systems: dy-
namic ¯owshops and jobshops, and dynamic
¯owshops with missing operations and jobshops.
Three new dispatching rules have been proposed
and a total of 13 dispatching rules have been
considered for a performance analysis with respect
to the objectives of minimizing mean ¯owtime,
maximum ¯owtime, variance of ¯owtime, pro-
portion of tardy jobs, mean tardiness, maximum
tardiness and variance of tardiness. The ®rst sim-
ulation study has been carried out in ¯owshops
with jobs undergoing processing on all machines
sequentially and in jobshops with random routeing
of jobs. The results of the study have revealed
some interesting observations on the performance
of the dispatching rules in these two types of
manufacturing systems. The second simulation
study has considered the ¯owshops with missing
operations on jobs and jobshops with random
routeing of jobs. It has been observed that the
relative performance of dispatching rules is being
in¯uenced by the routeing of jobs and shop¯oor
con®gurations. The performance of various rules
with respect to every measure of performance has
been discussed in detail.
Overall, a proposed rule, AT-RPT rule, emerges
to be very e�ective in minimizing the maximum
¯owtime and variance of ¯owtime of jobs. While
the PT + WINQ rule performs very well in mini-
mizing mean ¯owtime of jobs, the PT + WINQ +
SL rule performs well in minimizing the maximum
tardiness and variance of tardiness of jobs. The
RR rule appears to be a good rule with respect to
the tardiness-related performance measures in
many cases of manufacturing systems under study.
This rule reckons the process time, slack and
waiting time at the next operation of the job, and
also the shop load conditions. Hence the rule
adapts itself e�ectively to a number of di�erent
shop¯oor conditions. Likewise, we ®nd that two
proposed rules, viz. the (PT + WINQ)/TIS and
PT/TIS rules, seem to o�er good compromise so-
lutions with respect to the ¯owtime-related perfor-
mance measures in most cases of manufacturing
systems under study. These rules consider not only
the process time, but also the resident time of a
job, thereby enhancing the performance with re-
spect to the mean and maximum ¯owtime. As
mentioned earlier, the choice of a dispatching rule
®nally depends on the relative importance that the
decision maker assigns to each measure of per-
formance. The results also indicate that the rules
that include information about process time, total
C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170 169
work-content of jobs in the queue of next opera-
tion of a job, arrival time and due-date fare very
well in simultaneously minimizing many measures
of performance in jobshops as well as in ¯ow-
shops.
Acknowledgements
This research work was carried out when the
®rst author had been at the University of Passau
and was supported by the Alexander von Hum-
boldt Research Fellowship during 1996±1997. The
authors are thankful to the three referees for their
constructive comments and suggestions to improve
the earlier version of the paper.
References
Anderson, E.J., Nyirenda, J.C., 1990. Two new rules to
minimize tardiness in a jobshop. International Journal of
Production Research 28, 2277±2292.
Baker, K.R., 1974. Introduction to Sequencing and Scheduling.
Wiley, New York.
Baker, C.T., Dzielinski, B.P., 1960. Simulation of a simpli®ed
job shop. Management Science 6, 311±323.
Blackstone, J.H., Phillips, D.T., Hogg, G.L., 1982. A state-of-
the-art survey of dispatching rules for manufacturing job
shop operations. International Journal of Production Re-
search 20, 27±45.
Campbell, H.G., Dudek, R.A., Smith, M.L., 1970. A heuristic
algorithm for the n-job, m-machine sequencing problem.
Management Science 16, B630±B637.
Conway, R.W., Johnson, B.M., Maxwell, W.L., 1960. An
experimental investigation of priority dispatching. Journal
of Industrial Engineering 11, 221±230.
Conway, R.W., 1965. Priority dispatching and job lateness
in a job shop. Journal of Industrial Engineering 16, 228±
237.
Dannenbring, D.G., 1977. An evaluation of ¯ow-shop sequenc-
ing heuristics. Management Science 23, 1174±1182.
Day, J.E., Hottenstein, M.P., 1970. Review of sequencing
research. Naval Research Logistics Quarterly 17, 11±39.
French, S., 1982. Sequencing and Scheduling: An Introduction
to the Mathematics of the Job-Shop. Ellis Horwood,
Chichester, UK.
Haupt, R., 1989. A survey of priority rule-based scheduling.
OR Spektrum 11, 3±16.
Ho, J.C., 1995. Flowshop sequencing with mean ¯owtime
objective. European Journal of Operational Research 81,
571±578.
Holthaus, O., Rajendran, C., 1997. E�cient dispatching rules
for scheduling in a job shop. International Journal of
Production Economics 48, 87±105.
Hunsucker, J.L., Shah, J.R., 1992. Performance of priority rules
in a due date ¯ow shop. OMEGA 20, 73±89.
Hunsucker, J.L., Shah, J.R., 1994. Comparative performance
analysis of priority rules in a constrained ¯ow shop with
multiple processors environment. European Journal of
Operational Research 72, 102±114.
Ignall, E., Schrage. L., 1965. Application of the branch-and-
bound technique to some ¯owshop scheduling problems.
Operations Research 13, 400±412.
Ishibuchi, H., Misaki, S., Tanaka, H., 1995. Modi®ed simulated
annealing algorithms for the ¯ow shop sequencing prob-
lems. European Journal of Operational Research 81, 388±
398.
Law, A.M., Kelton, W.D., 1984. Con®dence intervals for
steady-state simulations: I. A survey of ®xed sample size
procedures. Operations Research 32, 1221±1239.
Lorenzen, T.J., Anderson, V.L., 1993. Design of Experiments:
A No-Name Approach, Marcel Dekker, New York.
Montgomery, D.C., 1991. Design and Analysis of Experiments,
3rd ed. Wiley, New York.
Nawaz, M., Enscore, Jr., E.E., Ham, I., 1983. A heuristic
algorithm for the m-machine, n-job ¯owshop sequencing
problem. OMEGA 11, 91±95.
Nanot, Y.R., 1963. An experimental investigation and com-
parative evaluation of priority disciplines in job-shop-like
queueing networks. Research Report No. 87. Management
Sciences Research Project, UCLA.
Pinedo, M., 1995. Scheduling Theory, Algorithms and Systems,
Prentice Hall, Englewood Cli�s, NJ.
Raghu, T.S., Rajendran, C., 1993. An e�cient dynamic
dispatching rule for scheduling in a job shop. International
Journal of Production Economics 32, 301±313.
Rajendran, C., 1994. A heuristic for scheduling in ¯owshop and
¯owline-based manufacturing cell with multi-criteria. Inter-
national Journal of Production Research 32, 2541±2558.
Ramasesh, R., 1990. Dynamic job shop scheduling: A survey of
simulation research. OMEGA 18, 43±57.
Rochette, R., Sadowski, R.P., 1976. A statistical comparison of
the performance of simple dispatching rules for a particular
set of job shops. International Journal of Production
Research 14, 63±75.
Russell, R.S., Dar-el, E.M., Taylor III, B.W., 1987. A
comparative analysis of the COVERT job sequencing rule
using various shop performance measures. International
Journal of Production Research 25, 1523±1540.
Scudder, G.D., Ho�mann, T.R., 1987. The use of cost-based
priorities in random and ¯ow shops. Journal of Operations
Management 7, 217±232.
Smunt, T.L., Buss, A.H., Kropp, D.H., 1996. Lot splitting in
stochastic ¯ow shop and job shop environments. Decision
Sciences 27, 215±238.
Vepsalainen, A.P.J., Morton, T.E., 1987. Priority rules for job
shops with weighted tardiness costs. Management Science
33, 1035±1047.
170 C. Rajendran, O. Holthaus / European Journal of Operational Research 116 (1999) 156±170