Published on

04-Jul-2016View

213Download

1

Transcript

Ruling

. D

lytech

l Chi

; acce

Abstract

1. Introduction namic behaviors characterized by a set of dynamic

namic parameters considered by Gupta et al.

(1987) or some earlier Russian papers (e.g. Tanaev

et al., 1994), Gupta and Gupta (1988) introduced

an interesting scheduling model in which the pro-*

European Journal of Operational ReCorresponding author. Tel.: +852-2766-5215; fax: +852-

2364-5245.Machine scheduling problems with time-de-

pendent processing times have received increas-

ing attention in recent years. For many years,

most scheduling research has focused on problems

with deterministic parameters. As mentioned in

Rinnooy Kan (1976), the traditional restrictiveassumptions may correspond to a somewhat over-

simplied picture of reality, though they can take

great advantage of computational convenience. In

real-life applications, many systems exhibit dy-

parameters. This fact is commonly recognized in

control theory, systems engineering and many

other areas. But scheduling problems with dy-

namic parameters have been studied only in a few

papers. It should, however, be noted that a con-

siderable body of literature has existed for sto-

chastic scheduling that deals with schedulingproblems in an environment of uncertainty, see,

Mohring and Rademacher (1985), Righter (1994)

and Pinedo (1995).

Based on some scheduling problems with dy-We consider a class of machine scheduling problems in which the processing time of a task is dependent on its

starting time in a schedule. On reviewing the literature on this topic, we provide a framework to illustrate how models

for this class of problems have been generalized from the classical scheduling theory. A complexity boundary is pre-

sented for each model and related existing results are consolidated. We also introduce some enumerative solution al-

gorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research.

2003 Elsevier B.V. All rights reserved.

Keywords: Survey; Scheduling; Sequencing; Time dependence; Computational complexityInvited

A concise survey of schedprocess

T.C.E. Cheng a,*, Qa Department of Management, The Hong Kong Pob Department of Information Management, Nationa

Received 22 April 2002E-mail addresses: mscheng@polyu.edu.hk (T.C.E. Cheng),

mtlin@ncnu.edu.tw (B.M.T. Lin).

0377-2217/$ - see front matter 2003 Elsevier B.V. All rights reservdoi:10.1016/S0377-2217(02)00909-8eview

ing with time-dependenttimes

ing a, B.M.T. Lin b

nic University, Hung Hom, Kowloon, Hong Kong

Nan University, Pu-Li, Nan-Tou County, Taiwan

pted 4 December 2002

search 152 (2004) 113

www.elsevier.com/locate/dswcessing time of a task is a polynomial function of

its starting time. From a modeling perspective,

ed.

l of Ohowever, the makespan scheduling problem withquadratic time-dependent processing times is al-

ready very intricate. For this reason, most subse-

quent research along this line has concentrated on

problems with linear or piecewise linear time-

dependent processing times.

This model reects some real-life situations in

which the expected processing time of a task in-

creases/decreases linearly or piecewise linearly withits starting time. Examples can be found in nan-

cial management, steel production, resource allo-

cation and national defense, where any delay in

tackling a task may result in an increasing/de-

creasing eort (time, cost, etc.) to accomplish the

task. The reader is referred to Kunnathur and

Gupta (1990), Mosheiov (1994, 1996a) and Sun-

dararaghavan and Kunnathur (1994) for a list ofapplications. Moreover, it seems that in other

cases, for example, re ghting, learning eect and

maintenance scheduling, a linear or piecewise lin-

ear function is a close approximation of the actual

nonlinear phenomenon.

Research on time-dependent problems has

spawned a new area in the scheduling eld. It has

uncovered many new properties neglected in theclassical scheduling theory and led to ecient

methodological approaches to algorithm design

and NP-complete reduction. For example, tech-

niques based on reductions from a multiplicative

type NP-complete problem, such as SUBSETSUBSET

PRODUCTPRODUCT, are crucial to the NP-completeness

proofs for many time-dependent scheduling prob-

lems. Regarding the development of polynomialtime algorithms, a very interesting phenomenon is

related to the existence of algorithms with time

complexities of On5 or On6 log n, which is notso common in the deterministic scheduling litera-

ture. Thus, research on these problems is signi-

cant in both practical and theoretical senses.

Alidaee and Womer (1999) presented a review

on scheduling problems with time-dependent pro-cessing times. Our study aims not only at survey-

ing recent developments in this line of research but

also at investigating several unsolved problems.

Based upon state-of-the-art status of research on

scheduling problems with time-dependent pro-

cessing times, we discuss the relationships of dif-

2 T.C.E. Cheng et al. / European Journaferent models and explicate how they aregenerated from a basic linear model. A complexityboundary is presented for each model and existing

and new results are consolidated. For the intrac-

