# 程序代写代做代考 AI scheme js assembly B95;10JAN99

B95;10JAN99

int. j. prod. res., 1999, vol. 37, no. 1, 165±187

An analysis of heuristics in a dynamic job shop with weighted tardiness

objectives

E. KUTANOGLU≤ and I. SABUNCUOGLU≥*

Meeting due dates as a re¯ection of customer satisfaction is one of the scheduling

criteria that is frequently encountered in today’s manufacturing environments.

The natural quanti®cation of this qualitative goal involves tardiness related meas-

ures. In this study, we consider the dynamic job shop scheduling problem with the

weighted tardiness criterion. After we present a comprehensive literature survey

on the topic, we measure the long-run performances of more than 20 single-pass

dispatching rules under various experimental conditions. In this study, we pay

special attention to recently proposed dispatching heuristics such as CEXSPT,

CR+ SPT, S/RPT+ SPT, and Bottleneck Dynamics (BD). We also investigate the

eÄects of six resource pricing schemes proposed recently for BD. Moreover, we

extend the earlier versions of inserted idleness and identify the conditions in which

these techniques can be applied without incurring too much computational cost.

Future research directions are also outlined in light of the computational results.

1. Introduction

Even though ¯exible manufacturing systems and computer integrated manu-

facturing are today’s key words that frequently appear in many research agendas,

scheduling of job shops still receives ample attention from both researchers and

practitioners. A part of the reason is that job shop problems in various forms still

exist in most of the advanced manufacturing systems. Besides, analysis of job shop

scheduling problems provides important insights into the solution of the scheduling

problems encountered in more realistic and complicated systems.

Meeting due dates, as a re¯ection of customer satisfaction, is one of the sched-

uling criteria that is frequently encountered in practical problems. The natural quan-

ti®cation of this qualitative goal involves the tardiness measure. Tardiness is the

positive lateness a job incurs if it is completed after its due date. When the jobs

have diÄerent importance levels or weights, the resulting problem is called a weighted

tardiness problem. In general, weighted tardiness problems (even the single machine

version) are NP-hard (Lenstra and Rinnooy Kan 1978). Hence, heuristics are gen-

erally preferred especially for dynamic and stochastic job shop problems. (In this

study, we assume that all the jobs are accepted for processing and each job has an

externally set due date.)

These heuristics can be classi®ed into two categories: (1) single-pass (one-pass)

and (2) multi-pass heuristics. In one-pass heuristics, a single complete solution is built

up one step at a time. Most priority dispatching rules proposed in the literature

0020±7543/99 $12.00 Ñ 1999 Taylor & Francis Ltd.

Revision received February 1998.

≤ Department of Industrial and Manufacturing Systems Engineering, Bethlehem, PA

18015, USA. This research was done while E. Kutanoglu was at Bilkent University.

≥ Bilkent University, Department of Industrial Engineering, Bilkent, Ankara, 06533

Turkey.

* To whom correspondence should be addressed.

(Panwalker and Iskander 1977) can be considered in this category. In multi-pass

heuristics, an initial schedule is generated in the ®rst pass, and then the consecutive

passes search, for improvement in performance. In this category, we can list neigh-

bourhood search, tabu search, simulated annealing, and iterative dispatching (see

Morton and Pentico (1993) for further discussion).

We focus on the single-pass heuristics, speci®cally priority dispatch rules. As we

discuss in the next section, there are studies which investigated performances of

dispatching rules by using discrete-event simulation. The general picture seems to

be that no single rule is the best under all possible conditions and the relative

performances of the rules are aÄected by factors such as shop load level, due date

tightness, and scheduling criteria. Since all these studies have been done in diÄerent

operational settings, the results sometimes give con¯icting reports. Hence, there is a

need for comprehensive research and testing to clarify these points, which is one

objective of this study. The rules evaluated in this study are listed in Appendix B

along with the notation as shown in Appendix A.

Some of these rules have been recently developed (such as CEXSPT, MDSPRO,

CR+ SPT, S/RPT+ SPT, and BD) and hence their performances are not generally

known in the literature. One goal of this study is to compare these new rules with the

existing ones so that a more complete picture can be drawn. Note that the majority

of these new rules are more complex and they demand more job and shop-related

information, which may not be available in unsophisticated systems. In this paper,

we will also show whether these complex heuristics can justify their high information

need with higher performance quality.

We also observed that the majority of the existing studies have been done in a

uniform (or balanced) environment (i.e. all machines are approximately equally util-

ized). Their relative performances are not generally known for the unbalanced

systems (i.e. non-uniform or bottleneck case). In this paper, we also analyse the

bottleneck case to see if the conclusions drawn from the uniform systems are still

valid.

We employ diÄerent resource pricing schemes for BD, most of which have been

proposed in Morton and Pentico (1993). Some of these are tested for the ®rst time in

a dynamic job shop environment. Since the mechanisms involved in resource pricing

distinguish loaded machines from less utilized ones, the performance of resource

pricing is expected to be dependent on whether the shop is balanced or unbalanced.

It is well known that schedules without idle time constitute the dominant set of

schedules in static single machine problems with regular performance measures and

that the semi-active schedules constitute a dominant set for dynamic problems

(Baker 1974). Unfortunately, dispatching heuristics normally generate a non-delay

schedule which does not include inserted idleness. However, with little additional

computation, some heuristics can be modi®ed to myopically search possibilities with

inserted idleness. One such method is proposed by Morton and Ramnath (1992) for

a dynamic single machine problem. In this study, we extend this technique for BD

and implement it for a job shop. By considering inserted idleness, we will try to

identify the conditions under which it may be better to keep the resource idle for a

soon-to-arrive urgent job.

In our experiments, we did not use multi-pass heuristics such as the lead time

iteration (LTI) method. First of all, such an iterative approach assumes either a

static environment or perfect information on the system’s future in the dynamic

case. Since we consider unknown job arrivals we cannot directly employ these

166 E. Kutanoglu and I. Sabuncuoglu

multi-pass mechanisms. More importantly, we think that LTI and other multi-pass

heuristics are search heuristics. Since the aim of this study is to test dispatching

heuristics, we only included the dispatch versions of BD. We think that search

heuristics and dispatching rules are two diÄerent categories that should be compared

with careful analysis of solution quality versus computational cost.

The rest of the paper is organized as follows: we present a comprehensive review

of the relevant literature along with the discussion of the rules tested in section 2.

Section 3 gives the system considerations and experimental conditions. Computa-

tional results are presented in section 4. (We primarily reported weighted tardiness,

although we present selected results for percent tardy jobs and conditional weighted

tardiness to initiate deeper discussion. ) The paper ends with concluding remarks and

suggestions for future research in section 5.

2. Review of literature

In this study, we only consider systems where jobs are independent. Hence, we

did not include assembly type work in which coordination of jobs plays a more

