实验五 分支限界算法的应用
一、 实验目的
1 ?掌握分支限界算法的基本思想、技巧和效率分析方法。 2?熟练掌握用分支限界算法的基本步骤和算法框架，
索，优先队列式搜索的思想。
FIFO搜索，LIFO搜
3 ?学会利用分支限界算法解决实际问题。
二、 算法问题描述
批处理作业调度问题：n个作业｛1,2,…,要在两台机器上处理，每个作业 必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai， 机器2处理作业i所需时间为bi ( K i菊n，批处理作业调度问题(batch-job scheduling problem)要求确定这n个作业的最优处理顺序，使得从第1个作业在 机器1上处理开始，到最后一个作业在机器 2上处理结束所需时间最少。
注意：由于要从n个作业的所有排列中找出具有最早完成时间的作业调度， 所以，批处理作业调度问题的解空间是一棵排列树，
并且要搜索整个解空间树才
能确定最优解，因此，其时间性能是 O(n!)。在搜索过程中利用已得到的最短完 成时间进行剪枝，才能够提高搜索速度。
三、 算法设计
批处理作业调度问题要从 n个作业的所有排列中找出具有最小完成时间和 的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树
2
B 2
3 F
3
IG 19
3
2
2 L
3
2
P
M
20 21
在作业调度问相应的排列空间树中, 每一个节点E都对应于一个已安排的作
业集:1--'……：。以该节点为根的子树中所含叶节点的完成时间和可 表示为：
匸工代+工的
设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为
{pk,k=1,2,……n}，其中pk是第k个安排的作业。如果从节点 E到叶节点L的 路上，每
一个作业pk在机器1上完成处理后都能立即在机器 2上开始处理，即 从p叶1开始，机器1没有空闲时间，则对于该叶节点 L有：
IX二￡ [%+心+1)仏+切」諾
踰 也'+!
注：(n-k+1)t1pk,因
为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上tlpk。
如果不能做到上面这一点，则si只会增加，从而有：
。
类似地，如果从节点E开始到节点L的路上，从作业p叶1开始，机器2没 有空闲时间，贝
n
炳辽画(咏凡+卿 』+山“ + 1)抵]二￡
同理可知，s2是
的下界。由此得到在节点E处相应子树中叶
节点完成时间和的下界是：
/+max{^1JS2}
ieA/
注意到如果选择Pk,使tlpk在k>=叶1时依非减序排列，S1则取 得极小
值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。
这可以作为优先队列式分支限界法中的限界函数。
四、运行结果
五、程序
#in clude
#define N 4〃作业数目设定为 4 机器2个 #defi ne MAX 1000 int x[N+1]={0,1,2,3}; int m[4][N+1]={
o,o,o,o, 0,2,3,2, 0,1,13 0,2,2,1 };
分支限界算法报告
