算法设计与分析资料报告资料报告材料课程大作业.doc

《算法设计与分析资料报告资料报告材料课程大作业.doc》由会员分享，可在线阅读，更多相关《算法设计与分析资料报告资料报告材料课程大作业.doc（17页珍藏版）》请在课桌文档上搜索。

1、题 目：作业调度问题与算法分析目录算法设计与分析课程大作业1一动态规划算法解决流水作业调度31、问题描述32、算法分析33. 算法的描述44、局部算法实现55. 运行结果66、时空效率分析6二贪心算法解多机调度问题61、问题描述62、算法分析73.局部算法实现74.计算复杂性分析85. 运行结果9三回溯法解决批作业调度问题91.问题描述92.算法思想103. 局部算法实现114.运行结果125.时间复杂性分析12四作业调度算法比拟12五课程学习总结13摘要：在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这

2、是一项复杂的工作本文就作业调度排序问题进展了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度与性能分析。关键词：作业调度；动态规划；贪心算法；回溯法；一动态规划算法解决流水作业调度1、问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进展下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设作业i在机器j上需要的处理时间为ti,j。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。2、算法分析 直观上，一个最优调度应使机器M1没有空

3、闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。由流水作业调度问题的最优子结构性质可知，12 从公式1可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进展试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。将问题规模缩小。 公式2说明一般情况下，对作业集S进展调度，在M2机器上的等待时间，除了需要等该部件在