important role than dispatching. As stated earlier, there are a number of dispatching

rules proposed in the job shop literature. Among them, some are very simple, known

and used for many years. We ®rst review these conventional rules. Then we discuss

more recent studies especially on bottleneck dynamics. Table 1 lists these papers

along with shop type, performance measure and rules tested.

2.1. Conventional priority dispatching rules

The information needed by dispatching rules are classi®ed by Ramasesh (1990)

according to their information content as follows:

ï arrival times (e.g. FCFS),

ï processing times (e.g. SPT),

ï due date information,

–allowance-based (e.g. EDD),

–slack based (e.g. SLACK),

–ratio-based (e.g. CR, S/RPT, S/OPN, A/OPN),

ï combination of one or more of the above (e.g. WSPT, MOD, ODD, OSLACK).

Among the rules, FCFS is generally used as a benchmark. WSPT is the weighted

version of the shortest processing time (SPT) rule. Flow allowance of a job is the time

between the release date and the due date, Ai = di – ri. The remaining allowance of a

job i at time t is calculated as Ai (t) = di – t. Since t is the same for all jobs, the

simplest version of the allowance based priority is the earliest due date rule (EDD).

The global slack time Sij (t) of a job is time after remaining work is deducted from

allowance (Sij (t) = Ai (t) – Pij where Pij is the total remaining processing time). The

simplest slack-based priority rule is the slack time rule (SLACK), which gives pri-

ority to the job with the smallest Sij (t) .

The ratio-based rules utilize a kind of ratio in their implementation. For instance,

critical ratio rule (CR) gives priority to the job with the smallest Ai (t) /Pij . Another

ratio-based rule is slack per remaining processing time (S/RPT) with the priority

index Sij (t) /Pij . The priority index of the slack per remaining operation rule (S/

OPN) is calculated as Sij (t) /mij , where mij is the remaining number of operations

from operation j to the last operation. S/RPT gives priority to the job with the longer

remaining processing time, while S/OPN considers the job with more operations

An analysis of heuristics in a dynamic job shop 167

remaining as urgent. The S/RPT rule is equivalent to the one with CR in the sense

that their priority indexes yield the same sequence (i.e. S /RPTij (t) = CRij (t) – 1.0).

Another ratio rule is the slack/allowance ratio which gives priority to the job with

minimum ratio of SL ACK/Aij (t) = Sij (t) /Ai (t) .

Since a negative ratio is diÅcult to interpret, the ratio-based priority rules have

drawbacks: when the remaining allowance or slack time is negative, these rules

behave contrary to their intent. For example, the intent of the S/OPN rule is to

give relatively higher priorities to the jobs which have more remaining operations

because they may encounter more queuing delay. However, when the slack becomes

negative it tends to misbehave as a result of assigning higher priorities to the jobs

with fewer remaining operations. Kanet (1982) resolved this anomaly by proposing

the rule called modi®ed dynamic slack per remaining operation (MDSPRO).

168 E. Kutanoglu and I. Sabuncuoglu

Authors Conditions Measure Rules tested

Gere (1966) Dynamic JS Unweighted T FCFS, SPT, SLACK SLACK/

A, EDD, S/OPN

Elvers (1973) Dynamic JS Percent T FCFS, EDD, LWKR, SPT ,

SLACK, S/OPN, CR

Weeks (1979) Dynamic JS Unweighted L SPT , S/OPN

Miyazaki (1981) Dynamic JS Unweighted T FCFS, S/OPN, A/OPN,

SLACK/A

Elvers and Taube (1983) Dynamic JS Unweighted T SPT, EDD, SLACK, S/RPT

Kanet and Hayya (1982) Dynamic JS Unweighted T SPT , EDD, SLACK, CR,

ODD, OSLACK, OCR

Baker and Kanet (1983) Dynamic JS Unweighted T COVERT, CR, S/RPT,

SLACK, MDD, MOD

Baker (1984) Dynamic JS Unweighted T S/OPN, A/OPN, MDD, MOD

Carroll (1965) Dynamic JS Unweighted T SPT, S/OPN, COVERT

Russell et al. (1987) Dynamic JS Unweighted T EDD, SLACK, S/OPN, SPT,

MDD, MOD, AU,

COVERT

Shultz (1989) Dynamic JS Unweighted T SPT, S/OPN, OCR, MOD,

COVERT, CEXSPT

Anderson and Nyirenda

(1990)

Dynamic JS Weighted T WSPT, MOD, COVERT,

CEXSPT, CR+ SPT ,

S/RPT+ SPT

Vepsalainen and Morton

(1987)

Dynamic JS Weighted T FCFS, WSPT, EDD, S/RPT,

COVERT, ATC

Vepsalainen and Morton

(1988)

Dynamic JS Weighted T FCFS, WSPT, EDD, S/OPN,

COVERT, ATC

Kanet and Zhou (1993) Dynamic JS Unweighted T FCFS, SPT, MOD, COVERT,

ATC, MEANP

Ovacik and Uzsoy (1994) Dynamic JS Maximum L EDD, ODD, ATC

Morton et al. (1988) Static FS

and JS

NPV CR, COVERT, EXP-ET,

SCHED-STA R

Lawrence and Morton

(1993b)

Static RCPS Weighted T 20 dispatching rules, pricing

heuristics

Lawrence and Morton

(1993a)

Static JS Weighted T FCFS, WSPT, ODD,

OSLACK, ATC , BD

Table 1. Papers reviewed and their main characteristics (JS: Job Shop, FS: Flow Shop,

RCPS: Resource-constrained project scheduling, T: Tardiness, L: Lateness, NPV: Net

present value of revenues and costs). (The rule(s) found to be best in corresponding

experimental study are in bold face.)

All these rules except MDSPRO have been extensively tested in the previous

studies although not every study included all of them and used the same test bed

(i.e. experimental conditions). It seems that the relative performances of the rules are

very sensitive to the system conditions. In general, EDD, SLACK, S/RPT perform

well in light-loaded shop conditions, whereas SPT performs well in congested shops

with tight due dates, but fails with light loads and loose due dates (Elvers 1983,

Elvers and Taube 1983, Gere 1966, Miyazaki 1981, Weeks 1979).

Some rules utilize operation due dates. Among several ways of assigning opera-

tion due dates, the work content method is generally suggested for mean tardiness

(Baker 1984). According to this method, the initial ¯ow allowance of a job is allo-

cated to the operations proportional to their processing times. The rules such as

EDD, SLACK and CR have their operation due date versions (ODD, OSLACK and

OCR). It seems that operation-based rules perform better than their job-based

counterparts (Kanet and Hayya 1982).

There are also rules which combine the processing time and due date informa-

tion. One such rule is the modi®ed due date (MDD) in which the job’s original due

date serves as the due date until the job’s slack becomes zero when its earliest ®nish

