算法-加工顺序.pptx

加工顺序问题动态规划解决方案2015/11/23问题描述 有n个工件需要在机器M1和M2上加工。工件先在M1上加工，再在M2上加工。 问：应如何安排生产，使得第一个工件从在M1上加工开始到最后一个工件在M2上加工完所需的总加工时间最短？问题分析M1没有空闲时间M2空闲时间最少 M2上分为两种情况：机器空闲作业等待问题分析? 设全部的作业集合为。是的作业子集。 一般情况下，机器M1开始加工 中作业时，机器M2还在加工其它作业，要等待时间 后才可利用。将这种情况下完成 中作业所需的最短时间记为 加工顺序问题的最优值为最优子结构性质?加工顺序问题具有最优子结构。证明： 设是所给n个作业的一个最优调度，它所需的加工时间为 其中是在机器M2的等待时间为时，安排作业所需的时间。记最优子结构性质?证明： 由 的定义知 若，则设是作业集在机器M2的等待时间为情况下的一个最优调度。那么是的一个调度，并且该调度所需的时间为 最优子结构性质?显然这与是的一个最优调度矛盾。因此 又因为所以这就证明了加工顺序问题具有最优子结构的性质。动态规划递归式?由流水作业问题的最优子结构性质可知推广到一般情形下便有其中这一项是由于在机器M2上，作业须在等待时间后才能开工。因此，作业在机器M1加工完成之后，还需 时间才能完成在机器M2上的加工。Johnson法则?设是作业集在机器M2上等待时间为时的任意一个最优调度。若在这个调度中，安排在最前面的两个作业分别是和，即，。则由动态规划递归式得 Johnson法则?其中= = = =如果交换作业集中作业和作业的加工顺序，得到作业集的另一个调度，它所需要的加工时间为其中Johnson法则?假设作业和作业不满足Johnson不等式 时，我们有因此对任意有从而。由此可见Johnson法则?所以，在作业集上的一个最优调度上，不满足Johnson不等式时，我们交换它们的加工顺序，使得，此时满足Johnson不等式，且不增加加工时间。Johnson法则?因此，对于加工顺序问题，必存在一个最优调度，使得满足Johnson不等式 我们称这样的调度为满足Johnson法则的调度由此可推导出一个更强的论述：调度满足Johnson法则的充分必要条件是，对任意有 由此可知任意两个满足Johnson法则的调度具有相同的加工时间。Johnson法则结论：满足Johnson法则的调度是最优调度因此我们将寻找加工顺序问题的最优调度转化为寻找满足Johnson法则的调度。构造满足Johnson法则的调度?(1)令, ;(2)将中作业按的非减序排序；将中作业按的非增序排序；(3) 中作业接中作业构成满足Johnson法则的调度。代码讲解演示