（运筹学与控制论专业论文）带成组加工的三阶段柔性流水作业加工问题.pdf

上海大学硕士学位论文 摘要 本文首次研究了以下三阶段柔性流水作业问题，其中阶段1s m 。台同 型机组成，阶段2 为一台批处理机，可同时加工若干个工件，而阶段3 由m ： 台同型机组成。加工工件必须依次经过阶段1 、阶段2 和阶段3 。以c 。为 极小化目标函数。对这种n p h a r d 问题，在加工工件分别满足u n f i x e d 和 f c d 的条件下，我们讨论了其中各阶段机器加工时间服从d d m 、i d m 、i d d m 和d i d m 的四种情况下的所有结果，并给出了相应的启发式算法及其性能比 分析。 关键词：柔性流水作业，同型机，专用机，批处理机，近似算法，性能比。 v l 上海大学硕士学位论文 a b s t r a c t t h i sp a p e rf i r s ts t u d i e st h ef o l l o w i n gt h r e es t a g e sf l e x i b l ef l o w s h o ps c h e d u l i n g p r o b l e mw i t hm l i d e n t i c a lp a r a l l e lm a c h i n e si ns t a g eo n e ，ab a t c hp r o c e s s o rw h i c h c a ns i m u l t a n e o u s l yp r o c e s ss o m ep r o d u c t si ns t a g et w oa n dm 2i d e n t i c a lp a r a l l e l m a c h i n e si ns t a g et h r e e a n yp r o d u c t sm u s tp a s st h r o u g ht h et h r e es t a g e si nt u r n m i n i m i z i n gt h ec i so u ro b j e c t i v e f o rt h i s a r dp r o b l e m , w h e np r o d u c t s s a t i s f yt h ec o n d i t i o no fu n f i x e da n df i x e d ，t h ea u t h o r sg i v eh e u r i s t i e sa n de s t i m a t e t h e i rw o r s t c a s ep e r f o r m a n c er a t i o sc o r r e s p o n d i n gt ot h ec a s e si nw h i c ht h ej o b s p r o c e s s i n gt i m e si nt h r e es t a g e so b e yt h ed d m 、i d m 、i d d ma n d d i d mr o l e s k e y w o r d s ：f l e x i b l ef l o w s h o p ，i d e n t i c a lm a c h i n e s ，d e d i c a t e dm a c h i n e ，b a t c h p r o c e s s o r , a p p r o x i m a t ea l g o r i t h m ，w o r s t - c a s ep e r f o r m a n c e r a t i o 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：兰盏! 型e t 期：丝z 磊：! f 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) i l l 上海大学硕士学位论文 第一章绪论 在本章中，我们首先简单地介绍一下有关排序问题的背景和基础知识，对本文所讨论的 排序问题进行解释并给出其已有的相关进展，最后对本文中所用到的符号和记号做一简单说 明并给出本文所获得主要结论。 1 1 排序问题简介 1 1 1 排序问题 排序理论是运筹学中的一个重要分支，虽然它是2 0 世纪5 0 年代初期才刚开始被研究， 但近5 0 年来得到了广泛重视，有着深刻的实际背景和广阔的应用领域。在市场销售、生产计 划、库存管理、运输问题、人事管理、计算机和信息系统、工程的优化设计等许多方面有着 广泛的应用。 概括地讲，排序是利用一些机器( 如设备、计算机的资源) 在执行某些任务( 如产品加 工、程序运算等) 时在某些限制条件下( 如工件的到达时间、完工截止时间、优先约束、机 器对加工时间的影响等) ，寻找一最优加工方式以使某或某些目标函数达到最优。它是“投 入最少，产出最优”的一种组合优化过程。由于排序问题最早是在机器制造领域提出来的， 因而排序问题各要素的描述沿用了机器制造中的术语。即机器( m a c h i n e ) 、工件( j o b ) 和目 标函数( o b j e c t i v ef u n c t i o n ) 这三要素组成了各种排序问题 排序问题中的约束条件，主要指工件或作业的性质以及工件在被加工过程中受到的限制， 同工件相关的一些变量常有 ( 1 ) 工件歹，的加工时间向量p ，- p v ，p 2 ，p = i ，其中毋是工件，在机器 毛上所需 要的加工时间 1 上海大学硕士学位论文 ( 2 ) 工件- ，j 的到达时间( a r r i v a lt i m e ) 或准备时间( r e a d yt i m e ) 0 ：它表示工件，可开始 加工的时间如果所有工件的准备时间相同，取- 0 ，一1 ，2 ，一 ( 3 ) 工件，的应交工时间( d u ed a t e ) d ，当d ，- d ，- 1 2 ，n 时，则d 是n 个工件的 共同应交工时间 ( 4 ) w ，。工件- ，的权因子，表示工件，的重要程度 j | 序文献中通常令： c ，：表示在序中工件j 的完工时间 0 一c j d ，：表示在序中工件，的迟后 e j m a x 0 ，d ，一c ， ，常称为工件，的超前。 t - m a x 0 ，c ，一d ，常称为工件，的延误。 工m a x 。! 紫蚤仁，) ：表示序中n 个工件的最大迟后( m a x i m u m l a t e n e s s ) c 。：表示序中工件的最大完工时间，它等于序中最后一个完工工件的完工时间 对任一排序问题，国际上通常采用g m h 锄e ta 1 ( 1 9 7 9 ) 【1 1 的三参数法来表示，即用 口i 卢ir 来表示，其中： 口：指机器环境 机器可以是单台，也可以是多台对多台机来说，按照功能可分为两大类；即平行机 ( p a r c e l ) 和专用机( d e d i c a t e d ) 。前者又可分为三类：( 1 ) 不同机器的加工速度完全一致， 且不依赖于工件，称为同型机( i d e n t i c a l ) ，记为p ；( 2 ) 不同机器具有不同的m t 速度，但其 速度并不依赖于工件，称为同类机( u n i f o r m ) ，记为q ；( 3 ) 机器的加工速度依赖于被加工工 件，不同的工件即使在同一台机器上也可能有不同的速度，称为异型机( u n r e l a t e d ) ，记为r 。 对于专用机来说也分为三类：( 1 ) 流水作业( f l o w - s h o p ) ，记为f ( 2 ) 自由作业( o p e n - s h o p ) 记为o ；( 3 ) 异序作业( j o b - s h o p ) ，记为j 。 2 上海大学硕士学位论文 一：特定的加工限制和约束 常出现的加工限制和约束有：工件j 需准备时间，有应交工时间，工件问存在偏序关系 ( 优先加工约束，p f ) ，对工件的加工允许中断继续( p r m p ) ，加工工件的机器一旦加工就 不允许出现空闲( n o - i d l e ) ，被加工的工件不允许在两相邻机器之间等待( n o - w a i t ) 等 y ：目标函数 目标函数一般根据实际需要来确定，在捧序序问题中常用的极小化目标函数有： c 一工一再c ，再_ 以及带权因子舶标函数如荟”，c ，再嘱等 1 1 。2 复杂性与近似算法 研究最优化问题往往涉及到算法复杂性以及n p 完全性的有关理论，这多少已经成为了 一种标准。1 9 7 1 年c o o k 的“t h ec o m p l e x i t yo f t h a n r e mp r o v i n gp r o c e d u r e s ”【2 】和1 9 7 2 年k a l p 的“r e d u c i b i l i t y a m o n gc o m b i n a l o r i a lp r o b l e m s ”【s - 论文为n 卜完全理论奠定了理论基础 n 卜完全理论涉及p ，n p 、n p - - c o m p l e t e 、普通意义下的n p - - - c o m p l e t e 和强h p - - c o m p l e t e 等各种概念。有关概念可参见g a r e ya n dj o h n s o n ( 1 9 7 9 ) 1 4 一书。就闯题的复杂性而言。后 者比前者的求解难度增加，精确解也难以找到( 因而出现找近似解的方法) ，其中最简单最重 要的区别是所谓的多项式时间算法和指数时间算法的区别，其算法之间的异同以及变化也是 n 卜完全理论的核心和基本准则。对某一组合最优化问题，若我不到解它的有效算法( 多项 式时间算法) ，根据n 卜完全理论。就要及时转向试着证明它是p 一加以的一旦知道问 题是翘，一h a r d 的，由n p 完全理论，人们可立即另辟蹊径转向寻找可供选择的合适算法。 许许多多的组合优化问题被证明是p 一加尼，甚至是强n p h a r d 的。二十世纪7 0 年代计算复杂性的n 卜完全理论创立后，人们逐渐意识到排序问题不可能存在大范围内的统 一算法，每一个排序问题必须充分利用其本身结构作不同处理，这一时期排序研究主要出现 3 上海大学硕士学位论文 了二种趋势：一是对给定具有舰，一加耐性质的捧序问题提出各种形式的动态规划解法和分 枝定界算法等以获得精确解；二是对某一具有p 一妇以性质的捧序问题，从获得近似解的 角度提出各种启发式算法，并对这些一般仅需要多项式时间的算法进一步做性能比的理论分 析。其中途径二更具有理论意义和实用价值 对某一问题f 及相应算法a ，如对于f 的任何实例，该算法a 给出的解的目标函数为 4 ( ，) ，而该问题的最优值为o p t ( i ) 。如果总有4 ( ，) = 0 p r ( j ) ，那么彳就是最优算法，否 则a 就是近似算法。衡量一个近似算法的好坏主要有两个标准；( 1 ) 算法的时问复杂性；( 2 ) 算法的近似程度。一般总是力求找出既快速且近似程度又尽可能好的近似算法。 为衡量一个算法的近似程度，常通过算法的性能比( w o r s t - c a s ep e r f o r m a n c er a t i o ) 来描述。 设a 是某极小化问题f 的近似算法，如存在p 己1 ，使得对于f 的任何实例i ，均有： a ( i ) p o p t ( i ) ，则称算法4 的性能比为p 。如p 能达到，则称此性能比为紧的要证 一性能比为紧的，通常是举一能达到此性能比的实例。 1 2 本文所研究的问题 流水作业是排序研究中的一个经典问题，排序问题研究的第一个重要结果就是 j o h n s o n 0 9 5 4 ) 5 为问题f 2 1 l c 一所构造o ( n l o g n ) 时间算法，而问题f 30 c 。已为 n p h a r d i 拘( g a r e y e ta 1 ( 1 9 7 6 ) 【6 】) 。自j o h n s o n 的工作以来，人们对问题砌i i c 。及各种 变形作了大量研究，获得了丰富的成果，在此我们只简要介绍同本文有关的二类问题的研究 成果，且仅涉及目标函数c 。 1 2 1f s m p 问题 一类为如下所述的f s m p ( f l o ws h o pw i t hm u l t i p l ep r o c e s s o r s ) 问题：个工件，需依次 通过k 个阶段加工，在每一阶段有若干平行机可履行该阶段任务，每一工件在每一阶段至多 4 上海大学硕士学位论文 只需在一台机器上加工记这样的问题为凡。，m 2 ，m i ) 0 ，其中k 为阶段数，m j 指第 i 个阶段有m j 台平行机o - 1 , 2 , - - - 七) ，为目标函数如果任一工件在每一阶段只需在该阶段 平行机中的任一台上加工，则称这样的问题为f s 帅n f i x e x l 问题；如果任阶段的平行机为 专用机，即任一工件在每一阶段只能在其指定的机器上加工，则称这样的问题为p s m p - - f i x c d 问题。 若每阶段的平行机为同型机( t i pf s e d 问题) 。对这类问题： h o o g e v e e ne t a l ( 1 9 9 3 ) 【刀证明了当m a x m l ，m 2 2 时，f 司h f 2 ( m l ，r a 2 ) i l c 。为强n p h a f d 雕j a r t h a n a r ya n dr a 残1 9 7 1 ) 【8 】对问题，2 ( 2 力0 c 一构造了一分支定界算法。 r a o ( 1 9 7 0 ) 9 、n a r a s i m h a na n dp a n w a 岫“1 9 8 4 ) 【1 0 】对问题，2 q 2 ) 0c 一分别构造了近似算法 对问题f 2 ( 2 舯i n o w a i t i c = u 和f 2 ( l 2 ) l n o w a i t i c 。，s r i s k a n d a j j a h ( 1 9 9 3 ) f 1 1 】指出利用 g n 哪e dg 伽r “1 9 6 4 ) 【1 2 解- f 2in o w a i t c 一的算法来解他们可得2 且该上界为 精确的( 其中，和厂。分别为算法所得的加工全程和问题的最优加工全程) 对肺2 的问题f 2 ( 掰，m ) i i c ，d e a l a n d h u n a n c k e r ( 1 9 9 1 ) 1 3 制- t 目标函数的下界。 s h e na n dc h e n ( 1 9 7 2 ) 1 4 ，b u t e na n ds h e n ( 1 9 7 3 ) 1 5 和l a n g s t o n ( 1 9 s 7 ) 1 6 对其分别给出了近似 算法。而s r i s k a n d a r a j a ha n ds e t h i ( 1 9 8 9 ) 1 7 结厶l i s t 算法( g r a h a m ( 1 9 6 6 ) 1 8 ) 与j o h n s o n 算 法( 1 9 5 4 ) 【5 】构造了算法h 。、致和也，分别得到乒t 3 一砉、s r ( 其中 争委s 一丢，和卿一3 对问题f 2 ( m l ，m 2 ) l ic 。，l e ea n d 、蛐让t a l a k 畋1 9 9 4 ) 【1 9 】和1 3 0c h e n ( 1 9 9 4 ) 2 0 名r 自在 d l o g n ) 时间内给出了近似算法。 均得到2 一丽1 若每阶段的平行机为专用机，则产生了另一类型的f s m p 问题( 即f s m p - - - f i x e d 问题) 5 上海大学硕士学位论文 对这类问题，目前研究的比较多的是所谓a f s ( m s e m b l y - t y p ef l o w s h o ps c h e d u l i n g ) 问题： l e ee l a l 0 9 9 3 ) | 2 q a , 虑了 a f s 问题f 2 ( 2 舯0 c ，其中阶段1 组成于二台专用机m 和 m ，阶段2 仅具一台总装机肼2 ，工件j i 组成于二个元件，h 和- ，m ，在阶段1 ，这二个元 件，k 和j m 在二台专用机m 和m 6 上分别加工，其所需时问分别为p * 和p m ，此二元件均 加工完后才能在机器m 2 上总装。其所需时间为p 要求适当排列它们的加工顺序使c 。最 小i _ e e e ta 1 ( 1 9 9 3 ) 【2 1 l 证明了此问题为强朋- h a r d 的，并给出了几个多项式时间可解的例 s u ne ta 1 0 3 ) 【2 2 】对a f s i 掘f 2 ( m , 1 ) 0 c 一证得，若s 二，s 五。，s 二i ，为 一最优序，对阶段1 给定的最优序s 二，s 二，s 二，如在阶段2 应用炳 ( f i r s t - c o m e - f k s t - s e r v e d ) 规则得文，则相应建的加工全程不大于相应的s ；加工全程。利 用这一性质、j o h n s o n 算法( 1 9 5 4 ) 【5 1 和g 1 p t a ( 1 9 韶) 【2 3 】解二阶段柔性流水作业中的基本思想和 最坏情况分析，给文给出了一系列1 4 个近似算法。数值例子表明，这些算法能解现存近似算 法不能解的最坏例子，并能解随机产生的9 0 0 0 个例子。故是强有力的 t o z k a p a ne ta 1 ( 2 3 ) 【2 4 】考虑了a f sf 司题f 2 ( m ，1 ) l l w ，c 对此问题文中做了以下几 方面的工作： ( 1 ) 证得存在置换序形式的最优解； ( 2 ) 利用w s p t 规则和l w r ( l a r g e s tw e i g h tr u l e ) 估计了问题的下界 ( 3 ) 给出了部分序间的优势准则； ( 4 ) 估计了问题的上界： ( 5 ) 最后又结合( 1 ) 一( 4 ) 给出了一分枝定界算法并作了数值计算。 1 2 2b i 问题 另一类为如下所述的b l ( b u m 蛐问题，此类排序问题是由l e e e ta 1 ( 1 9 9 回【2 5 1 首先引进的， 这类问题最常见的模式是有n 个工件需进行老化测试，其中元件，j 的到达时问、至少加热时 6 上海大学硕士学位论文 间和应交工时间分别为0 、p ，和d j ( ，仙2 ，玎 ) 一炉子以成批方式加热( 老化测试) 这些元件，炉子一次至多加热b 个工件，且在这过程中无元件进出，各元件占有炉子容积相 同，炉子加热某批元件所需时间为其中所有p 最大者要求将这n 个元件适当分批加热以使 某目标函数，达最小值，记次模式为1 i 脚i ，如具m 台同型机则记为砌i b i i ，。如在流 水作业的某些阶段采用这类分批加工则记作砌( e ，岛，以) j 肼i ，( 其中垦指第f 个阶段 级机器至多同时加热且个元件) s u n g a n d c h o u n 8 ( 2 o ) 嘲为问题1 l b i l c 一构造t - - o ( n l o g n ) 时问算法，并对序给定 的问题1 i 脚，r ，i c w 构造了一多项式时问的最优算法如各元件的容积不同，u z s o y ( 1 9 9 4 ) 2 7 证明t i - 题1 i 彤i c 一为朋- h a r d 的，并对其构造了近似算法。 对口一m 时的问题1 l 彤，r ji c 。，l d u z “1 9 9 6 ) 【2 8 】给出了一个d 0 2 ) 时间算法 对一般问题1 i 町，r ji c 。，【船a n du z s o y ( 1 9 9 6 ) f 2 8 】给出了多个有效的近似算法， j ua n dy u ( 2 0 0 0 ) 【2 9 】也对其构造了一个性能比为2 的贪婪算法，s u n ga n dc h o u n g ( 2 0 0 0 ) 2 6 为其构造了 动态规划解法和几个性能比为2 的近似算法 1 2 3 本文研究的问题 对f s m p 和m 问题作独立形式的研究如上所述已有很多成果，除此以外。s o e w a n da n d e l m a g h r a b y ( 2 0 0 1 ) 在【3 0 】中给出了，3 ( 小l ，m 2 ，m ，) 0 c 。的几个算法，其中最好的性能比为 1 0 3 一l m a x r t h ，b ) 一1 ，3 码。但以往研究的均为各阶段的平行机都为单处理机即任一机器 在任意时刻至多只能对一个工件作加工。而在下面的例子中将会看到f s m p 问题中存在着某 阶段需批处理机加工的情况。同这种新型加工方式略为有关的是s u n ga n dm n ( 2 0 0 0 ) 在p 1 】 中对肼3 0 ( 即二阶段加工) 的一个特殊的f s p 问题( 阶段1 为一台单处理机，阶段2 为 一台批处理机) ，相应一共同应交工时间的n 个工件的提前与延误之和的极小化问题，在不同 条件下分别构造了多项式时间和伪多项式时间算法。 7 上海大学硕士学位论文 而f s m p 和b i 问题二者的结合少有人问津，何龙敏【3 2 】【3 3 1 研究了带批处理机的二阶段 f s m pf 掘f 2 ( m l ，b ) 0c 。，和f 2 ( b ，m 1 ) 0c 。，前者阶段2 为一台容量为b 的批处理机， 后者阶段1 为一台容量为b 的批处理机，构造了相应的近似算法并估计了性能比。 本文研究的问题归属于，3 1 ，m 2 ，m 3 ) i i c 。其中阶段1 、3 各具m l 、m 3 台同型机， 而阶段2 仅具一台批处理机。这类问题的实际背景是：在机械加工中，随着原材料和产品的 不同，他们的加工方式也不同。如以钢材为原料的齿轮加工，往往要经过下列三阶段工艺流 程：切削加工 热处理( 调质) 产品包装。而以铸件为原料的零件加工，往往又要经过 以下工艺流程：清砂 热处理( 退火) 切削加工，以上第一和第三阶段往往在加工车间 中完成，而第二阶段在热处理车间里成批处理。本文对于这些加工时间满足一定规律的问题 进行了抽象研究( 简记为f 3 。，b ，m 2 ) 0c 。相应问题定义如下：有n 个工件需依次通过 三阶段的流水加工，其第一阶段有m l 台相同机器，且均可加工任一工件，一工件只需在任一 机器上作加工，工件j 在阶段1 所需的加工时间为p 可第二阶段为一台批处理机，一次可以 同时处理不超过口个工件，任一工件在该阶段的加工时间为p w p 6 第三阶段有历2 台相同 机器条件同阶段一，工件j 在该阶段的加工时间为p d 一工件一旦在一机器上开始被加工， 中间不可中断直到该工件在该机器上被加工完。而任一机器在任一时刻至多只能加工一个工 件。要求所有工件在第三阶段的最后完工时间最小。 a h m a d i 等人( 1 9 9 2 ) 在【3 4 1 中证明了，3 0 b 国i 彤，p 2 j - p 2 i c 一已是强p h a r d 问 题了，而即使所2 - m 3 一o 的问题，p m ii i c 。也为p - h a r d 酗j 3 5 1 因此在p n p 的假 设下，对本文所研究的问题不可能找到多项式时间算法，本文相应不同的情况构造了近似算 法并作了性能比分析，其中第二章给出各阶段的工件加工时间满足d d m 、i d m 、i d d m 和d i d m 规则时相应u n f i x e d 问题的一些结论，第三章分析了同样条件下的f i x e d 问题，最后给出结论。 1 2 4 规则与记号介绍 8 上海大学硕士学位论文 定义1 ：m 。，m 6 ：指m i n ：，- 1 , 2 ；咐2 m 觚：，- 1 , 2 , - 町 d d m ( d i 埘i g 辩舾o fd o m i n a t i n gm a c h i n e s ) ：指工件在各阶段的加工时间满足 m l m 2 m _ i d m ( i n i n gs e r i e s o fd o m i n a t i n gm a c h i n e s ) ：指工件在各阶段的加工时问满足 m l m 2 m _ i d d m ：指工件在各阶段m i ( f 一1 ，2 m ) 的加工时间先满足i d m 规则，后满足d d m 规则。 d i d m ：指工件在各阶段m f ( f - 1 ，2 ，肌) 的加工时间先满足d d m 规则，后满足i d m 规则 定义2 ：f o e ( n ，b ) 规则：n 个工件分批时，第一批有意一 b 1 一垆个工件，其余 ( p n 一l 、批都满批，e pb 个工件 定义3 ：l o e ( n b ) 规则：n 个工件分批时，前( 卜，丑1 1 ) 批都满批，最后一批有 雄一( p s 1 一i ) b j t 定义4 ：f a m ( f i r s ta v a i l a b l em a c h i n e ) 删：指任一可加工工件放在最先可加工的机器上 c 一( 日) ：表示按照算法h 加工所需的全程时间 c l ( h ) ：表示按照算法h 加工第i 阶段所需的全程时间 c 二| i ：表示问题依最优加工所需的全程时间 g ：表示厶0 c 。问题的最优值 c ；：表示己：0 c 。问题的最优值。 为简单起见，不妨我们简称第一阶段为a 阶段，第二阶段为b 阶段，第三阶段为c 阶段， ( 分别简记p 可，p 坷，p 奇为4 ，b ，c ) 并假设口l 七a 2 七七a 。 1 3 本文所获结论 本文的所有结果可见表1 1 和表1 2 注：( 1 ) 表中定理、性质、算法和算法h 的性能比分别简记为t h 、p r o 、h 、r x ( 2 ) 表中符号x 表示多种情况的集合。 口 上海大学硕士学位论文 ( 3 ) 三参数法中口域中省略了成组加工的符号j l ，其在口域中已有符号口表示了 表1 1 f 3 ( m 1 ，b ，坍2 ) i z ，u n f i x e d ，b j - b l c 。问题的结果( 同型机) f 3 ( 肼i ，b ，m 2 ) i d d m ，u n f t x e d ，b b i c 。 序号参数算法计算量 性能比 1 m ls b ，b m 2 h 2 1d m l o g n ) r n 5 3 - 1 3 鸭( t h 2 1 ) 2 m l b ，b m 2 眈1d 0 l o g n ) 如7 3 - 1 3 m t ( t h 2 2 ) m l 鲥2 h 2 2 5 3 - 1 3 n h ( t h 2 3 ) 3 m 1 b ，b m 2d 伽l o g n ) , r f l 堋2 h 2 3 舀7 ，3 一l ，3 i ，h ( t h 2 3 ) 4 册l 丑，b t l l 2 1 1 2 1 d m l o g n )嘞1 0 3 1 机( t h 2 4 ) 5 弹m i l l b l ，b ，掰2 ) 1 1 2 1 d q l o g n )s 4 3 ( p r 0 2 1 ) f 3 ( m l ，b ，m 2 ) i i d m ，u n f i x e d ，b j b i c 。 由定理2 5 ，参考f 3 ( m l ，b ，m 2 ) i d d m ，u n f i x e d ，b j - 6 i c 。的情况把此时的，m 2 视为 f 3 ( m l ，b ，m 2 ) i d d m ，u n f i x e d ，b j - b i c 。中的小2 ，打l l 可得相对应的算法，计算量性能比都相同 f 3 伽l ，b ，m 2 ：i i d d m ，u n f i x e d ，6 j - b i c 。 序号参数算法计算量性能比 1 m l b ，b m 2 1 1 2 。10 伽l o g n ) 略! ；7 3 1 孤 紧( t h 2 6 ) 2 m lz b ，b s m 2 1 1 2 4 d o i o g n )r 3 2 紧( t h 2 7 ) 研l b ，b m 2 ，n ，口3 紧( t h 2 8 ) 3 1 1 2 1d n l o g n ) m i b ，口) m 2 ，厅口7 ，3 1 3 i ，l i 紧( t h 2 8 ) 4 册l2 b ，b m 2 h 2 1 d m l o g n )7 3 1 3 i ，l l 紧( t h 2 9 ) 5 誓m i n 枷l ，b ，m 2 h 2 1 d 伽l o g n )r n 3 2 紧( p r 0 2 2 ) 上海大学硕士学位论文 表1 1 ( 续) f 3 ( m 。，口，历2 ) i x ，u n f i x e d ，b - 6 i c u 问题的结果( 同型机) f 3 ( m i ，b ，历2 ) i d i d m ，u n f i x e d ，b jj bic _ 。 序号参数算法计算量性能比 1 掰i b ，b m 2 记- 5 d 伽l o g n ) 如；一击一击眦1 0 2 朋l b ，b 之m 2 h 2 5 d 伽l o g n ) t ；一击壶瓤眦1 d 3 m l ，b ，b 2 m 2 h 2 5 d 伽l o g n ) ”；一击一去毗1 2 4 m l b ，b m 2 舵5 d 伽i o g n ) 即竽一击者眦1 3 5 珂n a n 坍l ，b ，m 2 ) 1 1 2 5 o ( n l o g n )2 紧( p r 0 2 3 ) 表1 2 f 3 ( m l ，b ，m 2 ) i x ，m e d ，b j - b l c 。问题的结果( 专用机) f 3 ( m l ，丑，m 2 ) d d m ，f i x e d ，b j - b i c 。 序号参数算法计算量性能比 1 m ls b ，b s m 2 h 3 ，2d 0 l o g n ) r 日2 紧( t h 3 1 ) 2 m l b ，b m 2 h 3 3 m a x o ol o gn ) ，d ( m 醪) )r h 2 紧( t h 3 2 ) 3 m l b ，b ，m 2 b 2 d 伽l o g n ) r j ；r j2紧( t h 3 3 ) 4 m i 丑，b ，2 磁3 m a x o o l o g n ) o ( 柚) r 2 紧( t h 3 。4 ) f 3 ( m ”b ，肼2 ) ii d m ，f f x e d ，b jn bic 。； 由定理2 5 参考f 3 ( m l ，b ，m 2 ) i d d m ，f z x e d ，b j b i c m 。的情况把此时的，小2 视为 f 3 ( m l ，b ，m 2 ) l a d m ，f l x e d ，b ，- b i c 。中的坍2 ，m l 可得相对应的算法，计算量性能比都相同 1 1 上海大学硕士学位论文 表1 2 ( 续) ，3 ( m 1 ，b ，m 2 ) i x ，f i r e d ，b j - b i c 。问题的结果( 专用机) f 3 ( m l ，b ，埘2 ) li d d m ，f i x e d ，b j - blc 。 序号参数算法计算量性能比 1 七占 1 1 3 2 d 西l o g n )r 月2 紧( t h 3 5 ) 2 慨口 m 3 m a x o ( n l o g n ) ，o ( 柚) r h 2 紧( t h 3 6 ) r 3 ( m l ，b ，m 2 ) i d i d m ，f t r e d ，b j bi c 。 1 ，l la b h 3 2 d 伽l o g n )r h 2 紧( t h 3 7 ) 2 m 曰 1 1 3 3 m a x o o l o g n ) ，d ( ，坍) )r 2 紧( t h 3 8 ) 1 2 第二章问题f 3 ( m l ，b ，m 2 ) ix ，u n f i x e d ，b j b i c 一 本章中我们对其中的x 为d d m ，i d m ，i d d m ，d i d m 规则分别进行了讨论 2 1x = d d m 、i d m 时，问题f 3 ( m 。，b ，m ：) 1 x , u n f i x e d , b ji b i c 一的求解 2 1 1 问题| 3 ( m l ，b ，m z ) i d d m ，u n f i x e d ，b j - b l c 一的习t 解 算法1 1 2 1 ( 1 ) 以 4 ， 的u r r 序将工件排于a 阶段最先可加工的机器上 ( 2 ) b 阶段以和，在a 阶段的完工顺序，用f o e ( n ，b ) 规则加工工件t 且其中每批工 件一旦完成其在a 阶段的加工，若可开始阶段b 的加工则尽可能早地开始b 阶段加工 ( 3 ) b 阶段中每完工一批工件后以该批工件p ) 的r r 序用f a m 规则将它们排于c 阶 段的各台机器上加工。 算法h 2 1 的计算量为0 l o g n ) 定理2 1 m l b , b m 2 时，对问题f 3 ( 肼l ，b ，m 2 ) l d d m ，u n f i x e d ，b ，i bi c 。，算法 h 2 1 的性能比为尺h 2 1 5 3 一1 1 3 m 1 证明：设口j 6 j ，c j 分别为a ，b ，c 阶段第f 个开始加工的工件，这里的q ，6 i ，q 不必相应同一个工件且第f 个和第f + 1 个工件有可能同时加工。( 参考如图2 1 ) 田z i 上海大学硕士学位论文 不妨设工件数万之m 酝钿。，b ，m 2 易知 c 一( 日2 1 ) c l ( 日2 1 ) + 6 + 嘴 c j ， c k 麟 c i + 6 + 嘧，臀 口，+ 6 + c ， 因此性能比为：r w u 一半s j 瑞+ 亏黠 【3 6 】中给出问题i ic 。的近似算法，其中以工件加工时间的u r r 排序，可得性能比 估计为4 ，3 1 3 m 1 由算法i - 1 2 1 中的( 1 ) 及c 二- i ( h 2 1 ) 和c ：的定义可知 一号攀击+ 1 ，击 。”i 。”l 对于工件数厅 b ，b m 2 时，对问题f 3 ( 册l ，b ，珥2 ) l 拗n ，u n f i x e d ，b ，- b l c = ，算法1 1 2 1 的性能比为r 日2 1s7 3 1 3 m 1 证明：( 参考图2 4 ) 当弹sm i n 钿l ，b ，m 2 时，见性质2 1 当 m i n 锄1 ，b ，m 2 时，设最后一个被加工的工件a n 在a 阶段开始加工的 时间为t ，各批工件在批处理机上加工前的空闲时间为，。 押) ，b 阶段的批集合为 易知 b i 2 吩 c 。2 c 日2 。荟 + f 詈1 6 并且 善私二i 。觑。a ，j + a i n 4 ：去善叩， 此处q 。】定义为a 阶段最后一个完工工件的加工时间，图2 4e o a t 一1 。a n _ l ，而口阻1 同口一 可能相同也可能不同，但口【。】开始加工时间总不大于4 。的开始加工时间且这两个工件的加工 时间满足口。口【。1 所以c 。( h 2 1 ) s 击善4 ，+ ，+ | 詈1 6 + 嘴h ( 2 。 1 2 吨 、， -_-j_l 挥一b -_-_i 2l r t d 上海大学硕士学位论文 当然也可写成c 一( h 2 1 ) c l 叫( h 2 1 ) + f 詈1 6 + m 胆a ，x ( c ， “2 2 ) 又因为c 二一 c + 噙 c n ，a n 啪+ 吲m ，i n c ， ) ， 此处我们用式( 2 2 ) 来讨论性能比。( z 1 ) 式的应用在本文的后面章节中将回出现 。- 半等等等+ o 。l 1 1 警等i 。， 嘧+ 吲a + 曾 墨兰一l + 1 一7 一l( 2 3 ) 口 33 鸺33 m ， 定理2 2 所给性能比可相当接近达到。 倒2 2m l = 2 t ，b = 2 ，m 2 = 2 ，n = 2 t 2 + 2 t ，b - 1 、号 12 2 t2 f + 12 t 2 + 2 t t 件 4 ， t 2t 2t 2 11 c fff 11 由算法h 2 1 得( 参考图2 5 ) c 一( h 2 1 ) 一2 t 2 + f + 1 t 2 t z + t2 1 2 + t2 f + t + l 而问题的最优值( 参考图2 6 ) c 二l i i l m t2 + 2 f + e a 。，i la 。，l“ a ，。，j ja ，。，ja ， f 雌续) a -钆舢。i b 1i 鲁糙的f 小广 瓯t ： b f 阳。刈 田 。n 当t + ，f - 0 + 时， - 半一黼一z 。、， p 2 一 吨 b l 2 1 2 吗 b ， 2 上海大学硕士学位论文 上述性能比2 与性能比与7 3 1 3 m l 相差a - 0 3 。 相应埘1 b ，b m 2 的情况，我们构造如下算法： 算法h 2 2 ( m l 蜊2 时) ( 1 ) 以恤，) 的u y r 序将工件捧于a 阶段最先可加工的机器上 ( 2 ) b 阶段以扣j 在a 阶段的完工顺序，用f o e ( n , b ) 规则加工，其中常数口满足口- m 2 ( 3 ) b 阶段中每完工一批工件后以f a m 规则将工件排于c 阶段加工。 算法h 2 3 ( m l 堋2 时) ( 1 ) 以扣) 的l i t 序将工件排于a 阶段最先可加工的机器上 ( 2 ) b 阶段以 4 ，) 在a 阶段的完工顺序，用f o e ( n ，b ) 规则加工t 其中常数口满足占一m l ( 3 ) b 阶段中每完工一批工件后以该批工件 c j ) 的l p t 序将工件尽可能早的在c 阶段加工 算法1 1 2 2 ，h 2 3 的计算量为o l o g n ) 。 定理2 3 m l b ，b m 2 时，椭f 3 ( m l ，b ，m 2 ) d d m ，u n f i x e d ，b i b i c 一。 ( 1 ) 当m l 坍2 时，算法i - t 2 2 的性能比为r 日2 2 5 3 1 3 m l ( 2 ) 当厅1 1 i n 2 时，算法h 2 3 的性能比为r n 2 3 7 3 1 3 m 1 证明：( 1 ) 由于算法h 2 2 的第二步保证了b 阶段比a 阶段的时间长度只多b ，且b 阶段每批 工件完工后在c 阶段都可以立即加工。证明过程同定理2 1 ，结论( 1 ) 成立 ( 2 ) 同样算法i - 1 2 3 的第二步也保证了b 阶段比a 阶段的时间长度只多b ，可是b 阶段 每批工件完工后在c 阶段不可以都立即加工，而是按照幻) 的u 叩序尽早进行c 阶段加工 由定理2 2 的证明过程和参考图2 4 易知 c 一( 日2 3 ) c l ( 日2 3 ) + b + d 此处d 表示：按照算法从b 阶段最后一批完工时间起到算法最后全程完工之间的时间段 与定理2 2 讨论相似，显然有： 1 7 上海大学硕士学位论文 d 丢，三。二，m 丢蚤c ，托 与口的定义一样，此处。i 鼻l 为c 阶段的最后一个完工工件的加工时间且口【- 】与【 不必相应同一个工件 c 一( 肌3 ) c k ( 胍3 ) + 6 + 去荟印， 又眺c 二乏一 c ? + 6 + 噙 ，r a 倒i n 哪+ 6 + 去善c ， ， 即。鼍笋 一4 一l + 1 7 一上( z 4 ) 一i _ 1 一+ l z j 3 3 m l 3 3 m l 唯一要说明的一种情况是当小l n 堋2 时b 阶段一次加工n 个工件，结论依然成立。 定理2 3 所给性能比可相当接近到达。 例2 3m l