动态规划--流水作业调度问题
n个作业{1,2,3,4….n} 要在 2 台机器M1 M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工完毕后
再在M2上加工,M1和M2加工作业i 分别需要时间为 ai 和 bi。 1<=i<=n;
流水作业调度问题要求确定这n个作业的最优加工顺序,最优条件是(从第一个作业在M1开始加工开始到最后一个作业在M2加工完毕)
时间最少。
可以直观的了解到M1应该没有空闲时间,M2可能会处于的状态是等待M1完成(阻塞)和正在处理 M1已经完成加工的任务(运行)。
Johnson法则
约翰儿子法则,果然是特么的儿子法则,数学公式看起来真闹心;
其实这个法则有贪心法则的影子,说是贪心变种也不为过;
$:理解
把所有的ai,bi放在同一个集合里面,按照从小到大的顺序进行排序,如果当前最小的值是ai,那么就把这个任务尽可能的往前调度
如果当前最小值是bi,那么就尽可能把这个任务往后面调度
然后把ai(bi) 和 对应的的bi(ai)从待调度集合中删除,放入优先调度队列(滞后调度队列);
$$:理解
俄罗斯方块之最短拼接问题;
优先队列,ai块向左靠拢,
滞后队列,bi块向右靠拢,
用实际问题来论证下
假设有5个产品需要加工
产品号 |
1 |
2 |
3 |
4 |
5 |
M1加工时间 |
3 |
1 |
4 |
2 |
6 |
M2加工时间 |
2 |
4 |
5 |
3 |
5 |
注:只有在M1加工完成后才能在M2进行加工
问题对应的五个方块
删除集合,就是把那个方块从可以调用的任务集合里排除;
处理相同
最后方块拼接下,Johnson法则最主要作用就是让拼接的时候方块不至于越界,就是在M1没完成的时候,M2就开始了
拼接时候要判断拼接处的越界情况,接口处的凸凹,优先队列,凸6,滞后队列,凸6,完美贴合
时间就是1+2+4+(6)+5+2了
()中的内容就是需要判断的内容了,(x) = max(凸(优先队列),凸(滞后队列));