CN105630608A

CN105630608A - Method for achieving multiprocessor scheduling through combined cross entropy

Info

Publication number: CN105630608A
Application number: CN201511003552.9A
Authority: CN
Inventors: 边莉; 张欣欣; 崔保峰
Original assignee: Heilongjiang University of Science and Technology
Current assignee: Guangdong Ocean University
Priority date: 2015-12-28
Filing date: 2015-12-28
Publication date: 2016-06-01

Abstract

本发明公开了一种利用组合型交叉熵实现多处理机调度的方法，其步骤如下：步骤一：构建多处理机调度问题的数学模型，确立目标函数和约束条件；步骤二：利用组合型交叉熵算法，通过Matlab对多处理机调度问题确立的目标函数和约束条件进行编程、求解，得到目标函数最优解。本发明依据处理机与作业的约束关系，将处理机调度问题表示为使目标函数最小化的线性0-1整数规划问题，采用组合型交叉熵算法对该问题求最优解。本发明采用的组合型交叉熵算法在得出最优解的同时具有迭代次数少、稳定性高、运行时间短等优点，进一步证明了该算法在处理多处理机问题上的有效性和实用性。The invention discloses a method for realizing multi-processor scheduling by using combined cross-entropy. The steps are as follows: Step 1: Construct a mathematical model for multi-processor scheduling problems, and establish objective functions and constraint conditions; Step 2: Use combined cross-entropy The entropy algorithm is used to program and solve the objective function and constraint conditions established by the multiprocessor scheduling problem through Matlab, and obtain the optimal solution of the objective function. According to the constraint relationship between the processor and the job, the invention expresses the scheduling problem of the processor as a linear 0-1 integer programming problem which minimizes the objective function, and adopts a combined cross-entropy algorithm to obtain an optimal solution to the problem. The combined cross-entropy algorithm used in the present invention has the advantages of less iterations, high stability, and short running time while obtaining the optimal solution, which further proves the effectiveness and practicability of the algorithm in dealing with multiprocessor problems .

Description

A Method of Realizing Multiprocessor Scheduling Using Combined Cross Entropy

技术领域technical field

本发明涉及一种多处理机调度方法，具体涉及一种利用组合型交叉熵实现多处理机调度的方法。The invention relates to a multi-processor scheduling method, in particular to a method for realizing multi-processor scheduling by using combined cross-entropy.

背景技术Background technique

当今世界发展的主要趋势是并行化、网络化、智能化，而并行分布式计算是这些发展的主要难题之一，也是当前科学邻域研究的热点问题之一。并行算法的设计、任务的划分、通信的协调和同步、多任务的调度是目前并行分布式计算需要解决的问题，而任务的调度会直接影响计算的效率，所以如何合理高效的进行多任务的调度与分配是目前急需解决的难题。于是多处理机调度问题的应用及理论方面的研究便得到了科学领域研究者极度关注。现实生活中，很多规划任务分配的问题都与多处理机调度问题密切相关。如与我们生活息息相关的工程技术、并行与分布式计算、工农业生产和交通运输等领域的具有组合优化性质的问题便可转化为多处理机调度问题来求解。多处理机调度问题实质上是NP完全问题，传统的线性规划无法解决，当前国内外多采用启发式算法如模拟退火算法、蚁群算法、量子粒子群算法近似求解。但这些算法大都存在收敛速度慢、效率较低等问题。The main trend of development in the world today is parallelization, networking, and intelligence, and parallel distributed computing is one of the main problems in these developments, and it is also one of the hot issues in the current scientific research field. Parallel algorithm design, task division, communication coordination and synchronization, and multi-task scheduling are the problems that need to be solved in parallel distributed computing at present, and task scheduling will directly affect the efficiency of computing, so how to carry out multi-task reasonably and efficiently Scheduling and allocation is a difficult problem that needs to be solved urgently. Therefore, the application and theoretical research of multiprocessor scheduling problem has been paid great attention by researchers in the field of science. In real life, many planning task allocation problems are closely related to multiprocessor scheduling problems. For example, problems with combinatorial optimization properties in the fields of engineering technology, parallel and distributed computing, industrial and agricultural production, and transportation, which are closely related to our lives, can be transformed into multiprocessor scheduling problems to solve. The multiprocessor scheduling problem is essentially an NP-complete problem, which cannot be solved by traditional linear programming. At present, heuristic algorithms such as simulated annealing algorithm, ant colony algorithm, and quantum particle swarm algorithm are used to approximate the solution. However, most of these algorithms have problems such as slow convergence speed and low efficiency.

