整数划分 流水作业调度 I.问题描述 N个作业{1,2,…,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 II.问题分析 假定这n个作业在机器M1上加工时间为ai,在机器M2上加工时间为bi，1<=i<=n. 由流水作业调度问题具有最优子结构性质可知， T(N,0)=min{ai+T(N={i},bi)} 1<=i<=n 推广到一般情况下， T(S,t)={ai+T(S-{i},bi+max{t-a,0})} i∈S 式子中，max{t-ai,0}这一项是由于在机器M2上，作业i必须在max{t,ai}时间之后才能开工，因此，在机器M1上完成作业加工i之后，在机器上还需 bi+max{t,ai}-ai=bi+max{t-ai,0} 时间才能完成对作业i的加工。 按照上述递归式，可以设计出流水作业调度问题的动态规划算法。但是算法还可以进一步简化。 设π是作业集S在机器M2的等待时间为t时的任一最优调度。若在这个调度中，安排在最前面的两个作业分别是i和j，记π(1)=i,π(2)=j，由动态规划递归式可得: T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij) 其中，tij=bi+max{bi+max{t-ai,0}-aj,0} =bj+bi-aj+max{max{t-ai,0},0},aj-bj} =bj+bi-aj+max{t-ai,aj-bi,0} =bj+bi-aj-ai+max{t,ai+aj-bi,ai} 如果作业i和j满足min{bi,aj}>=min{bj,ai},则称作业i和j满足Johnson不等式。 如果作业i和作业j不满足Johnson不等式，则交换作业i和作业j的加工顺序后，作业i和作业j满足Johnson不等式，而且不增加加工时间。 在作业集S当机器M2的等待时间为t时的调度π中，交换作业i和作业j的加工顺序，得到作业集S的另一调度π’，它所需的加工时间为 T’(S,t)=ai+aj+T(S-{i,j},tji) 式中，tji=bj+bi-aj-ai+max{t,ai+aj-bj,aj}。 当作业i和j满足Johnson不等式min{bi,aj}>=min{bj,ai}时，有 max{-bi,-aj}<=max{-bj,-aj} 从而 ai+aj+max{-bi,-aj}<=ai+aj+max{-bj,-ai} 由此可得 max{ai+aj-bi,ai}<=max{ai+aj-bj,aj} 因此对任意t有 max{t,ai+aj-bi,ai}<=max{t,ai+aj-bj,aj} 从而，tij<=tji。由此可见T(S,t)<=T’(S,t) III.算法描述 流水作业调度问题的Johnson算法： 令N1={i|ai
=bi}; 将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序； N1中作业接N2中作业构成满足Johnson法则的最优调度。 证明此算法满足Johnson不等式： 1.N1中作业满足Johnson不等式：i,j∈N1,i在前，j在后。所以ai=bi,aj>=bj,且有bi>bj。因为bj=bj，所以有min{ai,bj}<=min{aj,bi}。 代码如下： FLOW-SHOP(n,a,b) let flow[1…n][1…n] be a new structured array //job为True.N1集合，key为a[i] //job为Flase.N2集合，key为b[i] //index为作业编号 for i=1 to n flow[i].key=a[i]>=b[i]?b[i]:a[i] flow[i].job=a[i] #include using namespace std; #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 #define ERROR -1 typedef int time; struct element //元素定义 { time m1; time m2; int key; int index; bool job; }; void sort1(element L[],int m,int n) //冒泡排序（递增） //实现对数组L中的L[m]到L[n]元素进行排序 { int i,j; for(i=n;i>m;i--) for(j=m;jL[j+1].m1) { element ab; //中间变量 ab=L[j]; L[j]=L[j+1]; L[j]=ab; } } }//sort1 void sort2(element L[],int m,int n) //冒泡排序（递减） //实现对数组L中的L[m]到L[n]元素进行排序 { int i,j; for(i=n;i>m;i--) for(j=m;jL[i].m2?L[i].m2:L[i].m1; L[i].job=(L[i].m1<=L[i].m2); L[i].index=i; } //按算法对元素进行排序 for(i=0;i>n; if(n>100) { cout<<"你输入的作业个数太大!!!"<>L[i].m1; cout<>L[i].m2; cout<
本文档为【流水作业调度】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483