We consider the problem of scheduling a given set of tasks on multiple pro-
cessors with predefined periods of unavailability, with the aim of minimizing the
maximum completion time. Since this problem is strongly NP-hard, polynomial ap-
proximation algorithms are being studied for its solution. Among these, the best
known are LPT (largest processing time first) and Multifit with their variants.
We give a Multifit-based algorithm, FFDL Multifit, which has an optimal worst-
case performance in the class of polynomial algorithms for same-speed processors
with at most two downtimes on each machine, and for uniform processors with at
most one downtime on each machine, assuming that P 6= NP. Our algorithm finishes
within 3/2 the maximum between the end of the last downtime and the end of the
optimal schedule. This bound is asymptotically tight in the class of polynomial
algorithms assuming that P 6= NP. For same-speed processors with at most k
downtimes on each machine our algorithm finishes within ( 3
2 + 1
2k ) the end of the
last downtime or the end of the optimal schedule. For problems where the optimal
schedule ends after the last downtime, and when the downtimes represent fixed jobs,
the maximum completion time of FFDL Multifit is within 3
2 or ( 3
2+ 1
2k ) of the optimal
maximum completion time.
We also give an LPT-based algorithm, LPTX, which matches the performance
of FFDL Multifit for same-speed processors with at most one downtime on each
machine, and is thus optimal in the class of polynomial algorithms for this case.
LPTX differs from LPT in that it uses a specific order of processors to assign tasks if two processors become available at the same time.
For a similar problem, when there is at most one downtime on each machine
and no more than half of the machines are shut down at the same time, we show
that a bound of 2 obtained in a previous work for LPT is asymptotically tight in the
class of polynomial algorithms assuming that P 6= NP.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2010-05-7694 |
| Date | 2010 May 1900 |
| Creators | Grigoriu, Liliana |
| Contributors | Friesen, Donald |
| Source Sets | Texas A and M University |
| Language | English |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | application/pdf |
Page generated in 0.0022 seconds