交叉熵算法(CrossEntropyAlgorithm，CE)是以信息论中的交叉熵理论为基础提出的一种全局随机优化算法，该算法利用参数化的概率密度分布产生随机样本，使每次迭代使用的候选样本都发生变化，因此优化过程不易陷入局部最优解。目前，国内外学者已将该算法应用到解决多种组合优化问题中，并取得了一些进展与成果。Cross-entropy algorithm (CrossEntropyAlgorithm, CE) is a global stochastic optimization algorithm based on the cross-entropy theory in information theory. Therefore, the optimization process is not easy to fall into a local optimal solution. At present, scholars at home and abroad have applied this algorithm to solve a variety of combinatorial optimization problems, and have made some progress and results.

发明内容Contents of the invention

为了快速可靠的解决多处理机调度问题，本发明提供了一种利用组合型交叉熵实现多处理机调度的方法，该方法具有迭代次数少、稳定性高、运行时间短等优点。In order to quickly and reliably solve the problem of multiprocessor scheduling, the invention provides a method for realizing multiprocessor scheduling by using combined cross-entropy. The method has the advantages of less number of iterations, high stability, and short running time.

本发明的目的是通过以下技术方案实现的：The purpose of the present invention is achieved through the following technical solutions:

一种利用组合型交叉熵实现多处理机调度的方法，包括如下步骤：A method for utilizing combined cross-entropy to realize multiprocessor scheduling, comprising the steps of:

步骤一：构建多处理机调度问题的数学模型，确立目标函数和约束条件，其中，多处理机调度问题的数学模型如下：Step 1: Construct the mathematical model of the multiprocessor scheduling problem, and establish the objective function and constraint conditions. Among them, the mathematical model of the multiprocessor scheduling problem is as follows:

$z z = = \underset{11 \leq \leq n no \leq \leq c c}{max max} {Σ Σ}_{m m = = 11}^{d d} {y the y}_{n no m m} {t t}_{m m}$

$\begin{matrix} s the s . . t t . . & {Σ Σ}_{n no = = 11}^{c c} {y the y}_{n no m m} = = 11 \end{matrix}$

y_nm＝0,1(m＝1,2,...,d；n＝1,2,...,c)；y _nm =0,1(m=1,2,...,d; n=1,2,...,c);

式中，z表示完成d项作业所需要的时间，即目标函数；y_nm＝1表示作业T_m在处理机H_n上处理；表示处理机H_n完工的时间；t_m表示处理机完成作业T_m的时间；处理机表示作业T_m在一个处理机上完成，即约束条件；In the formula, z represents the time required to complete d tasks, that is, the objective function; y _nm =1 means that the task T _m is processed on the processor H _n ; Indicates the time when processor H _n completes work; t _m indicates the time when processor completes job T _m ; processor Indicates that the job T _m is completed on one processor, that is, the constraint condition;

步骤二：利用组合型交叉熵算法，通过Matlab对多处理机调度问题确立的目标函数和约束条件进行编程、求解，得到目标函数最优解。Step 2: Use the combined cross-entropy algorithm to program and solve the objective function and constraint conditions established for the multiprocessor scheduling problem through Matlab, and obtain the optimal solution of the objective function.

本发明具有如下优点：The present invention has the following advantages:

