流水线作业排序问题
流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。
一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作“同顺序”排序问题。对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。
这里只讨论排列排序问题。但对于2台机器的排序问题，实际上不限于排列排序问题。
#p#副标题#e#
一、最长流程时间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，则 可按以下公式计算：
#p#副标题#e#
在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。下面以一例说明。
例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。
#p#副标题#e#
二、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 )<min( aj , bi) (9.3)
则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。
#p#副标题#e#
三、一般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)变成：
λ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。
