流水作业调度

1、流水作业调度1问题描述：定义：设有n个作业，每一个作业Ti均被分解为m项任务：Til, 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, Kj m)均已给出，要找出一种安排作业的方法，使得完成这 n个作业的加工 时间为最少。完成n个作业的加工时间为从安排的第一个作业开始加工，到最后一个作业加 工完毕，其间所需要的时间。2分析：一个最优调度应使机器M没有空闲时间，且机器M2勺空闲时间最少。在一般情况下，机器M2!会有机器空闲和作业积压2种情况。设全部作业的集合为N=1, 2,n。S N是N的作业子集。 在一般情况下， 机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。 将这种情况下完成S中作业所需的最短时间记为 T(S, t)。流水作业调度问题的最优值为：T

3、(N,O)。设M和M2fe工作业i所需的时间分别为ai和bi。设是所给n个流水作业的一个最优调度，它所需的加工时间为a (1)+T T 是在机器M2的等待时间为b (1)时，安排作业 (2),(n)所需的 时间。记S=N - (1),那么有 T =T(S, b)流水作业调度的Johnson法那么设 是作业集S在机器M2的等待时间为t时的任一最优调度。假设n (1)=i, n (2)=j，那么由动态规划递归式可得：T ( s,t)=ai+T(S-is,bi+maxt-ai,O)=ai+aj+T(s-i,j,tij)假设作业i和j满足，那么称作业i和j满足Johnson不等式。如果作业i和j不满足

4、Johnson不等式，那么交换作业i和j的加工顺序后，作业i 和j满足Johnson不等式。证明：算法满足Johnson不等式N1中作业满足Johnson不等式i,j N1,i在前，j在后所以 aibi,ajbi ，且有 aiaj因为 aiaj,ai=bi,aj=bj, 且有 bibj因为 bjbi,bj=aj所以有 minai,bjv=minaj,biN1中作业接N2中作业满足Johnson不等式i N1,j N2,所以 ai=bj ，所以有 minai,bjv=minaj,bi 。3.算法描述：FLOW-SHOP (n, a, b)let flow1.n be a new structur

5、ed array/.job 为True, N1 集合，.key为ai/ .job 为False, N2集合，.key 为bi/ .index 为作业编号for i=1 to nflowi.key = ai=bi ? bi : aiflowi.job = aibi flowi.index = iSORT(flow, n); /以.key值，从小到大进行排序 left = 1, right = n/ N1集合，ai从小到大排序，小值放在order前面 / N2集合，bi从小到大排序，小值放在order后面 let order1.n be a new arrayfor i=1 to nif flow

6、i.joborderleft+ = flowi.indexelseorderright- = flowi.index temp = aorder1/ t ：依最优调度顺序得到的总的加工时间 t = temp+border1for i=2 to ntemp = temp+aorderit = tempt ? t+borderi : temp+borderi return order and t算法时间复杂度：算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的 计算时间为 O(nlogn) 。4. 程序：(main.java)public class main public sta

7、tic void main(String args)int a=5,12,4,8;int b=6,2,14,7;flowShop flow仁 new flowShop(); flow1. flowShop (4, a, b);(flowShop.java)public class flowShop public static void flowShop( int n,int a, int b) int key= new int n;/使用三个数组代替flow类int index= new int n;boolean job= new boolean n;for (int i=0;i=bi?bi

8、:ai;jobi=aibi;in dexi=i;sort(key,i ndex,job,0, n-1);int left=0,right=n-1;int order= new int n;for (int i=0;in;i+)if(jobi)orderleft+=in dexi;elseorderright-=i ndexi;int temp=aorder0;int t=temp+border0;for (int i=1;in;i+)temp+=aorderi; t=tempt?t+borderi:temp+borderi;System. out.print(作业顺序为：);for (int

9、i=0;in;i+)System. out .prin t(orderi+1+ );System. out.println( n 时间为：+t);/*使用快速排序算法*/public static void sort( int key, int index, boolean job, int p,int r) if (pr)int q= partition (key,index,job,p,r);sort (key,index,job,p,q-1);sort (key,index,job,q,r);public static int partition( int key, int index, boolean job, int p, int r)int x=keyr;int i=p-1,temp1;boolean temp2;for (int j=p;jr;j+)if (keyj=x) i+; temp1=keyi; keyi=keyj; keyj=temp1; temp1=indexi; indexi=indexj; indexj=temp1; temp2=jobi; jobi=jobj; jobj=temp2;i+; temp1=keyi; keyi=keyr; keyr