多机调度问题算法设计-毕业论文

本 科 毕 业 论 文多机调度问题算法设计Algorithm Design of Multi-machine scheduling problem姓 名：学 院：软件学院系：软件工程专 业：软件工程年 级： 学 号：指导教师： 年 月厦门大学本科毕业论文 多机调度问题算法设计摘 要众所周知，算法分析在当前软件领域发挥越来越大的作用，多机调度问题更是在管理和自动化方面起着不可或缺的作用。然而，手工管理方式在安全性、时效性等方面存在诸多弊端。开发多机调度问题的算法，研究在各种情况下对此问题解决的最佳方式成为当前的当务之急。现有解决多机调度问题的算法有三种，贪心法，模拟退火算法和蚁群算法，本文找出一个经典多级调度问题例子，利用贪心法，模拟退火算法，蚁群算法分别求解，比较过程和结果，最终验证贪心法虽然简便但是很死板，模拟退火可以找到最优解但是需花费很多时间，蚁群算法省时省力也可以找到最优解，详细剖析了三种算法的实用性，并尝试提出思路，贪心法可尝试每台机器单独分配。可利用蚁群思路，反其道而行之，先找最差解早找对立面。关键词：多机调度；模拟退火；蚁群算法Abstract As is well known, algorithm Analysis is currently playing a role which becomes more and more important. Furthermore, the Multi-machine Scheduling problem is indispensable to the aspects of management and automation. The mode of manual administration has a good many of disadvantages in the terms of security and timeliness. As a result, it has been one of the immediate concern to figure out what is the best way to solve the problem considering every condition.There are three algorithms to settle multi-machine scheduling problem the greedy algorithm, the simulated annealing algorithm and the ant colony algorithm. This article find a classic example of multi-level scheduling problem,which is respectively solving by greedy method, simulated annealing algorithm,and ant colony algorithm.After that,compare the process and the results. From sevaral examples, we can see that, the greedy algorithm is simple but rigid, the simulated annealing can find the optimal solution but have to spend a lot of time, whilt the ant colony algorithm can save time to find the optimal solution. This passage compare the practicalities of those three algorithms and try to find new creative ideas. It can try to assign every machine separately using Greedy algorithm., It can use Ant Colony Optimization to find out the worst answer to ultimately establish the opposite one as the old saying going,to do exactly the opposite.Keywords: Multi-machine Scheduling; Simulated Annealing; Particle Swarm Optimization目 录 第一章 引言11.1 算法概念11.2 算法特性11.3 算法描述21.4 算法作用2第二章 常见的算法设计方法32.1 贪心法32.2 动态规划32.3 回溯法42.4 分治法52.5 递归法52.6 粒子群算法62.7 模拟退火算法72.8 蚁群算法82.9 并行算法9第三章 多机调度问题算法设计113.1多机调度问题描述113.2 贪心法求解多机调度问题113.3 蚁群算法多机调度问题153.4 混合遗传模拟退火算法解决多机调度问题163.5 算法分析与比较173.6 实例分析21第四章 总结23致谢24参考文献25ContentChapter 1 Introduction11.1 The Concept of Algorithm Analysis11.2 The Characteristic of Algorithm Analysis11.3 The Description of Algorithm Analysis21.4 The Role of Algorithm Analysis2Chapter 2 General Methods of Algorithm Analysis Design32.1 Greedy Method32.2 Dynamic Programming42.3 Backtracking52.4 Divide-and-Conquer52.5 Recursive Method52.6 Particle Swarm Optimization72.7 Simulated Annealing82.8 Ant Colony Algorithm82.9 Parallel Algorithm9Chapter 3 The Algorithm Analysis Design about the Multi-machine113.1 State of the Multi-machine Scheduling Problem113.2 Solving Multi-machine Scheduling Problem by Greedy Method113.3 The Research of Parallel on Particle Swarm Optimization153.4 On Mixed Genetic Simulated Annealing Algorithm163.5 Algorithm Analysis173.6 Instance21Chapter 4 Conclusion23Acknowledgements24References2524第一章 引言1.1 算法概念算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。算法中包括大概五个方面的内容，首先设计算法，算法的设计工作是不能完全自动化的，需要先了解一些已经被实践证明的基本算法，然后加以应用，然后是表示算法，需要用自然语言或者算法预言，再就是确认算法，是人们确信这一算法能够正确无误的工作，紧接着分析这个算法，对这个算法需要的时间和存储空间做出计算，判断算法在什么环境中可以有效运行，最后验证算法，需要详细测试。1.2 算法的特性 确定性。算法的每一种运算必须有确定的意义，该种运算应执行何种动作应无二义性，目的明确； 能行性。要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成； 输入。一个算法有0个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象集合； 输出。作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的量； 有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。 满足前四个特性的一组规则不能称为算法，只能称为计算过程，操作系统是计算过程的一个例子，操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。1.3 算法的描述(1) 自然语言；(2) 图形，如NS图、流程图，图的描述与算法语言的描述对应；(3) 算法语言，即计算机语言、程序设计语言、伪代码；(4) 形式语言，用数学的方法，可以避免自然语言的二义性。(5) 用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。1.4 算法的作用 算法在程序开发应用中能起到很大的作用，首先可以使程序开发逻辑清晰，使需求分析以及软件的框架变的简便易懂。然后在一些典型的问题框架上，比如：线性规划问题，路径最短问题等等，可以很方便的调用算法迅速解决，节省人力物力，对软件开发起到非常大的作用。 第二章 常见的算法设计方法2.1 贪心法 贪心法(Greedy algorithm)是一种在每一步选择中都采取在当前状态下最好/优的选择，从而希望导致结果是最好/优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市， 那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。2.2 动态规划 动态规划的理论基础是最优化原理和嵌入原理。 最优化原理：一个最优策略，具有如下性质：不论初始状态和初始决策（第一步决策）如何，以第一步决策所形成的阶段和状态作为初始条件来考虑时，余下的决策对余下的问题而言也必构成最优策略。最优化原理体现了动态规划方法的基本思想。 嵌入原理：一个具有已知初始状态和固定步数的过程总可以看作是初始状态和步数均不确定的一族过程中的一个特殊情况。这种把所研究的过程嵌入一个过程族的原理称为嵌入原理。通过研究过程族的最优策略族的共同性质得出一般通解，此通解自然也适用于原来的特殊问题。动态规划的基本方法就是根据嵌入原理把一个多步决策问题化为一系列较简单的一步决策问题，可显著降低数学处理上的难度。 特点和应用范围：若多阶段决策过程为连续型，则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程，用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用。但动态规划还缺少严格的逻辑基础。60年代，沃尔昌斯基对动态规划方法作了数学论证。动态规划方法有五个特点：在策略变量较多时，与策略穷举法相比可降低维数；在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；对于不能用解析形式表达的函数,可给出递推关系求数值解;动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。2.3 回溯法 回溯法可称为通用的解题法。回溯是一个带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索一个问题的所有解或任意解。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大 提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些 不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。1. 它在包含问题的所有解的空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索2. 回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都要被搜索遍才结束。而回溯法在用来求问题的任意解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解算法适用于解一些组合数较大的问题。3. 回溯法对解空间做深度优化搜索，因此，在一般情况下用递归法实现回溯法。(代码） Void backtrack（int t） If(tn) output(x); else for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if(constraint(t)&bound(t)backtrack(t+1); 2.4 分治法1、 分治法的基本思想 2、 任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 3、 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 4、 分治法的适用条件。分治法所能解决的问题一般具有以下几个特征：（1） 该问题的规模缩小到一定的程度就可以容易地解决；（2） 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解；2.5 递归法 递归是设计和描述算法的一种有力的工具，在复杂算法的描述中被经常采用。 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。2.6 粒子群算法 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度. 爬山法精度较高,但是易于陷入局部极小. 遗传算法属于进化算法( Evolutionary Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995 年Eberhart 博士和kennedy 博士提出了一种新的算法;粒子群优化(Particle Swarm Optimization -PSO) 算法 . 这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。粒子群优化(Particle Swarm Optimization - PSO) 算法是近年来发展起来的一种新的进化算法( Evolutionary Algorithm - EA) .PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质. 但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作. 它通过追随当前搜索到的最优值来寻找全局最优 。粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，由Eberhart博士和kennedy博士提出。源于对鸟群捕食的行为研究 。PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域大多数演化计算技术都是用同样的过程：1. 种群随机初始化 2. 对种群内的每一个个体计算适应值(fitness value).适应值与最优解的距离直接有关 3. 种群根据适应值进行复制 4. 如果终止条件满足的话，就停止，否则转步骤2 从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解 。但是，PSO 没有遗传操作如交叉(crossover)和变异(mutation). 而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。 与遗传算法比较, PSO 的信息共享机制是很不同的. 在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子，这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。2.7 模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。【1】根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。模拟退火的基本思想: (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L (2) 对k=1，L做第(3)至第6步： (3) 产生新解S (4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数 (5) 若t0，然后转第2步。2.8 蚁群算法蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。通过建立适当的数学模型，基于故障过电流的配电网故障定位变为一种非线性全局寻优问题。2.9 并行算法并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。实际上，在自然界中并行是客观存在的普遍现象，关键问题在于能不能很好的利用。由于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性，同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。并行算法的研究历史可简单归纳为：上世纪70到80年代，并行算法研究处于高潮；到上世纪90年代跌入低谷；目前，又处于研究的热点阶段。现在，人们已经可以自己搭建PC cluster，利用学习到的理论知识来解决实际问题，不再是纸上谈兵，这也为我们提供了新的机遇和挑战。并行算法的研究内容：(1) 并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。【2】 (2) 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。 以上是并行算法的常规研究内容。随着时代的进步，我们需要不断调整研究方向。目前并行算法研究的新走向是：并行算法研究内容不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模式，如神经计算、量子计算等，这些模式能够解决某类特定问题，有其自身的优越性。 第三章 多机调度问题算法设计3.1多机调度问题描述 多机调度问题是生产管理与控制的一个基本问题。按照加工设备数量和加工作业的流动方式，一般可分为单机调度、并行机调度、Flowshop调度、可重入式调度和Jobshop调度等多种类型。作业调度中的许多问题，不仅具有随机性、约束复杂、规模大及多目标冲突等特点，而且许多都属于NP完全问题，即使在单机情形也是如此。因此，如何寻求有效可行的调度求解方案，一直是生产管理与控制研究的热点和难点。3.2 贪心法求解多机调度问题1提出问题经常遇到这样的问题，设有n个独立的作业1，2，n，由m台相同的机器进行加工处理。作业1所需的处理时间为t。现约定，每个作业均可在任何一台机器加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使n个作业在尽可能短的时间内由m台机器加工处理完成。2解决方法作业的个数为n，机器的数目为mA：n m设7个独立的作业（1，2，3，4，5，6，7）由3台机器M1，M2和M3加工处理，个作业所需的处理时间分别为（2，14，4，16，6，5，3）。这里给出3种解决的方法：（1） 如果将作业平均分配给每个机器，总共所需的时间为22。这种算法的优点是比较简单，容易想到。缺点是没有考虑节省时间，机器所运行的作业完全由作业的次序决定，当运行时间比较大的作业集中在一起时，会把他们分配给同一个机器，这样所用的时间比较长，效率比较低，如表3.1所示。表3.1 所有机器作业所需时间（2） 作业按从小到大依次分配给空闲的机器时间为：2，7，23。这种算法也容易想到，事先也比较方便，同时也考虑到时间的安排，比第一种算法有了改进。但是运行时间最长的作业一定是最后完成的，如果运行最长作业前，其他机器运行时间差不多就会造成其他几个机器等待一个机器的状况，这样机器的运行效率比较低。如表3.2所示.表3.2 各机器作业量及总时间（3） 经过上面两种算法的思考，就会想到把作业按从大到小一次分配给空闲的机器。当n m时，首先将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。如图3.3所示按Greedy算法产生的作业调度如图。所需要的加工时间为17。图3.3 最大优先算法图示（最优）时间长为6，11，15，17.这种算法很明显首先挑选了处理时间比较长的作业，这正是贪心算法的特点，总是做出在当前看来最好的选择，也就是说贪心算法并不从整体左右考虑，他所作出的选择只是在某种意义上局部最优的选择。/如果希望增加作业，请增加aN数组中的元素，以及N对应的数值：比如，7个作业，对应N就是7；/如果希望增加机器，修改M的数值即可#include #include #include using namespace std;#define N 7#define M 3typedef struct jobint ID;int time;Job;typedef struct machineint ID;int avail;Machine;Job aN=1,2,2,14,3,4,4,16,5,6,6,5,7,3;/原始作业数据，vectorm_vec_job;vectorm_vec_machine;bool UDgreater(Job elem1,Job elem2)return elem1.timeelem2.time;bool UDless(Machine elem1,Machine elem2)return elem1.availN)cout给每个任务分配一台机器即可endl;for (int i=0;iN;i+)m_vec_job.push_back(ai);sort(m_vec_job.begin(),m_vec_job.end(),UDgreater);/作业按时间长度排序完毕/coutm_vec_job0.IDendl;/作业是按照时间从大到小排列的for (i=0;iM;i+)Machine tmp=i+1,0;/机器的编号是从1开始的m_vec_machine.push_back(tmp);for(i=0;iN;i+)vector:iterator it;it = min_element(m_vec_machine.begin(),m_vec_machine.end(),UDless);cout将机器(*it).ID从(*it).avail到(*it).avail+ m_vec_jobi.time的时间段分配给作业m_vec_jobi.ID 规定的循环次数，记录当前蚂蚁的位置（当前的解）。停止运行，输出最好的解；否则转（2）。3.4 混合遗传模拟退火算法解决多机调度问题 1算法分析 自Davis首次将遗传算法（Genetic Algorithms，GA）引入到调度问题的研究中以来，进化算法（包括遗传算法）在制造生产零件和生产调度研究领域获得了广泛的应用，并取得了较好的优化效果。遗传算法用于求解某些并行多机调度问题也有不少的研究成果。遗传算法的优点是：不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在和单峰的假设，并且具有内在的并行性，收敛速度快，能够解决非常困难的寻优问题。当然，传统的遗传算法也有许多缺点，其中最为严重的是“过早收敛”问题。所谓“过早收敛”是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷入局部，达不到全局最优解的现象。遗传算法的另一个缺陷是“GA欺骗”问题，即在GA的搜索过程中，有可能搜索到最优解然后又发散出去的现象。另外，遗传算法还有参数选择未能定量和不能精确定位最优解等缺陷。【3】模拟退火算法（Simulated Annealing，SA）又称为模拟冷却法、统计冷却法、MonteCarlo退火法、随机松弛法和概率爬山法等。模拟退火算法是一种新的统计优化方法，其思想最早是由NMetropolis等人借鉴统计力学中物质退火方法而提出的。1983年Kirkpatrick等人开展了一些富有成效的工作，成功地将该思想引入组合优化理论。模拟退火算法源于对固体退火过程的模拟，采用Meteropolis接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火算法的主要优点之一就是能以一定的概率接收目标函数值不太好的状态。即算法不但往好的方向走也可向差的方向走；这使得算法即便落入局部最优的陷阱中，理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与求解时间长短之间的矛盾。为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大时，缺乏可行的解决途径。 2多机调度问题的混合遗传模拟退火算法 从测试结果来看，混合遗传模拟退火算法在搜优率上较遗传算法和模拟退伙算法有了较大的提高。从运算过程中的数据可以看出，由于混合遗传模拟退火算法中邻域的选择、变异发生的概率都取自模拟退火的接受概率，再加上它采取了适应度拉伸系数，使得遗传算法的“早熟”现象得到很好的解决。另外本文所采用的混合遗传模拟算法的还具有以下优点：优化行为的增强。它具有GA算法的优化时间性能和SA算法可以最终趋于全局最优的优点，克服了GA算法“过早收敛”问题和SA算法优化时间性能较差的缺点。优化效率的提高。它是一种并行而且具有自动保优功能的算法，同时利用GA和SA各自不同的邻域搜索结构相结合，这样使得算法在解空间中的搜索能力所增强，优化效率得到提高。鲁棒性的提高。它的多点搜索消弱了SA算法对初值的依赖性，同时它还利用GA算法不影响平稳分布的特性，提高了整个算法的鲁棒性。【4】遗传算法和模拟退火两种算法均属于基于概率分布机制的优化算法。遗传算法是通过概率意义下的“优胜劣汰”思想的群体遗传操作实现优化；模拟退火算法的优化机制是通过赋予搜索过程一种时变和最终趋于零的概率突变性，来避免陷入局部极小而达到全局最优。结合这两种算法的优缺点，将模拟退火的思想引入遗传算法，将模拟退火的接受概率应用于种群的选取以及变异操作，并采用适应值拉伸的方法，极大地缓解了遗传算法的选择压力。它不但丰富和优化了整个过程，而且增强了全局和局部意义下的搜索能力和效率。【5】从一些试验结果可以看出，混合遗传模拟退火算法在解决多机任务调度问题时较单一的遗传算法、模拟退火算法在优化行为与效率上有了很大的提高。3.5 算法分析与比较 现在通过一个实例来比较各种算法的优劣。多机调度的最经典问题，n台相同的处理机P1，P2，Pn，处理m个独立的作业A1，A2，Am，以互不相关的方式工作，任何作业可以在任何处理机上运行，未完成的作业不允许中断。作业也不能拆分成更小的子作业，调度的任务是给出一种作业调度方案，使m个作业尽可能短的时间内由这n台相同的处理机完成。1贪心法作业的个数为n，机器的数目为m （1）A：n m首先将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。图3.4 贪心法多机分配运行结果 2模拟退火算法（1） 给定起，止温度T，T0和退火速度c，处理及数目n，作业数目m，随机给出一个调度方案X0 = （Xia)n*m，计算完工时间f0；（2） 若TT0，转（3），否则算法停止，输出X0；（3） 随机产生作业a和处理机i，令Xki = 0（k = 1，2，n，ki），Xia = 1，此时变量记为X1；（4） 计算完工时间f1，E = f1 - f0，若Erand（0，1），也接受新值，X0X1，TcT，转（2）；否则转（3）。图3.5 模拟退火的计算过程和结果 3蚁群算法人们经过大量研究发现，蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。【6】在作业Ai（i=1，2，m）处分别设置1个蚂蚁，作业分配给处理机A，蚂蚁就在处理机A上留下外激素，设ra（a=1，2，n）表示处理机a的总的外激素，每个蚂蚁选择处理机a概率为；Pa = ra / ra ，ma = 1更新方程为；ra(new) = *ra（old) + Q/FF为此次分配后完工时间，表示强度的持久性系数，一般取0.5到0.9左右，Q为一正常数。解多机调度问题的蚁群算法如下：（4） nc0（nc为循环次数），给ra（a=1，2，n）赋相同的数值，给出Q，的值，随机给出一个调度方案；（5） 对每个蚂蚁按转移概率Pa选择下一个节点，计算本次分配完工时间F，按更新方程修信息强度；（6） 比较这次循环的结果，若目标函数F有改进，保留当前解为最好解，否则，外激素量采用上次最好解时的外激素量，ncnc + 1；（7） 若nc 规定的循环次数，记录当前蚂蚁的位置（当前的解）。停止运行，输出最好的解；否则转（2）。图3.6 蚁群算法的计算过程 3.6 实例分析通过实例进行算法比较分析贪心法的思路是先将作业按运行时间的长短从大到小排成非递增序，然后给空闲的处理机依次分配作业。假设有3台处理机和9个作业，运行时间分别为81，40，26，4，65，98，53，71，15.按贪心法，调度结果为P1（87，40，4），P2（81，53