time acts as the modi®ed due date (Baker and Bertrand 1982). Another operation-

based rule is the Modi®ed Operation Due date (MOD) rule. The MOD priority is

de®ned as its original ODD or its earliest ®nish time, whichever is larger. Baker and

Kanet (1983) tested these rules under various conditions and found that MOD out-

performs other rules for unweighted tardiness at high utilization. Later, Baker (1984)

compared allowance based, slack-based, and ratio-based rules against the modi®ed

rules (MDD and MOD). His results showed that slack-based rules do not oÄer an

advantage over simpler allowance-based rules, and operation-based rules perform

better than job-based rules. In another study, Christy and Kanet (1990) showed that

OD is the preferred rule for the mean tardiness criterion in systems with forbidden

early shipment.

Another popular rule is COVERT (Cost OVER Time) which was speci®cally

developed for the tardiness objective (Carrol 1965). The COVERT priority index

represents the expected incremental tardiness cost per unit of imminent processing

time. The expected tardiness is a relative measure of how much tardiness a job might

experience if it is delayed by one time unit. COVERT can be converted into the

weighted version since its derivation depends on the tardiness costs. In this case,

COVERT includes weight as a multiplier. If job i queuing for operation j has zero or

negative slack, then its expected cost per unit time is wi and priority is wi /pij . If its

slack exceeds some worst case estimate of the remaining waiting time over remaining

operations, its expected cost is set to zero. If slack is between these extremes, then the

priority goes up linearly as slack decreases.

Russell et al. (1987) examined the sensitivity of the COVERT rule to various

operating conditions and proposed diÄerent versions of COVERT. These rules were

compared with EDD, SLACK, S/OPN, SPT, truncated SPT, MDD, MOD, and

Apparent Urgency (AU, the very ®rst version of ATC). The results showed that

COVERT is the best rule for the mean tardiness and mean conditional tardiness

criteria. Shultz (1989) proposed an expediting heuristic (CEXSPT) which attempts to

lessen the undesirable properties of SPT by controlling the jobs with long processing

times. Job-based and operation-based due date information is employed to expedite

the late jobs. In the simulation experiments, CEXSPT and COVERT produced lower

unweighted tardiness.

An analysis of heuristics in a dynamic job shop 169

In a recent study, Anderson and Nyirenda (1990) developed two new rules. The

®rst rule combines CR and SPT by assigning operation due date dij for each job i

waiting for operation j as

dij = max {t + CRij (t)pij ,t + pij}.

The other rule combines S/RPT and SPT (S/RPT+ SPT) by assigning operation due

date

dij = max {t + S /RPTij (t)pij,t + pij} or dij = max {t + (CRij (t) – 1)pij,t + pij}.

It seems that these two rules are very competitive and hence they will be tested in our

study.

2.2. Bottleneck dynamics studies

Early BD studies started with the development of Apparent Tardiness Cost (ATC)

by Vepsalainen and Morton (1987). ATC is very similar to COVERT with two main

diÄerences: First, the slack is local resource constrained slack which takes into

account the waiting times on downstream machines. Second, the decay function

for the weight/processing time ratio is exponential rather than linear. In ATC,

global slack is allocated to the remaining lead time, which gives local resource-con-

strained slack as

SSij (t) = di –

mi

q=j+1

(Wiq + piq) – pij – t,

where the summation is over all un®nished downstream operations indexed as

j + 1,. . . ,mi and Wiq is the estimated waiting time for operation q of job i. (The

negative local slack can also be interpreted as the estimated lateness if the job is

scheduled immediately at time t so that its estimated completion time is

t + pij +

mi

q=j+1 (Wiq + piq) .)

The full priority formula is then

ATCij (t) =

wi

pij

´ exp –

(SSij (t) )

+

Kpavg

,

where (x)+ = max {0,x}. In this formula, the exponential term is called the urgency

factor if the job is scheduled and expected to be completed with slack SSij . Hence, the

urgency factor is

Uij (t) = exp –

(SSij (t) )

+

Kpavg

.

There are several methods to estimate waiting times. One quick and dirty method

called standard estimation inspired from the total work content rule was proposed by

the inventors of the rule: calculate Wiq as proportional to its processing time as

Wiq = bpiq, where b is a constant multiplier. One issue in this method is selecting

the right multiplier value. In actual systems this can be done by using regression

analysis with historically collected waiting times. In our study, we tried a couple of

values for b and ®xed at one level. Vepsalainen and Morton (1988) proposed two

additional techniques for waiting time estimation. The method called priority-based

estimation estimates shorter waiting times for high-priority jobs and longer for low

170 E. Kutanoglu and I. Sabuncuoglu

priority jobs. The method referred to as lead time iteration (LTI) is an iterative

procedure which aims to improve waiting time estimates from one iteration to the

next. The results showed an improvement in the performances of ATC and

COVERT with the LTI method whereas there is no signi®cant eÄect of the pri-

ority-based estimation as compared to the standard method outlined above.

Another alternative might be to calculate waiting times based on queue content

and length as proposed in Kanet and Zhou (1993). (We test both the standard

and these queue-based methods in our study.)

Kanet and Zhou (1993) proposed a decision theory approach called MEANP. It

seems that MEANP produces low unweighted tardiness and the fraction of tardy

jobs as compared to FCFS, SPT, COVERT, MOD and ATC, COVERT. However,

the authors recommended MOD for practical applications, since it is simple and

does not require parameter estimations. In another study, Ovacik and Uzsoy (1994)

extended ATC by including sequence-dependent set-up times. They compared it with

several versions of EDD and ODD in a dynamic job shop environment. The results

showed that the maximum lateness performance of ATC is not as good as that of

ODD dispatching.

Morton et al. (1988) developed the early version of the Bottleneck Dynamics

(BD) rule called SCHED-STAR. They used cost-bene®t analysis to make scheduling

decisions based on net present value (NPV) of revenues and costs. In experiments

with small-size static problems, SCHED-STAR was found to be the best performer

when compared with the diÄerent versions of COVERT, CR, and EXP-ET (Early/

Tardy version of ATC).

In another study, Lawrence and Morton (1993b) tested resource pricing heuris-

tics in static multi-project scheduling problems. They developed a resource price-

based rule similar to SCHED-STAR and tested ®ve pricing schemes. The results

indicated that all pricing heuristics dominate the 20 benchmark rules tested. In their

later work, Lawrence and Morton (1993a) tested two new resource pricing heuristics

in a static job shop. Results showed that resource pricing has the potential to

improve mean weighted tardiness.

Recently, Morton and Pentico (1993) brought together all the pieces of their

previous studies and called it Bottleneck Dynamics (BD). BD is very similar to

ATC in that it uses the numerator of the ATC function wiUij (t) as an activity

price which is a re¯ection of the current scheduling decision to the weighted tardi-

