（运筹学与控制论专业论文）同类平行机半在线排序问题的若干研究.pdf

摘要 本文主要研究了两类预先女h 道两释蘧患静两类平行裰半京线辩序闷遴。一类 燕带懿器毽蔷精润豹阕鳖平行褪半褒线瓣爨；茄一类是嚣类警行援半奁线掺滓阕 飚 全文熬分三牵然嚣主熨介缨了平行机排序阉题舳背景、基本概念和单信 惠半夜线摊岸问题的研究进展第二章介绍了复合半在线及带准备时间鹇闻墅橇 摊净瓣嚣，莠讨谂了带税嚣准餐辩阕置基知赛骞工释惑魏工辩麓黧最大工俸燕王 对闼的巍套阕燮枫豹半在线摊黪潞题，联禄遁数为投小他最大槐器帮最大工撵熬 究工射超戆翊题，势谨爨了蹦黪法为最饯半在线算法，竞争燃为拿。繁三章奔绍 5 了阿类机半在线排序问题，并讨论了预先知道所有工件总加= r = 时间和最大工件加 工孵阕嚣静倍感酶两螽瓣类橇半在线掭澎阉爨，鞲稼蘧数兔寝大铯最孛橇器竞 王辩蠲豹弱题，并绘趱了忿阅熬令竞争魄为芝3 s 磊+ 忑2 翡半杰线箨法。 关键调：排序问题；半在线；近似算法；竞争比 浙江大学硕士学位论文 a b s t r a c t i nt h i s t h e s i s ，t w o s e m i - o n l i n e s c h e d u l i n gp r o b l e m s w i t h c o m b i n a t i o no f t w ot y p e so f i n f o r m a t i o na r ec o n s i d e r e d o n ei ss c h e d u l i n g o nt w oi d e n t i c a lm a c h i n e sw i t hn o n - s i m u l t a n e o u sa v a i l a b l et i m e ，t h eo t h e r i ss c h e d u l i n go nt w ou n i f o r mm a c h i n e s t h et h e s i si so r g a n i z e da sf o l l o w s c h a p t e r1g i v e sa ni n t r o d u c f i o no ft h ep a r a l l e lm a c h i n es c h e d u l i n g p r o b l e m s ，b a s i ck n o w l e d g ea b o u ts c h e d u l i n ga n ds e m i o n l i n es c h e d u l i n g w i t hs i n g l e i n f o r m a t i o n c h a p t e r2m a i n l yd e a l sw i t ht h es e m i o n l i n e p r o b l e mo nt w oi d e n t i c a lm a c h i n e sw i t hn o n s i m u l t a n e o u sa v a i l a b l et i m e ， w h e r et h et o t a lp r o c e s s i n gt i m ea n dt h el a r g e s tp r o c e s s i n gt i m ea r ek n o w n i na d v a n c e ，t om i n i m i z et h em a x i m u mm a c h i n ec o m p l e t i o nt i m e w eg i v e a l lo p t i m a la l g o r i t h ms mw i t hc o m p e t i t i v er a t i oo f6 5 c h a p t e r3c h i e f l y c o n s i d e r st h eo t h e rs e m i - o n l i n ep r o b l e mo nt w ou n i f o r mm a c h i n e s ，f o r w h i c ht h et o t a l p r o c e s s i n gt i m ea n dt h el a r g e s tp r o c e s s i n gt i m ea r e k n o w ni na d v a n c e ，t om a x i m i z et h em i n i m u mm a c h i n ec o m p l e t i o nt i m e w e p r e s e n tt h ea p p r o x i m a t i o na l g o r i t h ms dw h i l ep r o v ei t sc o m p e t i t i v e r a t i oi s ( 3 s + 2 ) ( 2 s + 2 ) k e yw o r d s ：s c h e d u l i n g ；s e m i - o n l i n e ；a p p r o x i m a t i o na l g o r i t h m ： c o m p e t i t i v er a t i o 1 l 浙江大学硕士学位论文 第一章平行机排序理论 1 1 平行机排序问题 排序问题兴起于二十世纪五十年代初期，于1 9 5 4 年j o h n s o n j o h n 5 4 提出 了解f 2 c m 。问题的j o h n s o n 算法，拉开了排序问题的序幕，并迅速发展成为组 合优化领域的重要组成部分随着这一领域研究人员的与| = = 俱增，具有实际应用 背景的新问题的不断涌现，其研究的内容也越来越丰富，研究成果层出不穷，应 用领域也越来越广阔近几年来，排序问题已广泛地应用到理论计算机科学、网 络通信、自动化生产管理与调度和物流管理等多个方面现在它已受到运筹学 计算机科学、系统工程学和现代管理学等诸多学科的高度重视，并已成为其强有 力的工具 排序问题，又称调度问题一般地，在排序理论中称要完成地任务为工件， 而称任务地完成者为机器这样在企业的生产中排序问题可以简化抽象地描述如 下：给定一个工件集，要在一个特定的机器集m 上加工，在满足一系列约束条件 的前提下，给出一个工件的加工方案，使得给定的目标函数达到最优依据排序 问题所涉及到的三要素：机器、工件和目标1 9 7 9 年g r a h a m ，l a w l e r , l e n s t r a 和 r i n n o o yk a n 等提出采用三参数表示法口卢y 表示一个具体的排序问题 【g l l r 7 9 】，这里口，分别表示特定的机器状况，工件特征和目标函数三 个参数具体如下： 机器状况口是描述与机器相关的各种信息，如机器类型、数量及是否带准备 时问等常见的机器状况有单台机、平行机、流水作业、有序作业、自由作业等本 浙江大学硕士学位论文 文所涉及的机器类型为平行机( p a r a l l e lm a c h i n e ) ，其包括： 同类机( u n i f o r m m a c h i n e ) ，即机器有各自不同的速度，但任意工件在不同机 器上的加工时间有相同的比例关系，通常用q 表示第i 台机器用m ，表示，第i 台机器的速度用s 表示特别地，当同类机的机器速度均为1 时，称之为同型机 ( i d e n t i c a lm a c h i n e ) ，即所有机器完全一样，通常用p 表示 不同类型机( u n r e l a t e dm a c h i n e ) ，即机器有各自不同的加工速度，且工件在 不同机器上的加工时间比例不完全相同，通常用r 表示 机器数量为有限台，通常用m ( m = 1 , 2 ，) 表示巴，q ，r 。分别表示m 台同 型机，同类机，不同类型机 机器准备时间是指机器m ，自时刻起才能开始加工工件，通常用表示且位 于三参数表示法的第一个域中 工件特征是描述与工件有关的各种信息一般地，根据排序者在安排工件时 掌握工件信息的多少将排序问题分为三类：离线( o f f - l i n e ) ，在线( o n 1 i n e ) 和半 在线( s e m i o n l i n e ) 其中： 离线问题是全部工件的所有信息在排序时均己知，排序者可以利用工件信息 对工件进行排序 在线问题有两条基本假设：一是工件的信息是逐个释放的即某工件的信息 只有在排序者对其之前来的工件作出安排后才会被排序者所知，也意味着后续工 件的情况是未知的二是工件的加工不可改变即某工件一旦被排序者安排给某 机器加工，在其后的任何阶段不能以任何方式更改此工件的) j n z 半在线问题是排序者对工件信息的掌握情况介于离线与在线之间的排序问 浙江大学硕士学位论文 题也就是说不完全满足在线问题的两条基本假设的在线问题称为半在线问题 工件数量是有限的，其集合通常用d = d 。，t ，：，j 。) 表示 工件的加工按加工过程的连续性又可分为不可中断( 在一台机器上一次性加 工完毕) 与可中断( 用p m p t 表示工件加工可以中断) 按起始加工时刻可分为工 件带准备时间与工件不带准备时间( 或称零时刻开始加工) 排序问题中的目标是多种多样的常见的是机器数给定，对完工时间这一目 标寻求最优按全部机器的完工时间可分为两类：一类是使最后一台完工机器的 完工时间达到最小，简称为极小化最大机器完工时间，通常用c 。( m ) 表示另 一类是使最早一台完工机器的完工时间达到最大，简称为极大化最小机器完工时 间，通常用c 。( m ) 表示 g r a b 6 6 按全部工件的完工时间可分为两类：一类是 使最后一个完工工件的完工时间达到最小，简称为极小化最大工件完工时间，通 常用c 一( i ，) 表示另一类是使最早完工工件的完工时间达到最大，简称为极大化 最小工件完工时间，通常用c m m ( j ) 表示当机器准备时间r j = 0 时，显然有 c m 觚( m ) = c 。( ，) ，c 。( m ) = c 。( ，) 因此，在不引起混淆的情形下常用c o 或 c 。表示目标函数 浙江大学硕士学位论文 1 2 排序问题的算法与算法评估 排序问题是组合优化中的一类重要问题，随着解决组合优化问题方法的增多 排序问题的算法被分为确定性算法( d e t e r m i n i s t i ca l g o r i t h m ) 和随机性算法 ( r a n d o m i z e da l g o r i t h m ) 排序问题中的绝大部分问题都是p h a r d 问题对于这 类问题从计算量的角度看，不大可能存在有效多项式时间的求解方法，而这类问 题又是实际存在的，虽然一般不可能求到最优解，但有希望找到某种方法求出它 的近似解，也就是组合优化中的近似算法即对于一个组合优化问题i t ，如果给 定任意一个实例，算法a 总能找到所给实例的一个可行解，那么a 为石的近似 算法近似算法所研究的是要对于一种给定的简单易行的算法，估计出由它所产 生的解与问题的真正的最优解所对应的目标函数的值之间的差异程度因而，在 某种给定的标准下，它可以评估几种给定的算法之间的优劣近似算法好坏的评 估属于最坏情况分析，通常用最坏情况界、竞争比来刻画 对于离线问题，我们将求解离线问题的方法称为离线算法离线算法性能的 评估也用最坏情况界( w o r s t - c a s er a t i o ) 来衡量对极小化排序问题，称 q = i n f c 1 1 c 4 ( ) c c 掣( 巩v 1 ) 为算法a 的最坏情况界，这里c 。( j ) 和c 州( ，) 分别表示算法a 解实例i 的目标函数值和最优目标值同样地，对极大化排序问 题，称钆= i n f c 1 l c ”( ，) c c 4 ( ) ，v l 为算法a 的最坏情况界 对于在线问题，我们将求解在线问题的算法称为在线算法称衡量在线算法 性能好坏的最坏情况界为竞争比( c o m p e t i t i v er a t i o ) 其定义与离线算法的最坏情 况界类似，其中c ”( ，) 为相应离线问题的最优目标值如果在线算法a 的竞争比 4 浙江大学硕士学位论文 为c ，也称a 是c 竞争比的( c c o m p e t i t i v e ) 对于在线问题，我们希望设计出最 坏情况界或竞争比尽可能小的在线算法无论是极大化目标还是极小化目标，若 不存在该问题竞争比小于c 的在线算法，则称c 为该在线问题的竞争比下界，简 称为下界( 1 0 w e rb o u n d ) 为了得到下界，一般可以通过给出一系列实例，使得任 何在线算法都不能很好地求解所有实例来得到，称此方法为对手法对某在线问 题，如果在线算法彳的竞争比等于该问题的下界，则称算法4 为该问题的最优 ( o p t i m a l ) 算法这是从竞争比意义上说，最优算法是一个在线问题可能得到的 最好结果 所谓随机性算法是指算法执行过程中可以作出随机选择的一类算法随机算 法性能的评估用竞争比衡量，对极小化排序问题，称 c 。= i n f c2 1 ie ( c 。( 功c c ”( nv ， 为算法a 的竞争比，e ( c 4 ( 功表示算法a 解实例，所得的期望目标函数值，c w ( ，) 表示算法a 解实例i 的最优目标值同 样地，对极大化排序问题，称c 。= i n f c 1c ”( ，) c e ( c “( 功，w 为算法a 的 竞争比排序问题的随机下界可利用y a o 氏定理得到【y 如7 7 】本文所讨论涉及 到的方法都是确定性算法 在二十世纪六十年代，g r a h a m 提出了平行机排序问题中经典的在线算法即 求解p m c 。在线问题的l s ( l i s t s c h e d u l i n g ) 算法 g r a h 6 6 l s 算法是按照 工件到达的顺序，把工件安排使其最早完工的机器上加工，g r a h a m 证明l s 算法 的竞争比为2 一上蚶算法提出二十余年后，1 9 8 9 年f a i g l e ，k e r n 和t u r a n f k t 8 9 m 证明了当m = 2 ，3 时三s 算法是最优在线算法对于m 4 最优在线算法上界的改进， 【b f k v 9 5 】、【k p t 9 6 】、【a 1 b e 9 7 】分别给出了竞争比为1 9 8 6 、m 8 时1 9 4 5 、 浙江大学硕士学位论文 1 9 2 3 的算法目前最好的在线算法是2 0 0 0 年f l e i s c h e r 和w a h l i f w 0 0 l 提出的m r 算法，当m 斗m 时，竞争比趋近于l + ( 1 + 1 n 2 ) 2 o ，1 ，对任意m 和r 1 ，h e h e 0 0 a 证明了船仍是最优算法，当，m 时竞争比为，当， m 时竞争比为 而离线问题的经典算法也是g r a h a m 求解p m c m 。时提出的l p t ( l o n g e s t p r o c e s s i n gt i m ef i r s t ) 算法 g r a h 6 9 p 丁算法是先将工件按加工时间的非增序 排列，再以重排后的次序按l s 算法加工，g r a h 锄证明了三昙导一击，即 丁 算法的最坏情况界为；一_ i 对于己c 。的离线情形，该问题最早由 jj ，” d e u e m a e y e r 等 d f l 8 2 在1 9 8 2 年提出，并证明了l p t 算法的最坏情况界至少为 3 4 直到1 9 9 2 年, c s i r i k , k e l l e r e r ； i t w o c g i n g c r 【c k w 9 2 】证明了等笔鲁 浙江大学硕士学位论文 1 3 单信息的半在线排序问题 半在线排序理论的研究最早出现于1 9 9 6 年 l s v 9 6 1 它的产生源于现实中 普遍存在的生产、管理问题在经典的排序理论中，人们根据安排工件时对工件 信息掌握的多少将排序问题分为离线和在线离线问题的前提是人们掌握所有工 件的全部信息，而在线问题的前提是当前工件的信息，只有将其之前到达的工件 安排好后才得知，且一旦对工件做出安排就不能更改这属于两种极端的情形事 实上，尽管人们不会完全掌握工件的信息，但可以预知工件的某种信息或部分信 息如预知所有工件加工时间的总和，最大工件加工时间等不仅具有现实意义， 而且对实际的工件排序有可能产生有用价值由此，产生了不完全满足在线排序 问题的两条基本假设，难度介于在线和离线之间的模型称为半在线( s e m i o n l i n e ) 模型，即半在线排序问题其表示是将所知工件信息放在三参数表示法的第二个 域中求解半在线排序问题的算法被称为半在线算法由于半在线问题除了预知 工件的某种信息外，对工件做出安排决定前并未掌握工件的全部信息且一旦对工 件做出安排就不能更改来看，很大程度上接近于在线问题，是不完全满足在线问 题的两条假设，与在线问题之间只是程度上的差别在对后续工件信息不完全已 知这一点上是相同的，而与离线问题确有着本质的区别故半在线算法的好坏评 估仍采用在线算法的竞争比定义来衡量随着半在线问题的大量涌现，半在线问 题的研究已经取得了长足的进展大量的模型和优秀算法不断被提出，已经形成 了排序研究的一个非常活跃的富有生命力的新的分支 由于离线问题是掌握工件的全部信息，在设计算法时可以充分利用这些信息 浙江大学硕士擎位论文 设计出比在线情形更合理、更优韵辣法自然人们期望半在线问蹶的算法设计利 用预知的某种信息会设计出优于相成的在线问题的算法可事实并非如此因为 对予拳在线阉题，忽略其掰己知的王馋售惑，就是一个在线溺题嚣此，蓑在绘 定机器环境和目标函数下，只有求解半在线排序问题的算法的竞争比严格小于相 应在绞闳题的下赛f 重，繇澄翔兹工锌信怠方蠢价值。蠢英降低了润邃瓣难浚，有 利于相应在线算法的改进因此，邋常构建一个新的半在线模型酋先寻找该模型 的下界若半在线问题的下界等于相应在线问题的最佳算法的竞争比，则说明该 半在线模型不会使阉题交褥薅单，灏嚣，辑已知豹工 孛信惠是无份篷豹 下表中给出h e ，y a n g 和t a n h y t 0 3 a 猩最c m 。下无用信息的半在线模型 及下界等于辐纛在线闻纛靛最佳算法( l s 算法) 静竞争眈静实铡。 半柱线模型名称 记号 证明下界为3 2 的实例 p = p 2 = 1 ，p 3 = 2 ，p 4 = 一n = s 已螽一：件总数 k n o w nn u m b e r 及 p l = p 2 = l ，p 3 = p i = = p 。= 8 ) 已知工件最小加王时 k n o w ns m a l l e s t p l = g p 2 = p 3 = l ，尹4 = 2 间j o b n o n d e c r e a s i n g 工件加工时间非减 p l = p 2 = 1 ，p 3 = 2 ) j o b 已舞蠢蔽个( 个) 后续 j 件信息 l o o k a h e a d p l = p 2 = l ，p 3 = 一以+ 2 = g ，p i + 3 = 2 p l = p 2 = l ，p 3 = b p 4 = 2 6 ，p “= ( k 一1 ) 6 及 已知工件加工时间 f i n i t et y p e 只有k 种取值 j o d p 1 = p 2 = 1 ，p 3 = 2 ，p 4 = s ，p 5 = 2 s ，p + l = ( k 一2 ) e ) 够雀线模銎鹩猥翻【瓣l 3 8 】缀浚s l ，8 2 为任意掰令半在线模型，蓉饪露 濒江夫学硕士学谊论文 满足半在线假设s l 的实例均满足半在线假设s 2 ，刚称s 1 为s 2 的限制，记为 实际上，任意半夜线模型可以看成怒葵糨应在线模型的隈耧， 半在线摸垄静袋铡有戳下性质 t f f t 0 3 a ： ( 1 ) 若问题p 2 j l c 。和p 2 s 2 c 。的下界分别为c 1 和c 2 ，且有j 1 s 2 ， n c t 兰c 2 ( 2 ) 羞霎法矗浓舞p 2 s 2 嚷。魏凳争跑势白，登鸯s l - s 2 ，爨算法a 袋熬 p 2 s l c 。的竞争比趸多为c 。 上述性质可以推广到其它机器环境和目标函数上去 逶过建缝覆毽霹铡震已毒熬半在线攘鍪爨蘩薮梅建鹣拳褒线模型是否蠢徐 德如z h a n g 和y e z y 0 2 提出两个半在线模型：p 2 i l l c 模型，其中l l ( l a r g e s tl a s t ) 表示最后到达的工件为加工时间最大的工件p 2 s u g g e s t i v e ! c 。 模溅，其s u g g e s t i v e 夜示最后一个工件戮达时排序者会被告妇该工件确是最后一 个工件由于n o n d e c r e a s i n g _ l a r g e s tl a s t ，k n o w n n u m b e r 2 h e 和d o s a h d 0 4 研究了p 3 1g r o u p c o ，模型，证明了三s 算法的竞争比 1 。2 ( r 一1 ) 2 一二 r + 3 r 专l ，1 ， 1 ，要， 昙 r 瓶， 4 3 4 t 筘j - ，闷题酶下界 j m i 黧少为二4 5 、已知实例最傀籍僮( k n o w n ) ：假设实例的最优解值( 当然不是最优解本身) 珂在零时刻( 魏辩王 串溺寒至l 达) 隽蓑 窿者 莠知。 堑兰垄堂堕主堂堡垒查 h z a r 和r e g e v a r 9 8 证明只i o p t l c 。存在竞争比为詈的近似算法，埘3 存在竞争比为挈兽的近似算法，对m 2 此问题的下界至少为i 4 关于 j m + lj 巴o p t c m 。模型，t z a r 和e p s t e i n a e 9 7 给出了竞争比为2 - 1 - 的近似算法f i l l ， 当m = 2 ，3 时，算法是最优的，对m 4 ，问题的下界至少为二 4 另外，还有带缓冲区( b u f f e r ) 、己知工件加工时间序( o r d i n a l ) ，工件分两 批到达( t w ob a t c h ) 等其他重要的、有实际意义的半在线模型，可参看综述文章 【h y t 0 3 a ，h y t 0 3 b 】 浙江太学硕士学位论文 第二章复合蹰个信息的半在线排序问题 2 1 复合半在线排序问题 涎善对零售愚半在线接疼阂趱熬臻究，掰豹半在绫模型不凝被疆出。入霞奏 效地利用工件不同信息的价值，不断地改进了其相戚在线问题浇争比，得至r j - ；比 最优在线算法近似程度大大提高的高往雒半在线算法由诧揭示了在信恩不完全 的情况下，傣息的已知程度与瓣题的可近似程疫之闻的关系及不同信息猩近似算 法设计中的价值工件的信息受到研究者的广泛关注由于在某种程度上，可同 辩鼗翔工俸翡嚣耱或薅耱滏上熬镕惠是哥行鹣。因魏，热司联魏单痞愚霹降燕其 对应的在线问题的难度一样，复合两个信息有可能使相应的单信息半在线问题变 得楚为简单即使一些凭价值的筚信息的半在线模黧复合以后落有可能降低问题 的难度，剩予算法设诗困此，礤究复合半在线模型仍具有一定的现实意义。 复合半衣线模型【f i y t 0 3 a ：称s l & s 2 为半在线模型j 1 和s 2 复合，游该模型 露辩滚足半京线程设s l 秘珐，这鼙s l 羁戚是程意瑟个半在线模登。 下面仅就已知总和( s u m ) 与已知最大( m a x ) 两个模型概述复合半在线模型 的研究进展 1 、已知憨秘( s u m ) ( 1 ) 模型p 2 s u m ，s m a l l e s t g 。，p 2 s u m ，n o n - d e c r e a s i n g c 。， p 2 s u m , $ u g g e s 鼢c 。，尹2 ，s 瓤m ，l l c 。鹣最往繁法尧玛，下葬是昙，下赛 实例是 p 1 = p 2 = 1 ，p 3 = p 。= 2 ) 或 p i = p 2 = p 3 = 1 ，p 。= 3 ) k k s t 9 7 ( 2 ) 模逖p 2 ，s “碱m a x c m 。的最佳算法为s 碓，下界是拿，下界实例是 1 ，3 ，2 ，2 ，2 ， 1 ，3 ，1 ，3 ，2 ，( 1 ，3 ，1 ，1 ，3 ，1 ) ， 1 ，3 ，1 ，3 ，2 ) t h 0 2 b 】 模型p 3 s 姗，m a x c 一的竞争比为；，下界为j 4 ，下界实例 2 ，2 ，4 ，6 ，4 ， 2 ，2 ，2 ，6 ，6 l u 0 3 】 ( 3 ) 模型p 2 s “m ，出c c 。的最佳算法为s d ，下界是罢，下界实例是 4 ，4 毒筹扣。，4 3 1 3 ，3 ，1 ) t h 0 2 b 】 ( 4 ) 模型_ p 2 s u m ，m a x c m 的最佳算法为s m ，4 ，下界实例是 f l ，3 ，2 ，2 ，2 ， l ，3 ，1 ，3 ，2 ， 1 ，3 ，1 ，1 ，3 ，1 ，姐，3 ，1 ，3 ，2 ) l u 0 3 ( 5 ) 模型p 2 s “卅，出c c 一的最佳算法为s 。， 9 ，下界实例是 4 ，4 ，詈， ， ，詈) ， 4 ，4 ，3 ，3 ，3 ，l l u 0 3 1 二二 2 、已知最大( m a x ) ( 1 ) 模型p 2 m a x ，s m a l l e s t c 。，p 2 m a x ，n o n d e c r e a s i n g c m 。， 尸2 m a ) ( ，l l c 。，p 2 m a x ，s u g g e s 玎w c 。的最佳算法为p l s ，4 ，下界 实例是 n = p 2 = 1 ，p 3 = p 4 = 2 ) ， a = p 2 = 1 ，p 3 = 2 h z 9 9 1 复合半在线模型与单信息半在线模型的关系 h y t 0 2 b ( 1 ) 若问题p 2 s l ，s 2 c m 。，p 2 s l c 。和p 2 s 2 c m 。的下界分别为c c l 和c 2 ，j j c l 2s m i n q ，c 2 ( 2 ) 若算法a 求解p 2 s 1 c 。或p 2 j 2 c 一的竞争比为c ，则算法a 求解 p 2 s l ，s 2 c 。的竞争比至多为c 上述性质可以推广到其它机器环境和目标函数上去 另外，复合半在线模型的价值与构成它的单信息的两个半在线模型的价值是 无关的在第一章我们讨论了两个无价值的半在线模型p 2 三c 和 1 4 浙江大学硕士学位论戈 p 2 s u g g e s t i v e g 。，憾 z y 0 2 绘密求解p 2 ，瑟，s u g g e s t i v e 瓯。最优算法a ， 其竞争比为2 ，严格小于p 2 c 。的最优冀法的竞争比昙，因而是有价值的半 z 在线模型而- 。：, jp 2 s “m c 。，尸2 ，m a ) ( c 。的下界为4 3 ，t a n ， h e t h 0 2 b 对复合嚣懿模型尹2 s 辅孵& 氆a 影e 。透过巧妙建裂煺嚣耱不羁售惑， 给出了竞争比为6 1 5 的最优半在线算法，其巍争比6 5 严格小予4 3 ，因而也是 有价值的半在线模型 浙江大学硕士学位论文 2 2 带准备时间的平行机排序问题 在经典的排序论中总假设机器在零时刻可以开始工作，但在实际情况中未必 如此如机器开工前需做预防性维护，在此期间不能加工工件又如生产调度是 分阶段进行的，上阶段已分配好的工件在新阶段开始时仍未加工完成，且不允许 重新分配，这样每个机器的最后一个工件的完工时间就称为下一阶段的机器的准 备时间因此，从机器环境的角度，产生了一类新的模型带机器准备时间的 平行机排序问题该类模型最初是出现于 l e e 9 1 】、【y l h 9 2 】l e e ，h e ，t a n g l h t 0 0 、 h t 0 0 提出此类模型下的两个目标函数，即极小化最后一个完工工 件的完工时间和极小化最后一台完工机器的完工时间，未必相同在经典的排序 论中机器在零时刻开始工作凼此，曲个目标在最环情况分析上是相唰的但 t h 0 2 a 】给出模型p 2 ，r j m a x c 。( m ) 的竞争比为= 4 的最优半在线算法p l s ，并 给出了模型p 2 ，r j m a x c 。( ，) 的竞争比为芸的最优半在线算法m p l s ，两算法是 不同的说明机器的准备时间对两个目标的算法设计是有影响的尤其是 t h 0 2 c 研究了模型p ，r j o r d i n a l c 。( 肘) 和p ，0 o r d i n a l c 二。( j ) ， 该文对 p ，o r d i n a l c m 。( m ) ，给出了当m = 2 ，3 ，m 3 时竞争比分别为3 2 ，1 3 8 ，2 一i _ 。 的半在线算法，算法当m 2 2 ，3 ，4 时是最优的对模型p ，一o r d i n a l c 。( ，) ，给 出一个竞争比为m 的最优半在线算法说明这两个目标有显著不同 下文简述带准备时间的同型平行机半在线排序问题的研究进展： ( 1 ) b ，r j s u m c m 。模型协和h e t h 0 2 a 给出算法p s u m ，其竞争比为昙， 且为最优算法最，i s u m c 。模型，h e h e 0 1 给, q q 了竞争比为詈的最优半在线 算法日： ( 2 ) 最，0 m x c 。模型h e h e 0 1 】对最，0 m a x c 。模型给出了竞争比 为2 3 的最优算法日， b ，0 m a x c m 。模型t a n 和h e y h 0 2 a 给出了最，! ，m a x c 。( m ) 模型的 最优算法是p l s ，竞争比为芸，并给出了b ，r j i m a x c 。( ，) 模型的最佳算法 m p l s ，竞争比为昙 ( 3 ) 弓，o d e c 模型l s 算法的竞争比为詈一亡t a n 和h e t h 0 2 a 。 zz l n 给出，当i n = 2 时，l s 算法为最佳算法：当- n _ 3 时，问题的下界至少为生之亘 模型b ，：，如c c ：。c a i c a i 0 2 证明了l s 算法是解此问题的竞争比为三的最 优算法 浙江大学硕士学位论文 2 3 p 2 ，o s u m & m a x c 。, 模型 本文研究了p 2 ，0 s u m & m a x c 。问题即预知所有工件加工时间总和 ( s u m ) 和最大工件加工时间( m a x ) ，目标函数为极小化最大完工时间的两台处 理器的带准备时间的半在线问题，并给出了竞争比为6 5 的最优半在线算法具 体可描述为：设有竹个相互独立的工件j = j 。，：，以 工件j ，的加工时间为p 。， 在文中也用p 。指代工件以需要在2 台机器m = m 1 ，m 2 ) 上不中断地加工处理 器的准备时问分别为_ ，2 ，不失一般性，设_ 吃c 。( m ) 表示最后一台完工 处理器的完工时间c 。( j ) 表示最后一个完工工件的完工时间用c m 。表示 c 。( m ) 或c 。( ，) 目标为找到一个可行排序，使c 一( m ) 或c 一( ，) 尽可能地 小即讨论了最，0 s u m & m a x i ( m ) 和昱，s u m & m a x c m 。( ，) 问题，并给出 竞争比为6 5 的最优半在线算法关于带机器准备时间的平行机排序问题的复合 半在线算法的研究，尚未见文献涉及 2 3 1算法描述 i i 牛集j = ，以，以 包含玎个相互独立的工件，其中工件z 的加工时间为 b ，下面用b 代表z 记p = p i 为所有工件加工时间的总和，t = p + _ + 吒用 只斗m j 表示把b 分给m j 加工分别用c 。( ， ，c ”积m j 表示算法爿解 某实例( t ，m ) 的目标值和该问题在离线状态下的最优值，在不引起混淆的情况下 简记为c 。，c ” 若p 。 t 5 ，则称b 为大工件用p o 表示第一个到达的最大工件 算法s m ： 浙江大学硕士学位论文 1 + 如果2 t 5 ，则把所有工件安摊给磊毛，停枫如果o 2 t 5 ， 转2 ； 2 如果2 r 5 蕉p 。蔓t ，则成。砷2 1 4 ：，其余工件给m ，停机 3 如果o p 一t 5 ，用上s 算法安排所有工件，停机 4 舞鬃t 5 筘。 2 t 5 ，设豢薅王释为p ： 4 1 停机准则1 ：若p 能安排给菜处理器，使其加- i 究p 后的完工时间位于 2 t 5 ，3 ，5 】之间，则p 安排给此处理器，以后的所有工件都安排给另一台处理器， 缮飙。 停机准则2 ：转p 在z 。之前到，且如果把p 分配给菜处理器加工，p 的完 工时间位于【2 r ，5 一p 。，3 t 5 - p 。 ，则把p 和p o 。安排络此处理器，所有除砘。 多 的裁余工 孛安捺绘另一台处理器，势祝 4 2 著o 吃s t 5 ，如果p r 5 或p = 矗，刚p 啼蝎；否则p 是不同 于戍。的大工件，则p 呻m 2 如果鸠上已有两个大工件，则将所有剩余的工件 安摊给蝎，停机。否则转5 ； 4 3 若0 弓 - t 5 f l i t ，5 莲 r 2 + 尹，魁根据 删算法步1 ，有c “= r t ，所以s m 产生最优排序如果孥蔓 i t ，则一定 存c “3 t 5 ，因为g 州t 2 ，所敷僚程c 掰，e 董6 5 。 接着讨论 2 t 5 的情况若t 2 p 一 丁，根据删算法步2 ，照然删 是媛优排序若2 t 5 p 。 t 2 ，则根据s m 算法步2 ， c 删= m a x r 2 + p k ，f 一( 恐+ 尹：群) 若c “= 也+ p ，则s m 产生最优排序糟c “= t 一( 屯+ p ：。) ，则 c “ t p k 3 t 5 ，结合e 掣t 2 ，褥e “c 掣 6 5 + 若o 尹。t 5 ，则根据鼬f 算法步3 ，每台处理器上都加工工件，所以根 据上s 算法，两台处理器的完工时间相差簸多不超过。，所以 c s m ( t + p m a x ) 2 6 5 c 叶jll2 至此我们只需要讨论t 5 p 一 2 t 5 的情况如果s m 以停机准则1 或2 停机，由引理1 可知c “c o p ! s 6 5 ，所以只需证明两个停机准则不满足的情况 情形1 ：若0 t 3 t 由于 p 。p 一，p 。：p 。，且在任何最优排序中，总存在一台处理器至少加工 p n ，p 。p 一) 中的两个，所以s m 是最优排序否则，在盛到来之前，m ：上至 多有一个大工件，且m ：的负载小于孚由停机准则2 可知，在磕到来之前， m 。当前的负载小于警一p 。由虎。m t ，m 在排兀0 时的负载仍小于 丝5 又因m 只加工，j 、于詈的工f 牛，由停机准则1 可知，两个不同于盟的大 工件一定得来( 或许有一个大工件在喙之前来) 由以上同样证明可知跗是最 优排序 情形2 ：0 r 2 茎t 5 且t 5 2 t 5 因为t 5 p m , x 2 t 5 ，所以t 5 t + p 0 3 t 5 ，因为不满足停机准则1 ， 所以t 5 + p 2 t 5 下面仅讨论_ r 2 + p 。的情况，另一情况 r 2 + 证明类似 根据算法步4 3 1 ，p o m 。总给鸩加工，m 只加工小工件在p 。0 。到来之前， 如果m 2 上已有一个大工件p ，且吒+ p r 2 + p m a x i 3 t 褥在任何最优排痔中，慧存奁台楚理器至少鸯羁工 p ，r i ，p 一 中的两个，因k + p 。，所戳 c 踟= _ + p + p ：缸嚣m i n r 1 + p ，吃+ p + p 。拟，r i + p 慨 = c 掣西 f t s m 产生疆优 排序否则p 。0第一个来到鸩，且膨。的负载小于_ 2 7 又因 t 5 了2 t ，为避免停机准则1 ，如+ p 了3 t 按辣法步4 4 ，p ：。 到来时必在鸲上加工，又t ，则此时两台处理器总的加工时间至少为 恐+ p + 尹。0 + r z t 矛盾故此种情形工i 牛集中有且仅有个大工件p ：，又 恐t ，所以s m 产生最馕季 序。 至j 墩我翻诞明了算法s m 豹竞争毙为影5 ，照姥是最钱半在线算法。 定理2 繇f 求解p 2 ，r ；t s u m & m a x c 。( d 豹竞争毙为6 5 。 证翻：在定理1 兹 委疆中，我翻汪疆了黠嚣标e 一( 掰) ，算法s m 要么产生 最饶 序，要么产象个籍 序，它静謦标德不怒过最伉值静6 巧倍。对前一稀情 况，该稚序显然也惫关于露标瓯。( ，) 的最优莽 净，两对君种 骞况的每释可能， 我们的算法仍保证藏时c 掣t 2 成立( 由于_ i 龟时 l 台机器m = m 。，m ：，坂) 加工机器够的加工速度为 s ，= 1 , 2 ，m 任意工件在不同机器上的加工时间有相同的比例关系，它表示 若工件威分给m ，加工，则需用旦个单位时间完成该工件目标为寻求一个可行 j ， 排序，使目标函数达到极小( 或极大) 由于机器带有各自的速度，相对于同型平 行机排序问题( 可看成所有机器速