Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6893096 | Computers & Operations Research | 2013 | 8 Pages |
Abstract
First, we introduce this problem and establish the complexity of several variations of the problem. For a special case, we show that the decision version is unary NP-complete. For some other special cases, we develop optimal polynomial time solution procedures. Four heuristics based on simple rules such as Johnson's rule and the greedy-type scheduling rule are considered. For each heuristic, we provide some theoretical analysis and find a tight or asymptotically tight worst case bound on the relative error. Finally, the heuristics are empirically evaluated.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Jaehwan Yang,