TPRS_1987_v25_n1-6.pdf
Full Terms & Conditions of access and use can be found at
http://www.tandfonline.com/action/journalInformation?journalCode=tprs20
Download by: [Peking University] Date: 09 February 2017, At: 18:43
International Journal of Production Research
ISSN: 0020-7543 (Print) 1366-588X (Online) Journal homepage: http://www.tandfonline.com/loi/tprs20
A comparative analysis of the COVERT job
sequencing rule using various shop performance
measures
R. S. RUSSELL† , E. M. DAR-EL‡ & B. W. TAYLOR III
To cite this article: R. S. RUSSELL† , E. M. DAR-EL‡ & B. W. TAYLOR III (1987) A
comparative analysis of the COVERT job sequencing rule using various shop performance
measures, International Journal of Production Research, 25:10, 1523-1540, DOI:
10.1080/00207548708919930
To link to this article: http://dx.doi.org/10.1080/00207548708919930
Published online: 22 Oct 2007.
Submit your article to this journal
Article views: 60
View related articles
Citing articles: 60 View citing articles
http://www.tandfonline.com/action/journalInformation?journalCode=tprs20
http://www.tandfonline.com/loi/tprs20
http://www.tandfonline.com/action/showCitFormats?doi=10.1080/00207548708919930
http://dx.doi.org/10.1080/00207548708919930
http://www.tandfonline.com/action/authorSubmission?journalCode=tprs20&show=instructions
http://www.tandfonline.com/action/authorSubmission?journalCode=tprs20&show=instructions
http://www.tandfonline.com/doi/mlt/10.1080/00207548708919930
http://www.tandfonline.com/doi/mlt/10.1080/00207548708919930
http://www.tandfonline.com/doi/citedby/10.1080/00207548708919930#tabModule
http://www.tandfonline.com/doi/citedby/10.1080/00207548708919930#tabModule
A comparative analysis of the COVERT job sequencing rule using
various shop performance measures
R. S. RUSSELL?, E. M. DAR-ELI, and B. IY. TAYLOR, 1117
The COVERT job shop dispatching rule was tested extensively twenty years
ago with impressive results, however, since then it has been included in only
one comparative analysis with other sequencing rules, and, reported instances
of its application have been infrequent. In this paper, the COVERT rule is
examined in detail relative to its applicability, its sensitivity to various oper-
ating parameters and performance measures, and its performance compared to
several other sequencing rules including truncated SPT rules, dynamic slack
rules and modified duedate rules. The performance of COVERT is examined
for a variety of tardiness measures. The examination is conducted within the
context of a simulation model of a machine-constrained job shop with serial
jobs and random routings. The results indicate that COVERT performs well as
a sequencing rule and in most instances was superior to the other sequencing
rules tested both directly and across raging degrees of due-date tightness.
1. Introduction
The COVERT job shop dispatching rule prioritizes jobs in a queue according
to the largest ratio of expected job tardiness (a surrogate for delay penalty) to
operation processing time. It retains the performance of the shortest processing
time (SPT) rule but tends to minimize the extreme completion delays of a few
orders (Buffa and Miller 1979). The COVERT rule was tested extensively by
Carroll in 1965 with impressive results. Using mean tardiness as a performance
measure, COVERT proved superior to even the truncated SPT rule. Of the six
rules tested by Carroll, the lateness distribution of COVERT was effectively
skewed such tha t jobs completed on the due-date were the mode of the distribu-
tion (Buffa and Miller 1979). During the 20 years since Carroll’s examination,
COVERT has been promoted by Trilling (1966) and Buffa and Miller (1979) and
has been included in many major reviews of sequencing literature (see, for
example Blackstone el al. (1982), Day and Hottenstein (1970), Moore and Wilson
(1967), Panwalker and Iskander 1977). In general, i t has been considered one of
the most promising of sequencing rules (Blackstone el al. 1982).
However, in spite of the superlative performance of COVERT as reported by
Carroll (1965), it has been included in only one further publication comparing
sequencing rules (Baker and Kanet 1983), in which case i t was completely domi-
nated by SPT. In addition, applications of COVERT have been sparse (Green and
Appel 1981). Criticism of COVERT emphmizes the lack of testing against more
sophisticated truncated SPT and ‘minimum slack per remaining operations (S/
OPN)’ rules that have been formulated since Carroll’s research in 1965
Revision received February 1987.
t Department of Management Science, Virginia Polytechnic Institute, and State Uni-
versity, Blacksburg. Virginia, 24061, U.S.A.
f Technion-Israel Institute of Technology, Haifa, Israel.
1521 R. 5′. Russell e t al
(Blackstone et al. 1982). Also, recent studies of tardiness-oriented sequencing rules
have used the performance measures of mean tardiness, percent tardy, condition-
al mean tardiness (Baker 1984), maximum tardiness (Minor and Fry 1986), and,
root mean square of tardiness (Russell and Taylor 1985). The COVERT rule has
yet t o be tested using these additional tardiness performance measures or com-
pared to Inore recently developed tardiness-oriented sequencing rules.
The purpose of this paper is t o examine the COVERT rule in terms of its
applicability, its sensitivity to various operating parameters and performance
measures, and, recent advances in sequencing rule research. We will first analyse
several alternative methods for estimating the expected job tardiness or delay
penalty tha t is employed in the COVERT formulation. Next COVERT will be
compared t o several sequencing rules t h a t have been developed since COVERT
was initially presented, including truncated SPT rules, dynamic slack rules and
modified due-date rules. This will be followed by an examination of COVERT’S
performance for a variety of tardiness measures and an evaluation of the sensi-
tivity of COVERT t o changes in due-date tightness (as opposed to other
tardiness-oriented sequencing rules). This examination will be conducted within
the context of a simulation model of a hypothetical machine-constrained job shop
with serial jobs and random routings.
2. The COVERT rule
The COVERT sequencing rule is mathematically formulated, as follows
(adapted from Buffa and Miller (1979)).
where orders are sequenced based on the magnitude of ni, with the largest values
first and ties broken by the smallest t i , and
ci = ( z Xwi – s)/ x Xwi = expected delay penalty for operailon i
vie4 V i E,
where wi is waiting time for operation i , k is an approximating factor, kw, is
expected waiting time, s is slack = d – 1 li – T, ti is operation processing time,
V i e $
7′ is present time, d is due-date, and 4 is set of uncompleted operations.
In this formulation, ci is a penalty for delay expressed in terms of job tardi-
ness. Since actual delay costs may vary significantly from firm to firm, i t is
assumed that delay costs are a function of delay time. Carroll (1965) employed
the formulation presented above, and as such, tha t will be the convention in this
paper although we will later explore an alternative form of the penalty function.
Carroll (1965) estimated waiting time for an operation, wi, from previously
conducted simulations using the FCFS sequencing rule. A ‘k’ factor of 1 was used
to calculate expected waiting time. Carroll’s experiment was performed with an
80% utilization rate and the arrival rate set such t h a t 45% of the johs completed
using the FCFS sequencing rule were tardy. Processing time was exponentially
distributed.
A comparative analysis of the COVERT job sequencing rule 1525
Carroll’s experiment compared the mean tardiness of jobs processed by
COVERT with the mean tardiness of those processed by the FCFS (first-come,
first-served), FISFS (first-in-system, first-served), S/OPN (slack per remaining
operation), S P T (shortest processing time), and truncated SPT sequencing rules,
and found tha t COVERT produced significantly lower mean tardiness values.
Carroll further tested the sensitivity of COVERT to varying utilization levels
(0.90, 0.80 and 0.70), due-date allowances (60% tardy, 45% tardy, and 30%
tardy) and k factors (0.5, 1, and 2) , and found no significant difference in
COVERT’S performance.
In this study, COVERT is examined using the highest utilization rate reported
by Carroll (i.e., 90%), similar distributions of arrival and processing times and
several alternative levels of due-date tightness. I n addition, the procedure used by
Carroll to estimate waiting time is compared to two alternative methods, and,
both linear and quadratic penalty functions are assessed. Finally, COVERT is
compared to nine job sequencing rules, some of which appeared in Carroll’s 1965
study, as well as several recently developed dynamically calculated truncated
S P T rules, for a variety of performance measures.
3. The example job shop
In this study a representative job shop similar to those reported in the liter-
ature (see Baker (1984)) is constructed and simulated to serve as an experimental
vehicle for the analysis of the COVERT sequencing rule. The example shop con-
sists of four machine centres with one machine per centre. Jobs arrive contin-
uously during the simulation ‘with the time between arrivals generated from an
exponential distribution such tha t approximately a 90% utilization rate is
achieved. Upon arrival each job is assigned a due-date calculated by summing the
arrival time plus the total processing time multiplied by an allowance factor. The
allowance factor is determined from experimental simulations using the FCFS
sequencing rule such tha t 60% of the jobs are completed late. A job is subse-
quently routed randomly through the shop, visiting from one to six machine
centres before completion. Processing times are exponentially distributed and
queue disciplines a t each machine centre vary with the particular experimental
conditions under which the simulation is conducted. The shop operation is simu-
lated for 500 days (i.e., approximately two years) after an initial startup period of
150 days. Each simulation run is replicated five times.
Performance measures
Statistics for the simulation model are collected for the following performance
criteria: mean, variance, and maximum flowtime; mean, variance, maximum,
and root mean square of tardiness; mean, variance, and root mean square of
conditional tardiness; percent of jobs tardy; and mean and variance of lateness
for jobs completed by the shop.
J o b flowtime is a common measure of job shop performance with practical
significance as an estimate of work-in-process inventory. However, job tardiness
results are emphasized in this study because of their practical significance to pro-
duction managers. Typically, tardiness is represented by mean tardiness and
percent of jobs tardy. However, a dilemma arises when comparing systems with
R. S . Russell e t al
Performance measure Symbol Definition
hlean flowtime
Mean tardiness 2 max (0 , Lj)IN
ieO
–
Mean conditional CT max (0, Lj) /NT
tardiness j e 6
hlean lateness L 1 LjlN
j e 4
Root mean square of RMST
tardiness
Root mean square of RMSCT
conditional tardiness ) “l.
Percent tardy %T XT/Ar
Maximum tardiness Max T maximax (0, Lj ) }
v,<,
Notation: N is number of jobs completed, &J is set of jobs com-
pleted, rj is arrival time of jth job to shop, dl is due-date of job j ,
P j is time at which job j is completed, Lj = lateness of job j; Lj =
Pj - d j , and NT = 2 Ajwhere
j e @
I if Lj > 0
number of jobs tardy
0 if Lj a 0′
Table 1. Measures of performance
low mean t,ardiness and high percent of jobs tardy, t o systems with higher mean
tardiness but fewer jobs tardy. The root mean square of tardiness calculation is
designed tosolve this problem. Each job tardiness figure is squared, then summed
over the number of jobs tardy before taking the square root. This value tends to
penalize systems with a few jobs tha t are very late more than those with many
jobs tha t are a little late. Practitioners have expressed a preference for this logic
in assessing the impact of late jobs (Dar-El and Wysk 1982).
Statistics for both tardiness and conditional tardiness performance measures
are also reported. Tardiness measures consider those jobs completed on time or
early as having zero tardiness. Conditional tardiness measures only consider those
jobs completed past their due-date in t’ardiness calculations. Lateness measures
arc also reported for comparison purposes, as are thi: variance and maximum
value of each performance measure. Table I presents the mathematical formula-
tion of each performance measure.
4. Simulation experiment I: alternative formulations of COVERT
Referring to the formulation of COVERT presented previously, two values
must initially be estimated prior t o the simulation experiment, operation waiting
time, w i , and, a constant multiplier of waiting time, k. The inclusion of a waiting
time estimate in sequencing rules is not unique to COVERT. SLACK, S/OPN and
critical ratio sequencing rules have previously been considered with waiting time
A comparative analysis o j the COVERT job sequencing rule 1.527
estimates (see Berry and Rao (1975) for example). Also, the truncated SPT rules
tha t are addressed later in this paper require a control parameter tha t represents
waiting time. Finally, Vepsalainen and Morton (1985) examined three methods
for estimating leadtime, a standard estimation, a priority based estimation, and
an estimation using iterative simulations. They found significant improvements in
sequencing rule performance depending on the manner in which waiting time was .
estimated.~
Three methods of estimating waiting time for use in the COVERT rule are
considered in this s tudy: due-date allowance (DDALL), historic average waiting
time (HAWT), and dynamic average waiting time (DAWT). DDALL ignores esti-
mated waiting times for the individual machines and assumes tha t the allowance
built into the due-date calculation is an accurate measure of expected waiting
time for the remaining work to be performed. This approach has been employed
by Baker and Kanet (1983). HAWT, employed by Carroll (1965), is the average
waiting time across machine centre queues from previous shop operations (and for
our purposes using the FCFS sequencing rule), multiplied by the number of
remaining operations. A single waiting time value is used regardless of the partic-
ular machine centre and this value is nob changed over time. DAWT employs
current average waiting times for specific machine centres yet to be visited in the
routing sequence of a job. The waiting time is updated whenever a job joins a new
queue.
Each of these three methods for estimating waiting time is tested in the simu-
lation using values for t,he approximating factor, k, of 1.0 and 0.5 (values that
have previously been reported in the research literature).
The formulation of the COVERT rules presented previously assumes a linear
delay penalty function since i t was originally designed as a rule for minimizing
mean tardiness. However, if delay costs for a firm do not increase a t a constant
rate, but instead increase dramatically as the delay increases, the penalty func-
tion for delay would be more quadratic than linear. The COVERT formulation
can be adjusted to include a semi-quadratic delay penalty function by squaring
the expected delay penalty. This revised formulation may not minimize mean
tardiness but it should yield good results for the root mean square performance
measures.
To summarize this initial simulation experiment, the COVERT rule is tested
using three alternative methods for estimating waiting time, two alternative
values of k, and both linear and semi-quadratic penalty functions. The rule is
tested against the performance measures designated in Table I .
Simulation results for experiment I
The results of the initial simulation experiment in which alternative formula-
tions of the COVERT rule tested are presented in Table 2.
Observing Table 2 and considering only the alternative formulations of
COVERT using the different waiting time estimates, i t occurs tha t COVERT with
DDALL (due-date allowance) is dominated by both HAWT (historic average
waiting time) and DAWT (dynamic average waiting time). Furthermore, DAWT
appears to be superior to HAWT for all performance measures except mean tardi-
ness (T), percent tardy (%T) and lateness variances (u;). As such, the overall
– o m
“9C?
– m m
t – c w
s s s
t – w o
d m m
m e 0
w-b
+ – –
m e :
t- c
& & w = 0 ”
s s s
m o w
m m m
N j= m
Lf,
Z h m
O O F D g 2
m m m
$ $ z
I – m m
w m w “” C?
d C L C – – –
C
.-
L3
:
2 ,
h’!’
3 0
2;: c a- .-
c:
$ $ g
n e e
Q x n
G
p:
LZ!
>
0
2
0
C
.-
4
2
2
i?
P
m
a
.9
2
:
22
2
2
00
e
c
.-
4
2 z .-
(13
4
S
s
P
. .
c
.-
4 0 –
c 9
2 0
0 II .-
3 5 %
o k
CT
m o o
e – ”
o m –
w w t –
m m m
P ‘: ”
m m m
I I I
SSs
m m cn
m m m
m m o -?-?:
FD – C
9079
o m m
N O I N
$ g G
m o m
C d C
“99
Eon
l n m o
?’C?N
z 2 2
m 1 – o
‘!’I?C? – – –
– m w
” b ” – – –
f Z 8 .
; r * –
o m m
0 o 2
m 3
m w r C
P C t-
– – +
– 7
d m 2 – –
.
4 4 P
2 5 5
C x n
A comparative analysis of the COVERT job sequencing rule 1529
performance of DAWT as a methodology for computing estimated waiting time
for the COVERT rule appears to be best.
An approximating factor of k = 0.5 instead of k = 1.0, improved the per-
formance of COVERT with the DDALL and HAWT methods, however this
change worsened the performance of COVERT with DAWT. This can be
explained by the fact that the DDALL and HAWT methods are more imprecise
than DAWT. The results in Table 2 demonstrate tha t crude methods for estimat-
ing waiting time can be improved by varying k, whereas more sophisticated
methods of estimating waiting time are not necessarily improved.
Finally, while it appears tha t the quadratic penalty function in conjunction
with DDALL and HAWT decreases the mean and variance of conditional tardi-
ness, maximum tardiness, root mean square of tardiness and, root mean square of
conditional’ tardiness, the performance of COVERT with DAWT was not
improved.
1n summary, the overall performance of COVERT using DAWT to estimate
waiting time with k = 1.0 and a linear penalty function appears to be superior. As
such, we will employ this version of COVERT in our comparative analysis with
other sequencing rules.
5. Simulation experiment 11: a comparative analysis of COVERT and other
sequencing rules
In the simulation experiment performed in this section, the COVERT rule as
determined in the first simulation experiment (i.e., with k = 1.0, linear penalty
function and DAWT estimated waiting time), will be compared to nine other job
sequencing rules. The experiment will be conducted via the example job shop
employed in experiment I with a 90% shop utilization rate and 60% of the jobs
completed late using the FCFS sequencing rule.
The first five of the ten sequencing rules tha t will he compared to COVERT
are basic rules tha t are frequently referred to in the job shop scheduling research
literature. These five rules, defined in Table 3, are first-come, first-served (FCFS),
earliest due-date (DDATE), minimum slack (SLACK), minimum slack per
remaining operation (SJOPN), and shortest processing time (SPT). The remaining
five sequencing rules to be tested are dynamically calculated rules, i.e., each time
a job has finished processing a t a machine centre, the priorities of all remaining
waiting jobs are recalculated. These five rules, also defined in Table 3, are the
truncated S P T (SPT-T), the two-class truncated SPT (SIX), the modified due-date
(MDD), the modified operation due-date (MOD), and the apparent urgency (AU)
rule. The first five basic rules are, as already noted, frequently presented in the
scheduling literature, and as such, a detailed explanation of them is not offered,
however, the last five rules are not as visible and thus a brief explanation of each
will be presented.
In the SPT-T rule, proposed by Oral and Malouin (1973), two values are com-
puted for each job a t each operation, operation processing time plus an overall
control parameter, and, slack. A job’s priority is determined by the minimum of
these two values. Jobs with the lowest priority are processed first. I n the SIX rule
suggested by Eilon and Chowdhury (1976), a factor, F, defined as slack time
minus a control parameter is calculated for each operation of a job. Jobs wit,h,
zero or negative values are placed in a priority queue ordered by S P T while jobs
15JO R. 8. Russell e t al
Definition Formulation
Basic rules
PCFS First come, first served min rj
DDATE Job due-date min d j
SLACK Job slack
S/OI?N Slack per remaining operation
SPT Shortest processing time min t i
l~ynamically calculated rules
SPT-T Truncated SPT
min { vie 1 4 l i + k ; d j – vie* x ti – T I
81′ Two class truncated SPT P = d , – I t i – T – , k
V i e 4
( I ) F G O m i n l ,
(2) F > 0 min t i
JIDD Modified due-date’
rnin max d , , T + 1 ti i { vie+ 11
MOD Modified operation due-date min {max { d i j , T + 1 , ) )
CO\’ERT Continuously truncated SPT max ci/ti
AC Apparent urgency “‘1
d , – T – l i – 9 = i + l 2 ( wq + lq)
min
kpij
– – – — – –
Notation : a, is arrival time of job j to shop, r j is arrival time of job j to machine
centre, d j is due-date of job j = a , + k l i , d i j is due-date of operation i of job j; li
“i
is processing time for operation i , T is present time, 4 is set of uncompleted oper-
ations, nl, is number of operations in job j, n j is number of remaining operations in
job j, k is a constant control parameter, 1.0, ci is expected delay cost for operation
i, wi is waiting time for operation i, and i, is average processing time of jobs in
queue.
Table 3. Definition of sequencing rules.
with positive factor values a r e placed in a non-priority queue also ordered by
SPT. T h e SPT and SIX rules were included in this comparat ive analysis because of
Lheir good performance in Blackstone el al. ‘s (1982) analysis and the favourable
results reported by Minor and F r y (1986). Baker a n d Ber t rand (1982) reported
success with t he modified due-date (MDD) rule. I n this rule t he maximum of a
job’s due-da te o r early finish t ime is determined a s t he modified due-date. J o b s
with t he smallest MDD a re processed first. Baker a n d K a n e t (1983) have sug-
gested a modified operation due-date (MOD rule) as a n improvement t o t h e MDD
rule. I n MOD a job’s priority is determined a s t he maximum of i t s operation
due-date o r earliest operation finishing time. Vepsalainen and Morton (1985)
tested a n apparent urgency rule (AU) on t h e weighted tardiness problem where
the completion of certain jobs is more impor tan t t han others. AU compensates for
P
er
fo
rm
an
ce
m
ea
su
re
s
–
R
u
le
p
0:
m
ax
F
T
0:
m
ax
T
R
M
S
T
C
T
a
f,
R
M
S
C
T
%
T
l5
a:
F
C
F
S
2
2
.9
0
2
6
5
.8
1
8
1
.4
6
8
.3
5
1
2
3
.1
1
5
3
.8
4
1
3
.3
5
1
2
.8
6
7
5
.6
1
1
6
.6
3
6
1
%
5
.1
1
19
9.
64
D
D
A
T
E
1
8
.3
8
2
4
3
.6
6
8
2
.8
2
3
.8
5
3
3
.1
1
2
6
.3
0
6
.6
2
7
.1
3
1
2
4
.1
3
9
.1
7
4
4
%
0
.6
3
6
9
.8
9
S
L
A
C
K
18
.4
2
2
2
3
.6
2
77
.8
4
3
.7
0
3
4
.4
7
2
4
.3
7
6
.4
5
6
.8
0
3
9
.1
6
8
.8
7
45
%
0
.6
9
6
6
.1
0
S
/O
P
N
2
4
.8
0
4
8
1
.7
8
11
1
.2
8
1
1
.1
8
2
9
1
.9
9
7
5
.9
2
19
.4
4
1
8
.9
8
3
7
.8
4
2
5
.3
9
5
6
%
7
.0
3
4
2
2
.0
2
S
P
T
12
.2
7
2
9
2
.0
2
1
5
4
.7
6
1
.8
3
1
0
8
.8
8
1
1
0
.9
6
9.
14
11
.3
7
5
2
8
.0
0
2
2
.8
0
1
5
%
-5
.4
8
1
8
6
.9
9
S
P
T
-T
1
4
.8
0
1
7
0
.6
5
7
6
.0
2
2
.0
5
1
7
.7
3
1
7
.5
5
4
.0
0
4
.6
5
2
1
.7
1
6
.1
0
3
4
%
-4
.1
4
72
.6
0
S
I
1
4
.4
5
18
3.
07
9
4
.9
4
1
.7
5
2
1
.8
5
4
7
.7
0
4
.3
9
4
.1
3
3
5
.8
5
6
.7
7
3
6
%
-3
.3
5
1
8
.2
4
M
D
D
1
6
.8
2
3
0
6
7
2
1
3
1
.6
0
2
.4
6
6
5
.8
3
7
6
.7
4
7.
36
5
.5
3
1
1
7
.4
0
1
1
.0
5
3
8
%
-0
.8
4
9
4
.4
4
M
O
D
1
4
.6
4
20
1.
40
1
0
4
.8
0
1
.2
2
3
1
.6
9
5
5
.5
8
4.
57
3
.6
5
7
0
.5
5
7
.8
8
2
7
%
-3
.1
7
6
6
.5
7
A
U
1
8
.1
6
2
8
4
.8
0
1
4
6
.2
0
3
.4
9
8
9
.0
9
11
1
.6
4
9
.4
7
7.
04
1
5
6
.6
3
1
4
.0
1
4
5
%
0
.4
1
1
2
5
.0
2
C
O
V
E
R
T
1
3
.9
1
16
7.
79
9
1
.9
0
1
.2
6
11
.7
0
3
5
.4
6
3.
46
3
.2
8
1
8
.9
3
4
.9
0
3
5
%
-3
.8
4
6
3
.5
0
T
ab
le
4
.
S
im
u
la
ti
o
n
r
es
u
lt
s
fo
r
al
te
rn
at
iv
e
se
q
u
en
ci
n
g
r
u
le
s
.I 532 R. 9. Russell e t al.
shop load by scaling a job’s slack according t o the average processing time. The
simple, unweighted version of AU is tested in this study.
Of course the final rule tha t will be tested is COVERT with a linear delay
penalty function, k = 1.0, and expected waiting time computed using DAWT.
COVERT is actually a form of truncated SPT rule, prioritizing in separate queues
by SPT when a job has no slack remaining or has excessive slack, and, by
COVERT otherwise.
Sirnulalion results /or experintent I I
The example shop was simulated under the same operating conditions
described in experiment I using each of the nine alternative sequencing rules and
COVERT. The performance measures described in Table 1 and employed in
experiment T were also computed for this second experiment. The results are pre-
sented in Table 4.
We will first comment on the performance of the five basic sequencing rules as
prescnted in the top par t of Table 4. Observing the first two rows, the FCFS rule
is completely dominated by the DDATE rule for all measures of flowtime, tardi-
ness and lateness. Moving down t o the third row for the SLACK rule, there
appears t o be only a slight difference between the DDATE and SLACK rules with
the SLACK rule generally performing a little better. The variant of the SLACK
rule, S/OPN is completely dominated by SLACK. Although this result is some-
what surprising, it is consistent with Kanet’s (1979) observation tha t S/OPN per-
forms poorly when due-date allowances are tight and when jobs have many
operations remaining to be processed. Some trade-offs are evident between the
SLACK and SPT sequencing rules. S P T as expected displays a lower mean flow-
time, mean tardiness, mean lateness and percent of jobs tardy whereas SLACK
has a lower root mean square value, and, lower variances and maximum values
for flowtime, tardiness and lateness. Overall, among these five basic rules, the
pcrforrnance of SPT was superior.
Next, concentrating on the performance measures of the five dynamically cal-
culated rules in Table 4, SPT-T and SI’ produced somewhat similar results.
However, there are also some notable tradeoffs: S IX produced lower values of
mean flowtime, mean tardiness and mean conditional tardiness. SPT-T resulted in
lower m c a s ~ ~ r e s of variance, maximum values, root mean square and percent
tardy. These results confirm Minor and Fry’s (1986) observations regarding mean
and maximum tardiness.
COVERT generally performed better than both SPT-T and SIX, producing
lower mean values, and variances, for every performance measure and lower root
mean square values. MDD is completely dominated by MOD verifying Baker and
Kanet’s (1983) results. Also, consistent with Baker and Kanet (1983), MOD pro-
duced the lowest mean tardiness and percent tardy figures of the advanced
sequencing rules. However, COVERT performed better than MOD on every
mcasure of performance other than mean tardiness and percent tardy. AU’s per-
formance was disappointing in view of Vepsalainen and Morton’s (1986) earlier
results. Both MOD and COVERT outperformed AU for all measures of per-
formance reported in this study. The most notable difference in results appears in
the maximum and variance performance measures. However, these figures
P
er
fo
rm
an
ce
m
ea
su
re
s
S
eq
u
en
ci
n
g
–
ru
le
P
a
f
m
ax
F
T’
a
$
m
ax
T
R
M
S
T
C
T
a:,
R
M
S
C
T
%
T
15
0
:
S
P
T
12
.2
7
29
2.
02
1
5
4
.7
6
0
.9
5
60
.3
1
90
.9
4
6
.2
7
1
4
.1
5
5
9
5
.2
2
24
.2
5
6
%
-1
5
.4
2
2
7
3
.3
5
S
P
l-
T
1
3
.1
7
2
0
0
.2
8
9
7
.1
8
0
.3
1
1.
22
7.
91
0.
91
2
.1
4
4
.6
4
2.
87
8
%
–
1
0
.7
6
1
8
2
.8
8
S
I’
1
3
.2
8
2
0
8
.7
6
1
0
3
.4
2
0
.2
7
1.
51
1
0
.4
8
1.
03
2
.1
9
5
.6
2
3.
01
1
0
%
–
1
4
.4
9
1
8
6
.0
7
M
O
D
15
.5
4
25
8.
06
1
0
1
.2
4
0.
21
2.
79
14
.1
6
1.
16
2
.1
3
1
5
.2
5
3
.7
0
7
%
–
1
2
.2
3
1
1
9
.3
4
C
O
V
E
R
T
1
3
.2
3
20
3.
08
9
7
.6
6
0
.2
3
1
.0
9
8
.7
7
0
.9
1
1
.9
5
4
.1
4
2
.6
9
1
0
%
-1
4
.4
9
1
8
3
.5
6
T
a
b
le
5
.
S
im
u
la
ti
o
n
r
es
u
lt
s
fo
r
tr
u
n
ca
te
d
S
P
T
a
n
d
m
o
d
if
ie
d
d
u
e-
d
at
e
se
q
u
en
ci
n
g
r
u
le
s
u
n
d
er
m
o
d
er
at
e
d
u
e
-d
a
te
s
(4
0
%
t
a
rd
y
)
P
er
fo
rm
an
ce
m
ea
su
re
s
S
eq
u
en
ci
n
g
–
ru
le
P
o
f
m
a
x
F
T’
a:
m
ax
T
R
M
S
T
C
T
a
t,
R
M
S
C
T
%
T
L
0:
S
P
T
1
2
.2
7
29
2.
02
1
5
4
.7
6
0
.3
1
2
0
.9
8
6
2
.9
6
3
.2
4
1
0
.4
6
47
3.
00
1
9
.0
8
2
.0
%
-3
3
.8
8
7
1
3
.4
2
S
P
T
-T
1
2
.5
1
2
6
0
.2
4
1
3
4
.1
6
0
.0
2
0
.0
9
3.
14
0
.2
3
1
.1
5
1
.8
8
1
.5
5
1.
7%
-3
3
.5
8
6
6
6
.2
0
S
I
1
2
.5
9
26
1.
41
1
3
3
.7
6
0.
04
0
.1
8
4
.7
6
0
.3
4
1.
42
3.
06
2
.1
8
2
.0
%
-3
3
.5
4
6
7
0
.1
6
M
O
D
16
.0
4
38
1.
41
1
2
9
.6
4
0
.0
1
0.
02
2
.2
5
0
.1
4
0
.8
2
0
.6
5
1
.0
8
1
.5
%
-3
0
.3
2
9
5
2
.7
7
C
O
V
E
R
T
1
2
.6
9
26
1.
27
13
2.
76
0
.0
3
0.
1
1
4
.2
6
0.
29
1
.5
3
1
.8
6
1.
96
2
.0
%
-3
3
.5
0
6
7
4
.0
3
T
ab
le
6
.
S
im
u
la
ti
o
n
r
es
u
lt
s
fo
r
tr
u
n
c
a
te
d
S
P
T
a
n
d
m
o
d
if
ie
d
d
u
e-
d
at
e
se
q
u
en
ci
n
g
r
u
le
s
u
n
d
er
l
o
o
se
d
u
e
-d
a
te
s
(2
0
%
t
a
rd
y
)
1534 R. S . Russell e t al
provide a clue to AU’s apparent poor performance against unweighted per-
formance measures. It is hypothesized t h a t AU, in weighted form, causes the
most important jobs to be completed on time so tha t the high variability in com-
pletion times may not be a factor in weighted performance measures; i.e., the jobs
that. appear very late may be unimportant jobs. Under weighted conditions, the
A U role may indeed fare well against the other sequencing rules.
In summary, significant improvements were achieved in most measures of per-
formance by using the dynamically calculated rules instead of the basic rules,
although S P T still displayed the best performance in two measures, mean flow-
time and percent tardy. In general, COVERT performed better than the ot,her 10
scqucncing rules under most of the measures of performance. This may be attrib-
uted to the fact tha t COVERT continuously truncates the S P T rule while the
other rules set some parameter for truncation. Of all the rules tested COVERT’S
performance would have t o be deemed superior.
6. Simulation experiment 111: the effect of due-date tightness
As several researchers have noted (i.e., Baker 1984, Minor and Fry 1986) there
is a tendency for sequencing rules t o perform differently in terms of tardiness
given different levels of due-date tightness. For example, Baker (1984) indicated
tha t the SPT rule was moderately effective (relative t o other sequencing rules),
when due-dates are very t ight but not so when due-dates are loose. However,
MOD resulted in superlor performance for mean tardiness when due-dates were
both tight and loose. Similar results were achieved by Minor and Fry (1986) for
the truncated SPT rules. The SIX rule performed better a t low utilization rates
and loose due-date tightness whereas the SPT-T rule did better with high uti-
lization rates and tight due-dates (i.e., high shop congestion).
In the two simulation experiments we have conducted so far, due-dates have
been very t i g h t 6 0 % of the jobs were completed late under the FCFS sequencing
rule. As such, in this third experiment we will explore the sensitivity of several of
the sequencing rules t o due-date tightness. Specifically, the five sequencing rules
tha t yielded the best overall performance in experiment 11, SPT, SPT-T, SI’,
MOD and COI’ERT, will be analysed in the same example shop scenario as before
\vith two additional levels of due-date tightness: loose (20% of completed jobs
tardy) and moderate (40% of completed jobs tardy).
Sin~zclalior~ results for experiment I I I
The rcsults of this third simulation experiment are presented in Tables 5 and
6. Also, the level of performance of the five sequencing rules for several per-
formance measures across the three levels of due-date tightness (loose, moderate
and tight) are displayed graphically in Figs. 1-7. Our analysis will focus on these
graphical plots. (Note that in each figure, each sequencing rule consists of 3 points
representing the performance measure values presented in Tables 4-6. The lines
connecting these plotted points are strictly for visual enhancement and not
intended t o result in a functional interpretation.)
Figure 1 displays the performance of each of the five sequencing rules for
mean tardiness. It is interesting to note t h a t as suggested by Baker (1984) MOD
performs best while the performance of S P T deteriorates (relative to the other
A con~parative analysis of the COVERT job sequencing rule 1535
LEVELS OF DUE DATE TIGHTNESS
Figure I . Mean tardiness of due-date sequencing rules under varying levels of due-date
tightness.
sequencing rules) as due-dates loosen. (However, conversely SPT-T performs
better than S I k s due-dates loosen which conflicts with Minor and F r y (1986)). I n
general, COVERT performed well relative to the other sequencing rules a t all
t,hree levels of due-date tightness with only MOD achieving slightly superior
results.
SPT-T
/ %ERT
I2
V)
(I)
W I I –
z g I O –
4
I- 9 –
Z
2 ::
2
Z 6 –
0
5 –
5 4 –
0
3
0 1 I I I
LOOSE MODERATE TIGHT
(20% T) (40% T) (m T)
–
–
LEVELS OF DUE DATE TIGHTNESS
Figure 2. Conditional mean tardiness of sequencing rules under varying levels of due-date
tightness.
R. S. Russell e t al.
m l o –
SPT
Z
9
6 w
5 MfD
SI
W SPT-T
COVER1
I 2
k
0 I –
I I
LOOSE MODERATE TIGHT
(20% T) (40% T) (m T)
LEVELS OF DUE DATE TIGHTNESS
Figure 3. Hoot mean square of tardiness of due-date sequencing rules under varying
levels of due-date tightness.
Next observing Fig. 2, which displays the performance of the five rules under
conditional mean tardiness, SPT is completely dominated by the other rules. In
general, MOD performed relatively well at all three levels of due-date tightness.
All four rules performed similarly a t the moderate level while COVERT was
superior for t ight due dates. Figures 3 and 4 for the root mean square of tardiness
and root mean square of conditional tardiness respectively, display somewhat
similar results; SPT is dominated by all other rules while COVERT performs best.
under conditions of tight due-dates and MOD performs best with loose due-dates.
Figure 4. Root mean square of conditional tardiness of sequencing rules under varying
Ievelb of due-date tightness.
m 26 –
m
W
, 20
a
18
0
t
0 1 6 –
z
0 14
0
LL 12
0
W 10- u
–
–
6
Z
a
W 4 –
I
b 2
–
:: O I I I LOOSE MODERATE TIGHT
(20% T) (40% 1) (60% T)
LEVELS OF DUE DATE TIGHTNESS
A comparative analysis of the COVERT job sequencing rule 1537
–
LOOSE MODERATE TIGHT
(20% T) (4096 T) (60% T)
LEVELS OF DUE DATE TIGHTNESS
Figure 5. Percent tardy of sequencing rules under varying levels of due-date tightness.
Percent tardy is the performance measure presented in Fig. 5 and for this
measure, SPT performs well across all levels of due-date tightness and is best for
moderate and tight due-dates. Among the remaining four rules, all perform simi-
larly at loose due-date levels with MOD being superior a t the moderate and tight
levels.
Figures 6 and 7 display the simulation results of the five sequencing rules for
maximum tardiness and tardiness variance. In both cases, SPT is dominated and
the remaining four rules show similar results at the lowest level of due-date tight-
ness. MOD does not perform relatively well a t the tightest level for either per-
formance measure as opposed to COVERT, which does perform well a t the
t.ightest level.
120 –
1 l o –
I 0 0 –
8 0 –
z
g 70-
COVER1
2 0
SPT-T
10
0
LOOSE MODERATE TIGHT
(20% T) (40% T) (60% T)
LEVELS OF DUE DATE TIGHTNESS
Figure 6. Maximum tardiness of sequencing rules under varying levels of due-date tight-
ness.
R. S. Russell e t al
, 120 –
0
z 110-
4:
4 loo-
>
v) 9 0 –
g 8 0 –
n
U 70 –
Q
6 0 –
30 / MOD
SPT-T
COVERT
LOOSE MODERATE TIGHT
(2% T) (40% T) (rn T)
LEVELS OF DUE DATE.TIGHTNESS
Figure 7. Tardiness variance of sequencing nrles under \.arying levels of due-date tight-
ness.
To summarize the results of this third simulation experiment, the perfornlance
of MOD is superior for all performance measures related to tardiness for loose
due-dates, although the difference between all of the sequencing rules (except for
S I T ) for loose due-dates does not appear to be significant. COVERT, in general:
does almost, as well or better than MOD a t the moderate and tight due-date levels
for all the performance measures except one. As such, it appears tha t both
CO\’ISRT and MOD perform best (relative to the other sequencing roles) under
conditions of varying due-dates.
7. Summary
In general, it appears from. the results of the simulation experiments con-
duct.ed in this paper, tha t COVERT ,results in good performance as a sequencing
rule when compared with other well-known and popular sequencing rules, includ-
ing truncated S P T and modified due-date rules which have been formulated since
COVERT’S inception 20 years ago. 111 most instances, COVERT proved to be
superior when compared with other sequencing rules. both directly and across
varying degrees of due-date tightness. The only other rule tha t performed almost.
as well was the modified operation due-date (MOD) rule.
In addition, COVERT, originally formulated to minimize mean tardiness, also
performed well on other tardiness measures such as conditional mean tardiness,
A comparative analysis of the CO llERT job sequencing rule 1539
maximum tardiness, tardiness variance, root mean square of tardiness, and root
mean square of conditional tardiness. Finally, several formulations of COVERT
were tested in this s t udy with varying est imations of waiting t ime and assump-
tions on tardiness penalties. Although COVERT’S performance’ was improved
with more sophisticated information, even t h e simplest formulations performed
well, t h u s illustrating t he flexibility of COVERT as a sequencing rule. I n
summary , th i s s t u d y has shown t h a t COVERT is a viable sequencing rule for the
job shop environment and should be included in fu ture studies comparing sequen-
cing rule performance.
References
BAKER, K. R. , 1984, Sequencing rules and duedate assignments in a job shop. Management
Science, 30, 1093.
BAKER, K. R., and BERTRAND, J . W. M., 1982, A dynamic priority rule for scheduling
against due-dates. Journal of Operations Management, 3, 37.
BAKER, K. R., and KANET, J . J., 1983, Job shop scheduling with modified due-dates.
Journal of Operations Managemenl, 4, 11.
BERRY, \V. L., and RAO, V.. 19i5, Critical ratio scheduling: an experimental analysis.
Management Science, 22, 192.
BLACKSTONE. J . H.. JR. , PHILLIPS., D. T., and HOGG, G. L., 1982, A state of the ar t survey
of dispatching rules for manufacturing job shop operations. International Journal of
Production Research, 20, 27.
U V F P A , E. 8.. and MILLER, J. G., 1979, Produclion-Inventory Systems (Homewood, Illinois:
Richard D. Irwin) third Edition, p. 503.
CARROLL, I). C., 1965. Heuristic sequencing of single and multiple component jobs. Unpub-
lished Ph.1). dissertation, Sloan School of Management, MIT, U.S.A.
DAR-EL, E. M.. and WYSK, R. A,, 1982, Job shop scheduling-a systematic approach.
Journal of Manujacturing Systems, 1, 1.
DAY. J . E., and HOTTENSTEIN. M. P., 1970, Review of sequencing research. Naval Research
Logistics Quarterly, 17, 1 I.
EILOK. S.. and CHOWDHURY, I. G. , 1976, Due dates in job shop scheduling. Internalional
.Journal of Production Research, 14, 223.
GREEK, G. I., and APPEL, L. B., 1981, An empirical analysis of job shop dispatch rule
selection. Journal of Operalions Management, 1, 197.
KAKET, J . J. , 1979, Job shop scheduling to meet duedates: a simulation study. Unpub-
lished Ph.D. dissertation, The Pennsylvania State University, U.S.A.
M I X O R , E. D., and FRY, T. D., 1986, A comparison of processing time priority dispatching
rules. Proceedings of the Sixteenth Annual hfeeting of the Southeast A~nericun Institute
for Decision Sciences, p. 302.
MOORE, J . M., and WILSON, R. C., 1967, A review of simulation research in job shop
scheduling. Production and Inventory Management, 8, I.
ORAL, hl., and MALOUIN, J. L., 1973, Evaluation of the shortest processing time scheduling
rule with truncation process. AIIE Transaeliom, 5, 357.
PANWAI.KER. S. S., and ISKANDER, W., 1977, A survey of scheduling rules. Operations
Research, 25.45.
RUSSELL, R. S., and TAYLOR, B. W., 1985, An evaluation of sequencing rules for an
assembly shop. Decision Sciences, 16, 196.
TRILLING, D. R., 1966, Job shop simulation of orders that are networks. Journal of Indw-
trial Engineering, 17, 59.
VEPSALAINEN, A. P. J . , and MORTON, T. E., 1985, Priority rules and leadtime estimation
for job shops with weighted tardiness costs. Working paper, University of Pennsyl-
vania, U.S.A., and Carnegie-Mellon University, U.S.A.
1540 A cornparalive analysis of the COVERT job sequencing rule
La regle d’envoi d’atelier COVERT avait fait I’objet de tests approfondis i l
y a vingt ans qui ont donne des resultats frappants. Depuis, une seule analyse
comparative en a trait& avec d’autres regles de mise en sequence e t peu
d’exemples ont kt& donnes quant a son application. Le present article examine
en detail la rhgle COVERT quant a son applicabiliti, s a sensibilitk a divers
paramhtres d’exploitation e t mesures de performance e t sa performance par
rapport a plusieurs autres regles de mise en sequence dont les regles SPT tron-
quees, les rhgles moderees dynamiques e t les regles d’echbances modifihes. La
performance COVERT est etudiee pour une gamme de mesures de retard.
L’Btude est effectuee dans le contexte d’un modhle de simulation d’atelier a
contraintes machines avec travaux en skrie e t routages dlectifs. Les resultats
indiquent une bonne performance de COVERT en tan t que Ggle de mise en
sequence qui, dans la plupart des cas, est superieure aux autres Ggles de mise
en sequence test&es aussi bien directement qu’en fonction de degres divers de
contraintes d’echeances.
Die COVERT-Abfertigungsregel fur Auftragsarbeitsbetriebe wurde vor 20
,Jahren ausfuhrlich erprobt und fuhrte zu eindrucksvollen Ergebnissen. Spiiter
jedoch wurde die Regel nur einmal zusammen mit anderen Ablaufplanungsre-
geln in eine vergleichende Analyse aufgenommen. E s gibt auch nur wenige
Berichte uber Anwendungsfalle der COVERT-Regel. I n diesem Beitrag wird
die COVERT-Regel ausfiihrlich untersucht in bezug auf ihre Anwendbarkeit,
ihre Empfindlichkeit auf verschiedene Betriebsparameter und Leistungskri-
krian, und ihre Leistungsfahigkeit im Vergleich zu anderen Arbeitsahlaufpla-
nungsregeln, einschlieBlich der gestutzten SPT-Regeln, der dgnamischen
Schlupfregeln und der abgeanderten Terminplanregeln. Die Leistung der
COVERT-Regeln wird mit einer Vielfalt von Verspatungskriterien gemessen.
Die Untersuchung erfolgt im Rahmen eines Simulationsmodells eines maschin-
enbegrenzten Auftragsarbeitsbetriebs mit sequentiell eintreffenden Auftragen
und zufallsbedingter Arbeitsvorbereitung. Die Ergebnisse zeigen, daB sich
COVkiRT als eine Ablaufplanungsregel gut bewahrt, ja daO sie in fast allen
Fullen den anderen Ablaufplanungsregeln iiberlegen ist, und zwar sonohl bei
direkten Prufungen wie auch unter Termingenauigkeitsvorschriften verschie-
denen Grades.