《机器调度问题》由会员分享，可在线阅读，更多相关《机器调度问题（6页珍藏版）》请在金锄头文库上搜索。
1、1) 问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为t.,i则对n个作业进行机器分配，使得：(1) 一台机器在同一时间内只能处理一个作业；(2) 个作业不能同时在两台机器上处理；(3) 作业i 一旦运行，则需要t.个连续时间单位。i设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理 时间最短。2) 基本要求(1) 建立问题模型，设计数据结构；(2) 设计调度算法，为每个作业分配一台可用机器；(3) 给出分配方案。3) 设计思想假设有七个作业，所需时间分别为2, 14, 4,16, 6, 5, 3,有三台机器，编 号分别为mm2和m3。这七个作业在三台机器上进行
2、调度的情形如图所示, 阴影区代表作业的运行区间。作业4在0到16时间被调度到机器 1上运行，在这 16个时间单位中，机器 1完成了对作业4的处理；作业2在0到14时间被调度到 机器2上处理，之后机器2在14到17时间处理作业7；在机器3上，作业5在06 时间完成，作业6在611时间完成，作业3在1115时间完成，作业1在15 17时间完成。注意到作业i只能在一台机器上从s.时刻到s. +t.时间完成且任ii i何机器在同一时刻仅能处理一个作业，因此最短调度长度为7。聊4IIIpI?.在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业 按其所需时间的递减顺序排列，在分
3、配一个作业时，将其分配给最先变为空闲的机器下面设计完成LPT算法的存储结构。为每个机器设计数据类型：struct MachineNodeint ID;机器号int avail; 机器可用时刻；为每个作业设计数据类型：struct JobNodeint ID;作业号int time;/处理时间;LPT算法用伪代码描述如下：1. 如果作业数nW机器数m,则1.1将作业i分配到机器i上；1.2最短调度长度等于n个作业中处理时间最大值；2. 否则，重复执行以下操作，直到n个作业都被分配：2.1将n个作业按处理时间建成一个大根堆H1；2.2将m个机器按可用时刻建立一个小根堆H2；2.3将堆H1的堆顶作业
4、分配给堆H2的堆顶机器；2.4将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入h2中；2.5将堆H1的堆顶元素删除；3. 堆H2的堆顶元素就是最短调度时间;#includeviostream#define N 10限定机器数和作业数不超过N个，这里N取10using namespace std;/ / / Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Txstruct MachineNodei
5、nt ID;机器号int avail; /机器可用时间;struct JobNodeint ID; 作业号int time; 处理时间;建立大根堆void SiftD(JobNode r,int k,int m) int i,j;i=k;j=2*i;while(jv=m)if(jvm& rj.timevrj+1.time)j+; if(ri.timerj.time)break;elseint temp1,temp2;temp1=ri.time;ri.time=rj.time; rj.time=templ; temp2=ri.ID; ri.ID=rj.ID; rj.ID=temp2;void H
6、eapSortD(JobNode r,int n) for(int i=n/2;i=1;i-)SiftD(r,i,n);/ / /Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx建立小根堆void SiftX(MachineNode r,int k,int m) int i,j;i=k;j=2*i;while(jv=m)if(jvm& rj.availrj+1.avail)j+; if(ri.availvrj.avail)break;elseint temp1,temp2; temp1=ri.a
7、vail; ri.avail=rj.avail; rj.avail=temp1; temp2=ri.ID; ri.ID=rj.ID; rj.ID=temp2;void HeapSortX(MachineNode r,int n)for(int i=n/2;i=l;i-)SiftX(r,i,n);/ / / / Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Txvoid as
8、sign(MachineNode M,JobNode J,int m,int j) / 完成任务分配if(m=j)如果机器数m大于或等于作业数jcoutvv 台机器完成一个作业，最大工作时间为:；HeapSortD(J,j);/以各作业所需时间建立大根堆，堆顶元素即为最大耗时的作业coutvvJ1.timevvendl; 最大工作时间即为最大耗时的作业的所需时间else 如果机器数m小于作业数jfor(int i=1;iv=m;i+) /先为每台机器分配一个作业，先把所需时间最大的m个作业分配给 m台机器。HeapSortD(J,j); 建立大根堆求堆顶元素确定其中耗时最大的作业Mi.avai
9、l=J1.time; 机器i的处理时间即为作业的所需时间coutvv机器vvMi.IDvv完成作业vvJ1.IDvvendl;for(int k=1;kvj;k+) /减去已分配的作业Jk=Jk+1;j=j-1；for(int q=j;j=1;q-) /把剩余的j-m个作业分配下去(j=j-m)HeapSortX(M,m); 将m机器个机器按可用时建立小根堆HeapSortD(J,j); /将 j个作业按处理时间建立大根堆coutvv机器vvM1.IDvv完成作业vvJ1.IDvvendl; 将大根堆的堆顶作业分配给小根堆的堆顶机器Ml.avail+=Jl.time; /将小根堆的堆顶机器加上
10、大根堆的堆顶作业的处理时间，重新插入 小根堆(循环执行HeapSortX(M,m)时完成)for(int k=1;kvj;k+) /减去已分配的作业Jk=Jk+1;j=j-1；coutvv最短调度时间为：vvM1.availvvendl; 小根堆的堆顶元素就是最短调用时间void main()int j=0;作业个数int m=0; 机器个数int i;MachineNode MN;机器的结构体数组JobNode JN;/作业的结构体数组coutvv请输入作业个数：；cinj;coutvv请输入每个作业需要的处理时间:vvendl;for(i=1;iv=j;i+)Ji.ID=i;为每个作业确定序号coutvv第vvivv个作业：；cinJi.time;/输入每个作业的用时coutvv请输入机器的个数：；cinm;for(i=1;iv=m;i+)Mi.ID=i;为每台机器确定序号assign(M,J,m,j);调用完成分配任务的函数