ness. In contrast to ATC, BD trades oÄ this activity price with total remaining

resource usage instead of current processing time. The resource usage of job i for

operation q at machine k(q) at time t is calculated as the resource price of the

machine times the processing time of the operation, i.e. Rk (q) (t)piq, where Rk(q) (t)

is the resource price of the machine k(q) . The total remaining resource usage is

de®ned over all remaining operations of the job and the ratio of activity price to

this resource usage gives the BD priority:

BDij (t) =

wiUij (t)

wi

q=j Rk(q) (t)piq

.

In this way, BD prioritizes the jobs with larger activity prices (most urgent ones),

while penalizing the jobs with longer processing times on bottleneck machines which

presumably have high resource prices.

An analysis of heuristics in a dynamic job shop 171

2.2.1. Resource pricing

From an optimization point of view, resource price can be interpreted as the

value of a dual variable for the resource’s capacity constraint. Hence, the resource

price can be estimated by calculating extra costs if the resource capacity is decreased

for one time unit. One such approach, called empirical resource pricing, is proposed

in Lawrence and Morton (1993b). The change in objective function gives a relative

measure of resource price. Since both exact calculation and the empirical pricing are

diÅcult to implement in a dynamic environment, approximation methods have been

developed.

We ®rst consider the price of the current machine in resource usage calculation,

which is referred to as myopic pricing in the terminology of Lawrence and Morton

(1993b). In this method, the current machine’s price is scaled to 1 and all others have

zero prices (we called BD with myopic pricing BD-Myp; this is actually equivalent to

ATC). The second alternative is uniform pricing (BD-Unif), which assumes that all

resources are of equal importance and assigns them resource prices of 1. In this case,

the denominator of the priority formula is the summation of processing times of

downstream operations, Pij . The third alternative, bottleneck pricing (BD-Bot), iden-

ti®es the bottleneck machine with highest utilization, and gives it a scaled price 1.0,

while other resources are assigned prices of zero.

Morton and Pentico (1993) developed other approximate methods based on

busy-period analysis and queuing theory. The static pricing (BD-Stat) depends on

the machine’s utilization:

Rk (t) = (wU)avg

qk

(1.0 – qk)2

,

where (wU)avg is the average activity price of the jobs and qk is long term utilization

rate of machine k. A more complex dynamic price, which changes according to the

current queue length and utilization of the machine, is given by

Rk (t) =

L k (t)

i=1

wiUij (t) + (wU)avg L k (t)

qk

1.0 – qk ,

where L k (t) is the current queue length. We will test two diÄerent versions of BD

with dynamic pricing. The ®rst one uses standard waiting time estimation (called

BD-DynSt), while the other uses the estimation technique developed by Kanet and

Zhou (1993) called BD-DynKZ). The waiting time for job i for operation j (i) at

machine k with queue length L k (t) is estimated by

Wij (i) =

L k (t)

i=1,l /=i

plj (l)

2

.

2.2.2. Inserted idleness

As pointed out previously, inserted idleness can improve the performance of the

dispatching rules in a dynamic environment. However, one should know when it is

worth keeping the machine idle even though it has jobs in its queue. As shown by

Morton and Ramnath (1992), for any regular objective, no operation can be sched-

uled next on a given machine, unless it is currently available in the queue, or else will

arrive before the current time plus the processing time of the shortest job in the

172 E. Kutanoglu and I. Sabuncuoglu

queue. By observing this fact, they proposed a modi®cation of the ATC rule for the

dynamic single machine problem. Assuming arrival times to the machine are known,

they calculated the priorities of those jobs with a penalty proportional to inserted

idleness involved. In this paper, we have extended their approach to job shops.

In our case, the arrival times are not known in advance. However, for a job that

is being processed at a machine, we can exactly calculate the job’s arrival time to the

next machine in its routing. In this way, we extend the candidate job set by adding

the jobs that will arrive in the near future. We reduce the priorities of such jobs

proportional to the idleness. The proportionality multiplier b goes up linearly with

the utilization of machine k as suggested in Morton and Ramnath (1992). If we

denote the arrival time of job i to machine k for operation j as aij , then the priorities

of such jobs are revised according to the following

BDij (t)Â= BDij (t) ´ 1.0 – b

(aij – t)+

pmin

,

where pmin is the processing time of shortest job in the queue. This means that the

original priority of a job is degraded by a term proportional to the idleness as a

fraction of the minimum of the processing times of waiting jobs. If this priority is still

greater than the priorities of the jobs in the queue, then the machine is kept idle until

this job arrives at the machine. We employ this method only for BD although it is

not too diÅcult to modify other dispatching rules to include this type of inserted

idleness.

3. System considerations and experimental factors

The environment considered in this study is a dynamic shop with the classic job

shop assumptions (Morton and Pentico 1993, p. 387). It is a re-entrant job shop with

10 machines continuously available. Jobs arrive according to a Poisson process and

are released immediately to the system. The jobs have a number of operations uni-

formly distributed between 1 and 10. The operations are randomly processed

through the machines. Two types of shop are simulated: the ®rst one is a uniform

shop where every machine is approximately equally utilized with operation pro-

cessing times drawn from a uniform distribution (Anderson and Nyirenda 1990,

Vepsalainen and Morton 1988). The second is a bottleneck shop where one or

more machines are bottlenecks with longer processing times. The relative speeds

of three machines are highly utilized, some are lightly utilized. Job weights are

drawn from U (Anderson and Nyirenda 1990, Vepsalainen and Morton 1988).

Since our aim is not to investigate the due date setting policies, we assign more

general and somewhat random due dates controlled by a processing time multiplier

