有一个流水作业调度问题, n =4, a []={5,10,9,7}, b []={7,5,9,8},给出采用优先队列式分枝限界发求一个解的过程
时间: 2023-09-27 14:07:57 浏览: 55
好的,针对你的问题,我来简单地解释一下流水作业调度问题和优先队列式分枝限界算法的基本思路,再结合给出的数据进行具体过程的解释。
流水作业调度问题是指有n个作业需要在m台相同的机器上完成加工,每个作业需要在其中一台机器上加工,每台机器一次只能处理一个作业,每个作业具有加工时间和加工顺序,求所有作业完成所需的最短时间。
优先队列式分枝限界算法是一种常用于解决最优化问题的算法,其基本思路是在搜索过程中维护一个优先队列,每次取出队首元素进行扩展,直到找到最优解或队列为空。
针对给出的数据,我们可以按照以下步骤进行优先队列式分枝限界算法求解流水作业调度问题:
1. 定义一个优先队列,用于存储待扩展的状态;
2. 定义一个状态结构体,包括当前完成的作业数、当前机器状态、当前花费时间、当前已分配的作业;
3. 将初始状态加入队列中;
4. 不断从队列中取出队首元素进行扩展,直到找到最优解或队列为空;
5. 对于每个扩展出的状态,考虑将剩余的作业分配到哪一台机器上,并计算出该状态下的最小花费时间;
6. 将计算出的状态加入优先队列中。
具体过程如下:
1. 初始状态:完成0个作业,每台机器的状态为0,花费时间为0,已分配的作业为空;
2. 对于初始状态,首先将第一个作业分配到第一台机器上,得到状态1:完成1个作业,第一台机器的状态为5,花费时间为5,已分配的作业为1;
3. 将状态1加入优先队列中;
4. 取出队首元素状态1进行扩展,考虑将第二个作业分配到哪一台机器上,有两种情况:
- 将第二个作业分配到第一台机器上,得到状态2:完成2个作业,第一台机器的状态为15,花费时间为15,已分配的作业为1、2;
- 将第二个作业分配到第二台机器上,得到状态3:完成2个作业,第二台机器的状态为10,花费时间为10,已分配的作业为1、2;
5. 将状态2和状态3加入优先队列中;
6. 取出队首元素状态2进行扩展,考虑将第三个作业分配到哪一台机器上,有两种情况:
- 将第三个作业分配到第一台机器上,得到状态4:完成3个作业,第一台机器的状态为24,花费时间为24,已分配的作业为1、2、3;
- 将第三个作业分配到第二台机器上,得到状态5:完成3个作业,第二台机器的状态为19,花费时间为19,已分配的作业为1、2、3;
7. 将状态4和状态5加入优先队列中;
8. 取出队首元素状态3进行扩展,考虑将第三个作业分配到哪一台机器上,有两种情况:
- 将第三个作业分配到第一台机器上,得到状态6:完成3个作业,第一台机器的状态为24,花费时间为24,已分配的作业为1、2、3;
- 将第三个作业分配到第三台机器上,得到状态7:完成3个作业,第三台机器的状态为9,花费时间为9,已分配的作业为1、2、3;
9. 将状态6和状态7加入优先队列中;
10. 取出队首元素状态7进行扩展,考虑将第四个作业分配到哪一台机器上,有两种情况:
- 将第四个作业分配到第二台机器上,得到状态8:完成4个作业,第二台机器的状态为29,花费时间为29,已分配的作业为1、2、3、4;
- 将第四个作业分配到第三台机器上,得到状态9:完成4个作业,第三台机器的状态为16,花费时间为16,已分配的作业为1、2、3、4;
11. 将状态8和状态9加入优先队列中;
12. 取出队首元素状态5进行扩展,考虑将第四个作业分配到哪一台机器上,有两种情况:
- 将第四个作业分配到第二台机器上,得到状态10:完成4个作业,第二台机器的状态为29,花费时间为29,已分配的作业为1、2、3、4;
- 将第四个作业分配到第三台机器上,得到状态11:完成4个作业,第三台机器的状态为16,花费时间为16,已分配的作业为1、2、3、4;
13. 将状态10和状态11加入优先队列中;
14. 取出队首元素状态4进行扩展,考虑将第四个作业分配到哪一台机器上,有两种情况:
- 将第四个作业分配到第二台机器上,得到状态12:完成4个作业,第二台机器的状态为29,花费时间为29,已分配的作业为1、2、3、4;
- 将第四个作业分配到第四台机器上,得到状态13:完成4个作业,第四台机器的状态为7,花费时间为7,已分配的作业为1、2、3、4;
15. 将状态12和状态13加入优先队列中;
16. 取出队首元素状态9进行扩展,此时队列中只剩下状态10和状态11,继续扩展状态10和状态11,直到找到最优解为止。
通过以上算法过程,可以得到最短的完成时间为29,对应的作业调度方案为1->2->4->3。