第十一章 流水作业的排序问题

流水线作业排序问题/productioncontrol/200908091604.html流水作业排序问题的基本特征是每个工件的加工路线都一致。

在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。

我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。

如果某些工件不经某些机器加工，则设相应的加工时间为零。

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

但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。

这就是排列排序问题。

流水作业排列排序问题常被称作“同顺序”排序问题。

对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有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所示。

机械制造行业中的流水作业排序问题一、生产作业计划与流水作业排序问题假如某个车间需要生产n种零部件,这n种零部件需要经过m台设备进行加工,并且每种零部件在每台设备上的加工时间各不相同.那么怎样编排这n种零部件的加工顺序可以使总加工时间最短，这是排序要解决的问题。

一般说来，排序只是确定工件在机器上的加工顺序，而编制生产作业计划，则不仅包括确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间和完工时间。

可以说解决好排序问题是顺利完成生产作业计划的保障.二、排序问题的表示方法通常我们用4个参数来表示不同的排序问题，4个参数表示法为:n/m/p/Fmax其中,n为零部件数，m为设备（或机器数），p表示流水作业排列排序问题，Fmax则表示目标函数，通常是使其值最小。

流水作业排序问题的基本特征是每个零部件的加工路线都一致，并且每个零部件在每台设备上的加工顺序都相同。

我们所说的加工路线一致，是指零部件的流向一致，并不要求每个零部件必须经过加工路线上每台设备加工.如果某些零部件不经过某些设备加工，则设相应的加工时间为零。

上述公式是一个递推公式，在熟悉这个计算公式之后，可以直接在矩阵上计算完工时间。

某车间生产的产品符合4/3/p/Fmax问题，其加工时间如下表所示：如果车间按照S=（1，2，3,4)的顺序组织生产，按照上述公式递推，将每个零部件的完工时间标在其加工时间的右上角。

对于第一行第一列,只需要把加工时间的数值作为完工时间标在加工时间的右上角。

对于第一行的其它元素，只需从左到右依次将前一列右上角的数字加上本列的加工时间,将结果填在计算列加工时间的右上角.对于第二行到第m行，第一列的算法相同.只要把上一行右上角的数字和本行的时间相加,将结果填在本行加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本列上一行右上角数字中取大者，再和本列加工时间相加,将结果填在本列加工时间的右上角。

这样最后一行的最后一列右上角的数字即为Fmax。

