Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

93 Citations (Scopus)

Abstract

This paper studies the single-machine scheduling problem with deteriorating jobs and learning considerations. The objective is to minimize the makespan. We first show that the schedule produced by the largest growth rate rule is unbounded for our model, although it is an optimal solution for the scheduling problem with deteriorating jobs and no learning. We then consider three special cases of the problem, each corresponding to a specific practical scheduling scenario. Based on the derived optimal properties, we develop an optimal algorithm for each of these cases. Finally, we consider a relaxed model of the second special case, and present a heuristic and analyze its worst-case performance bound.
Original languageEnglish
Pages (from-to)57-70
Number of pages14
JournalEuropean Journal of Operational Research
Volume178
Issue number1
DOIs
Publication statusPublished - 1 Apr 2007

Keywords

  • Deteriorating jobs
  • Learning effects
  • Makespan
  • Scheduling
  • Single-machine

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this