《流水作业调度》word版

《《流水作业调度》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、流水作业调度1.问题描述：定义：设有n个作业，每一个作业Ti均被分解为m项任务：Ti1,Ti2,…,Tim(1≤i≤n)，要把这些任务安排到m台机器上进行加工。如果任务的安排满足下列3个条件，则称该安排为流水作业调度：1.每个作业i的第j项任务Tij(1≤i≤n,1≤j≤m)只能安排在机器Mj上进行加工2.作业i的第j项任务Tij(1≤i≤n,2≤j≤m)的开始加工时间均安排在第j-1项任务Ti,j-1加工完毕之后，即任何一个作业的任务必须依次完成，前一项任务完成之后才能开始着手下一项任务；3.任何一台机器在任何一个时刻最多只能承担一项任务。设任务Tij在机器Mj上进行加工需要的

2、时间为tij。如果所有的tij(1≤i≤n,1≤j≤m)均已给出，要找出一种安排作业的方法，使得完成这n个作业的加工时间为最少。完成n个作业的加工时间为从安排的第一个作业开始加工,到最后一个作业加工完毕，其间所需要的时间。2.分析：一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N={1,2,…,n}。SÍN是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值

3、为：T(N,0)。设M1和M2加工作业i所需的时间分别为ai和bi。设p是所给n个流水作业的一个最优调度，它所需的加工时间为ap(1)+T’。T’：是在机器M2的等待时间为bp(1)时，安排作业p(2),…,p(n)所需的时间。记S=N-{p(1)}，则有T’=T(S,bp(1))流水作业调度的Johnson法则设p是作业集S在机器M2的等待时间为t时的任一最优调度。若π(1)=i,π(2)=j，则由动态规划递归式可得：T（s,t）=ai+T(S-{is],bi+max{t-ai,0})=ai+aj+T(s-{i,j},tij)若作业i和j满足，则称作业i和j满足Johnson不

4、等式。如果作业i和j不满足Johnson不等式，则交换作业i和j的加工顺序后，作业i和j满足Johnson不等式。证明：算法满足Johnson不等式N1中作业满足Johnson不等式i,j∈N1,i在前，j在后所以ai=bi,aj>=bj,且有bi>bj因为bj

5、ai=bj，所以有min{ai,bj}<=min{aj,bi}。3.算法描述：FLOW-SHOP(n,a,b)letflow[1..n]beanewstructuredarray//.job为True,N1集合，.key为a[i]//.job为False,N2集合，.key为b[i]//.index为作业编号fori=1tonflow[i].key=a[i]>=b[i]?b[i]:a[i]flow[i].job=a[i]

6、]从小到大排序，小值放在order前面//N2集合，b[i]从小到大排序，小值放在order后面letorder[1..n]beanewarrayfori=1tonifflow[i].joborder[left++]=flow[i].indexelseorder[right--]=flow[i].indextemp=a[order[1]]//t：依最优调度顺序得到的总的加工时间t=temp+b[order[1]]fori=2tontemp=temp+a[order[i]]t=temp

7、法时间复杂度：算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。4.程序：（main.java)publicclassmain{publicstaticvoidmain(Stringargs[]){int[]a={5,12,4,8};int[]b={6,2,14,7};flowShopflow1=newflowShop();flow1.flowShop(4,a,b);}}(flowShop.java)publicclassflowSho