1、本发明依据处理机与作业的约束关系，将处理机调度问题表示为使目标函数最小化的线性0-1整数规划问题，采用组合型交叉熵算法对该问题求最优解，并给出组合型交叉熵算法的具体步骤。采用组合型交叉熵算法对多处理机问题的具体事例进行测试，并通过与模拟退火算法和蚁群算法的测试结果对比分析，得出本发明采用的组合型交叉熵算法在得出最优解的同时具有迭代次数少、稳定性高、运行时间短等优点，进一步证明了该算法在处理多处理机问题上的有效性和实用性。1. The present invention expresses the processor scheduling problem as a linear 0-1 integer programming problem that minimizes the objective function according to the constraint relationship between the processor and the job, adopts the combined cross-entropy algorithm to find the optimal solution to this problem, and gives The specific steps of the combined cross-entropy algorithm are presented. Adopt combined type cross-entropy algorithm to test the concrete example of multiprocessor problem, and by comparing and analyzing with the test result of simulated annealing algorithm and ant colony algorithm, draw the combined type cross-entropy algorithm that the present invention adopts in drawing optimal solution At the same time, it has the advantages of less iterations, high stability, and short running time, which further proves the effectiveness and practicability of the algorithm in dealing with multiprocessor problems.

2、本发明将组合型交叉熵算法应用到多处理机调度问题中，通过对该算法和多处理机调度问题的介绍、建模和仿真，并与其他启发式算法比较分析，得出该算法对解决多处理机调度问题的有效性与准确性。2. The present invention applies the combined cross-entropy algorithm to the multiprocessor scheduling problem, and through the introduction, modeling and simulation of the algorithm and the multiprocessor scheduling problem, and comparative analysis with other heuristic algorithms, the algorithm is obtained Effectiveness and accuracy for solving multiprocessor scheduling problems.

3、本发明对于可转化为类似多处理机问题模型的解决方案提供了一种全新的思路。3. The present invention provides a brand-new idea for a solution that can be transformed into a problem model similar to a multiprocessor.

附图说明Description of drawings

图1为CCE算法的计算过程；Figure 1 is the calculation process of the CCE algorithm;

图2为模拟退火算法的计算过程；Fig. 2 is the calculation process of the simulated annealing algorithm;

图3为蚁群算法的计算过程。Figure 3 shows the calculation process of the ant colony algorithm.

具体实施方式detailed description

下面结合附图对本发明的技术方案作进一步的说明，但并不局限于此，凡是对本发明技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围，均应涵盖在本发明的保护范围中。The technical solution of the present invention will be further described below in conjunction with the accompanying drawings, but it is not limited thereto. Any modification or equivalent replacement of the technical solution of the present invention without departing from the spirit and scope of the technical solution of the present invention should be covered by the present invention. within the scope of protection.

本发明提供了一种利用组合型交叉熵实现多处理机调度的方法，具体实施步骤如下：The invention provides a method for utilizing combined cross-entropy to realize multiprocessor scheduling, and the specific implementation steps are as follows:

1、多处理机调度问题模型1. Multiprocessor scheduling problem model

多处理机调度问题是指有c台相同的处理机H₁，H₂，…，H_c，d项相互独立的作业T₁，T₂，…，T_d，作业以互不相关的方式工作，而且任意作业都可以在任何处理机上工作，但是未完成的作业不允许中断。d项相互独立的作业不能拆分为更小的子作业。调度的目的是给出一种合理优越的调度方案，使c台处理机以尽量短的时间完成d项作业。多处理机调度问题的目标是指在满足一定性能指标和约束条件的前提下，将可并行的任务按适当的分配策略确定一种分派和执行顺序，合理分配到各处理机上有序执行，以达到减少总的执行时间的目标。因此多处理机调度问题的数学模型如式(1)所示：The multiprocessor scheduling problem is that there are c identical processors H ₁ , H ₂ ,..., H _c , and d items of independent jobs T ₁ , T ₂ ,..., T _d , and the jobs work in a mutually independent manner , and any job can work on any processor, but unfinished jobs are not allowed to be interrupted. Jobs that are independent of each other in item d cannot be split into smaller sub-jobs. The purpose of scheduling is to provide a reasonable and superior scheduling scheme, so that c processors can complete d tasks in the shortest possible time. The goal of the multiprocessor scheduling problem is to determine a dispatch and execution sequence of parallel tasks according to an appropriate allocation strategy on the premise of satisfying certain performance indicators and constraints, and reasonably allocate them to each processor for orderly execution, so as to Reach the goal of reducing the total execution time. Therefore, the mathematical model of the multiprocessor scheduling problem is shown in formula (1):

