简介概要

Approximation algorithm for multiprocessor parallel job scheduling

来源期刊:中南大学学报(英文版)2002年第4期

论文作者:陈松乔 黄金贵 陈建二

文章页码:267 - 272

Key words:multiprocessor parallel job; scheduling; approximation algorithm; NP-hard problem

Abstract: Pk|fix|Cmaxproblem is a newscheduling problembased on the multiprocessor parallel job, and it is proved to be NP-hard problemwhenk≥3. This paper focuses on the case of k=3. Some new observations and new techniques for P3|fix|Cmax problem are offered. The concept of semi-normal schedulings is introduced, and a very simple lineartime algorithm Semi-normal Algorithm for constructing semi-normal schedulings is developed. With the method of the classical Graham List Scheduling, a thorough analysis of the optimal scheduling on a special instance is provided, which shows that the algorithm is an approximation algorithm of ratio of 9/8 for any instance of P3|fix|Cmaxproblem, and improves the previous best ratio of 7/6 by M.X.Go- emans.

详情信息展示

<上一页 1 下一页 >

相关论文

  • 暂无!

相关知识点

  • 暂无!

有色金属在线官网  |   会议  |   在线投稿  |   购买纸书  |   科技图书馆

中南大学出版社 技术支持 版权声明   电话:0731-88830515 88830516   传真:0731-88710482   Email:administrator@cnnmol.com

互联网出版许可证:(署)网出证(京)字第342号   京ICP备17050991号-6      京公网安备11010802042557号