• DocumentCode
    1918738
  • Title

    An efficient scheduling algorithm for dependent tasks

  • Author

    Ruan, Youlin ; Liu, Gan ; Li, Qinghua ; Jiang, Tingyao

  • Author_Institution
    Coll. of Electr. Eng. & Inf. Technol., China Three Gorges Univ., Yichang, China
  • fYear
    2004
  • fDate
    14-16 Sept. 2004
  • Firstpage
    456
  • Lastpage
    461
  • Abstract
    Scheduling for dependent tasks is NP-hard. In this paper, we propose a greedy algorithm that can generate a shorter schedule than other major algorithms. The time complexity of our algorithm is O(dv2 logv), where v represents the number of tasks and d represents the maximum in degree of tasks. Simulation results show that the proposed algorithm achieves considerable performance improvement over other important algorithms.
  • Keywords
    computational complexity; directed graphs; greedy algorithms; minimisation; processor scheduling; NP hard; dependent tasks; greedy algorithm; maximum task degree; scheduling algorithm; time complexity; Clustering algorithms; Computer science; Educational institutions; Gallium nitride; Greedy algorithms; Information technology; Merging; Optimal scheduling; Processor scheduling; Scheduling algorithm;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computer and Information Technology, 2004. CIT '04. The Fourth International Conference on
  • Print_ISBN
    0-7695-2216-5
  • Type

    conf

  • DOI
    10.1109/CIT.2004.1357237
  • Filename
    1357237
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1918738