Single Machine Scheduling with Learning Effect Considerations

Edwin Tai Chiu Cheng, Guoqing Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

263 Citations (Scopus)

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 languageEnglish
Pages (from-to)273-290
Number of pages18
JournalAnnals of Operations Research
Volume98
Issue number1-4
Publication statusPublished - 1 Dec 2000

Keywords

  • Learning
  • Scheduling
  • Sequencing

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Cite this