Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations

Edwin Tai Chiu Cheng, Peng Jen Lai, Chin Chia Wu, Wen Chiung Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

70 Citations (Scopus)

Abstract

Scheduling with learning effects has attracted growing attention of the scheduling research community. A recent survey classifies the learning models in scheduling into two types, namely position-based learning and sum-of-processing-times-based learning. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the first model and when the normal job processing times are large in the second model. Motivated by this observation, we propose a new learning model where the actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed. The use of the logarithm function is to model the phenomenon that learning as a human activity is subject to the law of diminishing return. Under the proposed learning model, we show that the scheduling problems to minimize the makespan and total completion time can be solved in polynomial time. We further show that the problems to minimize the maximum lateness, maximum tardiness, weighted sum of completion times and total tardiness have polynomial-time solutions under some agreeable conditions on the problem parameters.
Original languageEnglish
Pages (from-to)3127-3135
Number of pages9
JournalInformation Sciences
Volume179
Issue number18
DOIs
Publication statusPublished - 21 Aug 2009

Keywords

  • Learning effect
  • Scheduling
  • Single-machine

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Software
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this