Show simple item record

dc.contributorFriesen, Donald
dc.creatorGrigoriu, Liliana
dc.date.accessioned2010-07-15T00:16:16Z
dc.date.accessioned2010-07-23T21:47:05Z
dc.date.accessioned2017-04-07T19:57:21Z
dc.date.available2010-07-15T00:16:16Z
dc.date.available2010-07-23T21:47:05Z
dc.date.available2017-04-07T19:57:21Z
dc.date.created2010-05
dc.date.issued2010-07-14
dc.identifier.urihttp://hdl.handle.net/1969.1/ETD-TAMU-2010-05-7694
dc.description.abstractWe 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.
dc.language.isoeng
dc.subjectmultiprocessor scheduling
dc.subjectLPT
dc.subjectmachine shutdowns
dc.subjectworst-case bounds
dc.subjectmakespan
dc.subjectfixed jobs
dc.subjectMultifit
dc.subjectuniform processors
dc.titleMultiprocessor Scheduling with Availability Constraints
dc.typeBook
dc.typeThesis


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record