y_nm＝0,1(m＝1,2,...,d；n＝1,2,...,c)(1)。y _nm =0,1 (m=1,2,...,d; n=1,2,...,c) (1).

式中z表示完成d项作业所需要的时间；y_nm＝1表示作业T_m在处理机H_n上处理；表示处理机H_n完工的时间；t_m表示处理机完成作业T_m的时间；处理机表示作业T_m在一个处理机上完成，多处理机调度问题的目的即求z的最小值。In the formula, z represents the time required to complete d items of operations; y _nm =1 means that the operation T _m is processed on the processor H _n ; Indicates the time when processor H _n completes work; t _m indicates the time when processor completes job T _m ; processor It means that the job T _m is completed on one processor, and the purpose of the multiprocessor scheduling problem is to find the minimum value of z.

根据多处理机调度问题的特点和模型可知多处理机调度问题属于离散优化问题，本发明应用CE对多处理机问题进行优化求解，即通过交叉熵算法求出z的最小值。因为y_nm的取值为0或1，所以多处理机调度问题是0-1整数规划问题。According to the characteristics and models of the multiprocessor scheduling problem, it can be seen that the multiprocessor scheduling problem belongs to the discrete optimization problem. The present invention uses CE to optimize and solve the multiprocessor problem, that is, find the minimum value of z through the cross-entropy algorithm. Since the value of y _nm is 0 or 1, the multiprocessor scheduling problem is a 0-1 integer programming problem.

2、交叉熵算法2. Cross entropy algorithm

CE算法最早是由Rubinstein教授在信息论的基础上提出的一种全局随机优化算法，近些年来交叉熵算法被应用到故障诊断、预测等大型复杂、优化问题中。该算法的基本特征是在优化过程中根据参数化概率密度分布，使每次迭代使用的候选样本都发生变化。因此CE算法优化过程中的关键是迭代，具体的实现过程可分为两步：The CE algorithm was originally a global stochastic optimization algorithm proposed by Professor Rubinstein on the basis of information theory. In recent years, the cross-entropy algorithm has been applied to large-scale, complex and optimization problems such as fault diagnosis and prediction. The basic feature of the algorithm is that the candidate samples used in each iteration are changed according to the parameterized probability density distribution in the optimization process. Therefore, the key to the CE algorithm optimization process is iteration, and the specific implementation process can be divided into two steps:

(1)由给定的概率密度函数生成一组随机样本；(1) Generate a set of random samples from a given probability density function;

(2)根据产生的随机样本更新概率密度函数，进而为下一步迭代产生更优的样本数据。(2) Update the probability density function according to the generated random samples, and then generate better sample data for the next iteration.

2.1交叉熵算法的基本原理2.1 The basic principle of cross entropy algorithm

针对优化问题：For optimization problems:

$S S (({x x}^{* *})) = = {γ γ}^{* *} = = \underset{x x &Element; &Element; χ χ}{min min} S S ((x x)) - - - - - - ((22)),,$

式中，S是以χ为定义域的实值函数；γ^*为S的最小值；x^*为最优解；χ为有限集。设概率密度函数族为{f(·；u),u∈U}，u为密度函数的参数，对于给定的概率密度函数f(·；v),v∈U，v为给定的概率密度函数的参数，式(2)可转化为：In the formula, S is a real-valued function with χ as the domain of definition; γ ^* is the minimum value of S; x ^* is the optimal solution; χ is a finite set. Let the probability density function family be {f(·;u), u∈U}, u is the parameter of the density function, for a given probability density function f(·;v), v∈U, v is the given probability The parameters of the density function, formula (2) can be transformed into:

$l l ((γ γ)) = = {P P}_{v v} ((S S ((X x)) \leq \leq γ γ)) = = \underset{x x &Element; &Element; χ χ}{Σ Σ} {I I}_{{{S S ((X x)) \leq \leq γ γ}}} f f ((x x;; v v)) = = {E E.}_{v v} {I I}_{{{S S ((X x)) \leq \leq γ γ}}} - - - - - - ((33)) . .$