-、流水作业排序1. 最长流程时间的计算例：有一个6/4/F/Fmax 问题，其加工时间如下表所示，当按顺序 加工 S=(6, 1, 5, 2, 4, 3) 时,求Fmax工件代号i 14 6 35 2 P 订 4 5 3 4 8 5 P 「23 9 1 3 7 5 PQ7 6 8 2 5 g563924解：列出加工时间矩阵根 据 公式Gsi 二max{Gk-i )si , C KSM }+ P sik,计算各行加丄时间，最后得出结果 Fmax=CmsnFmax=572•两台机器排序冋题的最优算法(Johnson 算法)例：求下表所示的6/2/F/Fmax 的最优解将工件2排在第1位 2将工件 将工件 将工件将工件将工件 3排在第 5排在第 6排在第 4排在第 最优加6位2位 3位5位4位2 56 1 4 S=(2, 5, 6, 1,4,33由上表可计算出，Fmax =283.—般n/m/F/Fmax问题的最优算法(一)Palmar算法(入i二刀[k-(m+l)/2]P ik k二1, 2,…,m按入i不增的顺序排列」】件)例：有一个4/3/F/Fmax问题，其加工时间如下表所示，用Palmar求解.解：入i二刀[k-(3+l)/2]P ik , k=l,2 , 3入i二-Pil+ Pi3于是,入1=-PU+ P13 =-1+4=3入2二-P21+ P23 =2+5二3入3二-P31+ P33 =-6+8=2入4二-P41+ P43 =-3+2二T按入i不增的顺序排列工件，得到加工顺序(1, 2, 3, 4)和(2, 1, 3, 4 )，经计算,二者都是最优顺序，Fmax=28(二)关键工件法例：有一个4/3/F/Fmax问题，其加工时间如下表所示,用关键工件法求解.3■ ■Pa Pit 24解：由上表可知，力口 u工时间最长的是3号工件，Pil<=Pi3的工件为1和2,按Pil不减的顺序排成Sa=(l,2),Pil>Pi3 的工件为4号工件，Sb= (4),这样得到加工顺序为(1,2, 3,4 )。

第11章（8分）将下面程序划分为基本块，并画出其基本块程序流图。

(1) if a<b goto (3)(2) halt(3) if c<d goto (5)(4) goto (8)(5) t1:=y+z(6) x :=t1(7) goto (1)(8) t2:=y-z(9) x :=t2(10) goto (1)11.1答：所谓代码优化即对代码进行等价变换，使得变换后的代码与变换前代码运行结果相同，而运行速度加快或占用存储空间少，或两者兼有。

进行优化的基础是中间或目标代码生成，以及基本块的识别、控制流分析和数据流分析。

2答：根据不同的阶段，分为中间代码优化和目标代码的优化。

根据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化。

3答：最常用的代码优化技术有：（1）删除多余运算（2）代码外提（3）强度削弱（4）变换循环控制条件（5）合并已知量和复写传播（6）删除无用赋值4 图11.23是图11.22的C代码的部分四元式代码序列(1) 请将图11.23的四元式代码序列划分为基本块并做出其流图?(2) 将每个基本块的公共子表达式删除?(3) 找出流图中的循环,将循环不变量计算移出循环外?(4) 找出每个循环中的归纳变量，并且在可能的地方删除它们图11.22void quicksort(m,n)int m,n;1 / 10{ int i,j;int v,x; if (n<=m) return;/* fragment begins here */ i = m-1;j = n;v = a[n];while(1) {do i = i+1;while (a[i]<v);do j = j-1; while (a[j]>v);if (i>=j) break;x = a[i];a[i] = a[j];a[j] = x;}x = a[i];a[i] = a[n];a[n] = x;/* fragment ends here */ quicksort (m,j);quicksort(i+1,n);}图11.23(1) i:=m-1(2)j:=n(3) t1:=4*n(4) v:=a[t1](5) i:=i+1(6) t2:=4*i(7) t3:=a[t2](8) if t3< v goto (5)(9) j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)if t5> v goto (9)(13)if i >= j goto (23)(14)t6:=4*i(15)x:=a[t6] (16) t7:=4*i(17) t8:=4*j(18) t9:=a[t8](19) a[t7]:=t9(20) t10:=4*j(21) a[t10]:=x(22) goto (5)(23) t11:=4*i(24) x:=a[t11](25) t12:=4*i(26) t13:=4*n(27) t14:=a[t13](28) a[t12]:=t14(29) t15:=4*n(30) a[t15]:=x答：（1）1-4为第1块，5-8为第2块，9-12为第3块，13句为第4块，14-22为第5块，23-30句为第6块。

一、 问题描述给定n 个作业，每个作业有两道工序，分别在两台机器上处理。

一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。

一个作业只有在机器1上的处理完成以后才能由机器2处理。

假设已知作业i 在机器j 上需要的处理时间为t[i,j]。

流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。

二、 算法分析n 个作业{1,2,…,n}要在由2台机器1M 和2M 组成的流水线上完成加工。

每个作业加工的顺序都是先在1M 上加工，然后在2M 上加工。

1M 和2M 加工作业i 所需要的时间分别为t[i,1]和t[i,2], n i ≤≤1.流水作业调度问题要求确定这n 个作业的最优加工顺序，使得从第一个作业在机器1M 上开始加工，到最后一个作业在机器2M 上加工完成所需的时间最少。

从直观上我们可以看到，一个最优调度应使机器1M 没有空闲时间，且机器2M 的空闲时间是最少。

在一般情况下，机器2M 上会有机器空闲和作业积压两种情况。

设全部作业的集合为},....,2,1{n N =。

N S ⊆是N 的作业子集。

在一般情况下，机器1M 开始加工S 中作业时，机器2M 还在加工其他作业，要等时间t 后才能利用。

将这种情况下完成S 中作业所需的最短时间计为),(t S T 。

流水作业调度问题的最优解为)0,(N T 。

1. 证明流水作业调度问题具有最优子结构设a 是所给n 个流水作业的一个最优调度，它所需要的加工时间为']1),1([T a t +。

其中，'T 是在机器2M 的等待时间为]2),1([a t 时，安排作业)(),......,3(),2(n a a a 所需的时间。

记)}1({a N S -=，则我们可以得到])2),1([,('a t S T T =。

事实上，有T 的定义可知])2),1([,('a t S T T ≥.若])2),1([,('a t S T T >，设'a 是作业集S 在机器2M 的等待时间为]2),1([a t 情况下的一个最优调度。