A concise survey of scheduling with time-dependent processing times

  • Published on

  • View

  • Download


  • Ruling

    . D


    l Chi

    ; acce


    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,


  • 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


    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


    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


    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



    nd va


    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


    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...


View more >