式中，γ表示给定实数；l表示S(X)比给定实数γ小的概率；I_{S(X)≤γ}为指示函数集合；X是由f(·；v)产生的随机样本；E_v表示相应的期望值。In the formula, γ represents a given real number; l represents the probability that S(X) is smaller than the given real number γ; I _{S(X)≤γ} is a set of indicator functions; X is a random sample; E _v represents the corresponding expected value.

当γ接近γ^*时，l值将会越来越小，因此为了有意义，l值不能太小，则γ和v的选取至关重要。为了解决此问题，采用多级别算法，构造分布参数序列{u_t,t＞0}和级别序列{γ_t,t＞0}(t为迭代次数)。然后将v_t和γ_t更新迭代，直到某次迭代后分布参数序列中对应元素改变量的最大值小于某一规定的参数b_tol，迭代结束。When γ is close to γ ^* , the value of l will become smaller and smaller, so in order to be meaningful, the value of l should not be too small, so the selection of γ and v is very important. In order to solve this problem, a multi-level algorithm is used to construct a distribution parameter sequence {u _t , t>0} and a level sequence {γ _t ,t>0} (t is the number of iterations). Then v _t and γ _t are updated and iterated until the maximum value of the change of the corresponding element in the distribution parameter sequence after a certain iteration is less than a specified parameter b _tol , and the iteration ends.

2.2组合型交叉熵算法2.2 Combined cross-entropy algorithm

CE算法分为连续型交叉熵算法和组合型交叉熵算法(CCE)，两者之间的区别在于概率密度函数的选择，针对组合优化问题组合型交叉熵算法的概率密度函数为Berboulli分布。设成功概率为p，则CCE算法的概率密度函数为：The CE algorithm is divided into a continuous cross-entropy algorithm and a combined cross-entropy algorithm (CCE). The difference between the two lies in the selection of the probability density function. The probability density function of the combined cross-entropy algorithm for combinatorial optimization problems is Berboulli distribution. Assuming that the probability of success is p, the probability density function of the CCE algorithm is:

f(x；p)＝p^x(1-p)^1-x(4)。f(x; p)=p ^x (1-p) ^1-x (4).

(4)式中，当x＝1时，f(x；p)＝p；当x＝0时，f(x；p)＝1-p。In formula (4), when x=1, f(x; p)=p; when x=0, f(x; p)=1-p.

CCE算法的步骤为：The steps of the CCE algorithm are:

第一步：设概率向量初始值为p₍₀₎(k为p₍₀₎的维数)，分位数系数ρ，样本数M，平滑系数α，迭代次数t＝0，终止参数b_tol。The first step: set the initial value of the probability vector p ₍₀₎ (k is the dimension of p ₍₀₎ ), the quantile coefficient ρ, the number of samples M, the smoothing coefficient α, the number of iterations t=0, and the termination parameter b _tol .

第二步：令t＝t+1，p_t-1以Bernoulli分布产生M×k的样本矩阵X_t＝[x_1(t),x_2(t),...,x_M(t)]^T，其中x_a(t)＝(x_a(t),1,x_a(t),2,...x_a(t),k)，1≤a≤M，M为随机样本的个数；k为每个随机样本向量的维数。The second step: Let t=t+1, p _t-1 generate M×k sample matrix X _t =[x _1(t) ,x _2(t) ,...,x _M(t) with Bernoulli distribution ] ^T , where x _a(t) = (x _a(t),1 ,x _a(t),2 ,...x _a(t),k ), 1≤a≤M, M is the random sample number; k is the dimension of each random sample vector.

第三步：求出目标函数矩阵S_(t)＝[S_1(t),S_2(t),...,S_M(t)]^T，将S_(t)进行排序(升序或降序)，排序后的矩阵记为并计算的(1-ρ)分位数，如式(5)所示：Step 3: Calculate the objective function matrix S _(t) = [S _1(t) ,S _2(t) ,...,S _M(t) ] ^T , sort S _(t) (in ascending order or descending order ), the sorted matrix is denoted as and calculate (1-ρ) quantile of , as shown in formula (5):

