对枚举树的某些节点必须分支决策,即凡是界限小于迄今为止所有可行解最小下界的任何节点,都有可能作为分支的选择对象。目前对于分支而言,主要有以下两种方式。 FBMH1608HM221-T

   (1)从最新产生的最小下界分支。从最新产生的各子集中选择具有最小下界的节点进行分支。这种分支法优点是节省空间,但缺点是需要较多的分支运算,耗费的时间较多。

   (2)从最小下界分支。每次算完界限后,把枚举树上当前所有节点的界限进行比较,找出界限最小的节点,此节点即为下次分支的节点。优点是检查子问题较少,能较快地求得最佳解,缺点是要储存很多子节点的界限及对应的耗费矩阵,花费很多内存空间。在调度问题的研究上,分支定界算法一直是最重要的算法之一,例如,本章参考文献[13~16]分别提出不同的分支定界算法,它们的不同主要表现为分支规则、定界机制和上界3个方面的差异。但是所有分支定界算法的主要缺陷在于缺乏足够的下界以保证分支程序具有理想的效率。虽然很多有效的分解程序被提出以解决加快搜索,但仍要大量的计算去解决大规模复杂的调度问题[叼。本章参考文献Ⅱ8~23]最先系统地研究具有滞留时间约束下的双臂集束型装各调度问题,并提出基于各种特定分支规则的分支定界算法。