二、任务委派方法

（一）任务委派的一般程序

任务委派方法，一般说，在厂部把订货任务委派给车间或某一加工中心时，与“生产周期法”相似。也就是按照上述每项订货的周期进度表和订货进度计划，选摘出相应的任务分派到相应的车间或加工中心，同时也就确定该单位的负荷量。在委派任务时，必须掌握下列资料，逐步进行。

1. 根据每项订货的零部件清单所列的种类和数量，以及每种零部件的工艺路线所列出的工艺顺序，按照各车间所能完成的工艺，如焊接车间、冲压车间、机加工车间等，把任务分派给有关车间。

2. 根据工艺设计所规定的每道工序或综合的工时定额，确定该项订货在某一车间或加工中心所应完成的工作量，即负荷量。工作量一般以定额工时为计量单位。

3. 根据车间或加工中心同类设备的数量，生产工人人数和工作时间，以及所能完成的工时定额系数，计算出该车间或加工中心在某一段时间内（如某一月），以定额工时为单位的正常生产能力。

例如某冲压车间有 5 台冲压机床，开两班，每班工作 8 小时，定额完成系数为 120％，那么该车间每日的正常生产能力就是 5×8X2X120％＝96 定额工时。假定上述订货，03-1、03-2、03-3 三个零件都要经过冲压制造，其定额工时合计为 384 工时。则该车间完成该项订货的负荷量为 384÷96＝4 天， 即占用 4 天的正常生产能力。

1. 按照订货进度表中规定的每个加工阶段的开始和完成日期，把订货分派的负荷量和现有的正常生产能力进行平衡，反映出已安排了多少生产能力，尚余多少能力，负荷有否多余，能否再安排任务，以便继续接受和安排新的订货任务。如果负荷已经饱满，就要采取措施，进行调整。

委派任务和确定负荷量一般可用甘特图法进行。在甘特图上要表明各车间已安排的订货和已接受的负荷量，如下图 15-5 所示

图 15-5 委派任务和确定负荷量甘特图

图中，A、B、C、D、E 是订货单编号，如从某一个月开始看，冲压车间已有四项订货，已有 22 天的负荷量。如果一个月只有 22 天工作日，则负荷量己饱满，在该月就不能再接受订货。锻造，小件和大件加工的负荷仍有余力，但装配已经超负荷。假如 E 项订货可迫至下期交货，则问题不大。否则就要采取措施，如加班，才能使负荷平衡。

（二）匈牙利法

在委派任务中，特别是车间把任务委派给工段和机床，常常可以有几种类型的工艺设备可以完成同种工艺。例如普通车床、六角车床、普通铣床等都可以完成某种工艺，但它们的效率和成本对不同的零件工艺加工却不同。因而就有一个如何择优分配问题，使总的效率最佳或成本最低。这可以运用线性规划求解。常用的和较为简便的方法有两种，即“匈利牙法”和“分伎界限法”。

匈利牙怯的要求，一般是加工任务的项数和能完成这些任务的机床类型数相等，并且每类机床只能委派一项加工任务。其演算方法举例说明如下：

假设某一加工小组，接到四项订货 A、B、C、D。有四台机床 M1、M2、M3、M4，都可以加工。但每台机床对不同订货所耗的定额工时不同，列表如下（见表 15-1）。在任务委派中要求达到所耗总工时最少。

表 15-1 工时定额表（小时）

其演算步骤如下：

1. 将矩阵表进行行列变换。即使每一行和每一列至少有一个“0”元素。首先用每一行的元素减去该行的最小元素；行变换后，再用每一列的元素减去该列的最小元素。如上例

行变换后的矩阵为（见矩阵 1）

1. 作“0”的覆盖线。用最少线段覆盖所有的“0”元素，检查是否己得出最优委派方案。如果覆盖线的数等于矩阵阶数时，就是己得出最优方案。如果少于矩阵阶数时，则未得出最优方案，需要继续进行下面第三个步骤。如上例，矩阵（2）中只需用三条线就可以覆盖所有“0”元素，因此未得到最优方案，需要作第（3）步演算。

2. 再增加“0”元素。在已演算出的矩阵（2）中选出未被覆盖的最小元素，如上例是 2，将未被覆盖的元素减去这个最小元素，同时处在覆盖线交叉点上的元素加上这个最小元素，其余元素不变，形成新的矩阵（见矩阵

3）。

1. 再在新矩阵（3）中作覆盖线，结果已达到矩阵阶数，即得到最优方案。否则，回到第三步继续进行。如上例，见矩阵（3），最少覆盖线是 4 条，已可得最优方案。

2. 作业分派。根据已得出的最后矩阵，按行或列中只有一个“0”元素的先分配，作记号△，逐次进行。如上例第 2、4 两行只有一个“0”元素， 故 B 分配给 M4，D 分配给 M2。这一来 C 只好分配给 M1，A 分配给 M3。见矩阵 4。

分配结果，所用工时总数是 2＋1＋4＋3=10 工时，效率最佳。

（三）分枝界限法

分枝界限法对于委派任务较多，可委派的单位也较多的情况下，比匈牙利法较佳。因为在这种情况下，运用匈牙利法，其迭代次数会很多，反而不易求解，但分枝界限法的比较复杂，应用较难。

分枝界限法，简略地可按以下 4 个步骤进行。兹举例说明如 下： 1.建立问题的下限（或上限）。

