Approximation Algorithm for Scheduling Independent Multiprocessor Jobs
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This paper studies the multiprocessor job scheduling problem, and describes the m processors system, and analyze the algorithm for the problem of the offline version, both Pm|fix|Cmax of the scheduling problem with arbitrary process time jobs, and Pm|fix, p=1|Cmax of the scheduling problem with unit processing time jobs. Severalvery simple and practical polynomial time approximation algorithm are constructed, a (√2m+1)-approximation algorithm for the problem Pm|fix, p=1|Cmax and a 2√m -approximation algorithm for the problem Pm|fix|Cmax , by usingthe Split Scheduling (SS), the First Fit (FF) and the Large Wide First (LWF) technique. The results are better than any seen in the literature at present.

    Reference
    Related
    Cited by
Get Citation

黄金贵,李荣珩.独立多处理机任务静态调度问题的近似算法.软件学报,2010,21(12):3211-3219

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 26,2009
  • Revised:November 04,2009
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063