A concise survey of scheduling with time-dependent processing times

Edwin Tai Chiu Cheng; Q. Ding; B. M.T. Lin

doi:10.1016/S0377-2217(02)00909-8

A concise survey of scheduling with time-dependent processing times

Edwin Tai Chiu Cheng, Q. Ding, B. M.T. Lin

Research output: Journal article publication › Review article › Academic research › peer-review

583 Citations (Scopus)

Abstract

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 presented for each model and related existing results are consolidated. We also introduce some enumerative solution algorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research.

Original language	English
Pages (from-to)	1-13
Number of pages	13
Journal	European Journal of Operational Research
Volume	152
Issue number	1
DOIs	https://doi.org/10.1016/S0377-2217(02)00909-8
Publication status	Published - 1 Jan 2004

Keywords

Computational complexity
Scheduling
Sequencing
Survey
Time dependence

ASJC Scopus subject areas

Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

More information

10.1016/S0377-2217(02)00909-8

Cite this

@article{d19323f1ed2f4ff681e6982cea5087e3,

title = "A concise survey of scheduling with time-dependent processing times",

abstract = "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 presented for each model and related existing results are consolidated. We also introduce some enumerative solution algorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research.",

keywords = "Computational complexity, Scheduling, Sequencing, Survey, Time dependence",

author = "Cheng, {Edwin Tai Chiu} and Q. Ding and Lin, {B. M.T.}",

year = "2004",

month = jan,

day = "1",

doi = "10.1016/S0377-2217(02)00909-8",

language = "English",

volume = "152",

pages = "1--13",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A concise survey of scheduling with time-dependent processing times

AU - Cheng, Edwin Tai Chiu

AU - Ding, Q.

AU - Lin, B. M.T.

PY - 2004/1/1

Y1 - 2004/1/1

N2 - 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 presented for each model and related existing results are consolidated. We also introduce some enumerative solution algorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research.

AB - 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 presented for each model and related existing results are consolidated. We also introduce some enumerative solution algorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research.

KW - Computational complexity

KW - Scheduling

KW - Sequencing

KW - Survey

KW - Time dependence

UR - http://www.scopus.com/inward/record.url?scp=0141859880&partnerID=8YFLogxK

U2 - 10.1016/S0377-2217(02)00909-8

DO - 10.1016/S0377-2217(02)00909-8

M3 - Review article

SN - 0377-2217

VL - 152

SP - 1

EP - 13

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -

A concise survey of scheduling with time-dependent processing times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this