γ_(t)＝S_[(1-ρ)M](5)；γ _(t) = S _[(1-ρ)M] (5);

式中，γ_t为的(1-ρ)分位数；S为目标函数。In the formula, γ _t is The (1-ρ) quantile of ; S is the objective function.

第四步：利用(6)式更新参数p＝(p₁,...,p_k)；Step 4: update parameter p=(p ₁ ,...,p _k ) by formula (6);

${p p}_{j j} = = \frac{{Σ Σ}_{i i = = 11}^{M m} {I I}_{{{S S (({X x}_{i i})) \leq \leq γ γ}}} {X x}_{i i j j}}{{Σ Σ}_{i i = = 11}^{M m} {I I}_{{{S S (({X x}_{i i})) \leq \leq γ γ}}}},, ((j j = = 11,, 22,, ... ... k k)) - - - - - - ((66));;$

式中，I_{S(Xi)≤γ}为指示函数集合；X_ij表示样本矩阵的第i行第j个元素；p_j为更新参数p的第j个元素(j＝1,...,k)。In the formula, I _{S(Xi)≤γ} is a set of indicator functions; X _ij represents the jth element of the i-th row of the sample matrix; p _j is the jth element of the update parameter p (j=1,... ,k).

第五步：利用平滑参数α，对p_j处理，如(7)式所示；Step 5: Use the smoothing parameter α to process p _j , as shown in formula (7);

p_j(t)＝αp_j(t)+(1-α)p_j(t-1)(7)；p _j(t) = αp _j(t) +(1-α)p _j(t-1) (7);

式中，p_j(t)为第t次迭代后参数序列中的第j个元素(j＝1,...,k)。In the formula, p _j(t) is the jth element (j=1,...,k) in the parameter sequence after the tth iteration.

第六步：若相邻两次迭代产生的参数矩阵满足(8)式则停止迭代，否则从第二步开始重新迭代。Step 6: If the parameter matrix generated by two adjacent iterations satisfies the formula (8), then stop the iteration, otherwise start from the second step to iterate again.

max(|p_j(t)-p_j(t-1)|)＜b_tol(8)。max(|p _j(t) -p _j(t-1) |)<b _tol (8).

程序执行结束后输出最优解最优值γ^*＝S(X^*)＝z_min。Output the optimal solution after program execution Optimum value γ ^* = S(X ^* ) = z _min .

3、算例分析3. Case analysis

c＝3台相同的处理机和d＝9项作业，每项作业需要运行的时间t_m＝(81,40,26,4,65,98,53,71,15)，下面解决如何使9项作业在尽可能短的时间内由3台处理机完成的NP完全问题。设Y_nm为作业T_m分配到处理机H_n上所有的处理方案，则多处理机调度问题的数学模型又可表示为式(9)：c=3 identical processors and d=9 jobs, each job requires running time t _m =(81,40,26,4,65,98,53,71,15), how to make 9 An NP-complete problem in which a job can be completed by three processors in the shortest possible time. Let _Ynm be all the processing schemes assigned to the processor _Hn by the job _Tm , then the mathematical model of the multiprocessor scheduling problem can be expressed as formula (9):

$\begin{matrix} z z = = max max {{{Y Y}_{n no m m} \times \times {t t}_{m m}^{T T}}} \\ = = m m a a x x {{[\begin{matrix} {y the y}_{1111} & {y the y}_{1212} & ... ... & {y the y}_{1919} \\ {y the y}_{21 twenty one} & {y the y}_{22 twenty two} & ... ... & {y the y}_{2929} \\ {y the y}_{3131} & {y the y}_{3232} & ... ... & {y the y}_{3939} \end{matrix}] \times \times {[\begin{matrix} {t t}_{11} & {t t}_{22} & ... ... & {t t}_{99} \end{matrix}]}^{T T}}} \end{matrix}$

y_nm＝0,1(m＝1,2,...,9；n＝1,2,3)(9)。y _nm =0,1 (m=1,2,...,9; n=1,2,3) (9).

3.1多处理机调度问题的CCE算法3.1 CCE Algorithm for Multiprocessor Scheduling Problem

