Machine scheduling with DeJong's learning effect

Min Ji, Danli Yao, Qinyun Yang, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

We consider a relatively new learning model in scheduling based on DeJong's learning effect. Compared with the classical learning model for scheduling, this model is more general and realistic. The objectives are to minimize makespan and total completion time. For the single-machine case, we show that both of the objectives are polynomially solvable. For the parallel-machine case, we show that minimizing total completion time is still polynomially solvable, while minimizing makespan is NP-hard, for which we provide a fully polynomial-time approximation scheme (FPTAS).
Original languageEnglish
Pages (from-to)195-200
Number of pages6
JournalComputers and Industrial Engineering
Volume80
Issue number1
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

  • DeJong's learning effect
  • FPTAS
  • Makespan
  • Total completion time

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this