table problems, we also introduce some enumera-

tive solution algorithms and heuristics and analyze

their performance. Finally, we give some insights

into scheduling problems of this type, which reveal

several potential future directions of research for

this exciting eld of study.In Section 2, we introduce a notation-and-

model system for the scheduling problem with

time-dependent processing times. In Section 3, we

present a set of complexity results for each model.

In Section 4, we illustrate a series of polynomial

and pseudo-polynomial algorithms. In Section 5,

we discuss some enumerative and heuristic solu-

tion algorithms in the literature. Some concludingremarks and suggestions for future research are

given in Section 6.

2. Notation and models

Since most of the time-dependent scheduling

problems are a natural generalization of their

classical counterpart, we adopt the notation, de-

nitions and assumptions prevalent in classical

scheduling theory, see the survey of Graham et al.

(1976).Research on time-dependent problems has

mainly dealt with the single machine model, with

only a few exceptions dealing with the parallel

machine and ow shop situations. The objective

has been conned to the minimization of a handful

of traditional regular performance measures, such

as makespan, ow time, maximum lateness and

number of tardy tasks. The time-dependent func-tion used to model the processing time of a task is

usually a linear or piecewise linear function of the

starting time of the task in a schedule. We give

below a formal statement for the basic linear

model.

A task system consisting of n independent tasksis denoted by TS fTig; faig; fbig; frig; fdig.Each task Ti is associated with a release time ri anda due date di, and is characterized by a normalprocessing time ai P 0 and a processing rate bi.The actual processing time of Ti depends on its

perational Research 152 (2004) 113start time si and is given by pi ai bisi.

pi bisi, if si 0, then every actual processingtime is 0, a trivial case. Thus, we assume that si P e

l of OGupta et al. (1987), Gupta and Gupta (1988),Browne and Yechiali (1990), Gawiejnowicz and

Pankowska (1995) and some earlier Russian pa-

pers (e.g. Tanaev et al., 1994) proposed the model

pi ai bisi from dierent perspectives. Themodel reects real-life situations, such as searching

for an object under worsening weather or perfor-

mance of medical treatments under deteriorating

health conditions, where any delay may incur extraeorts to accomplish the task (Mosheiov, 1994).

Motivated by a military application concerning

aerial treats, Ho et al. (1993) proposed the model

pi ai bisi with deadline di. Some special casesof the model pi ai bisi have also been investi-gated in the literature.

Mosheiov (1994) rst considered the special

case with ai 0, i.e., the model pi bisi. For thecases with bi b or ai a, the problems with adeadline or release time restriction have been

studied by Cheng and Ding (1998a,b, 1999, 2000,

2003). Next we introduce some piecewise linear

models.

In some situations, if a task starts after a time

di, its processing time deteriorates with its startingtime. Note that the parameter di is not the classicaldeadline or due date, but a kind of deteriorating

(decreasing) break point. Practical examples arise

from jobbing production where jobs are produced

at a normal or overtime cost depending on whe-

ther the job is started before a specied time point,

i.e., the break point. Kunnathur and Gupta (1990)

proposed a model with piecewise increasing pro-

cessing times, denoted by pi maxfai; aibisi dig. Sundararaghavan and Kunnathur(1994) and Mosheiov (1995) independently intro-

duced another model with step deteriorating pro-

cessing times, denoted by pi ai or pi ai bi,where pi ai, if si6 di; pi ai bi, otherwise.When the parameter di is considered, only themakespan and ow time problems have been

considered in the literature.To approximate the learning eect, Cheng et al.

(2003) studied a model with piecewise linear de-

creasing processing times, denoted by pi ai biminfsi; dig. In this model, if a task startsbefore or at di, its processing time decreases withits starting time linearly; otherwise, the decrease of

T.C.E. Cheng et al. / European Journaits processing time is a constant bidi. Bachman et al.for the model pi bisi, where e is a given smallpositive number.

For the model pi ai or pi ai bi, all pa-rameters are assumed to be integers. For the other

models, the normal processing times ai are as-sumed to be integers. Since the deteriorating rates

bi are rational numbers in most practical cases andthe actual processing times are always greatly af-

fected by some exponential terms of the corre-

sponding deteriorating rates, the other parameters

are allowed to be positive rational numbers.Discussions and justications for these as-

sumptions are provided in the remainder of this

paper when necessary. Table 1 presents a list of the

dierent models that have appeared in the litera-

ture, along with the corresponding references. Fig.

1 illustrates the time-dependent function of each

model.

3. NP-complete problems

The NP-complete results for the class of clas-

sical scheduling problems have been well re-

searched and surveyed in several papers and

books, for example, Rinnooy Kan (1976), Graham

et al. (1976) and Lawler et al. (1993). However, thetime-dependent scheduling problems present quite

