动态规划--流水作业调度问题

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(凸(优先队列),凸(滞后队列));

 

动态规划--流水作业调度问题

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwwgww.html