三、启发式方法

实际的生产线平衡问题的规模都是相当大的，多达 1000 多个工序或作业，200 多个工作地，用最优法求解这样的问题往往是不可能的，由此而产生了一类简单的算法——启发式方法：根据事先由具体实践经验而确定的某种相对合理的简单规则，仅探索与其相应的解（或方案），而不考虑其他可能的解。按某种规则得到的解,于某个特定的平衡问题，可能相当好，甚至可能是最优的，但不能保证总是最优的，由于这类算法简单、效果较好，而被广泛使用。

启发规则可以很多，各种规则的不同总在于：在向某个工作地分配工序或作业时，在所有可被考虑分配的工序或作业中，首先被考虑分配的工序或

作业不同。常用的规则主要有：

1. 最小后续作业数从其开始直到结束所有工序或作业数最小的工序或作业首先被考虑分配；

2. 最大后续作业数 从其开始直到结束所有工序或作业数最大的工序或作业首先被考虑分配；

3. 最小紧后作业数 紧接其后的工序或作业数最小的工序或作业首先被考虑分配；

4. 最大紧后作业数 紧接其后的工序或作业数最大的工序或作业首先被考虑分配；

5. 最短作业时间 作业时间最短的工序或作业首先被考虑分配；

6. 最长作业时间 作业时间最长的工序或作业首先被考虑分配；

7. 最先进行的作业 排序编号最前的工序或作业首先被考虑分配；

8. 最后进行的作业 排序编号最后的工序或作业首先被考虑分配；

9. 最大位置权数所在位置的权数最大的工序或作业首先被考虑分配；

10. 随机 工序或作业等可能（同概率）地首先被考虑分配。

启发式方法的求解过程，类似于树型寻求法，只是在向每个工作地分配工序或作业时仅按一种规则进行，使得树的分枝远远少于树型寻优法的分枝，即所得的可行解远少于树型寻优法的。所以，启发式方法的求解规模小， 速度快。在运用各种规则求解时，同样要满足二个基本约束条件：

1. 工序或作业问的先后顺序关系；

2. 不超过工作地的总的可用时间（周期时间 C）。

以下以最大位置权数规则为例说明其他启发规则的应用。

某工序（或作业）的位置权数，是指该工序以及其后所有工序的作业时间之和，表 11-18 给出了上表 11-15 或用 11-13 所述平衡问题的各工序的权数，一般将各工序按权数的大小从大到小进行排列，其中，工序 A 的位置权数为全部工序的作业时间之和（5＋3＋1＋7＋6＋4＋2＋3＋4＋2＝38）；工序 D 的位置权数为 D、C、H、I、J 五道工序作业时间之和（7＋2＋3＋4＋3

＝19）；⋯⋯。

表 11-18 工序及其位置权数

若给定周期时间 C＝10，则可按表 11-18 中谷工厅的仅置权数和图 11-13

表明的工序关系得到最大位置权数规则下的可行解树，如图 11-14 所示。该规则的可行解仅有一个，即为最终解，4 个工作地所分配的工序为：（A，C，

F）（D，B）（E，G）（H，I，J）时间闲置率 BD 为 5％（1 −

正好就是最优解。

38

4 × 10

），可见

其他规则下的求解过程类似于最大位置权数规则下的求解过 程，这里略去过程，仅将各规则下的最优结果之一列入表 11-14 中，随机规则下的解有多种可能，有好有坏，表中仅列出其中之一。

表 11-19 C=10 时各种启发规则对应的解

启发式方法已开发出软件，可在微机上求解。