Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479222 | European Journal of Operational Research | 2007 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Xiuli Wang, T.C. Edwin Cheng,