4、M1机器上完成时间，还要冲抵一局部原来的等待时间，如果冲抵已成负值，自然仍需等待M1将作业做完，所以公式取maxt-ai,0。3. 算法的描述 从分析可知，流水作业调度问题一定存在满足Johnson法如此的最优调度，且容易由下面的算法确定。流水作业调度问题的Johnson算法：1令；2将中作业依的非减序排列；将中作业依的非增序排列；作业接种作业构成满足Johnson法如此的最优调度。4、局部算法实现int FlowShop(int n,int a,int b,int c)int i;Jobtype *d = new Jobtypen;for( i=0; ibi?bi:ai;/按Johnson法

5、如此分别取对应的bi或ai值作为关键字di.job = ai=bi;/给符合条件aibi的放入到N1子集标记为truedi.index = i; BubbleSort(d,n);/对数组d按关键字升序进展排序 int j = 0,k = n-1; for( i=0; in; i+)if(di.job)cj+ = di.index;/将排过序的数组d，取其中作业序号属于N1的从前面进入elseck- = di.index;/属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序 j = ac0;k = j+bc0;for( i=1; in; i+)j += aci;/M1在执行ci作业

6、的同时，M2在执行ci-1号作业，最短执行时间取决于M1与M2谁后执行完k = jk?k+bci:j+bci;/计算最优加工时间delete d;return k;5. 运行结果6、时空效率分析 算法Flowshop的主要计算时间花在对作业集的排序上。在这里，我们使用冒泡排序法(BubbleSort)，因此，在最坏情况下算法FlowJob所需要的计算时间为。所需要的空闲显然是。二贪心算法解多机调度问题1、问题描述 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小

7、的子作业。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。2、算法分析 贪心算法只需按顺序以数组方式提供各作业的加工时间和机器的台数；求出作业的个数，假设小于机器台数，就将作业逐个分配给就近的机器，所需要的加工时间，即为最长作业所需时间。 假设作业数大于机器台数，将作业按加工时间的多少降序排序，以机器数建立最小堆，先将前m个作业分配给m个机器，最小堆顶是最小的元素即m个作业中加工时间最少的作业，将其移出并加上后续作业的加工时间，再插入堆，这时会改变原来的状态，升到堆顶的机器加工总时间最少，它再移出加后续作业的加工时间，在插入堆，依

8、此类推，直到全部作业完毕。堆中的最大值就是完成所有作业所需的最短时间。3.局部算法实现 typedef struct Node int ID, avail;manode; /ID 机器编号 avail 每次作业的初始时间 manode machineN; jobnode jobN; /* 找出下个作业执行机器 */ manode* Find_min(manode a, int m) manode* temp = &a0; for (int i = 1; im; i+) if (ai.availavail) temp = &ai; return temp; /* 对作业时间由大到小进展排序 */

9、 void Sort(jobnode t, int n) jobnode temp; for (int i = 0; ii; j-) if (jobj.timejobj - 1.time) temp = jobj; jobj = jobj - 1; jobj - 1 = temp; void main() for (i = 0; ijobi.time; jobi.ID = i + 1; printf(输入机器数目(机器编号按输入顺序处理)n); cinm; for (i = 0; im; i+)/给机器进展编号并初始化 machinei.ID = i + 1; machinei.avail =

10、 0; putchar(n); if (n = m) printf(为每个作业分配一台机器,可完成任务!n); return; Sort(job, n); for (i = 0; i %d 的时间段分配给作业: %dn, putchar(n); printf(该批作业处理完成所需加工时间为: %dn, temp); 4.计算复杂性分析当nm 时，所有作业可以一次安排给各机器，算法greedy需要o(1) 时间。当nm 时，排序耗时O(nlogn)。初始化堆需要O(m) 时间。关于堆的removeMin和put运算共耗时O(nlogm),因此算法greedy 所需的计算时间为O(nlogn+nl

11、ogm)=O(nlogn)。5. 运行结果三回溯法解决批作业调度问题 输入：1. 任务数N2. 机器数M3. 随机序列长度ti,其中ti=x表示第i个任务完成需要时间单位x，输出：1. 开销时间besttime，表示最优调度需要时间单位2. 最优调度序列bestx，其中bestxi=x，表示将第i个任务分配给第x个机器执行。解空间的表示：一个深度为N的M叉树。ti:第i个任务的时间xi=j:当前输出结果Resi=j:表示第i个任务要运行在第j台机器上time_machinei:第i个机器上的运行时间根本思路： 1、搜索从开始结点根结点出发，以DFS搜索整个解空间。2、每搜索完一条路径如此记录下

12、time_min和Resi序列，开始结点就成为一个活结点， 同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点， 并成为一个新的活结点，也成为当前扩展结点。 3、如果在当前的扩展结点处不能再向纵深方向扩展，如此当前扩展结点就成为死结点。此时，应往回移动回溯至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。3. 局部算法实现bool placetest(int k)int time_max_K = time_machine1;for(int i=2;i time_max_K )time_max_K = time_machinei;if(time_m

13、ax_K time_min)return false;elsereturn true; void Backtrack(int k,int t,int x) if(k N )int time_max_K = time_machine1;for(int i=2;i time_max_K )time_max_K = time_machinei;if(time_max_Ktime_min)time_min = time_max_K;for(int i=1;i=N;i+)Resi = xielsefor(int i=1;i=K;i+)xk = i;/将第k个任务放到第i个机器上面if( placetes

14、t(k) )time_machinei += tk;Backtrack(k+1,t,x);time_machinei -= tk;由于没有使用限界函数进展优化，算法时间和空间复杂度呈指数级增长。所以该算法不适合较大规模的计算。蓝线表示机器数一定M=3时，n增大时求解最优调度对所消耗的时间，该趋势随着指数增加。四作业调度算法比拟在流水作业调度中，Johnson算法这是在只有两台设备情况下的最优排序算法，同时说明工件的第一道工序和最后一道工序的加工时间对排序的影响是主要的。 贪心算法只需按顺序以数组方式提供各作业的加工时间和机器的台数；求出作业的个数，假设小于机器台数，就将作业逐个分配给就近的机器

15、，所需要的加工时间，即为最长作业所需时间复杂度为O(nlogn)。 回溯算法解决批作业调度问题与前面两个问题不同，前两个是求所有作业在M2机器上加工完成的最后时间，而这里要求的是求所有作业在机器M2上完成处理时间的总和达到最小。这种调度算法可用于计算加工费用。批处理作业调度问题属于排列树的解空间问题，因此时间复杂度为(n!) 五课程学习总结算法分析与设计是一门非常重要的课程，很多问题的解决，程序的编写都要依赖它，算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。但是算法的学习同时也需要较强的理解能力，有些算法程序不易读懂，这时需要在理解问题的本质上对算法程序进展解读。在对一个问题进展算法设计时，要了解问题的特点，找到适合的方法才能得到理想的结果。 在本门课程过程中， 我深刻体会到算法是建立在解法根底之上的，是在某个具体问题解法过程的分析之后，归纳出的解决一类相关问题的程序或步骤；如果一个具体问题具有代表性，其解法又具有程序性，那么这样的解法也能表现算法思想在学习过程中教师起到了极大的引导与指导作用，也让我们明白了在算法学习中我们要多了解一些问题的最新解法与关注算法在实际问题中的应用。在本次学习过程中还发现了自己的很多不足，在以后的学习中更要弥补不足，要熟练掌握一些算法思想与其应用。