一种求解多处理机调度问题的α-平坦化调度算法  

Scheduling Algorithm of α-Planarization for Solving the Problem of Multiprocessor Scheduling

作　　者：魏嘉银[1] 秦永彬[1] 许道云[1] 

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

出　　处：《计算机科学》2012年第1期178-181,共4页Computer Science

基　　金：国家自然科学基金(60863005;61011130038);贵州省省长基金(200802);贵州大学自然科学青年基金(贵大自青基合字[2009]021号)和贵州大学研究生创新基金项目(校研理工2011036)资助

摘　　要：在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。In this paper,the concept of α-flatness was proposed based on analyzing the multiprocessors scheduling problem,and then introduced it into the multiprocessors scheduling problem.Finally,a new algorithm based on the concept of α-flatness was proposed to solved the multiprocessors scheduling problem.In this algorithm,the job set was flatting at first,and then solved the new problem obtained by the first step,finally an approximate solution for the original scheduling problem was obtained.The experimental results show that the solution obtained by this algorithm is good,and compared with the heuristic algorithm the result obtained by this algorithm is more stable.

关 键 词：多处理机调度 α-平坦 平坦化处理 调度算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]