根据多处理机调度问题的数学模型可得CCE算法的目标函数(式(9)所示)为z，z中的变量y_nm的取值为0和1，因此y_nm服从Bernoulli分布，因此该算法可以解决多处理机调度问题。为了得到目标函数的最小值，利用CCE算法优化目标函数z，选取初始为p₍₀₎＝(0.5,0.5,...,0.5)(p₀的维数为k)，ρ＝0.85，M＝60，α＝0.9，b_tol＝1.0e-4。用Matlab对该问题编程，程序运行10次，结果如表1所示。According to the mathematical model of the multiprocessor scheduling problem, the objective function of the CCE algorithm (shown in formula (9)) is z, and the variable y _nm in z takes the values of 0 and 1, so y _nm obeys the Bernoulli distribution, so the Algorithms can solve multiprocessor scheduling problems. In order to obtain the minimum value of the objective function, the objective function z is optimized using the CCE algorithm, and the initial selection is p ₍₀₎ = (0.5,0.5,...,0.5) (the dimension of p ₀ is k), ρ = 0.85, M =60, α=0.9, b _tol =1.0e-4. Use Matlab to program this problem, run the program 10 times, and the results are shown in Table 1.

表1CCE算法10次运行结果Table 1 Results of 10 runs of CCE algorithm

次数frequency 运行时间(秒)run time (seconds) 得到最优解的迭代次数The number of iterations to get the optimal solution 最优解Optimal solution 11 0.0847180.084718 1212 162162 22 0.0848750.084875 1313 163163 33 0.0741490.074149 1111 158158 44 0.0798630.079863 1212 152152 55 0.0853060.085306 1414 151151 66 0.0821220.082122 1212 158158 77 0.0896650.089665 66 163163 88 0.0470690.047069 66 152152 99 0.0852450.085245 88 162162 1010 0.0794400.079440 1010 169169

由表1可得，计算结果平均在第10次收敛，选取10次计算结果中最好解，目标函数与迭代次数的关系如图1所示。It can be seen from Table 1 that the calculation results converge at the 10th time on average, and the best solution among the 10 calculation results is selected. The relationship between the objective function and the number of iterations is shown in Figure 1.

由图1可知CCE算法在第7次时已经寻找到了目标函数的最小值即最优值，z＝151，此时对应的最优解为 $y = [\begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}],$ 对应的调度方案为H₁(65,71,15)，H₂(98,53)，H₃(81,40,26,4)，调度时间为151。It can be seen from Figure 1 that the CCE algorithm has found the minimum value of the objective function, that is, the optimal value, at the seventh time, z=151, and the corresponding optimal solution at this time is $the y = [\begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}],$ The corresponding scheduling schemes are H ₁ (65,71,15), H ₂ (98,53), H ₃ (81,40,26,4), and the scheduling time is 151.

3.2算法比较分析3.2 Algorithm comparison analysis

本发明针对多处理机调度问题采用模拟退火算法和蚁群算法与CCE算法进行对比分析。模拟退火算法中起始温度20000度，终止温度1度，退火速度α＝0.95，最好解的测试结果如图2所示；蚁群算法中信息素持久性系数ρ＝0.8，信息素总量Q＝100，最好解的测试结果如图3所示。The invention adopts simulated annealing algorithm, ant colony algorithm and CCE algorithm for comparative analysis aiming at multi-processor scheduling problem. In the simulated annealing algorithm, the initial temperature is 20,000 degrees, the termination temperature is 1 degree, and the annealing speed α=0.95. The test results of the best solution are shown in Figure 2; the pheromone persistence coefficient ρ=0.8 in the ant colony algorithm Q=100, the test result of the best solution is shown in Figure 3.

将图2和图3与图1进行比较得三种算法都可以得到最优解151，但是各个算法的性能有较大差距。通过用模拟退火算法和蚁群算法对该问题进行多次测试得到表2。Comparing Figure 2 and Figure 3 with Figure 1, the three algorithms can all get the optimal solution 151, but the performance of each algorithm has a large gap. Table 2 is obtained by using simulated annealing algorithm and ant colony algorithm to test this problem several times.

