流水作业调度与johnson法则

bk201 · 2019-08-09 16:17:52 · 个人记录

流水作业调度与johnson法则

0、写在前面

感谢CSDN风仲达博客提供（剽窃）的思路和图片。

1、问题描述

n个作业在由两个机器A和B组成的流水线上完成加工，并且必须先在A机器加工后才可以到B机器加工。A和B加工作业i所需时间分别为a_i和b_i。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器A上开始加工，到最后一个作业在机器B上加工完成所需的时间最少。

2、问题分析

显然，一个最优调度应使机器A没有空闲，且机器B空闲时间最短。设作业全集为N，S为N的作业子集。一般情况下，机器A在加工S中作业时，机器B还在加工其它作业，需等待t时间后才可使用。这种情况下记完成S中作业所需最短时间为T(S,t)，显然流水作业调度最优值是T(N,0)。

N个流水作业中的第i个的最优调度，它所需要的时间为a_i+T'。其中T'为在机器B等待时间为b_i时，安排其余作业最短时间。

记S=N-{i}，则T'=T(S,b_i)。

证明：由T'定义易得T'>=T(S,b_i)。当T'>T(S,b_i)时，调度所需时间为a_i+T'>a_i+T(S,b_i)。这与其是最优调度矛盾。故定有T'<=T(S,b_i)，从而T'=T(S,b_i)。这也就证明了流水作业调度问题具有最优子结构的特征。

从而可以得出

ps:这个真打不出来了。。。

3、动规求解

看到了上面的方程，第一反应难道不应该是心动的感觉？

假设有一组作业要在A和B上进行流水作业，工作时间如下表

问题是如何安排加工顺序使，总加工时间最短。

考虑如果只有一个作业的情况，肯定所需时间就是它自身需要在A和B上的加工时间总和，如果有两个作业就要考虑在两种不同的加工顺序下选取最优的一种作为候选，三个作业的时会出现三种组合情况(0,(1,2))，(1,(0,2))， (2,(0,1))，拿第一种为例，它表示先加工作业0，然后再按照作业1和作业2的优化顺序加工；将三种的作业时间计算出来，取最小值，即为三个作业的优化结果，同理可对更多的作业进行排序优化。具体做法是，用类似矩阵连乘的办法，自底向上将所有能的情况计算出来，并产生一个表，供后面的计算查用，减少重复计算的工作量。

对于j_1在B上工作的等待时间为b_0，实际上在B加工j_0的同时，A加工j_1，实际上它需要等待b_1-a_0的时间。

从j_0和j_1两个作业的加工顺序，可以看出，先加工j_0后加工j_1，所用时间最短为9，将其填入表中，依此类推，即可得出最优解。

选其中加工时间短的作为候选方案；在具体计算时非最优子集不必考虑，这样可以减少计算次数。

4、流水作业问题的johnson法则

先歇歇。。。。