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

Problem of multiprocessor scheduling based on combinatorial cross-entropy algorithm

为提高大型多处理机调度的效率与稳定性,提出一种利用组合型交叉熵实现多处理机调度的方法。该方法依据处理机与作业的约束关系,将处理机调度问题表示为使目标函数最小化的线性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.