文档介绍：:..综合实验实验报告Emai1:claoOoad@:算法的综合应用问题描述:有加台不同的机器,〃个不同的工件。每个工件有多道工序,每道丁•序由指定的机器在間定的时间内完成。一道工序一旦开始处理,就不能屮断。每台机器一次只能处理i道工序。一个调度就是决定毎台机器上T序的处理顺序,使得机器完成所有工件的时间最短。具体的,该问题就是要求在满足(1)、(2)两个约束条件的前提下,确定每台机器上工序的顺序,使加工的时间跨度(从开始加工到全部工件都加工完所需要的时间)达到最小。其中,(1)表示工件约束条件:对每个T件而言,机器对它的加工路线是事先确定的;(2)表示机器约束条件:对每台机器而言,一次只能对一•道工序进行加工。要求:利用所学的算法求解该问题,任给一个输入实例,能输出最短时间以及每台机器上工序的加工顺序。能设计出一个用户界面。:原先考虑过用冋溯法进行解体,解空间树是所有工件的所有工序的一棵排列树,但这样如果没有好的剪枝函数是不可能实现的,因为这样实现的话时问复杂度将是O(2Fn),3£中m为机器数,n为T件数,题H能用的剪枝函数的设计是毎个T件的加T次序是有要求的,个人预测需要用到线性规划的内容,最后没有如此实现。木程序使用贪心算法实现,程序所有的工件所有的工序保存在一个二维数组屮,并且维护一个指针,该指针毎次走动一个工序时间,这样的一次走动将产生n个工序需要加工,其屮n为工件数目,将这n个丁•件放到相应的m个机器上,在m个机器按照加王时间递增排序,Z所以选择递增排序,是想让每个工序尽可能快的通过他所需要的机器,即可以让该机器上的工序可以更快的加:T,也可以让他Z示的工序可能更快的在其他机器上进行加工,当然这样的设计只是直观上的说明,并不能得到最优解。程序屮维护的数据结构如下图所示,共有两个,一个用来保存所有工件的所有工序,另一个用来表示机器加工工序。在图一中共有六个工件1〜6以及每个_丁件有6个T序,图上方的箭头表示移动的指针,每个移动一个工序,由于图一中的数组元素结构体设计如下:typedefstruct{〃机器节点定义int(ime;//当前的加I[的最示时间Sequence*S;〃维护一个丁•件链表[Machine;因此对于每个可以加工的工序,可以直接链入图二屮的链表屮不需要另外申请空间。1**********(图一)(图二)图二表示共有四个机器,每个机器头指针后血链接一个链表,链表元素为每个工件且每个工件按照加工时间递增排序。对于图一中的指针走动,产生的工序加入图二加工,图二加工完成后,图一屮指针继续走动,肓到图一屮没有其他工序。由以上分许,程序只需要对所有工件的所有工序扫描一遍即可算出最后完成加工的时间,故程序的时间复杂度为O(m*n),空间复杂度为O(m*n):for(i=O;i<m;i++)〃对所仃的工件所有的T序进行操作for(j=0;j<n;j++){ 〃扫描所侑的工件if(flag==1){〃说明是笫一个丁序,记录开始时间为0flag=0;SortInsert(Head[j][i].m,&Head〃插入到机器队列中Opertion();〃机器操作,计算时问}els