求解多处理机调度问题的近似算法  

Approximation algorithm for solving multiprocessor scheduling problem

作　　者：曹杰先 秦永彬[1] 许道云[1] 

机构地区：[1]贵州大学计算机科学与技术学院,贵州贵阳550025

出　　处：《计算机工程与设计》2014年第7期2407-2411,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(60863005;61262006);贵州省科学技术基金项目(黔科台J字[2012]2125号);贵州大学引进人才科研基金项目(贵大人基合字[2011]14号);贵州省科技攻关计划基金项目(GY(2011)3074);贵州大学研究生创新基金项目(校研理工2013047)

摘　　要：为提高某建筑设计院工作流管理项目的开发效率、降低开发成本,针对项目任务分配过程中出现的一类多处理机调度R Cmax问题,分析了这类问题的特点,综合考虑任务的工作量及难易程度、开发团队的人员数量及个人能力,建立了这类问题的数学模型,利用贪心算法思想,设计了一种适合求解这类问题的近似算法MFTM。该算法遵循的主要思想是使最大完成时间的任务最快完成。给出了实施的具体步骤,验证了该算法的界。分别采用现实项目调度过程中的数据及仿真数据进行大量实验,实验结果表明了该算法的有效性。To improve the efficiency of the development of an architectural design institute’s workflow management proj ect and to reduce development costs,characteristics of R Cmax that was a multiprocessor scheduling problem found in task allocation process of the proj ect were analyzed,and factors such as workload,difficulty of the task,the number of personnel development team and individual capabilities were also taken into consideration.A mathematical model of this kind of problem was construc-ted.An approximation algorithm based on greedy algorithm,which was suitable for solving such problems was designed.The fastest machine was chosen to finish the task with max-completion time.Detailed operation steps were given and the bound was proved.A large number of experiments using realistic project schedule data and simulation data were done,and the calculated re-sults showed that the algorithm was effective.

关 键 词：多处理机 任务调度 近似算法 贪心策略 任务分配 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]