表2三种算法结果比较Table 2 Comparison of the results of the three algorithms

综合以上三种算法对多处理机调度问题的测试结果得出CCE算法比模拟退火算法和蚁群算法具有运行时间短，收敛速度快，稳定性高的优点。Combining the test results of the above three algorithms on the multiprocessor scheduling problem, it is concluded that the CCE algorithm has the advantages of shorter running time, faster convergence speed and higher stability than simulated annealing algorithm and ant colony algorithm.

Claims

1. a method utilizing combined cross-entropy to realize multiprocessor scheduling is characterized in that the method steps are as follows:

Step 1: Construct the mathematical model of the multiprocessor scheduling problem, and establish the objective function and constraints;

Step 2: Use the combined cross-entropy algorithm to program and solve the objective function and constraint conditions established for the multiprocessor scheduling problem through Matlab, and obtain the optimal solution of the objective function.

2. the method utilizing combined type cross-entropy to realize multiprocessor scheduling according to claim 1, is characterized in that the mathematical model of described multiprocessor scheduling problem is as follows:

z z = = \underset{11 \leq \leq n no \leq \leq c c}{m m a a x x} {Σ Σ}_{m m = = 11}^{d d} {y the y}_{n no m m} {t t}_{m m}

\begin{matrix} s the s . . t t . . & {Σ Σ}_{n no = = 11}^{c c} {y the y}_{n no m m} = = 11 \end{matrix}

y _nm =0,1(m=1,2,...,d; n=1,2,...,c);

In the formula, z represents the time required to complete d tasks, that is, the objective function; y _nm =1 means that the task T _m is processed on the processor H _n ; Indicates the time when processor H _n completes work; t _m indicates the time when processor completes job T _m ; processor Indicates that the job T _m is completed on one processor, which is the constraint condition.

3. the method utilizing combined type cross-entropy to realize multiprocessor scheduling according to claim 1, is characterized in that the concrete steps of described step 2 are as follows:

The first step: set the initial value of the probability vector p ₍₀₎ , the quantile coefficient ρ, the number of samples M, the smoothing coefficient α, the number of iterations t=0, and the termination parameter b _tol ;

The second step: Let t=t+1, p _t-1 generate M×k sample matrix X _t =[x _1(t) ,x _2(t) ,...,x _M(t) with Bernoulli distribution ] ^T , where x _a(t) = (x _a(t),1 ,x _a(t),2 ,...x _a(t),k ), 1≤a≤M, M is the random sample number; k is the dimension of each random sample vector;

Step 3: Calculate the objective function matrix S _(t) = [S _1(t) ,S _2(t) ,...,S _M(t) ] ^T , sort S _(t) , and the sorted The matrix is denoted as and calculate The (1-ρ) quantile of:

γ _(t) = S _[(1-ρ)M] ;

In the formula, γ _t is The (1-ρ) quantile of ; S is the objective function;

Step 4: update the parameter p=(p ₁ ,...,p _k ) using the following formula:

{p p}_{j j} = = \frac{{Σ Σ}_{i i = = 11}^{M m} {I I}_{{{S S (({X x}_{i i})) \leq \leq γ γ}}} {X x}_{i i j j}}{{Σ Σ}_{i i = = 11}^{M m} {I I}_{{{S S (({X x}_{i i})) \leq \leq γ γ}}}},, ((j j = = 11,, 22,, ... ... k k));;

In the formula, is the set of indicator functions; X _ij represents the j-th element of the i-th row of the sample matrix; p _j is the j-th element of the update parameter p;

Step 5: Use the smoothing parameter α to process p _j :

p _j(t) = αp _j(t) +(1-α)p _j(t-1) ;

In the formula, p _j(t) is the jth element in the parameter sequence after the tth iteration, j=1,...,k;

Step 6: If the parameter matrix generated by two adjacent iterations satisfies the following formula, stop the iteration, otherwise start from the second step to iterate again;

max(|p _j(t) -p _j(t-1) |)<b _tol ;

After the execution of the program, the optimal solution X ^* is output, and the optimal value γ ^* = S(X ^* ) = z _min .