对于流水调度问题为什么可以采用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,并且必有以下关系成立：
故而必有min{bi,aj}>=min{bj,ai}满足Johnson规则。
综上所述，按此算法构造的流水作业排序满足Johnson规则，是所求的最优解。
爱华网本文地址 » http://www.aihuau.com/a/25101015/253543.html
更多阅读
? ? 之前在使用电脑的时候，老是弹出COM Surrogate已经停止工作的提示，我实在是忍受不了这种莫名奇妙的错误，于是上网查了一些资料，现在将这些资料总结一下！事先声明一下,我只是在总结所查找到的资料!大家按照下面的方法操作失败了的话请
对生产性生物资产会计核算问题的探讨沈鹏飞什么是生物资产？生物资产是有生命的动物或植物，生物资产和农业生产密切相关。生物资产分为消耗性生物资产、生产性生物资产和公益性生物资产。生产性生物资产，是指为产出农产品、提供劳务
关于量子力学及波粒二象性问题的探讨——就《对“量子力学波粒二象性问题”的一点看法》一文与张子、叶军、王浩明等好友的讨论张子2012-06-0812:38:22[举报]我在《洛伦兹运动及其几种存在形态》和《波粒二象性的本质》中已推出
【点评】读者可以把这篇讲话，与*鲍*彤、辛*子*陵、茅*于*轼、李*锐、何*方等人的言论，以及H*耀*邦小儿子在《炎*黄*春*秋》某次聚会上的讲话等，对照起来读。关于意识形态问题的一些看法中央文献研究室原主任逄先知罗援少将：一篇振聋发
ppt课件制作过程中常见问题的解决方法及技巧启明按：作为老师的你，一定遇到过自己做的ppt课件在讲课时演示不顺利的情况，如视频播放不了，文字显示不是想要的效果甚至成乱码……不用着急，现在，我把大家在使用ppt课件时遇到的一些常见问题
爱华网