dierent boundaries for the computational com-

plexities of the problems. In this section, we in-

troduce the new scheduling results, starting from

the simple models and gradually progressing to(2002b) investigated the model pi ai bisi, illus-trating with an example where a worker gains

knowledge and skills when assembling a large

quantity of similar products.

For the models pi ai bisi and pi ai biminfsi; dig, if bi > 1, then some performancemeasures become nonregular. If ai < bidi, then theactual processing time may reduce to 0. To avoid

these unrealistic and uninteresting cases, we as-sume that 0 < bi < 1 and ai > bidi for these twomodels. For the case without the deadline restric-

tion, we assume ai > biP

aj. For the model

perational Research 152 (2004) 113 3their generalizations.

7), Gu

, 1996

d Pan

; Hsie

wiejn

upta

nd va

and

l of OTable 1

Time-dependent scheduling models and references

Model References

pi ai bisi Gupta et al. (198(1991, 1994, 1995

Gawiejnowicz an

1999, 2000, 2003)

Kononov and Ga

pi maxfai; ai bisi dig Kunnathur and G(1998), Kubiak a

pi ai or pi ai bI Sundararaghavan

4 T.C.E. Cheng et al. / European JournaIn the literature, studies involving multiple

machines or shops center around the two models

pi bisi and pi ai bisi. For the model pi bisi,Mosheiov (1994, 1998), Chen (1996) and Mos-

heiov (1996a, 2002) reduced the SUBSET PRODUCTSUBSET PRODUCT

problem (Garey and Johnson, 1979) to P2jpi bisijCmax, P2jpi bisij

PCi and F 3jpi bisijCmax

respectively, where the respective parameters were

explained at the beginning of Section 2 and the

three-eld notation is adopted from Graham et al.

(1976). Kononov (1997) independently established

(2001), Jeng and Lin (2

pi ai biminfsi; dig Cheng et al. (2003)

Fig. 1. Time-dependent functions.the ordinary NP-completeness of P2jpi bisijCmaxand P2jpi bisij

PCi. As mentioned in Chen

(1997), SUBSET PRODUCTSUBSET PRODUCT is NP-complete in the

ordinary sense, not strongly NP-complete as used

in the above three papers. See also Johnson (1981)for a correction of the complexity results of SUB-SUB-

SET PRODUCTSET PRODUCT. Thus, these three problems are

only NP-complete in the ordinary sense and the

respective original reductions need some modi-

cation for their correctness. For the open shop and

job shop problem, Mosheiov (2002) showed that

O3jpi bisijCmax and J2jpi bisijCmax are NP-complete. The above results demonstrate a com-plexity structure similar to that of classical shop

oor scheduling problems where pi ai.For the model pi ai bisi on multiple

machines, Kononov and Gawiejnowicz (2001) pre-

sented a strong NP-completeness proof for F 3jpi ai bisijCmax by a reduction from 3-PARTITIONPARTITION,

pta and Gupta (1988), Browne and Yechiali (1990), Mosheiov

a, 2002), Ho et al. (1993), Woeginger (1995), Chen (1995, 1996),

kowska (1995), Kononov (1997); Cheng and Ding (1998a,b,

h and Bricker (1997); Bachman and Janiak (1997, 2000),

owicz (2001); Ng et al. (2002), Bachman et al. (2002a)

(1990); Sundararaghavan and Kunnathur (1990), Cai et al.

n de Velde (1998)

Kunnathur (1994), Mosheiov (1995, 1998), Cheng and Ding

002)

perational Research 152 (2004) 113which is known to be strongly NP-complete

(Garey and Johnson, 1979). They also presented areduction from PARTITIONPARTITION for the model pi ai bisi with two machines. Moreover, by a re-duction from SUBSET PRODUCTSUBSET PRODUCT, they showed that

makespan minimization on a three-machine open

shop with the model pi ai bisi remains NP-complete even if all jobs have the same deteriora-

tion rate on the third machine.

For the model pi ai bisi with bi b and dion a single machine, Cheng and Ding (1998a) re-

duced PARTITIONPARTITION to 1jpi ai bsi; di 2 fD1;D2gjCmax and Cheng and Ding (1999) reduced 3-PAR-PAR-TITIONTITION to 1jpi ai bsi; dijCmax. Naturally, thecorresponding maximum lateness problems are

l of Oalso NP-complete and strongly NP-complete,respectively.

Given a schedule, one convenient approach to

analyze it is to interchange the positions of one

pair of adjacent tasks and compare the properties

(such as the makespan and ow time) of the

original and the new schedules. Such an approach

of analysis is called the adjacent jobs interchange

argument. The use of this approach to facilitate theNP-completeness analysis of a problem is outlined

in the following exam...