第3章 作业分配问题
3.1 问题描述
题1:作业分配问题：设有A,B,C,D,E, ?等n个人从事J1,J2,J3,J4,J5,?等n项工作，每人只能从事一项任务，每个任务由不同的工人从事有着不同的费用，求最佳安排使费用最低。
要求：输出每人所从事的工作任务以及最佳安排的最低费用。
题2: 有两艘船和需要装运的n个货箱，第一艘船的载重量是c1，第二艘船的载重量是c2，Wi是货箱i的重量，且W1+W2+W3+W4+......+Wn<=c1+c2。希望确定是否有一种可将所有n个货箱全部装船的方法。
要求:输出每艘船最终载重量.
3.2 问题分析
分支搜索法是一种在问题解空间上进行搜索尝试的算法。是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：
(1)产生当前扩展结点的所有孩子结点；
(2)在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点； (3)将其余的孩子结点加入活结点表；
(4)从活结点表中选择下一个活结点作为新的扩展结点。
如此循环，直到找到问题的可行解（最优解）或活结点表为空。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。
题1:先看一个实例,设有A,B,C,D,E 5人从事J1,J2,J3,J4,J5项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。
A B C D E J1 10 13 5 15 10 J2 11 10 9 12 11 J3 10 10 7 10 8 J4 4 8 7 11 8 J5 7 5 4 5 4 要求：输出每人所从事的工作项目以及最佳安排的最高效益。
考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务J1分配给人员A,任务J2分配给人员B,任务J3分配给人员C,任务J4分配给D,任务J5分配给E,其总效益是10+10+7+11+4=42;或者应用贪心法求得一个近似解:人员A从事J2时效益最大,将任务J2分配给人员A,剩余工作中人员B从事J1时效益最大,任务J1分配给人员B,J3、J4、J5中人员D从事J4时效益最大,任务J4分配给人员D,J3和J5中人员C从事J3时效益最大,任务J3分配给人员C,任务J5只能分配给人员E,其总效益是11+13+11+7+4=46.显然,42和46都不能确定是最优解,有可能还有比其更大的效益,这两个解其一并不一定是一个最可行的选择,它们仅仅提供了一个参考,这样,可以以其中一个作为参考来进一步对各种作业分配方案进行搜索,比较其每种分配方式的效益.最大的总效益为最优解,其分配方案为最佳分配方案.
题2: 先看一个实例,当n=3,c1=c2=50,w={10,40,40}时,可将货箱1,2装到第一艘船上,货箱3装到第二艘船上.但如果w={20,40,40},则无法将货箱全部装船.由此可知问题可能有解,可能无解,也可能有多解.下面以找出问题的一个解为目标设计算法.
虽然是关于两艘船的问题,其实只讨论一艘船的最大装载问题即可.因为当第一艘船的最大装载为bestw时,若w1+w2+?+wn-bestw<=c2则可以确定一种解,否则问题就无解.这样问题转化为第一艘船的最大装载问题.
3.3 算法设计
题1:问题的解空间为一个子集树,所有可能的解都可通过一个求解树给出.也就是算法要考虑任务是否分配给人员的情况组合,n个任务分配给n个人员的组合共
- 1 -
n*n种情况,作业分配子集树是n=4的子集树它是用FIFO分支搜索算法解决该问题的扩展结点的过程编号的.
1 个人作业分配 2 3 1 3 4 2 2 4 5 3 4 5 3 5 4 5 5 4 4 作业分配子集树
在任务分配中,如实例中若n=4时,J1分配给A则向左走,否则往右走,直到走到最后,把最终的总效益求出,并把第一次求出的总效益作为最大效益与后边的总效益相比较,比其大者,交换两者,大的作为最大效益.依次方法,直到找到最优解,并输出其值以及其最大效益时的最佳分配方案.
(1)用FIFO分支搜索所有的分支,并记录已搜索分支的最优解,搜索完子集树也就找出了问题的解.图中结点1为第零层,是初始E-结点;扩展后结点2,3为第一层;3,4,2是第一个任务分配出去后的下一层扩展结点,4,5,3,4,5是第二个任务分配出去后下一层的扩展结点(即分配情况).
(2)用task[i]来表示任务是否分配及分配了给哪个工人,即task[i]=0时表示任务i未分配, task[i]=j表示任务i分配给了工人j;用worker[k]=0或1来表示工人k是否分配了任务, worker[k]=0表示工人k未分配任务, worker[k]=1表示工人k已分配了任务.
(3)把最低费用用mincost来表示和c[i][j]表示工人j执行任务i时的费用,并把c[i][j]和mincost分别初始化为c[1000][1000]和100000;同时把ask[i]和temp[i]、worker[i]的存储空间初始为task[1000]和temp[1000]、worker[1000],之后把其初始化为0.
(4)用Plan(int k,unsigned int cost)来对分配作业的解空间树进行搜索,搜
- 2 -