rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Multiprocessor scheduling with availability constraints
  name:
    name part: Grigoriu, Liliana Gentiana Alex.
    role:
      role term: creator
  name:
    name part: Friesen, Donald K.
    role:
      role term: thesis advisor.
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: txu
    date issued: 2010
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: remote
    extent: 1 online resource.
  abstract: 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.
  note: by Liliana Gentiana Alex Grigoriu.
  note: "Major Subject: Computer Science"
  note: Title from author supplied metadata (automated record created 2010-08-20 08:31:34).
  note: Electronic resource.
  note: Doctor of Philosophy Texas A&M University 2010 http://hdl.handle.net/1969.1/ETD-TAMU-2010-05-7694
  note: Includes bibliographical references.
  note: Text (Dissertation)
  subject:
    topic: Major computer science
  subject:
    topic: worst-case bounds
  subject:
    topic: LPT
  subject:
    topic: Multifit
  subject:
    topic: machine shutdowns
  subject:
    topic: makespan
  subject:
    topic: fixed jobs
  subject:
    topic: multiprocessor scheduling
  subject:
    topic: uniform processors
  identifier: http://hdl.handle.net/1969.1/ETD-TAMU-2010-05-7694
  record info:
    record content source: TXA
    record creation date: 100907
    record change date: 20151201155031.0
    record identifier: in00002605843