二、树型寻优法

求生产线平衡问题最优解的方法有多种（如线性规划法、动态规划法）， 树型寻优法是其中的一种较为简易直观的方法，它将工序（作业）关系图（网络图）变换成为一种“树”将工序（作业）表示为树中的“结点”。在给定周期时间（节拍）C 的值的条件下，求得工作地数量 N 最小的工作地安排。其寻优过程如下（树型寻优法已开发有软件，可在微机上求解）：

1. 根据工艺流程，绘出所有工序的网络图（结点式图）

2. 根据网络图和给定的周期时间乙将工序依次分配给各工作地，同时得到关于所有可行方案的树型图，分配方式如下：

从最早进行的工序开始，将其分配给第 1 个工作地，与其平行的或紧接

其后的工序都为树的第 1 级可能的结点，在分配给该工作地的总作业时间不超过工作地可用时间（给定的周期时间 C）的条件下，向该工作地分配一个工序，即可在第一道工序与下一个分配的工序间建立起一节“链”，其后进行类似的分配，直到第 1 个工作地的可用时间分配使用完为止；在第：个工作地的未端，按照上述第一个工作地的分配方式为第二个工作地分配工序； 其后工作地的分配，类似进行，直到所有的工序全部分配完毕为止，得到一棵完整的“倒树”。

1. 根据“倒树”，对所有从“尾”到“头”的链进行比较，可将其最

短的“链”（工作地数量门最小）对应的分配方案作为最优方案（可能有多个）。一般是将其工作地数量刀最小，且相应的各工作地实际所用时间的方差最小的方案为最优方案。

按下列规则寻优时，可以简化过程：

1. 在对某一个特定工作地分配工序时，修剪其作业时间超过工作地尚未分配时间的任何结点（工序）；

2. 按（1）修剪掉的结点（工序）不能在同一工作地的任何下一级分配；

3. 在同一个工作地，如果从一个分枝得出具有相同的工序但次序不同的两条链时，则修剪掉其中多余的链，仅保留一条链。

表 11—15 给出了一个有 10 道工序的生产线平衡问题，规定周期时间 C 为 10（分钟）。按树型寻优法的过程和规则，先得到如图 11—10 所示的网络图，再得到如图 11—11 所示的树型图，最后得到的可行解（方案）有五个， 如表 11—16 所示，其中，1、2 和 5 号解都有最少的工作地数（4 个），所以这三个解均为最优解，其时间闲置率最小，为：

BD = 1 −

38

4 × 10

= 5%

但，三个最优解中，2 和 3 号解较 1 号解有更为均衡的工作负荷分配，即各工作地所用时间的方差最小。

表 11—15 工序、时间和相互关系

对于上述的例子，如果在一定的范围内依次改变周期时间 C 的值，作类似上述的寻优，可分别得到各个 C 值下的最优解。由“瓶颈工序时间和总工序时间约束”，该问题的循环时间 C 的可行范围为：

max**｛**t i **｝≤**C**≤** ∑*ti* **即**7**≤**C**≤**38**。**

i=1

表 11-17 给出了 C＝7，8⋯⋯，19 时的最优解汇总表，图 11-13 绘出了相应的时间闲置率曲线。C＝19（n＝2）时，生产线达到完全平衡，即有 BD

＝0（C＝38，n＝1 时，也是完全平衡，但这种特殊情形无实际意义），完全平衡意味着所有工作地都按周期时间 C 进行工作。完全平衡在实际中是很难实现的，对于手工生产线有可能实现，而对于机械生产线则难上加难。

表 11-17 周期时间 C＝7-19 的最优解汇总表

根据时间闲置率曲线图，可以在特定要求限制下，选择一个相应的最佳方案。（1）规定周期时间为某个值时，确定最佳的工作地分配，如 C＝14 时，则 n＝3，工作地的情况为（A ，D，C）（E，F，B）（G,H，I,J）。（2） 规定工作地数，确定最佳的周期时间，如 n＝5 时，则 C＝8。（3）工作地数和周期时间都不规定，确定最佳的工作地数和周期时间数，如选 N＝2、c＝ 19（此时 BD＝0）或 n＝3，c＝13（此时 BD＝2，6％很小）或 n＝4，c＝10

（此时 BD＝5％较小）或 n＝5,c＝8（此时 BD＝5％较小），这四种选择对应着 BD 曲线的四个极小点，当然，n＝2、c＝19 对应其中的最小点。