算法设计与分析课程大作业

题目作业调度问题及算法分析学院名称：计算机与信息工程学院专业名称：计算机科学与技术算法分析课程设计目录《算法设计与分析》课程大作业....................................................................错误!未定义书签。一．动态规划算法解决流水作业调度...........................................................................................31、问题描述.............................................................................................................................32、算法分析.............................................................................................................................33.算法的描述.........................................................................................................................44、部分算法实现.....................................................................................................................55.运行结果.............................................................................................................................66、时空效率分析.....................................................................................................................6二．贪心算法解多机调度问题.......................................................................................................61、问题描述.............................................................................................................................62、算法分析.............................................................................................................................73.部分算法实现.......................................................................................................................74.计算复杂性分析....................................................................................................................85.运行结果.............................................................................................................................9三．回溯法解决批作业调度问题...................................................................................................91.问题描述...............................................................................................................................92.算法思想..............................................................................................................................103.部分算法实现...................................................................................................................114.运行结果..............................................................................................................................125.时间复杂性分析..................................................................................................................12四．作业调度算法比较.................................................................................................................12五．课程学习总结.........................................................................................................................13算法分析课程设计摘要：在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。关键词：作业调度；动态规划；贪心算法；回溯法；一．动态规划算法解决流水作业调度1、问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。2、算法分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。算法分析课程设计在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。由流水作业调度问题的最优子结构性质可知，)}},{({min)0,(1iinibiNTaNT（1）})}0,max{},{({min),(iiiSiatbiSTatST（2）从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。将问题规模缩小。公式（2）说明一般情况下，对作业集S进行调度，在M2机器上的等待时间，除了需要等该部件在M1机器上完成时间，还要冲抵一部分原来的等待时间，如果冲抵已成负值，自然仍需等待M1将作业做完，所以公式取max{t-ai,0}。3.算法的描述从分析可知，流水作业调度问题一定存在满足Johnson法则的最优调度，且容易由下面的算法确定。流水作业调度问题的Johnson算法：（1）令]}2,[]1,[|{]},2,[]1,[|{21ititiNititiN；（2）将中作业依的非减序排列；将中作业依的非增序排列；算法分析课程设计作业接种作业构成满足Johnson法则的最优调度。4、部分算法实现intFlowShop(intn,inta[],intb[],intc[]){inti;Jobtype*d=newJobtype[n];for(i=0;in;i++){d[i].key=a[i]b[i]?b[i]:a[i];//按Johnson法则分别取对应的b[i]或a[i]值作为关键字d[i].job=a[i]=b[i];//给符合条件a[i]b[i]的放入到N1子集标记为trued[i].index=i;}BubbleSort(d,n);//对数组d按关键字升序进行排序intj=0,k=n-1;for(i=0;in;i++){if(d[i].job){c[j++]=d[i].index;//将排过序的数组d，取其中作业序号属于N1的从前面进入}else{c[k--]=d[i].index;//属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序}}j=a[c[0]];k=j+b[c[0]];for(i=1;in;i++){j+=a[c[i]];//M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完k=jk?k+b[c[i]]:j+b[c[i]];//计算最优加工时间}deleted;returnk;}算法分析课程设计5.运行结果6、时空效率分析算法Flowshop的主要计算时间花在对作业集的排序上。在这里，我们使用冒泡排序法(BubbleSort)，因此，在最坏情况下算法FlowJob所需要的计算时间为)log(nnO。所需要的空闲显然是)(nO。二．贪心算法解多机调度问题1、问题描述多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。算法分析课程设计2、算法分析贪心算法只需按顺序以数组方式提供各作业的加工时间和机器的台数；求出作业的个数，若小于机器台数，就将作业逐个分配给就近的机器，所需要的加工时间，即为最长作业所需时间。若作业数大于机器台数，将作业按加工时间的多少降序排序，以机器数建立最小堆，先将前m个作业分配给m个机器，最小堆顶是最小的元素（即m个作业中加工时间最少的作业），将其移出并加上后续作业的加工时间，再插入堆，这时会改变原来的状态，升到堆顶的机器加工总时间最少，它再移出加后续作业的加工时间，在插入堆，依此类推，直到全部作业结束。堆中的最大值就是完成所有作业所需的最短时间。3.部分算法实现typedefstructNode{intID,avail