1、 本 科 毕 业 论 文 多机调度问题 算法设计 Algorithm Design of Multi-machine scheduling problem 姓 名： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 学 号： 指导教师： 年 月 厦门大学本科毕业论文 多机调度问题算法设计 1 摘 要 众所周知，算法分析在当前软件领域发挥越来越大的作用，多机调度问题更是在管理和自动化方面起着不可或缺的作用。然而，手工管理方式在安全性、时效性等方面存在诸多弊端。开发 多机调度问题的算法，研究在各种情况下对此问题解决的最佳方式成为当前的当务之急。 现有解决多机调度问题的算法有三种，贪心法，
2、模拟退火算法和蚁群算法， 本文找出一个经典多级调度问题例子，利用贪心法，模拟退火算法，蚁群算法分别求解，比较过程和结果，最终 验证贪心法虽然简便但是 很死板，模拟退火可以找到最优解但是需花费很多时间，蚁群算法省时省力也可以找到最优解，详细剖析了三种算法的实用性， 并尝试提出思路， 贪心法可尝试每台机器单独分配。可利用蚁群思路，反其道而行之，先找最差解早找对立面。 关键词： 多机调度； 模拟退火；蚁 群算法 厦门大学本科毕业论文 多机调度问题算法设计 2 Abstract As is well known, algorithm Analysis is currently playing a ro
3、le 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 im
4、mediate 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 mult
5、i-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 opt
6、imal 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 ca
7、n 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 厦门大学本科毕业论文 多机调度问题算法设计 3 目 录 第一章 引言 . 1 1.1 算法概念 . 1 1.2 算法 特性 .
8、 1 1.3 算法 描述 . 2 1.4 算法 作用 . 2 第二章 常见的算法设计方法 . 3 2.1 贪心法 . 3 2.2 动态规划 . 3 2.3 回溯法 . 4 2.4 分治法 . 5 2.5 递归法 . 5 2.6 粒子群算法 . 6 2.7 模拟退火算法 . 7 2.8 蚁群算法 . 8 2.9 并行算法 . 9 第三章 多机调度问题算法设计 . 11 3.1 多机调度问题描述 . 11 3.2 贪心法求解多机调度问题 . 11 3.3 蚁群算法多机调度问题 . 15 3.4 混合遗传模拟退火算法解决多机调度问题 . 15 3.5 算法分析与比较 . 15 3.6 实例 分析 .
9、 21 第 四 章 总结 . 23 致谢 . 23 参考文献 . 24 厦门大学本科毕业论文 多机调度问题算法设计 4 Content Chapter 1 Introduction. 1 1.1 The Concept of Algorithm Analysis. 1 1.2 The Characteristic of Algorithm Analysis. 1 1.3 The Description of Algorithm Analysis . 2 1.4 The Role of Algorithm Analysis . 2 Chapter 2 General Methods of Alg
10、orithm Analysis Design . 3 2.1 Greedy Method . 3 2.2 Dynamic Programming . 4 2.3 Backtracking . 5 2.4 Divide-and-Conquer. 5 2.5 Recursive Method . 5 2.6 Particle Swarm Optimization . 7 2.7 Simulated Annealing . 8 2.8 Ant Colony Algorithm. 9 2.9 Parallel Algorithm . 9 Chapter 3 The Algorithm Analysis
11、 Design about the Multi-machine .11 3.1 State of the Multi-machine Scheduling Problem .11 3.2 Solving Multi-machine Scheduling Problem by Greedy Method.11 3.3 The Research of Parallel on Particle Swarm Optimization. 15 3.4 On Mixed Genetic Simulated Annealing Algorithm. 15 3.5 Algorithm Analysis . 1
12、5 3.6 Instance . 21 Chapter 4 Conclusion . 23 Acknowledgements . 23 References . 24 厦门大学本科毕业论文 多机调度问题算法设计 1 第一章 引言 1.1 算法概念 算法 是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法 +数据结构 =程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和
13、程序之间存在密切的关系。 算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定 一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。 算法中包括大概五个方面的内容，首先设计算法，算法的设计工作是不能完全自动化的，需要先了解一些已经被实践证明的基本算法，然后加以应用，然后是表示算法，需要用自然语言或者算法预言，再就是确认算法，是人们确信这一算法能够正确无误的工作，紧接着分析这个算法，对这个算法需要的时间和存储空间做出计算，判断算法在什么环境中可以有效运行，最后验证算法，需要详细测试。 1.2 算法的特性 确定性。算法的每一种运算必
14、须有确定的意义，该种运算应执行何 种动作应无二义性，目的明确； 能行性。要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成； 输入。一个算法有 0 个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象集合； 输出。作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的量； 厦门大学本科毕业论文 多机调度问题算法设计 2 有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。 满足前四个特性的一组规则不能称为算法，只能称为计算过程，操作系统是计算过程的一个例子，操作系统用来 管理计算机资源，控制作业
15、的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。 1.3 算法的描述 (1) 自然语言 ； (2) 图形，如 图、流程图，图的描述与算法语言的描述对应； (3) 算法语言，即计算机语言、程序设计语言、伪代码； (4) 形式语言，用数学的方法，可以避免自然语言的二义性。 (5) 用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。 1.4 算法的作用 算法在程序开发应用中能起到很大的作用，首先可以使程序开发逻辑清晰，使需求分析以及软件的框架变的 简便易懂。然后在一些典型的问题框架上，比如：线性规划问题，路径最短问题等等，可以很方便的调用算法
16、迅速解决，节省人力物力，对软件开发起到非常大的作用。 厦门大学本科毕业论文 多机调度问题算法设计 3 第二章 常见的算法设计方法 2.1 贪心法 贪心法 (Greedy algorithm)是一种在每一步选择中都采取在当前状态下最好 /优的选择，从而希望导致结果是最好 /优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市， 那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择，不能
17、回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。 贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助 算法或者直接解决一些要求结果不特别精确的问题。 2.2 动态规划 动态规划的理论基础是最优化原理和嵌入原理。 最优化原理：一个最优策略，具有如下性质：不论初始状态和初始决策（第一步决策）如何，以第一步决策所形成的阶段和状态作为初始条件来考虑时，余下的
18、决策对余下的问题而言也必构成最优策略。最优化原理体现了动态规划方法的基本思想。 嵌入原理：一个具有已知初始状态和固定步数的过程总可以看作是初始状态和步数均不确定的一族过程中的一个特殊情况。这种把所研究的过程嵌入一个过程族的原理称为嵌入原理。 通过研究过程族的最优策略族的共同性质得出一般通解，此通解自然也适用于原来的特殊问题。动态规划的基本方法就是根据嵌入原理把一个多步决策问题化为一系列较简单的一步决策问题，可显著降低数学处理上的难度。 厦门大学本科毕业论文 多机调度问题算法设计 4 特点和应用范围：若多阶段决策过程为连续型，则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题
19、归结为多阶段决策过程，用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用。但动态规划还缺少严格的逻辑基础。 60 年代，沃尔昌斯基对动态规划方法作了数学论证。动态规划方法 有五个特点：在策略变量较多时，与策略穷举法相比可降低维数；在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；对于不能用解析形式表达的函数 ,可给出递推关系求数值解 ;动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新
20、、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。 2.3 回 溯法 回溯法可称为通用的解题法。回溯是一个带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索一个问题的所有解或任意解。 对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大 提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些 不可能的解，这
21、样就不 必继续把解的剩余部分列出从而节省部分时间。 1.它在包含问题的所有解的空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索 2.回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都要被搜索遍才结束。而回溯法在用来求问题的任意解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解算法适用于解一些组 合数较大的问题。 3.回溯法对解空间做深度优化搜索，因此，在一般情况下
22、用递归法实现回溯法。 (代码） 厦门大学本科毕业论文 多机调度问题算法设计 5 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) 2.4 分治法 1、 分治法的基本思想 2、 任何一个可以用计算机求解的问题所需的计算时间都与其规模 N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于 n个元素的排序问题，当 n=1时，不需任何计算； n=2 时，只要作一次比较即可排好序； n=3 时只要作 3 次比较即可，。而当 n 较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 3、 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治 之。 4、 分治法的适用条件 。 分治法所能解决的问题一般具有以下几个特征： （ 1） 该问题的规模缩小到一定的程度就可以容易地解决； （ 2） 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （ 3）利用该问题分解出的子问题的解可以合并为该问题的解； 2.5 递归法 递归是设计和描述算法的一种有力的工具，在复杂算法的描述中被经常采用 。
