（机械设计及理论专业论文）柔性开放车间调度算法研究.pdf

柔忡开放下问闻度锋法研究 摘要 在制造领域，调度足生产管理的核心和关键技术，合理的调度可以缩短制造期、减 少资源浪费，提高经济效益。随着生产过程的h 益复杂和竞争的加剧，调度的作用越来 越重要。 柔性丌放车问渊度问题( f o s s p ) 是生产中常见的调度问题，也足亟待解决的高难 度组合优化问题。本文主要研究加工可中断、不可中断和具有机器使用限制三种情况下 的柔性丌放车f h j 渊度问题( o 册( p ) l p m m ，r i l c 所舯 0 ，则称j 攻e ( v ，w ) 为剩余弧。m 剩余弧组成的网络称为原网络g 的 剩余网络。若r ( v ，w ) = 0 ，则称弧e ( v ，w ) 为饱和弧。 在满足容量约束的i ，j 提下，寻找从源点到汇点的最大流量属f 最大流问题的研究范 畴。最大流问题是网络流理论研究的基本问题之一一5 1 ，它关注的足网络的最大化流通能 力，而不考虑流通的费用。 用线性舰划模型可将最大流问题表示为如下形式： m a x ( z 妒胞w ) ( 2 1 ) 约束条件： f ( v ，w ) 0 且为整数 f ( v ，w ) c ( v ，w ) 川f ( w ，v ) 一一f ( v ，w ) - o 2 1 2 最大流算法概述 ( 2 2 ) ( 2 - 3 ) ( 2 - 4 ) 按照原理的不同，可将常用的最大流算法分为增广路径法和预流推进法两大类，下 面简要介绍一下两种最大流算法的特点。 1 增广路径法 最大流l 、u j 题出现彳i 久，f o r d 和f u i k e r s o n i 就提m 了著名的最大流最小割定理，定理 指出网络的最大流等于最小割( 截集) 的容量之和。也就是浣，当网络达到最大流时，必 存在一个割集，此割集中的所有弧都达到饱和。 最大流最小割定理是一个非常重要的定理，在此基础上，f o r d 和f u l k e r s o n 二人提 出了基本增广路径算法1 。增广路径指在剩余网络中从s 剑丁的一条路径，它一定要经 过最小割集中的一条边。只要存在增广路径，就说明网络末达到最大流。若剩余网络中 不存在增广路径，就说明网络达到了最大流。这就是基本增广路径算法的核心思想，许 多学者对基本增广路径算法进行了改进，相继提出了容帚缩放增广路径算法一7 1 、最短增 广路径算法一8 叫和最大增广路径算法等算法一5 1 ，有关增广路径算法的详细介绍请参看上 述文献。 增广路径法的特点是沿从s 到7 1 的路径进行推流，所以路径的选择策略是影响算法 效率的关键冈素。此外，在最大流搜索过程中，网络中的流始终满足守恒约束。当多条 增广路径有公共弧时，算法要重复增加陔弧上的流，所以造成计算时i u j 的浪费。因此， 第2 审降l 论j 网络流荩本矢i i 识 当网络中公共弧较多时，会降低算法的效率，尤其是在大舰模网络中效率问题变得更加 突出。 2 预流推进法 为弥补增广路径法在效率方面的不足，k a r z a n o v ，j 提出了预流推进法，它的特点是 推流的对缘不是针对一条增j 。路径，而足针对一条弧。事先加入充足的流( 跟s 相连的 所有弧的容量之和) ，然后以弧为坼位按照弧的方向和网络结构向汇点推流，最后将多 余的流反向推回源点。 预流推进法的优点是能够高效的求解存在共用弧的网络最大流问题，但是对于一些 特殊网络，也会存在p i 退过多导致效率降低的情况。因此，预流推进法和增广路径法不 存在孰优孰劣的| 、u j 题，每种算法都有其计算性能较好和较筹的情况。在选择时，应根据 网络的特点确定具体求解算法。 本文建立的可中断柔性丌放车m 调度l u j 题的网络流模型具有分层、公共弧多等特 点，所以采用了预流推进法，设计了最大流求解算法。为了便于描述算法的步骤，本文 在2 2 3 小节将会详细介绍预流推进最大流算法的基本步骤。 2 1 3 预流推进最大流算法 在1 9 7 4 年，k a r z a n o v 提出了颅流的概念，用于解决分层网络的阻塞流问题。弧 e ( v ，w ) 的颅流f ( v ，w ) 是满足式2 5 和式2 6 的流： 。n 。，。一厂( v ，w ) 一。叱。，；一f ( w ，v ) o 0 厂( b w ) c ( v ，w ) ( 2 - 5 ) ( 2 6 ) 流从当日订顶点沿弧流到下一顶点的过程叫做推流。对于预流，顶点w 的盈余e ( w ) 定 义为： p ( w ) = = 。，。，。爿厂( v ，w ) 。，。，。一f ( w ，v ) ( 2 - 7 ) 由于源点s 没有输入流，所以e ( s ) 0 ；而汇点没有输出流，所以e ( t ) 0 。对于其 它顶点w ，如果e ( w ) 0 ，则称顶点w 为活跃顶点。如果网络存在活跃顶点，则说明预 流厂是不可行的。预流推进算法的基本思想就是通过将活跃顶点的盈余流昔推向它的邻 接顶点，消除活跃顶点，从而将流尽可能多的推向汇点7 1 ，使流厂成为可行的最大流。 般情况下，推流应该沿着距离丁最近的路径进行，所以为了衡量顶点与r 的距离，提 出了距离标号的概念： 1 9 哈尔滨i 样人予：博十。予：何论文 【定义2 2 】距离标号：距离标号简称标号，表示顶点v 与汇点丁的距离，用符号 l a b ( v ) 表示。 初始状态下，l a b ( s ) = i vl ，而其它顶点的距离标号都为0 。如果弧p ( v ，w ) 满足条件 l a b ( v ) = l a b ( w ) + l ，则称其为可行弧。在网络中，距离标号相刚的顶点构成一个层。如果 在两个连续的层f 和f + 1 之| 日j ，仪存在第f + 1 层中的顶点到第f 层中顶点的弧，称这样的 网络为分层网络。 预流推进算法的堆本操作是推流重标号p u s h r e l a b e l ，以函数的形式可以表示为： p u s h r e l a b e l ( v ) i f 存在可行弧( v ，w ) ，则执行如下操作： 在弧( v ，w ) 上推流，流值为m i n e ( v ) ，c ( v ，w ) ) 。 e l s el a b ( v ) = 1 + m i n l a b ( w ) ) ) 推流一重标号过程就是将活跃顶点的多余流量沿着可行弧推1 l i h t 号更低的顶点，若 不存存! 可行弧，则通过藿标号构建可行弧。 综上所述，基本预流推进算法的详细步骤为： s t e p l 初始化： s t e p l - 1 设网络所有弧的预流厂= 0 ； s t e p l 一2 对于所有e ( s ，v ) e ，f ( s ，) = c ( s ，v ) ； s t e p l - 3 设置标号：l a b ( s ) = ly i ，其它顶点标号设为0 ； s t e p 2 若存在活跃顶点，则执行如下操作： 选择一个活跃顶点v ； 调用函数p u s h r e l a b e l ( v ) ； s t e p 3 输出最大流结果。 以上介绍的基本预流推进算法l i 是预流推进算法的最基本形式，算法中活跃顶点 的选择具有任意性和随机性。为了进一步提高算法的效率，许多学者对活跃顶点的选择 方法进行了深入研究，先后提出了三种活跃顶点的启发式选择策略1 9 ”，具体为： ( 1 ) 先进先出：算法维护一个活跃顶点队列，优先从队列的头部丌始选择活跃顶点 进行推流操作，新检测到的活跃顶点加入到队列的尾部； ( 2 ) 最高( 最低) 标号优先：优先选择距离标号最高或最低的活跃顶点进行推流操作； ( 3 ) 盈余缩放：优先选择盈余“较大”的活跃顶点进行推流操作。 2 0 第2 章l 冬1 论j 网络流萆本知识 采用不同的活跃顶点选择策略，设计出了先进先出预流推进算法、最高( 最低) 标号 颅流推进算法和盈余缩放预流推进算法，这三类算法在实际中应用十分广泛。 文献 9 5 1 是- 目i ，j 最权威的网络流理论专注，本文中的相关概念和定理均参考文献 9 5 】。 2 2 网络流在调度研究中的应用 在应用研究中，发现许多实际调度| 、u j 题与网络流问题有联系，而有些表面上没有直 接联系的问题，也可通过图论、线性规划等方法把问题转化为最大流问题，这样就可以 通过最人流算法简化f u j 题的求解1 1 0 2 1 0 3 1 。目的，网路流理论在调度研究中有很多成功的应 用，例如： g h a r b i 和h a o u a r i ”0 4 1 住研究机器使用限制情况下多机调度问题的精确算法时，采用 最大流算法计算下界，对搜索树进行剪枝，显著提高了分枝定界算法的性能，试验表明 该算法能够解决7 0 0 x 2 0 规模的调度问题。 j a c e k 等人仍1 对可中断的同速平行机调度问题进行了研究，针对机器不可用时问窗 具有阶梯状关系的情况，探讨了最大延迟调度问题。作者根据工件i 叫无关的特点，建立 了调度问题的分层网络流模型，结合二分杏找求得了调度j 、u j 题的摄大延迟。 g u p t a 和r u i z t o r r e s ”叫研究了叮中断t - 行机渊度问题，提出了两个基于最人流算法 的启发式算法，二者的时l h j 复杂度均为o ( n 2 ) 。 喻小光等”0 7 1 为解决单件企业对柔性资源的高效均衡使用问题，设计了基于两级映射 网络的柔性资源模型，提出了网络最大流柔性资源分配模型的路径重连算法，可以有效 解决柔性资源分配问题。并通过数值实验，证明了该算法具有较高的求解质量和较好的 时问性能。 经过五十多年的研究，网络流理论发展得f 1 趋成熟，出现了许多优秀的算法，并且 在发展过程中不断吸收数学、计算科学和优化理论等学科领域的研究成果，所以可以说 网络流理论已经成为一利一解决线性优化问题的有效工具。随着网络流理论的不断完善， 以及调度研究的不断深入，网络流理沦在调度领域的应用将会更加广泛。 2 3 半匹配 2 3 1 基本概念 哈，j ： 宾i 科人。亍：f 辱1 _ 。：1 寺论丈 i i 【定义2 3 】赋权二分图：无向图g = 【ke ，w 足一个赋权二分图，若顶点集合v 可分割为两个互不相交的子集和圪，对r e 中任意边p = ( v ，v j ) ，均有v v i 和坎， 且每条边e 都对应一个杖。蕈瞰p ) 。 二分图是一类特殊的无向图，图2 2 为一个赋权二分图，边表示两个顶点问存在邻 接关系。为了进一步分析v i 和圪中顶点f b j 的二元关系，引出了匹配的概念。 图2 2 二分阁 f i g 2 2b i p a r t i t eg r a p h 【定义2 4 】匹配：边集合f c _ e 是图g 的一个匹配，若图g 中的每个j 页点鄙仅与 f 中的一条边关联。 由定义2 4 可知，图2 3 ( a ) 是合法匹配，任意两条边都没有公共顶点。而图2 3 ( b ) 是非法匹配，顶点和有两条关联边。 i a ) 止确的v 配 ( a ) r i g h tm a t c h i n g i b ) 错洪的v l 配 ( b lw r o n gm a t c h i n g 图2 3 二分幽的u l 配 f i g 2 3m a t c h i n g o fb i p a r t i t eg r a p h 【定义2 5 】匹配边：边e c ：f 称为匹配尸的匹配边，否则称其为f 的1 卜匹两己边。 【定义2 6 】饱和顶点：对于顶点v e ev ，若存在边e f ，使得v 与e 关联，! l ! i j 称v 为匹配f 的饱和顶点或匹配定点，否则称其为非饱和顶点或白山定点。 传统的匹配问题包括最大匹配和完美匹配两个： 第2 节蚓论j j 网络流萆本知识 【定义2 7 】最大匹配：f 是图g 的最大匹配，若g 不存在另一匹配f ，使得l f l 1 月。 【定义2 8 】完美匹配：f 为陶g 完荚匹配，若g 中的每个顶点都是f 的匹配顶点。 半匹配足上述摹本匹配问题的扩展，它放松了匹配边没有公共顶点的限制，允许一 个顶点子集中的顶点，以关联多条边，腼另一个顶点子集中的顶点只能关联一条边，它 的准确定义为： 【定义2 9 】赋权二分图的半匹配：对于给定赋权二分图g = 【v iu 圪，e ，缈】，设边 集f 为边集e 的个子集，若f 满足集合中任一顶点都与集合圪中的唯一顶点桐邻 接的条件，则称f 是g 的一个半匹配”0 8 l 。 图2 4 为图2 2 所示二分图的一个半匹配，由定义2 9 可知，一个二分图存在多个半 匹配。在某个目标函数下，最优半匹配是指使目标函数值极人或极小的半匹配。在构建 最优半匹配时，最常用到增广路径的概念。 【定义2 1 0 】交错路径：称在赋权二分图g 的半匹配f 和边集( e f ) 中交替取边 的路径为交错路径 【定义2 il 】增广路径：若交错路径的起点是半匹配f 的非饱和顶点，则称此变错 路径为增广路径。 _ 2 幽2 4 二分图的、i ，匹配 f i g 2 4s e m i - m a t c h i n go fb i p a r t i t eg r a p h 增广路径具有如下五个重要性质： ( 1 ) 增j “路径含有奇数条边： ( 2 ) 增广路径起点v 足非饱和顶点； ( 3 ) 增广路径的起点属于v i ，终点属于圪； ( 4 ) 增广路径不包含苇复的顶点； ( 5 ) 增广路径的所有奇数边都不属于原匹配，而所有偶数边都属于原匹配。 哈尔演i 科人j ! ；f ：博- i - ：何论文 将增广路径的所有奇数边加入到原半匹配f 中去，并把所有偶数边从原半匹配中删 除，通过这种增广路径的取反操作生成新的半匹配r 。从增广路径的定义i i 矢t l ，f 和 r 满足f 列关系： ri = lfi + 1 ( 2 8 ) 2 3 2 二分图半匹配的求解算法 目前，在二分图半匹配求解算法设计中，基于增广路径的算法是最基本的方法，原 因是这样就可以利用最大匹配和完美匹配等传统匹配i 口j 题在增广路径研究上取得的成 果。算法的基本过程为： 【算法2 1 】最优半匹配搜索基本算法 输入：赋权二分图g = 【u 圪，e 】和初始匹配f 。 输出：赋杈二分图g 的半匹配。 步骤： s t e p1 构造以非饱和顶点v e 5v l 为起点的增广路径p ； s t e p2 对p 进行取反操作，更新半匹配f ； s t e p3 若v l 中彳i 存在非饱和顶点，那么f 即为g 的半匹配，否则转到s t e pl 。 一般情况下，初始半匹配f 是一个空匹配。通过增广路径的取反操作，可以得到任 何二分图的半匹配。在实际应用中，人们关心的是最优半匹配，很多文献提m 了基于增 广路径的最优半匹配搜索算法，并且研究发现最优半匹配具有以下两个重要性质： ( 1 ) 最优半匹配中不存在费用减少增广路径。 ( 2 ) 最优半匹配一定包含二分i 割的最大匹配。 增广路径和最优半匹配性质的详细证明参看h a r v e y ”0 8 1 、l o w ”咀0 】和h a r a d a ”1 等学 者发表的文章。 2 4 半匹配的应用 半匹配i 、u j 题最早由h o r n 2 1 在1 9 7 3 年研究平行机调度问题时提出，此后的许多年罩 相关研究一直处于停滞不自，j 的状态。但是近几年半匹配理论研究取得了很多突破，无论 是普通二分图还足赋权二分图，理沦界都提出了多种最优半匹配算法。随着匹配和半匹 配理论的成熟，出现了一些成功的应用。f 歹, j o h ： 李文权等1 采用最大匹配算法研究了车站中的凋机作业调度问题，旨在提高凋机在 火车编组和取送牟组等作业的效率。文中将作业时| h j 交叉的多个任务表示为一个有向网 络，每个顶点代表一个仟务，调度算法要解决的l u j 题就足要将陔有f 旬嘲络分解为没自公 第2 节降j 论o j 网络流麟本知 ! 共弧的多条路径。为了有效解决网络分解问题，作者通过对偶定理，将问题转化为偶l 刘 的最大匹配问题，通过最大匹配算法缺点每台调机需要完成的任务。 此外在t d m a 通信中，信息的传输通道是由多个无线传感器升l 成的分层网络，要 求各传感器顶点以最短的时l l j j 将收到的数据传输至7 l 聚顶点，从而实现多对一的汇聚传 输。为了高效的传输信息，需要解决两个予问题：( 1 ) 根据传感器网络，构建信息传输 树；( 2 ) 分配传感器，使信息尽快传输至汇聚顶点。其中，构建信息传输树足实现信息 高效传输的基础，b a l j e e t 等人4 1 提出了基于半匹配的最短时问信息树建立方法，具有过 程为：给定一个信息传输时间下界，以传感器顶点到汇聚顶点信息传输时问尽叮能接近 下界为目标，通过二分图的半匹配确定传感器顶点i 日j 的信息传输关系，得到传输时问最 短的信息传输路径，进i 而构建出信息传输树。 2 5 本章小结 本章针对柔性丌放牟l 日j 调度算法设计的需要，介绍了网络流与匹配理论的相关知 识，为后续各章节的展丌和调度算法的介绍做好准备。首先，介绍了网络流的概念、可 行流的性质和主要的最大流算法，重点阐述了预流推进最大流算法的暴本思想及其基本 流程；然后，介绍了半匹配理论中的重要概念，包括赋权二分图、匹配、交错路径和增 广路径等，并在给m 最大匹配和完美匹配等皋本匹f l 己f o j 题的基础上，重点介绍了最优半 匹配问题的特点和基了二增广路径的最优半匹配搜索算法。 哈尔演i ：烈人学博卜学伊论文 第3 章可中断柔性开放车间调度算法研究 3 1 引言 本章的研究对象是可中断的柔性丌放车问调度问题( p r e e m p t i v eo p e ns h o p s c h e d u l i n gw i t hm u l t i p r o c e s s o r ，p o s s m ) ，以制造期最短为优化目标。为使研究成果更具 有普遍性，假设工件含有就绪t 付l u j 约束，即在工件就绪之前不能对其进行加工。当所有 工件在调度丌始就可以加工时，调度问题就退化为没有就绪时i 日j 约束的情况。g r a h a m 等人5 6 】用三参数法( “汐i y ) 表示调度问题，其中a 域表示工厂类型，域表示约束条件， y 域表示优化目标。采用此法，可将j 中断柔性丌放车问调度问题表示为0 脚( p ) p m t n ， ，l ( _ 甜。其中，d 表示，i ：放车问，m 表示m 种操作，尸表示含有平行机；p m t n 表示加 工过程可中断，_ ，表示= t ：件具有就绪时i i i j 约束；( 甜表示调度优化目标为制造期最短。 可中断是0 ，( p ) t p m t n ，厂| g 煅问题的最大特点，由此导致最优调度解并不是唯一的。 只要能够保证机器都满负荷工作，这样的渊度解就足接近最优的。本章采用这种求解思 路，采用机器资源分配和：1 ：件排序二阶段算法解决o , ( p ) p m t n ，| ，i 巳似问题。具体过程为： 首先，建立以制造期最短为优化目标的混合整数规划模型，将0 册( 尸) p m t n ，n lg 槲问题 的各项约束转化为混合整数规划模型中的约束条件。然后，通过整数规划模型与网络流 模型的本质对应关系，将前者转化为网络流模型，求得的最大流即为资源分配结果。为 解决最大流陷入局部最优、导致出现工件集中的| u j 题，本章给出了最大流优化算法。在 此基础上，通过构造加工时i 兀j 矩阵的减量集合，确定工件的加工顺序。最后，通过理论 分析和算例试验证明了算法的i f 确性和可行性。 3 2 统( 尸) i p m t n ，厂，l 乙问题描述及其混合整数规划模型 3 2 1 现( 尸) i p m t n , 厂名，问题描述 0 坍( p ) p m t n ，| 厶甜问题可以表示为：车问中有m 种功能的机器，每种功能的机器 含有m ( m 兰l ，= 1 ，2 ，啪) 个同速平行机，符号m ( j = 1 ，2 ，聊；k = 1 ，2 ，m ) 表示具 有功能的第七号机器。设工件集合为j = ，如厶 ，工件z 的就绪h , j f b j 为，需要 完成，c u ，三脚) 种操作，符号0 表示工件z 的第项操作，同一r ：件的各操作问没有加工 顺序要求。为了简化| 口j 题，本文假设，i = 0 ，且r ，川。在调度之前已知各操作的加工时 问，使用符号p “( 正整数) 表示操作d 的加工时l 、n j 。 o , ( p ) l p m t n ，e l ic t ，。甜问题允许加工中断，这极大降低了问题解决的难度。例如，可 以中断操作d 川的加：1 ：过程，更换机器后马上继续力i ii ：操作0 “，或者更换机器后加：l 2 6 第3 节可r l 晰柔。件开放下问i i 5 | f 变芹法f i j l ：究 此工件的其它操作o “u 笱) 。为了简化问题，本文假设所有中断都发生在整数时刻， 并且中断加工和更换机器所花费的时i 日j 为0 。 凋度的目标是通过合理的确定工件的加：l ：机器和加工顺序，使 件集合，的制造期 最短，并要求i j 一时刻，一台机器只能加工一个工件；| 一j 一时刻，一个工件只能进行一 种加工操作。 3 2 2o m ( p ) i p m t n , 厂，i 如，问题的混合整数规划模型 在0 卅( p ) p m t n ，r , l c m 甜l 、u j 题中，可埘：【件z 进行加工的最早时间为，在此之 j ，不 能对其进行任何操作，由此可知不同时刻可加工的工件集合是不刖的。为了确定可加工 工件集合随时问的变化情况，本文采取以f 方法： 对工件的就绪时i 日j 进行排序”，并删除重复值，得到一个升序的时i 日j 序列产 ，j ， = l ，2 ，1 ) ，其中t t t l + l ，a = i t i 冬门，并假设t l = 0 。显然，只有在t t 处j 会有新的工件就 绪，而当即 ， “l 的时侯，可加工的工件集合不会发生变化。 在序列t 的最后捅入时i 日j 点t a + l ，使工件集合的制造期( 甜满足条件“ 0 ，d o ( ) 卜1 9 ( m ) ： ，t m no m 铺、) 一r a i ni e ( m c ( m i o m n 0 、； p ( m ) 卜p ( m ) 一( 尬，o m 甜) ； e o o m n 0t e 0 0 m n 0 + f i 、m l ，o m 似、) ： 谴f l 、m | ，( ) m d 。、) = a 4 。d o 胃口。甜为堵塞顶点： e n di f e n di f e l s e 置为堵塞顶点； e n df o r e n dw h i l e s t e p4 按照f i f o 原则对d 层和层的活跃顶点进行推流； s t e p5 按层反向推流( 7 _ s ) w h i l e 网络中存在活跃顶点fa n d 没有可行弧，d o l a b ( i ) 卜r a i n l a b ( j ) + 1 i ( f ，) 彳) ； 在弧( ，) 上推流； e n dw h i l e s t e p6 输出最大流结果。 3 6 机器上工件的加工排序算法 最大流算法只求得了工件在每个时问窗中占有特定机器的时问长度，而并无法确定 工件的加工顺序，或者说足无法确定工件的加工丌始时l 日j 。本章使用文献 6 8 1 提出的基 于加工时l 开j 矩阵和减量集合的方法解决这个问题，可以确保工件i 司时只能进行一种加工 操作。在介绍排序方法之前，首先定义些概念： 【定义3 6 】加工时间矩阵：每个时问窗中操作加工时间组成的矩阵为加工时1 1 j j 矩 阵。 哈，j ： 毒i 十￥人予：f 弹十j 予：1 市论文 - f t i ；i ；i ；i ；i i ；i ；i ； 【定义3 7 】紧行( 列) ：如果加：。 时l 日j 矩阵的某行( 列) 的和等于时i b j 窗的长度，则 称其为紧行( 列) ，否则称其为松驰行( 列) 。 【定义3 8 】减量集合：加工时问矩阵中的一个非零元素子集为减量集合，若其包 含每个紧行和紧列中的一个元素，至多含有一个松弛行或松弛列中的一个元素。 排序算法的主要操作是选择一个时| 玎j 长度，对减最集合的每个元素，机器慨加 工工件z 的时i 日j 等于m i n ( x f ，k l ，) 。然后，更新加工时l u j 矩阵，对应元素减为m a x ( o ，x q k l 一) 。 设c 一为时| 日j 窗占，中各机器的总加 ：时i b j 与工件总加工时f 日j 的最大值，为了保证排序 的合理性，的选择遵循以下原则： ( 1 ) 要小于减量集合中属于紧行和紧列的元素； ( 2 ) 对于减量集合中属于松弛行和松弛列的元素，的取值要满足式3 1 6 和式3 1 7 ： a _ x n 盯+ c | ：i 孙一2 x 。， ( 3 1 6 ) g 州+ q a x - ：俐x i i ( 3 - 1 7 ) ( 3 ) i z n 黝n 一1 2 时| 日j 矩阵中第i 行或第列f i 包含减量集合中的元素，则的取值要满 足式3 18 和式3 1 9 ： 。一二x i 彬 ( 3 l8 ) a 瓯。一：x q “ ( 3 - 1 9 ) 综上所述，基于加工时f j p l 阼和减量集合的排序算法町以表示为： 【算法3 2 】工件的加工排序算法 输入：各时i b j 窗工件的加工时问矩阵 输出：每台机器上工件的加工顺序 步骤： s t e p1 建立原始加工时间矩阵； s t e p2 若加工时i 日j 矩阵中所有元素均为0 ，则结束：否则，计算所有行和列的和， 确定紧行和紧列： s t e p3 建立加工时i 口j 矩阵的减茕集合； s t e p4 根据式3 1 6 3 1 9 确定的最大值； s t e p5 根据值更新加工时i 日j 矩阵，转s t e p 2 继续执行。 镐3 市可中断柔件开放下i 开】i 嘲窿铮浃 i j l = 究 3 7 玩( 尸) l p m t n 厂，i 厶问题调度算法的性能分析 3 7 1 调度算法的时间复杂度分析 作为调度算法的核心，最大流算法决定了调度算法的时f h j 复杂度。根据文献【1 1 9 】 可知，最大流算法的时间复杂度主要由推流操作的数日决定。本章提出的最大流算法利 用了网络的拓扑结构特点，按层推流，所以讨箅出每层的最大推流数f 1 ，然后) r hj ：i l 即可 得到最大流算法的最大推流数目。 山网络的定义可知m 层共有：n ，个顶点，0 层共有胆m 个顶点，层共有门个顶 点。显然，在前向推流时，各层问推流操作的次数至多为： ( 1 ) m 层一( ) 层：t x m x ：。，次： ( 2 ) 0 层一j 层：行m 次； ( 3 ) ，层一7 1 层：玎次； 在反向推流时，各层州推流操作的次数全多为： ( 1 ) 层一d 层：”所次； ( 2 ) o 层一m 层： x m ：n ，次； ( 3 ) m 层弼层：，n ，次： 冈此，本章提出的最人流算法的时间复杂度为：o ( 2 n m ( i + - 、t n ：。n ，) + ：n ，+ n ) 。 3 7 2 调度算法的最坏情况界 设最优调度解的制造期为。，显然。满足式