有一个流水作业调度问题,n=4,a[]={5,10,9,7},b[]={7,5,9,8},给出采用优先队列式分枝限界法求一个解的过程
时间: 2023-06-27 14:05:29 浏览: 131
首先,我们需要明确流水作业调度问题的目标是最小化完成所有作业的时间。给定n个作业,每个作业有两个参数:处理时间ti和流水线编号j。每个流水线上可以同时进行一项作业,且同一作业在不同流水线上的加工时间可能不同。假设作业在流水线上的加工顺序是按照j=1,2,...,m的顺序进行的,求最小化完成所有作业的时间。
接着,我们使用优先队列式分枝限界法求解该问题:
Step 1: 初始化
我们首先将所有作业分配到第一个流水线上,并计算完成所有作业的时间。对于该初始状态,我们记录下当前完成时间和当前作业的状态,以及当前状态的上界(即用贪心算法计算出的最小完成时间,即当前状态下的最优解)。
对于本题,初始化状态如下:
- 当前完成时间:5
- 当前作业状态:[1, 0, 0, 0] (表示作业1已完成,作业2~4未完成)
- 上界:5 + max(b[1], b[2], b[3], b[4])
Step 2: 分枝
我们从未完成的作业中选择一个作业,将其分配到下一个流水线上,并计算得到新的状态。对于每个新状态,我们都计算出其上界,并将其放入优先队列中。我们优先处理上界最小的状态。
对于本题,我们从未完成的作业中选择作业2,将其分配到下一个流水线上,得到以下两个新状态:
- 当前完成时间:15
- 当前作业状态:[1, 1, 0, 0]
- 上界:15 + max(b[1], b[2], b[3], b[4])
- 当前完成时间:14
- 当前作业状态:[1, 0, 1, 0]
- 上界:14 + max(b[1], b[2], b[3], b[4])
Step 3: 剪枝
我们在加入新状态时,需要对其进行剪枝。具体来说,如果当前状态的上界大于等于已经找到的最优解,则可以将该状态剪枝。
对于本题,我们发现第一个新状态的上界已经大于等于最优解,因此可以将其剪枝。
Step 4: 迭代
我们不断重复步骤2和步骤3,直到队列为空或者找到最优解为止。
对于本题,我们得到以下状态:
- 当前完成时间:15
- 当前作业状态:[1, 1, 0, 0]
- 上界:15 + max(b[1], b[2], b[3], b[4])
- 当前完成时间:14
- 当前作业状态:[1, 0, 1, 0]
- 上界:14 + max(b[1], b[2], b[3], b[4])
- 当前完成时间:16
- 当前作业状态:[1, 0, 0, 1]
- 上界:16 + max(b[1], b[2], b[3], b[4])
- 当前完成时间:12
- 当前作业状态:[0, 1, 0, 1]
- 上界:12 + max(b[1]+b[2], b[3], b[4])
- 当前完成时间:13
- 当前作业状态:[0, 0, 1, 1]
- 上界:13 + max(b[1]+b[2], b[3], b[4])
- 当前完成时间:21
- 当前作业状态:[1, 1, 1, 0]
- 上界:21 + b[4]
- 当前完成时间:19
- 当前作业状态:[1, 0, 1, 1]
- 上界:19 + b[4]
- 当前完成时间:24
- 当前作业状态:[1, 1, 0, 1]
- 上界:24 + b[3]
- 当前完成时间:22
- 当前作业状态:[0, 1, 1, 1]
- 上界:22 + max(b[1], b[2]+b[3], b[4])
- 当前完成时间:23
- 当前作业状态:[1, 1, 1, 1]
- 上界:23 + b[4]
可以发现,最优解为23,对应的作业顺序为1、2、4、3。