to generate desired levels of due date tightness (similar external setting of due dates

can be found in the literature, e.g. Vepsalainen and Morton (1989). Speci®cally, due

dates are assigned randomly over a full range of ¯ow allowances, with a maximum of

12.0, 9 and 6.0 times the mean total job processing time for relatively loose, medium,

and tight due dates, respectively. We call this rule the random average total work

content rule (RATWK), formulated as follows:

di = ri + U 0,D *

(mmin + mmax)

2

pavg ,

An analysis of heuristics in a dynamic job shop 173

where D is the tightness parameter, mmin and mmax are minimum and maximum

number of operations, respectively. The average utilization of the shop is determined

by calibrating the arrival rate of the jobs. In a uniform shop, the arrival rate is

adjusted to achieve approximately 60% average utilization in the low level, 80%

in the medium level, 90% in the high level. In the bottleneck shop, the utilization of

the bottleneck determines the system load level. In this case, arrival rate is adjusted

to achieve 60% utilization on the bottleneck machine in the low level, 80% in the

medium level and 95% in the high level. (For a summary of experimental factors, see

table 2.)

The system is simulated by using SIMAN simulation language (Pegden et al.

1990) with additional C subroutines linked within the UNIX environment. We use

the method of batch means to collect the output data. Based on pilot runs, we

determine a conservative warm-up period for the system as 2500 job completions.

To reduce correlation between batches, we use 10 rather long batches with 1000 jobs

each. Common random numbers are used as a variance reduction technique to

provide the same experimental conditions for the rules (Law and Kelton 1991).

The dispatching rules presented in Appendix B are used in the experiments. We

test 6 diÄerent pricing schemes for BD:

(1) BD with myopic pricing (BD-Myp);

(2) BD with dynamic pricing (standard waiting time estimation, BD-DynSt);

(3) BD with dynamic pricing (K-Z waiting time estimation, BD-DynKZ);

(4) BD with static pricing (BD-Stat);

(5) BD with uniform pricing (BD-Unif);

(6) BD with bottleneck pricing (BD-Bot).

Inserted idleness versions of these rules are represented by adding X as a pre®x

(X-BD-Myp, X-BD-DynSt, etc.). In the inserted idleness case, only the jobs whose

next operation is on the machine under consideration are considered as additional

candidates, as described in the previous section.

The previous research has indicated that the performances of parametric rules

such as COVERT and BD are sensitive to the selection of the parameter value. For

example, studies showed that look-ahead parameter K should be adjusted according

to conditions such as utilization and due date tightness (Morton and Rachamadugu

1982, Vepsalainen and Morton 1988). We have conducted some pilot experiments to

choose values for parameters. As a result of these simulation runs, COVERT is

found to be robust and we use b = 2.0 and h = 2.0 for all settings. For BD rules,

the waiting time estimation parameter (b) is set to 2.0. The look-ahead parameter

(K) is adjusted according to the job shop type and utilization level. In the uniform

shop K is ®xed at 2.0 in low utilization, K = 3.0 in medium, K = 4.0 in high utiliza-

tion. In the bottleneck shop, K is 1.5 in the low and medium levels of utilization, and

174 E. Kutanoglu and I. Sabuncuoglu

Factor Number of levels Levels

Shop type 2 Uniform, bottleneck

Utilization 3 Low (60%), Medium (80%), High (90%±95%)

Due date tightness 3 Loose, Moderate, Tight

Dispatching rules 30 BD rules (6), X-BD rules (6), Others (18)

Table 2. Experimental factors and their levels in the simulation experiments.

vagrant

it is ®xed at 3.0 in high utilization. Experiments conducted by Morton and Ramnath

(1992) show that b = 1.3 + qk is appropriate for ATC with inserted idleness in the

single machine case. In order to ®nd the best value for the job shop, we have tried

diÄerent values for b for the inserted idleness version of BD, and ®nally set

b = 2.0 + qk .

4. Computational results

First, we measure the performance of the BD rules and identify the promising

ones that can be used for further tests. Then we present the overall results of other

dispatching rules.

4.1. Experiments with bottleneck dynamics

Figure 1 shows eÄects of due date tightness and utilization level on the weighted

tardiness (T) performance of non-delay BD rules. As one can intuitively expect, the

performances deteriorate as the due date tightens and/or the utilization increases.

However, the sensitivity of BD to these changes varies for diÄerent resource pricing

schemes. For example, while every pricing scheme yields almost the same WT at low

utilization rates, their performances are diÄerent at medium and high utilization

levels. In the uniform shop case, BD with myopic pricing (BD-Myp) draws the

lower envelope regardless of the utilization level and due tightness. However, the

An analysis of heuristics in a dynamic job shop 175

Figure 1. EÄects of utilization and due date tightness on average weighted tardiness per-

formance of non-delay BD rule with diÄerent resource pricing schemes for uniform and

bottleneck shops.

tests conducted at the 5% signi®cance level show that the diÄerences among the best

four BD rules (BD-Myp, BD-DynSt, BD-DynKZ and BD-Bot) are statistically

insigni®cant in general, although they are all signi®cantly better than BD-Stat and

BD-Unif. The diÄerence between the latter two is not distinguishable.

In the bottleneck shop, although the main observations are somewhat similar to

those of the uniform case, there are some diÄerences that show the eÄects of unbal-

anced machine loads. First, we observe that as expected the performances of the

rules are less distinguishable at low and medium utilization rates than the uniform

case, since the overall utilization is lower in the bottleneck case. The second best

performer after BD-Myp is BD with bottleneck resource pricing (BD-Bot) instead of

BD with dynamic pricing. This indicates the eÄectiveness of bottleneck resource

pricing for unbalanced shops.

Results show that our previous observations about non-delay BD rules are still

valid for X-versions of BD. For brevity, we plot WT with respect to inserted idleness

considerations in order to see the overall eÄect of inserted idleness. As seen in ®gure

2, there is always improvement due to inserted idleness, although the improvement

rate changes according to the pricing method and the shop type. For instance, in the

uniform shop, inserted idleness considerably improves performances of both

dynamic pricing methods (BD-DynSt and BD-DynKZ). The diÄerence is almost

negligible for other pricing schemes. We also note that the improvement is more

signi®cant for almost all types of pricing schemes in the bottleneck case.

In general, the improvement achieved by inserted idleness over non-delay ver-

sions varies from 1.4% to 16.8%. The overall improvement due to inserted idleness is

statistically signi®cant at the low and medium utilization levels. This improvement is

especially visible for BD with dynamic pricing (BD-DynSt and BD-DynKZ). To

observe the eÄect of inserted idleness with respect to utilization and due date tight-

ness, we plot the percent decrease in WT of a selected BD rule (BD-DynKZ, see

®gure 3). It seems that the improvement in the bottleneck shop is always more than

the one in the uniform case. The improvement percentage decreases with increasing

utilization and tightening due dates.

We can summarize the main ®ndings as follows.

ï BD with myopic pricing performs better than the others. This interesting result

can be attributed to several reasons. First, myopic pricing calculates the total

176 E. Kutanoglu and I. Sabuncuoglu

Figure 2. EÄects of inserted idleness method on average weighted tardiness performance of

BD rule with diÄerent resource pricing schemes.

resource usage by considering only the current machine’s price scaled to 1.0

and the current operation processing time, both of which are deterministic. In

global pricing schemes, the total usage cost depends on estimated prices of

downstream machines. If these prices are not accurate, they might lead to

inferior scheduling decisions. If we want to calculate the price of a downstream

machine we should know the load of that machine when the job arrives at that

machine. This is very diÅcult to predict in dynamic environments such as ours.

As shown in the results, assuming that all machines have the same resource

price (BD with uniform pricing) does not yield encouraging performance.

Hence, discriminating machines using diÄerent prices improves the perform-

ance signi®cantly. At this point, the focus should be on developing better

schemes with better predicting mechanisms. Global pricing was shown to be

better than myopic pricing in previous studies (Lawrence and Morton 1993b).

One important diÄerence between these studies and ours is that they used a

static environment where the scheduler can estimate the prices with high accuracy.

ï Inserted idleness improves the performance of BD, up to 16.8% in this

research. As we have shown, the improvement is considerably higher at low

utilization levels. Since there is slack in capacity and time in these cases, the

scheduler has more opportunities to wait for a hot job, and the cost of keeping

the machine idle is not as high as in a congested shop. Hence, inserted idleness

versions of BD can be suggested for low and moderately loaded shops.

However, it should be noted that in reality these are not usually the situations

in which tardiness is a major problem.

ï The results with the bottleneck shop are somewhat diÄerent from those of the

uniform case. This is expected because the purpose of resource pricing is to

discriminate the machines according to their loads. Therefore, in an unbal-

anced shop, resource pricing schemes eÄectively distinguish the resources as

bottleneck and non-bottleneck. The performance of BD with bottleneck pri-

cing is better in the bottleneck shop than in the uniform shop.

4.2. Experiments with other rules

Since the number of rules to be tested is quite large, we have put them into four

groups for easy presentation of the results: (1) FCFS, WSPT, WLWKR; (2) EDD,

An analysis of heuristics in a dynamic job shop 177

Figure 3. EÄects of due date tightness and utilization on the percentage improvement in

weighted tardiness achieved by implementing inserted idleness with BD-DynKZ dispatch-

ing rule.

MDD, SLACK, CD, S/OPN, MDSPRO (mostly job-based): (3) ODD, OSLACK,

OCR, MOD, CEXSPT (mostly operation-based); and (4) W(CR+ SPT), W(S/

RPT+ SPT), COVERT.

Relative performances of the rules are very similar in both uniform and bottle-

neck shops except that the diÄerences are more visible in the bottleneck case.

Therefore, we present only the bottleneck shop results for brevity. As ®gures 4

and 5 show, the diÄerences between the performances of the rules become more

signi®cant with tightening due dates and increasing shop loads.

The best rule in the ®rst group, WSPT, is most robust to changes in the levels of

experimental factors whereas FCFS is the worst. MDD is the best rule in the second

group, followed by CR and S/OPN. Although MDSPRO was designed to eliminate

the drawbacks of S/OPN, it performs poorly. Among the operation-based rules in

the third group, MOD and CEXSPT compete for the ®rst rank, while the opera-

tional slack rule (OSLACK) draws the upper envelope. The last group includes the

best performers among all the rules tested. The maximum diÄerence between the

worst and the best performer in this group is around 4.3% in the uniform shop and

2.8% in the bottleneck case. It is diÅcult to rank them since their performances are

close to each other. The statistical tests conducted on the overall results show that

the rules in the last group (W(CR+ SPT), W(S/RPT+ SPT) and COVERT) are all

signi®cantly better at the 5% signi®cance level than the others. However, the per-

formance diÄerences within the last group are indistinguishable. If we group the

178 E. Kutanoglu and I. Sabuncuoglu

Figure 4. EÄects of due date tightness on average weighted tardiness performance of the

non-BD rules for bottleneck job shop.

rules according to their statistically signi®cant diÄerence, we achieve the following

ranking: (1) W(CR+ SPT), W(S/RPT+ SPT) and COVERT, (2) WSPT, (3) MOD,

(R) CEXSPT, WLWKR, OCR, (5) CR, MDD, ODD, S/OPN, OSLACK, (6)

SLACK, EDD, MDSPRO, (7) FCFS. The low ranked groups are better than the

higher ranked groups and the overall performance diÄerence within a group is not

signi®cant.

The major conclusions in this section can be summarized as follows.

ï Priority rules which make use of operational information such as operation

due dates and operation processing times perform consistently better than their

job-based counterparts. The results also show that the performances of the

job-based and operation-based rules are very sensitive to the system con-

ditions.

ï WSPT is more robust in general. For instance, while WSPT is worse than

almost all job- and operation-based rules at low load levels, it performs better

than these rules in congested shops with tight due dates.

ï The rules in the last group perform quite well regardless of changes in due date

tightness and utilization levels. Complex and composite rules such as

COVERT and W(CR+ SPT) are very eÄective when compared with the

other rules. Although MOD is reported as the best rule for unweighted tardi-

An analysis of heuristics in a dynamic job shop 179

Figure 5. EÄects of utilization on average weighted tardiness performances of the non-BD

rules for bottleneck job shop.

ness in previous studies, it is outperformed by these new rules tested in our

study.

4.3. Cross comparisons of BD and other rules

Finally, we compare the best performing BD rules (non-delay and X-versions of

BD with myopic pricing) and selected rules WSPT, CR, MOD and W(CR+ SPT).

For the same of brevity, we present the results for the bottleneck shop. As depicted in

®gure 6, the BD rules are quite eÄective in improving the WT performance when

compared to all the rules except W(CR+ SPT). The tests show that the overall

performances of the best four BD heuristics and the best three among conventional

rules are not statistically signi®cant. This shows that W(CR+ SPT) is very successful

in combining the characteristics of CR and SPT into one rule. Note that CR is

relatively good at low load levels/loose due dates, whereas WSPT produces very

good WT results at high utilization rates/tight due dates. This rule discriminates

jobs with diÄerent due dates and processing time requirements. This is similar to

the urgency factor idea behind the BD rules, but BD also discriminates between the

resources according to their loads. In our experiments, however, we did not observe

any additional bene®ts of pricing over the best non-parametric rule (W(CR+ SPT).

To get more insight, we have collected percent tardy (PT) and conditional

weighted tardiness (CWT) statistics. As shown in ®gure 7, BD is a good performer

in PT regardless of due date tightness and utilization level. Since its WT performance

is close to that of W(CR+ SPT), it is expected that BD yields poor CWT perform-

ances as compared to W(CR+ SPT) (see ®gure 8). In general, BD loses its advantage

by producing jobs with long tardiness even though tardy jobs are considerably less.

MOD has a similar drawback. We note that W(CR+ SPT) is the best in CWT in

almost every condition. Our previous observation about W(CR+ SPT) in combining

WSPT and CR is also strengthened with these graphs. The CWT measure of WSPT

is very high with loose due dates and low utilization levels, whereas CR is relatively

good in that region. As utilization increases or due dates tighten, WSPT’s curve

intersects CR’s curve and WSPT starts producing less CWT than CR does.

Hence, we see that W(CR+ SPT) combines the advantageous parts of the two rules.

180 E. Kutanoglu and I. Sabuncuoglu

Figure 6. EÄects of due date tightness and utilization level on weighted tardiness perform-

ances of selected rules.

5. Conclusions and further research directions

In this study, we measured the performance of numerous dispatch heuristics

using simulation. We also tested new scheduling techniques, such as dispatching

with inserted idleness and resource pricing. The results indicated that the priority

rules which make use of operational information such as operation due dates and

operation processing times perform consistently better than their job-based counter-

parts. Additionally, we observed that complex and composite rules designed speci®-

cally for tardiness, such as W(CR+ SPT), COVERT and BD, are very eÄective in

reducing weighted tardiness. We also tested several resource pricing heuristics for

BD and found that diÄerent pricing schemes should be used in diÄerent environ-

ments. In general, myopic pricing is very eÄective. In unbalanced shops, however,

bottleneck resource pricing can also be suggested.

The results show that inserted idleness improves the performance of ordinary

dispatching heuristics. The inserted idleness versions of BD can be especially sug-

gested for low and medium utilization rates. Actually, inserted idleness would have

improved the performance more if we had expanded the candidate job set. In this

study, we considered only the jobs that are being processed and those whose next

An analysis of heuristics in a dynamic job shop 181

Figure 7. EÄects of due date tightness and utilization on percent tardy performance of

selected rules in bottleneck shop case.

Figure 8. EÄects of due date tightness and utilization on conditional weighted tardiness

performance of selected rules in bottleneck shop case.

operations are on the machine under consideration. To achieve further improve-

ment, all the jobs in the system must be considered and the arrival times of these

jobs to the machine should be accurately estimated. We consider this a good future

research topic.

The results also indicated that there are very promising tardiness related rules

such as W(CR+ SPT) and COVERT. Although BD outperforms may other dis-

patching rules, we could not show that it can beat W(CR+ SPT) and COVERT.

One reason for this could be the resource pricing scheme utilized in BD. More eÄort

should be expanded to develop eÄective resource pricing schemes in a dynamic

environment. A second reason may be the urgency factor calculation, which is

based on estimated waiting times and a look-ahead parameter. For the look-ahead

parameter, we can decide on the value by making some pilot runs. However, as

Morton and Pentico (1993) noted, the lead time estimation is one of the important

issues for better performance. If the lead time is accurately estimated, then the

scheduler can predict estimated lateness of a job very well. Hence researchers need

to ®nd more eÄective ways of estimating waiting times or total lead time.

In this study, we tested Kanet and Zhou’s (1993) waiting time estimation whose

performance is good but not suÅcient to get higher-quality performances. Another

option is the multi-pass version of BD known as lead time iteration (LTI). We did

not include LTI in our study because of the reasons outlined previously. Further

research can focus on LTI and other methods of estimating lead times in a dynamic

job shop. Additional improvement for BD might be achieved by analysing why the

rule yields few but long tardy jobs (high conditional weighted tardiness).

Another further research topic is testing the rules using diÄerent order review

release (ORR) methods. In our study, we used immediate release, but it would be

very interesting to see the performance of sophisticated rules under other ORR

policies.

We also note that up-to-date accurate information need is highest for BD. The

majority of the rules in our test set are dynamic, which require recalculation of the

priority as time advances. However, they utilize mostly job-related attributes which

might be readily available in most of the real systems. In contrast, the rules such as

COVERT and BD need more shop status information (machine utilization, queue

length, etc.) which can be gathered only in sophisticated shops with a good informa-

tion collection/distribution system. If the shop lacks such an information network,

then it is better to use less-demanding rules such as W(CR+ SPT). On the other

hand, if such a network is already available, which is very viable with today’s hard-

ware and software infrastructure, then BD or other information-based rules can

easily be employed. In this case, historical data can be used for value estimation

in BD and other parametric rules (utilization, waiting time, etc.).

Acknowledgment

We thank the anonymous referees for providing us with constructive comments

which improved the initial draft.

Appendix A: Notation and symbols used in the paper

i job index

j, q operation index

j (i) operation j of job i

182 E. Kutanoglu and I. Sabuncuoglu

k machine index

t current time

n number of jobs in a speci®c planning horizon or in a simulation run

mi number of operations of job i

wi weight or tardiness penalty of job i

di due date of job i

Ci completion time of job i

Ti tardiness of job i, max {0,Ci – di}

ai initial ¯ow allowance of job i

Ai (t) ¯ow allowance of job i at time t

aij arrival time of job i for operation j to the current machine

pij processing time of operation j of job i

pavg average processing time of jobs waiting for a resource

pij remaining total processing time of job i from operation j

Sij (t) slack of job i waiting for operation j at time t

mij remaining number of operations in job i from operation j

dij operation due date of operation j of job i

Wij estimated waiting time for operation j of job i

TL ij estimated tail lead time for operation j of job i

SSij (t) local resource constrained slack of operation j of job i at time t

Uij (t) urgency factor of operation j of job i at time t

APij (t) activity price of operation j of job i at time t

b waiting time estimation multiplier

K, h look-ahead parameters

k(q) the machine required for operation q of the job under consideration

Rk (t) resource price of machine k at time t

qk utilization of machine k

L k (t) queue length of machine k at time t

pmin k minimum processing time of operations waiting for machine k

b inserted idleness parameter

W T average weighted tardiness measure WT = ( ni=1 wi Ti) /n

PT per cent tardy measure, PT = [( ni=1 d (Ti) /n]´ 100

d (Ti) =

1.0 if Ti > 0

0.0 otherwise

CW T conditional weighted tardiness measure:

CWT =

n

i=1

wi Ti

(PT ´ n /100)

.

(x)+ max {0, x}

An analysis of heuristics in a dynamic job shop 183

Appendix B: Priority dispatching rules

The priorities are calculated for job i waiting for operation j at machine k at time

t as listed in the following table.

184 E. Kutanoglu and I. Sabuncuoglu

Priority rule Description

FCFS

(®rst come

®rst served)

FCFSij = aij

WSPT

(weighted shortest

processing time)

WSPTij =

wi

pij

WLWKR

(weighted least

work remaining)

WL WKRij =

wi

mi

q=j piq

EDD

(earliest due date)

EDDi = di

MDD

(modi®ed due date) MDDij (t) = max di, t +

mi

q=j

piq

SLACK

(least slack) SLACKij (t) = di – t –

mi

q=j

piq

CR

(critical ratio) CRij (t) =

di – t

mi

q=j piq

S/RPT

(slack per remaining

processing time) S /RPTij (t) =

di – t –

mi

q=j

piq

mi

q=j piq

S/OPN

(slack per remaining

operation) S /OPNij (t) =

di – t –

mi

q=j

piq

mi – j + 1

MDSPRO

(modi®ed dynamic

slack per remaining

operation)

MDSPROij (t) =

di- t-

mi

q=j

piq

mi- j+1 if di – t-

mi

q=j

piq > 0,

(mi – j + 1) di – t – miq=j piq otherwise

ODD

(operation due date) ODDij = ri +

di – ri

mi

q=j

´

j

q=1

piq

An analysis of heuristics in a dynamic job shop 185

OSLACK

(operation slack) OSLACKij (t) = ri +

di – ri

mi

q=j

´

j

q=1

pij – t – pij

OCR

(operation

critical ratio)

OCRij (t) =

ri +

di- ri

mi

q=j

piq

´ jq=1piq – t

pij

MOD

(modi®ed

operation due date) MODij (t) = max ri +

di – ri

mi

q=j

piq

´

j

q=1

piq, t + piq

CEXSPT (see Note 1)

W(CR+ SPT)

(weighted CR

and SPT

W (CR+ SPT ) ij (t) =

wi

pij ´ max 1.0, di- tmi

q=j

piq

W(S/RPT+ SPT)

(weighted S/RPT

and SPT)

W (S /RPT + SPT ) ij (t) =

wi

pij ´ max 1.0,

di- t-

mi

q=j

piq

mi

q=j

piq

COVERT

(cost over time)

COVERTij (t) =

wi

pij

´

h

mi

q=j

Wiq – di – t –

mi

q=j

piq

h

mi

q=j

Wiq

BD

(bottleneck dynamics)

BDij (t) =

wi exp –

di-

mi

q=j+1

(Wiq + piq) – piq – t

+

Kpavg

mi

q=j

Rk (q)p – iq

Note. CEXSPT rule partitions the original queue into 3 queues which are late queue, i.e. Sij (t) =

di – t – miq=j piq < 0, operationally late queue (behind the schedule), i.e. Oij (t) = dij - t - pij =
ri + (diri) /
mi
q=j piq ´
j
q=1 piq - t - pij < 0, and ahead of schedule queue, i.e. Oij (t) ≥ 0. Then the rule
selects SPT job from queue 1, if this job does not create a new late job with Sij (t) < 0. If it does, then a new
SPT job is selected from queue 2, if it does not create a new operationally late job in queue 3. If it does,
then a new SPT job is selected from queue 3.
References
Anderson, E. J. and Nyirenda, J. C., 1990, Two new rules to minimize tardiness in a job
shop. International Journal of Production Research, 28 (12), 2277±2292.
Baker, K. R., 1974, Introduction to Sequencing and Scheduling (New York: Wiley).
Baker, K. R., 1984, Sequencing rules and due date assignments in a job shop. Management
Science, 30, 1093±1104.
Baker, K. R. and Bertrand, J. W. M., 1982, A dynamic priority rule for sequencing against
due dates. Journal of Operations Management, 3, 37±42.
Baker, K. R. and Kanet, J. J., 1983, Job shop scheduling with modi®ed due dates. Journal of
Operations Management, 4, 11±22.
Carrol, D. C., 1965, Heuristic sequencing of jobs with single and multiple components. PhD
thesis, Sloan School of Management, Massachusetts Institute of Technology.
Christy, D. P. and Kanet, J J., 1990, Manufacturing systems with forbidden early shipment:
implications for choice of scheduling rules. International Journal of Production Research,
28, 91±100.
Elvers, D. A., 1973, Job shop dispatching using various due date setting criteria. Production
and Inventory Management, 14, 62±69.
Elvers, D. A. and Taube, L. R., 1983, Time completion for various dispatching rules in job
shops. OMEGA, 11, 81±89.
Gere, Jr, W. S., 1966, Heuristics in job shop scheduling. Management Science, 13, 167±190.
Kanet, J. J., 1982, On anomalies in dynamic ratio type scheduling rules: a clarifying analysis.
Management Science, 28, 1337±1341.
Kanet, J. J. and Hayya, J. C., 1982, Priority dispatching with operation due dates in a job
shop. Journal of Operations Management, 2, 155±163.
Kanet, J. J. and Zhou, Z., 1993, A decision theory approach to priority dispatching for job
shop scheduling. Production and Operations Management, 2, 2±14.
Law, A. M. and Kelton, W. D., 1991, Simulation Modeling and Analysis (New York:
McGraw-Hill).
Lawrence, S. R. and Morton, T. E., 1993a, Myopic dispatch scheduling and bottleneck
dynamics. Technical Report 1993±22, Graduate School of Industrial Administration,
Carnegie-Mellon University.
Lawrence, S. R. and Morton, T. E., 1993b, Resource-constrained multi-project scheduling
with tardy costs: comparing myopic, bottleneck, and resource pricing heuristics.
European Journal of Operational Research, 64, 168±187.
Lenstra, J. K. and Rinnooy Kan, A. H. G., 1978, Computational complexity of scheduling
under precedence constraints. Operations Research, 26 (1), 22±35.
Miyazaki, S., 1981, Combined scheduling system for reducing job tardiness in a job shop.
International Journal of Production Research, 19, 201±211.
Morton, T. E., Lawrence, S. R., Rajagopolon, S. and Kekre, S., 1988, SCHED-STAR: a
price based shop scheduling module. Journal of Manufacturing and Operations
Management, 1, 131±181.
Morton, T. E. and Pentico, D., 1993, Heuristic Scheduling Systems with Applications to
Production and Project Management (New York: Wiley).
Morton, T. E. and Rachamadugu, R. M. V., 1982, Myopic heuristics for the single machine
weighted tardiness problem. Technical Report 30-82-83, Graduate School of Industrial
Administration, Carnegie-Mellon University.
Morton, T. E. and Ramnath, P., 1992, Guided forward tabu/beam search for scheduling
very large dynamic job shops, I. Technical Report 1992-47, Graduate School of
Industrial Administration, Carnegie-Mellon University.
Ovacik, I. M. and Uz soy, R., 1994, Exploiting real-time shop ¯oor status information to
schedule complex job shops. Journal of Manufacturing Systems, 13, 73±84.
Panwalker, S. S. and Iskander, W., 1977, A survey of scheduling rules. Operations
Research, 25, 45±61.
Pegden, C. D., Shannon, R. E. and Sadowski, R. P., 1990, Introduction to Simulation Using
SIMAN (New York: McGraw-Hill).
Ramasesh, R., 1990, Dynamic job shop scheduling: a survey of simulation research. OMEGA,
18, 43±57.
186 E. Kutanoglu and I. Sabuncuoglu
Russell, R. S., Dar-el, E. M. and Taylor II, B. W., 1987, A comparative analysis of the
COVERT job sequencing rule using various shop performance measures. International
Journal of Production Research, 25, 1523±1539.
Shultz, C. R., 1989, An expediting heuristic for the shortest processing time dispatching rule.
International Journal of Production Research, 27, 31±41.
Vepsalainen, A. P. J. and Morton, T. E., 1987, Priority rules for job shops with weighted
tardiness costs. Management Science, 33, 1035±1047.
Vepsalainen, A. P. J. and Morton, T. E., 1988, Improving local priority rules with global
lead-time estimates: A simulation study. Journal of Manufacturing and Operations
Management, 1, 102±118.
Weeks, J. K., 1979, A simulation study of predictable due dates. Management Science, 25,
363±373.
An analysis of heuristics in a dynamic job shop 187