2024年4月30日发(作者：)

流水线作业排序问题

/productioncontrol/

流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零

件，遇到的就是流水作业排序问题。我们说加工路线一致，是指工件的流向一致，并不要求

每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工，则设相应的

加工时间为零。

一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。但本节要讨论

的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问

题。流水作业排列排序问题常被称作“同顺序”排序问题。对于一般情形，排列排序问题的

最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和

3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的

最优解。

这里只讨论排列排序问题。但对于2台机器的排序问题，实际上不限于排列排序问题。

一、最长流程时间Fmax的计算

这里所讨论的是n／m／P /Fmax，问题，其中n为工件数， m为机器数，P表示流水线作

业排列排序问题，Fmax为目标函数。目标函数是使最长流程时间最短，最长流程时间又称

作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台

机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(ri=0， i= 1，

2，„，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最

长完工时间Cmax。

设n个工件的加工顺序为S＝(S1，S2，S3，„，Sn)，其中Si为第i位加工的工件的代号。

以 表示工件Si在机器 M k上的完工时间, 表示工件Si在 Mk上的加工时间，k= 1，2，„，

m； i=1，2，„，n，则 可按以下公式计算：

在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。下面以一例说

明。

例9．4 有一个6／4／p／F max问题，其加工时间如表9—6所示。当按顺序S=(6，1，5，

2，4，3)加工时，求 Fmax 。

解：按顺序S=(6，l，5，2，4，3)列出加工时间矩阵，如表9-7所示。

按式(9．1)进推，将每个工件的完工时间标在其加工时间的右上角。对于第一行第一列，只

需把加工时间的数值作为完工时间标在加工时间的右上角。对于第一行的其它元素，只需从

左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右

上角。对于从第二行到第m行，第一列的算法相同。只要把上一行右上角的数字和本行的

加工时间相加，将结果填在加工时间的右上角；从第2列到第n列，则要从本行前一列右上

角和本列上一行的右上角数字中取大者，再和本列加工时间相加，将结果填在本列加工时间

的右上角。这样计算下去，最后一行的最后一列右上角数字，即为，也是Fmax。计算

结果如表9-7所示。本例 Fmax =46。

二、n/2/F/ F max 问题的最优算法

对于n/2/F/ F max 问题，F 表示流水线作业排序问题。著名的Johnson算法是S．M．Johnson

于1954年提出了一个有效算法。为了叙述方便，ai以Ji表示 在M1上的加工时间，以bi 表

示Ji 在M2上的加工时间。每个工件都按M1 → M2的路线加工。Johnson算法建立在

Johnson法则的基础之上。Johnson法则为：如果

min(ai , bj )

则Ji应该排在Jj之前。如果中间为等号，则工件i既可排在工件j之前，也可以排在它之后。

按式(9．3)可以确定每两个工件的相对位置，从而可以得到n个工件的完整的顺序。但是，

这样做比较麻烦。事实上，按Johnson法则可以得出比较简单的求解步骤，我们称这些步骤

为Johnson算法。

Johnson算法：

(1)从加工时间矩阵中找出最短的加工时间。

(2)若最短的加工时间出现在M1上，则对应的工件尽可能往前排；若最短加工时间出现在

M2上，则对应工件尽可能往后排。然后，从加工时间矩阵中划去已排序工件的加工时间。

若最短加工时间有多个，则任挑一个。

(3)若所有工件都已排序，停止。否则，转步骤(1)。

例9．5 求表9-8所示的6／2/F／Fmax 问题的最优解。

解：应用Johnson算法。从加工时间矩阵中找出最短加工时间为1个时间单位，它出现在

M1上。所以，相应的工件(工件2)应尽可能往前撑。即，将工件2排在第1位。划去工件2

的加工时间。余下加工时间中最小者为2，它出现在M2上，相应的工件(工件3)应尽可能

往后排，于是排到最后一位。划去工件3的加工时间，继续按Johnson算法安排余下工件的

加工顺序。求解过程可简单表示如下：

将工件2排第1位 2

将工件3排第6位 2 3

将工件5排第2位 2 5 3

将工件6排第3位 2 5 6 3

将工件4排第5位 2 5 6 4 3

将工件1排第4位 2 5 6 1 4 3

最优加工顺序为s=(2，5，6，1，4，3)。求得最优顺序下的Fmax=28。

i

ai

bi

工时计算

i

ai

bi

2

1

3

5

4

10

6

8

14

1

13

21

4

18

25

3

26

27

2

1

2

5

3

7

6

4

4

1

5

7

4

5

4

3

8

2

三、一般n／m／P／F max 问题的启发式算法

对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的

流水车间排列排序问题，可以用运筹学中的分支定界法。用分支定界法可以保证得到一般n

／m／P／F max 问题的最优解。但对于实际生产中规模较大的问题，计算量相当大，以至

用计算机也无法求解。同时，还需考虑经济性。如果为了求最优解付出的代价超过了这个最

优解所带来的好处，也是不值得的。

为了解决生产实际中的排序问题，人们提出了各种启发式算法。启发式算法以小的计算量得

到足够好的结果，因而比较实用。下面介绍用Palmer法求一般n／m／P／F max问题近优

解的启发式算法。

1965年，D．S．Palmer提出按斜度指标排列工件的启发式算法，称之为 Palmer法。工件

的斜度指标可按下式计算（计算每工件（按列）的加工时间，然后进行递减排序）：

式中，m为机器数；pik为工件i在Mk上的加工时间。

按照各工件λi不增的顺序排列工件，可得出令人满意的顺序。

例9．6 有一个4／3／F／F max 问题，其加工时间如表9-9所示，用Palmer法求解。

解：对于本例，式(9-4)变成（因为过机器2时，k-(m+1)/2的值始终为0，所以不考虑）：

λi =－Pi1＋Pi3

于是，λ1 = －P11＋P13=－1＋4=3

λ2 = －P21＋P23=－2＋5=3

λ3 =－ P31＋P33=－6＋8=2

λ4 = －P41＋P43=－3＋2=－1

按λi 计算结果递减的顺序排列工件，得到加工顺序(1，2，3，4)和(2，1，3，4)，恰好这

两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下， F max =28。