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: Approximation algorithms for scheduling to minimize the makespan of communicating processes on selected computer networks
  name:
    name part: Drew, Maxwell Sutherland
    name part: 1945-
    role:
      role term: creator
  name:
    name part: Friesen, Donald K.
    role:
      role term: degree supervisor.
  name:
    name part: Lively, William M.
    role:
      role term: degree committee member.
  name:
    name part: Sielken, R. L.
    role:
      role term: degree committee member.
  name:
    name part: Williams, G. N.
    role:
      role term: degree committee member.
  name:
    name part: Texas A & M University
    role:
      role term: degree granting institution.
  type of resource: text
  genre: bibliography
  genre: Academic theses
  origin info:
    place:
      place term: xx
    date issued: 1980
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: print
    extent: x, 187 leaves : illustrations ; 29 cm
  abstract: The problem addressed in this research is to determine how to efficiently schedule a task system, in which the precedence relation is a tree, on the processors of centralized and distributed-loop computer networks. In particular, the problem is investigated for the case in which there is a single task that must receive messages from all the other tasks before it can be executed. It is desired to find a schedule for which the makespan, the earliest time at which the tasks have completed execution, is minimal. Previous research [41] suggests this problem is NP-Hard in all but the most trivial cases, when the cost of transferring a message is negligible. It is shown in this research that the problem is also NP-Hard when the tasks all execute in unit time, the message costs are arbitrary, a "time-efficient" policy is used for routing message packets, and the network is a centralized, distributed-loop, or topologically distributed store-and-forward computer network. Because of the complexity of the problem, schedules which produce "almost" optimal solutions are regarded as satisfactory. Two approximation algorithms which produce such schedules are investigated for the cases in which the task system is executed on a centralized or distributed-loop computer network. These cases are in fact shown to be equivalent. An f(m)-approximation algorithm produces schedules whose makespan is no more than m times optimal, where m is the number of processors. This bound is the best possible when m = 2. For m [greater than or equal to] 3 examples exist for which this algorithm produces schedules in which the makespan approaches (2 m+1)/3 times optimal. Constant bounds of 2 and 3 times optimal are established for special cases. The algorithm is also investigated in isolated cases when the tasks are first sorted suboptimally. If n is the number of tasks the worst case time complexity of the algorithm may be expressed as 0(n log n + mn) when the tasks are first sorted. When sorting is not …
  note: "Major subject: Computing Science."
  note: Typescript (photocopy).
  note: Vita.
  note: Ph. D. Texas A & M University 1980
  note: Includes bibliographical references (leaves 184-186).
  subject:
    topic: Network analysis (Planning)
  subject:
    topic: Major computing science
  identifier: http://proxy.library.tamu.edu/login
  identifier: https://hdl.handle.net/1969.1/DISSERTATIONS-644906
  identifier: http://gateway.proquest.com/openurl
  related item:
    location:
      url: http://proxy.library.tamu.edu/login
  related item:
    location:
      url: https://hdl.handle.net/1969.1/DISSERTATIONS-644906
  related item:
    location:
      url: http://gateway.proquest.com/openurl
  record info:
    record content source: TXA
    record creation date: 811112
    record change date: 20220104090413.0
    record identifier: in00000640076
    language of cataloging:
      language term: eng