该题题目为：
设有n个作业要在2台机器M1和M2 组成的流水线上完成加工。每个作业加工的顺序都是现在M1 上加工，然后在M2 上加工，所需时间分别为ai和bi。流水作业调度问题要求求加工完这些作业所需的最短时间。
为了得到最短时间，需要将总的等待时间将为最少，那么有：假设第i个作业在M1上的时间为ai，在M2上工作的时间为bi，那么根据ai和bi的大小可以分为两种情况：
① 当ai>bi时，有在M1上的时间比M2上的时间长，所用的时间为在M1上的时间和。
②当ai《bi时，在M1上的时间比M2上的时间短，所用时间为在M2上的时间和。
如图为四个作业：上面一行代表一个作业在M1上的时间，下面一行表示一个作业在M2上的时间：
如果并不加以处理顺序的加工，那么就有：
由图得，在进行了第一个作业的加工后，M2有一段时间是等待时间，而在M1加工完毕后，会有一段时间是M1在等待M2，因此会有时间浪费，故需要重新加以分析：
ai>bi与ai《bi时，时间分布如下：
ai<bi 与 ai>bi
可以看到可以将ai>bi与ai《bi分成两组，然后加以组合，得到最小的等待时间：
为了得到如图效果，需要将a1得到最小，且bn达到最小。（假设共有n个作业）。进而使两者相接的部位（假设在i处相接，即小于i时为ai《bi，大于i时为ai》bi）达到ai最大，bi最小，故算法步骤为：
假设在M1上的时间较大，将其设为时间数组1，若在M2上时间较长，则设为时间数组2，假设四个工件：ai：3 5 2 6；bi：5 4 3 2
①其可以将其归并为：（第五个参数表示时间数组）
0 0 3 5 1
1 1 5 4 2
2 2 2 4 1
3 3 6 2 2
②根据时间数组将其排序：
0 0 3 5 1
1 2 2 4 1
2 1 5 4 2
3 3 6 2 2
③将时间数组1内的作业按照ai为目标从小到大排序，将时间数组2内的作业按照bi为目标从大到小排序。排序结果为：
0 2 2 4 1
1 0 3 5 1
2 1 5 4 2
3 3 6 2 2
则可知，加工顺序为2 0 1 3。
而在进行多个作业（n》4）时，或者每个作业按照多个有序的程序逐个执行时，同样可以按照上述的规律，先将最小时间的所在集合进行排序，再按照每个集合内对应的程序执行先后进行排序。
网友评论