Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141659 | Discrete Optimization | 2015 | 11 Pages |
Abstract
We consider the problem of scheduling a given set of tasks on uniform processors with predefined periods of unavailability, with the aim of minimizing the maximum completion time.We give a simple polynomial MULTIFIT-based algorithm, the schedules of which finish within 1.5 times the maximum between the latest end of a downtime and the end of the optimal schedule, when there is at most one downtime on each machine. Even when all processors have the same processing speed, it is NP-hard to obtain schedules that obey better bounds for this problem.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Liliana Grigoriu, Donald K. Friesen,