• DocumentCode
    3622816
  • Title

    Dynamic scheduling on parallel machines

  • Author

    S. Feldmann;J. Sgall;S.-H. Teng

  • Author_Institution
    Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
  • fYear
    1991
  • fDate
    6/13/1905 12:00:00 AM
  • Firstpage
    111
  • Lastpage
    120
  • Abstract
    The problem of online job scheduling on various parallel architectures is studied. An O((log log n)/sup 1/2/)-competitive algorithm for online dynamic scheduling on an n*n mesh is given. It is proved that this algorithm is optimal up to a constant factor. The algorithm is not greedy, and the lower bound proof shows that no greedy-like algorithm can be very good. The upper bound result can be generalized to any fixed-dimensional meshes. Competitive scheduling algorithms for other architectures are given.
  • Keywords
    "Dynamic scheduling","Parallel machines","Scheduling algorithm","Parallel architectures","Processor scheduling","Phase change random access memory","Computer science","Heuristic algorithms","Upper bound","Time sharing computer systems"
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
  • Print_ISBN
    0-8186-2445-0
  • Type

    conf

  • DOI
    10.1109/SFCS.1991.185355
  • Filename
    185355
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3622816