Approximation algorithm for scheduling independent multiprocessor jobs

被引：0
|
作者：
Huang J.-G. [1 ]
Li R.-H. [2 ]
机构：
[1] Department of Computer Teaching, Hu'nan Normal University
[2] College of Mathematics and Computer, Hu'nan Normal University
来源：
Ruan Jian Xue Bao/Journal of Software | 2010年 / 21卷 / 12期
关键词：
Approximation algorithm; Approximation ratio; Multiprocessor job scheduling; NP-hard problem;
D O I：
10.3724/SP.J.1001.2010.03764
中图分类号：
学科分类号：
摘要：
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. © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：3211 / 3219
页数：8
相关论文
共 23 条
  • [1] He K., Zhao Y., Huang W.Q., A clustering and scheduling algorithm based on task duplication, Chinese Journal of Computers, 31, 5, pp. 733-740, (2008)
  • [2] Wu Q., Bian J.N., Xue H.X., Scheduling with resource allocation for system-level synthesis, Journal of Software, 18, 2, pp. 220-228, (2007)
  • [3] Blazewicz J., Drabowski M., Weglarz J., Scheduling multiprocessor tasks to minimize schedule length, IEEE Trans. on Computing, 35, 5, pp. 389-393, (1986)
  • [4] Drozdowski M., Scheduling multiprocessor tasks - An overview, European Journal of Operational Research, 94, 2, pp. 215-230, (1996)
  • [5] Jansen K., Porkolab L., Preemptive scheduling with dedicated processors: Applications of fractional graph coloring, Journal of Scheduling, 7, pp. 35-48, (2004)
  • [6] Jansen K., Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme, Algorithmica, 39, pp. 59-81, (2004)
  • [7] Jansen K., Porkolab L., Linear-Time approximation schemes for scheduling malleable parallel tasks, Algorithmica, 32, pp. 507-520, (2002)
  • [8] Johannes B., Scheduling parallel jobs to minimize the makespan, Journal of Scheduling, 9, pp. 433-452, (2006)
  • [9] Ye D.S., Zhang G.C., On-Line scheduling of parallel jobs in a list, Journal of Scheduling, 10, pp. 407-413, (2007)
  • [10] Graham R.L., Lawler E.L., Lenstra J.K., Kan A.H.G.R., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, pp. 287-326, (1979)
123