流水作业调度问题的Johnson算法 作业调度算法经典例题

对于流水调度问题为什么可以采用Johnson算法的推导详见《算法设计与分析(第三版)》(王晓东编著)的第三章第9节。此处仅对书上的算法描述中构造Johnson序列的方法的正确性加以说明:
1.Johnson不等式:min{bi,aj}>=min{bj,ai};
2.作业i在作业j之前执行.
书上已经证明如果对于作业集N的任意排列如果满足上述两点条件,那么这种调度必为最优调度,即所需总调度时间最短。
流水调度问题的Johnson算法:
1)令N1={i|ai<bi},N2={i|ai>=bi}
2)将N1中作业按照ai的非递减排序(<=),将N2中作业按照bi的非递增排序(>=);
3)N1中作业和N2中作业相连接构成满足Johnson法则的最优调度。
证明:
1.N1满足
首先对于N1中的任意两个元素i,j(i<j)有以下关系

由此我们可以得出结论min{ai,bi,aj,bj}=ai;由此必有:min{bi,aj}>=min{bj,ai}满足Johnson规则;
2.N1满足
对于N2中的任意两个元素i,j(i<j)有以下关系

由此可以得出结论min{ai,bi,aj,bj}=bj;故而必有:min{bi,aj}>=min{bj,ai}满足Johnson规则;
3.N1和N2连接后仍满足(N1在前)
任取N1中元素i,N2中元素j,必有i&l t;j,并且必有以下关系成立:

流水作业调度问题的Johnson算法 作业调度算法经典例题
故而必有min{bi,aj}>=min{bj,ai}满足Johnson规则。
综上所述,按此算法构造的流水作业排序满足Johnson规则,是所求的最优解。

  

爱华网本文地址 » http://www.413yy.cn/a/25101015/253543.html

更多阅读

转 逄先知:关于意识形态问题的一些看法

【点评】读者可以把这篇讲话,与*鲍*彤、辛*子*陵、茅*于*轼、李*锐、何*方等人的言论,以及H*耀*邦小儿子在《炎*黄*春*秋》某次聚会上的讲话等,对照起来读。关于意识形态问题的一些看法中央文献研究室原主任逄先知罗援少将:一篇振聋发

声明:《流水作业调度问题的Johnson算法 作业调度算法经典例题》为网友予你所有分享!如侵犯到您的合法权益请联系我们删除