Single Machine Scheduling with Learning Effect Considerations

Edwin Tai Chiu Cheng; Guoqing Wang

Single Machine Scheduling with Learning Effect Considerations

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

Abstract

In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.

Original language	English
Pages (from-to)	273-290
Number of pages	18
Journal	Annals of Operations Research
Volume	98
Issue number	1-4
Publication status	Published - 1 Dec 2000

Keywords

Learning
Scheduling
Sequencing

ASJC Scopus subject areas

General Decision Sciences
Management Science and Operations Research

Cite this

@article{cb29b6f454d74395a4b4f31106ea6045,

title = "Single Machine Scheduling with Learning Effect Considerations",

abstract = "In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.",

keywords = "Learning, Scheduling, Sequencing",

author = "Cheng, {Edwin Tai Chiu} and Guoqing Wang",

year = "2000",

month = dec,

day = "1",

language = "English",

volume = "98",

pages = "273--290",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer Netherlands",

number = "1-4",

}

TY - JOUR

T1 - Single Machine Scheduling with Learning Effect Considerations

AU - Cheng, Edwin Tai Chiu

AU - Wang, Guoqing

PY - 2000/12/1

Y1 - 2000/12/1

N2 - In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.

AB - In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.

KW - Learning

KW - Scheduling

KW - Sequencing

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

M3 - Journal article

SN - 0254-5330

VL - 98

SP - 273

EP - 290

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1-4

ER -

Single Machine Scheduling with Learning Effect Considerations

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this