TPRS_1982_v20_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: 08 December 2016, At: 04:46
International Journal of Production Research
ISSN: 0020-7543 (Print) 1366-588X (Online) Journal homepage: http://www.tandfonline.com/loi/tprs20
A state-of-the-art survey of dispatching rules for
manufacturing job shop operations
JOHN H. BLACKSTONE , DON T. PHILLIPS & GARY L. HOGG
To cite this article: JOHN H. BLACKSTONE , DON T. PHILLIPS & GARY L. HOGG (1982) A state-
of-the-art survey of dispatching rules for manufacturing job shop operations, International
Journal of Production Research, 20:1, 27-45, DOI: 10.1080/00207548208947745
To link to this article: http://dx.doi.org/10.1080/00207548208947745
Published online: 06 Apr 2007.
Submit your article to this journal
Article views: 386
View related articles
Citing articles: 456 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/00207548208947745
http://dx.doi.org/10.1080/00207548208947745
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/00207548208947745
http://www.tandfonline.com/doi/mlt/10.1080/00207548208947745
http://www.tandfonline.com/doi/citedby/10.1080/00207548208947745#tabModule
http://www.tandfonline.com/doi/citedby/10.1080/00207548208947745#tabModule
””T ..I. PROn. H~~S., 1982, VOL. 20, xo. 1,27-45
A state-of-the-art survey of dispatching rules for
manufacturing job shop operations
,JOHN H. BLACKSTONE, JRt, DON T. PHlLLIPSt and
GARY L. HOGGt
This paper reviews recent studies of dispatching rules. A dispatching rule is used
to select the next job to be processed from a set of jobs awaiting service. The paper
has two objectives. The first is to discuss the state of the art in the study of
dispatching rules. The discussion includes analytical approaches, simulation
techniques and evaluation criteria. The second objective of the paper is to
compare several of the dispatching rules listed in the Appendix using the results of
recently published studies. It is impossible to identify any single rule as the best in
all circumstances. However, several rules have been identified a,s exhibiting good
performance in general.
Introduction
This paper reviews recent studies ofdispatching rules. A dispatching rule is used
to select the next job to be processed from a set of jobs awaiting service. The
dispatching rule selected can be very simple or extremely complex. Examples of
simple dispatching rules are ‘Select a job at random’, or ‘Select the job that has been
waitin’g longest’. A complex rule might be one that selects the job with the ‘shortest
due date whose customer’s inventory is less than a specified amount’. Thirty-four
dispatching rules are formally defined in the Appendix. This set of rules has been
selected from recent articles and actual industrial usage. The rules included in this
paper have all been suggested or used in practice. Hence, they are representative but
not exhaustive.
The difficulty of I.he dispatching problem arises from the fact that, first, given n.
jobs queued at a work station there are n! ways to sequence those jobs and, second,
some shop condition at another work station might influence the optimal sequence of
jobs at the present work station.
Dispatching rules are normally used to minimize total inventory cost. The nature
of the dispatching rule employed influences delay costs, in-process and final
inventory costs, and set up costs. The need for studying dispatching rules arises from
the fact that no dispatching rule has been demonstrated to be optimal for a job shop
environment. That is, no dispatching rule has been shown to consistently produce
lower total costs than all other rules under a variety of shop configurations and
operating conditions.
This paper has two objectives. The first is to discuss the state of the art in the
study ofdispatching rules. This discussion appears in the second section of the paper
and includes analytical approaches, simulation techniques, bias of .estimates
produced by simulation, sample size, and evaluation criterion. The second objective
of the paper is to compare several of the dispatching rules listed in the Appendix
Received 24 February 1981.
t Department of Management, Auburn [Jniverxitv, Alabama, U.S.A.
t Depm-t nu-nt of I ndu-t rial Enuinect-ing, ‘I’exas A&)I Universitv. U .:–i.A.
28 J. H. Blncksume et al ,
usiug the results of recently published studies. Apparently no study has ever
included nll of the better rules listed in the Appendix. It. is impossible to identify any
single I”IIle as the best in all circumstances. However, several rules have been
identified as exhibiting good performance in general.
In addition to dispatching rules, the third section presents a discussion of
‘secondury dispatching heuristics’. These heuristics are procedures that may be used
to identify circumstances under which the job indicated by the dispatching rule
should ‘1/01 be processed first. The use of secondary dispatching heuristics has been
shown to significantly increase the performance of some dispatching rules.
Another approach to the problem of job selection is job sequencing. Job
sequencing differs from job dispatching in that. the sequencing procedure orders all
jobs in the queue, whereas the dispatching procedure only indicates the single job to
be performed first. Sequencing procedures are not. discussed in this study.
The state of the art in developing dispatching rules
Mell.
previously described although several are in actual use. A good discussion ofseveral
“riti”al ratio rules (including some in actual use at Blaek and Decker, Hughes
Airoruft, and Western Electric) is provided by Putnam et at. (1971). Critical Ratio is
.a variant of the dynumic slnok-per-operation rule. In its most general form it is
computed as
[Due Date-s-Date Now]
Critical Ratio = -‘———-“-
Lead Time Remaining
Thus, using the Critical Ratio rule requires an estimate of system delay (queue time
remaining). Critical Ratio rules are in farily common use throughout industry. The
need 1,)1′ comparison of the performances of Critical Ratio with other rules would
seem upparent.
Simple rules involviny neither processinq times nor due dales
The most commonly used rule involving a shop oharuoteristio is First-infFirst-
out, 01′ simply .FIFO. A number of researchers have found that the FIFO rule
performs substantially the same as a random selection with respeet to mean flowtime
01’ mean lateness, although FIFO produces a lower varianee of performance
measures than does random selection. In general, FIFO has been found to perform
worse than good proeessing-time rules and good due date rules with respect to both
the mean and variance of most measurement eriteria. Conway (1965 a), and
Rochette and Sadowski (1976), tested a variation of FIFO called tirst-arrived-at-
shop-first-served (FASFS). Conway found that FASFS was slightly better than
I?II”O on flowtime and slightly worse on tardiness. Rochette and Sadowski found
I?ASli’S to be better than FIFO on tardiness for 13 to 15 replications. These results
seem to show that there is no significant differenee in the performance of the two
rules, but this conjecture lacks rigid statistical support.
Another rule tested by Rochette and Sadowski was the number of operations
remaining (NOP). This rule performed mueh worse with respect to mean tardiness
than all other rules tested.
Dispatching rules for job shop operations :3i
Conway (19li5 b) examined two ‘look-ahead’ rules: NINQ, which selects the job
going next to the queue having the smallest number ofjobs (breaking tie, by SI), and
WINQ, which selects the job going next to the queue containing the least. total work.
Both rules are intended to compete with SI as they attempt to select jobs that can be
processed rapidly through the next work station. However, they have greater mean
ftowtime than ST, and generally perform worse than SI for in-process inventory
criteria.
Conway et al. (1960) also considered a ‘value