文档介绍：一、流水作业排序
1．最长流程时间的计算
例:有一个6/4／F/Fmａx问题,其加工时间如下表所示,当按顺序Ｓ=(6,1,５,2,4,3）加工时,求Fmaｘ
解:列出加工时间矩阵
i
6
1
５
2
4
3
Pｉ1
3
４
８
6
５
４
Ｐi２
1
3
7
5
9
３
Ｐｉ3
８
7
5
９
6
２
Ｐi4
3
５
２
4
６
９
根据公式:
CｋSi＝ｍax{C(ｋ－１)Si, ＣｋSｉ-１}+ PＳｉk,计算各行加工时间,最后得出结果Fmaｘ＝Cmsn
Ｆmaｘ＝57
两台机器排序问题的最优算法（Johｎｓoｎ算法)
例:求下表所示的 6/２／Ｆ/Fｍax 的最优解
将工件2排在第1位 2
将工件３排在第6位 2 3
将工件５排在第２位 2 5 3
将工件6排在第3位 2 5 6 3
将工件4排在第5位 2 ５ ６ 4 ３
将工件1排在第4位 ２ ５ 6 1 4 3
最优加工顺序为S＝（2,５,6,1,4,3)
i
２
５
6
1
4
3
ａi
１
３
4
5
５
8
bｉ
2
7
4
7
4
2
由上表可计算出, Fmａx =２8
一般n/m/F/Ｆｍaｘ问题的最优算法
(一)Pａlmar算法(λi= ∑ ［ｋ-(m+１)／2］Pｉｋ ｋ=1,２,…,m 按λi不增的顺序排列工件 )
例:有一个４／3／F/Fｍaｘ问题,其加工时间如下表所示,用Pａlmａr求解.
解:λi= ∑ [k-(３+１）／2]Piｋ ,k=１,2,3
λｉ=－Pｉ1＋Pi3
于是,λ１＝-P11＋Ｐ13 ＝－１+４=３
λ２=-P2１+P2３ ＝=2+5＝3
λ3＝－P３1＋P33 ＝-6+8＝2
λ４=－P41＋Ｐ４３ =-３+２=－1
按λｉ不增的顺序排列工件 ,得到加工顺序(1,２,３,４)和（２,1,3,４),经计算,二者都是最优顺序,Fmax=28
（二)关键工件法
例:有一个４／3/F／Fmａｘ问题,其加工时间如下表所示,用关键工件法求解．
解:由上表可知,加工时间最长的是3号工件,Pi1<=Pi３的工件为１和２,按Ｐｉ1不减的顺序排成Ｓa=(１,2),Ｐi1>Pi３的工件为４号工件,Ｓｂ=（４),这样得到加工顺序为（1,２,3,４）。经计算,Ｆmａｘ=28
二、生产能力的计算
(一)、对于加工装配式生产,生产能力是一个模糊的概念。
大量生产,品种单一,可用具体产品数表示;
大批生产,品种数少,可用代表产品数表示;
多品种、中小批量生产,则只能以假定产