所谓问题的下限是指完成全部工作最少必须耗费多少工时或成本，即最低限度；上限是指完成全部工作最多能获得多少收益或利润，即最高限度。任何方案的设立都不可能低于下限或高于上限。如果能达到这个最低或最高限度，这个方案就是最理想的。但一般说很难达到这个上下限，只能是尽可能接近这个限度。

例如有 A、B、C、D、E 五项订货，需要分派给 M1、M2、M3、M4、M5，五部机床加工。其工时定额如表：15-2 所示。

表： 15-2 工时定额表

求问题下限，就是把上表 15-2 每行的最小元素，即工时定额最小的加总起来，意思是指完成全部订货最小要耗用的定额工时。本例是：

下限＝17 十 8 十 14 十 7 十 9＝55（工时）

但是要达到这个下限是不可能的。虽然 D 和 E 可以分别在 M3 和 M1 上加工，但 A、B、C 却都要在 M2 加工，而 M4 和 M5 却没有任务。而我们只有一台M2 只能加工一项订货，又不愿 M4 和 M5 闲置。因此，这是一个不可行解。如果是可行解，就可得到最理想的委派方案。

1. 将可能委派的方式进行分割，寻找最优解。

上例有 5 项订货分派给 5 台机床，就有很多方式，按照排列组合方式有5！＝120 种，不可能一一列举。分枝界限法就是把数量很多的可能委派的方式进行分割，把范围尽可能缩小，把不需要的分枝舍弃，以较快的方法找出最优的方案。

一般的做法是：假定把各项任务分配第一台机床开始。这时有五种分派方式，即 A 分配给 M1 或 B、C、D、E 分配给 M1，有五种方案。然后计算出每种方案的工时总数，如下表 15-3 所示

表 15-3 把任务分配给 Ml 的工时总数表

工时总数的计算方法是：将某项订货分配给 M1 的工时后，再加上未分配任务的机床对其余订货加工的最小工时，就是该方式的工时总数。如表 15-3 所示，把 A 分配给 M1，它的工时是 40，余下的 M2、M3、M4、M5 就选择在 B、C、D、E 四项订货中工时最小的元素加总。如 M2 在 B、C、D、E 四项订货中， 最小工时为 8，拟加工 B；M3 是 7 拟加工 D；M4 是 17 拟加工 E，而 M5 是 30， 也拟加工 D，这就同 M3 也要加工 D 重复，C 却无人加工。这就是不可行解。如果把 B 分配给 M1，按其余的最小加工工时分配，则 C 一 M2，D 一 M3，E 一M4，A 一 M5，可以把任务分配下去，这是一个可行解。其余类推。表 15-3 中有两个可行解，工时总数均为 113 工时，有三个不可行解，其中最小的工时总数是 91 工时。我们把可行解中工时总数最低值称为上限，本例是 113。如果以后求解过程中比这个上限高的可行解都不要，而回到这个可行解上来。然后，从其余的不可行解中选出工时总数最小的方案，本例是 91，即把 E 分配给 M1 的方案，其余的不可行解舍去，即将 A 分配给 M1，D 分配给 M1 这两个方案不再继续研究，只保留 E 分配给 M1 这个方案，割去大部分分枝。分枝界限法的优点就在这里。我们把不可行解中的总工时最小的数值称为下限，本例为 91，同可行解中的最小值（即上限）113 进行比较。如果下限大于上限， 则这里的可行解就是最优解，意思是即使再往下寻找下去也不会找出比这个数值再低的方案。如果上限大于下限，本例是 113＞91，就是从 91 这个分枝， 即从 E 分配给 M1，这个分枝中寻求最优方案。分枝界限图如图 15-6 所示。

图 15-6 分枝界限图

1. 在已定的第一段委派方式的基础上，从既定的分枝开始，进一步寻求最优解。

其方法与第 2 步基本相同。第一·已得出把 E 分配给 M1，开始寻求最优解，在这个前提下，把 A、B、C、D 分配给机床 M2 的可能方案，并分别计算这四个方案的工时总数，进行分枝，如表 15-4 所示。

表 15-4 分配给 M2 的工时总数表

从表 15-4 中看出，C 分配给 M2 是可行解，工时总数 97。B 分配给 M2 是不可行解，但其工时总数为 94，小于 97，与上法一样，从 B 分配 M2 这个分枝中再寻找最优解，其余舍去。

同上法演算下去，E 给 M1，B 给 M2，余下是 A、C、D 三项订货如何分派蛤 M3M4M5 的问题。先分派给 M3，如表 15-5 所示。

表 15-5 分配给 M3 的工时总数表

1. 得出最优委派方案

到这里，从表 15-5 中可以看出，D 分配给 M3 是可行解，数值为 97 最小， 并且小于不可行解的 139，因此，不需再继续寻找最优方案（否则仍要继续进行）。这就是最优解。再回头来检查一下，见上图 15-6，C 分配给 M2 的方案，其数值也是 97，可见有两个最优方案可供选择。即方案 1 是 E→M1，C

→M2，D→M3，B 一 M4，A→M5，其工对总数是 9＋14 十 7＋42 十 25＝97。方案 2 是 E→M1，B→M2，D→M3，C→M4，A→M5，其工时总数力 9＋8＋7＋4s

＋25＝97。

换言之，当可行解上限都小于或等于不可行解下限时，这个可行解就是最优解。

匈牙利法和分枝界限法在任务委派中具有科学性，广为应用，但也有其局限性。一般用于规模较小的车间、工段。对于规模较大的工厂和车间，若干订货交错进行，就不能直接应用。但可应用其原理，用选择法，根据经验， 利用甘特图进行委派。