利用组合型交叉熵实现多处理机调度的算法  

Problem of multiprocessor scheduling based on combinatorial cross-entropy algorithm

作　　者：车向前[1] 张欣欣[2] 边莉[3] CHE Xiangqian ZHANG Xinxin BIAN Li(School of Computer ＆ Information Engineering, Heilongjiang University of Science ＆ Technology, Harbin 150022, China School of Electrical ＆ Control Engineering, Heilongjiang University of Science ＆ Technology, Harbin 150022, China School of Electronic ＆ Information Engineering, Heilongjiang University of Science ＆ Technology, Harbin 150022, China)

机构地区：[1]黑龙江科技大学计算机与信息工程学院,哈尔滨150022 [2]黑龙江科技大学电气与控制工程学院,哈尔滨150022 [3]黑龙江科技大学电子与信息工程学院,哈尔滨150022

出　　处：《黑龙江科技大学学报》2016年第3期323-326,335,共5页Journal of Heilongjiang University of Science And Technology

基　　金：国家自然科学基金项目(51504085)

摘　　要：为提高大型多处理机调度的效率与稳定性,提出一种利用组合型交叉熵实现多处理机调度的方法。该方法依据处理机与作业的约束关系,将处理机调度问题表示为使目标函数最小化的线性0-1整数规划模型,采用组合型交叉熵算法对该模型进行优化求解。利用组合型交叉熵算法对多处理机问题的具体事例进行测试,与模拟退火算法和蚁群算法的测试结果对比分析。结果表明:组合交叉熵算法的优化速度是蚁群算法的6.1倍,是模拟退火的29.5倍,该算法稳定性高,收敛速度快,运行时间短,在解决大型多处理机问题时效率明显高于模拟退火算法和蚁群算法。This paper presents a novel method designed for realizing multiprocessor scheduling using combinatorial cross entropy as part of the dedicated efforts to improve the efficiency and stability of a large multiprocessor scheduling.This method works by using the constraint relation between processor and job to define the multiprocessor scheduling as a 0-1 integer programming model for minimizing the objective function;realizing the optimal solution using the combinatorial cross-entropy algorithm;testing the concrete example of the multiprocessor scheduling problem using the combinatorial cross-entropy algorithm;and performing a comparative analysis of the results with the simulated annealing algorithm and the ant colony algorithm.Results demonstrate that the combinatorial cross entropy algorithm working at 6.1 times and 29.5 times respectively the speed of the ant colony algorithm and simulated annealing boasts a significantly greater efficiency than simulated annealing algorithm and ant colony algorithm in solving the large scale multiprocessor scheduling problem.

关 键 词：组合型交叉熵 多处理机调度 0-1整数规划 

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