• DocumentCode
    3349256
  • Title

    An NC algorithm for finding minimum weighted completion time schedule on series parallel graphs

  • Author

    Sunder, S. ; He, Xin

  • Author_Institution
    Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
  • fYear
    1992
  • fDate
    1-4 Dec 1992
  • Firstpage
    120
  • Lastpage
    127
  • Abstract
    The authors present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O(log2 n ) time with O(n3) processors on a CREW (concurrent-read exclusive-write) PRAM (parallel random-access machine), where n is the number of vertices of the input graph. It is noted that this is the first NC algorithm for solving the problem
  • Keywords
    computational complexity; parallel algorithms; random-access storage; scheduling; CREW; NC algorithm; PRAM; concurrent-read exclusive-write; minimum weighted completion time schedule; parallel algorithm; series parallel graphs; Algorithm design and analysis; Computer science; Design optimization; Helium; Optimal scheduling; Parallel algorithms; Phase change random access memory; Processor scheduling; Scheduling algorithm; Virtual manufacturing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel and Distributed Processing, 1992. Proceedings of the Fourth IEEE Symposium on
  • Conference_Location
    Arlington, TX
  • Print_ISBN
    0-8186-3200-3
  • Type

    conf

  • DOI
    10.1109/SPDP.1992.242754
  • Filename
    242754
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3349256