Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
469682 | Computers & Mathematics with Applications | 2009 | 5 Pages |
Abstract
We study a single machine scheduling problem. The processor needs to go through a maintenance activity, which has to be completed prior to a given deadline. The objective function is minimum total weighted completion time. The problem is proved to be NP-hard, and an introduction of a pseudo-polynomial dynamic programming algorithm indicates that it is NP-hard in the ordinary sense. We also present an efficient heuristic, which is shown numerically to perform well.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gur Mosheiov, Assaf Sarig,