（运筹学与控制论专业论文）可重排排序问题研究.pdf

摘要 本文以经典排序模型p 2 l | g ，。为例，研究一类新的排序模型，可重排在线 排序问题，即当工件到来时必须确定它将在那台机器上加工，但当所有工件都 安排完毕后，我们可以在一定的条件下对己安排的工件进行重新安捧在本论 文中，我们研究了四类不同的模型，第一类是我们可以重排整个工件序列中的 最后k 个工件，其下界为3 2 第二类是我们可重排全部工件安排完毕后每台机 器上的最后一个工件，其下界是v 厄，同时我们给出了最优算法第三类是可以 重排任意有限的k 个工件，其下界为4 3 ，同时我们设计出只需重捧一个工件的 最优算法在第四类模型中，我们研究带费用重排问题，即可以在工件安排完毕 后重排任意工件，重排费用为工件加工时间的q 倍，目标函数为m a k e s p a n 和重 排费用之和我们给出了问题的下界，并分析了一些简单算法的竞争比 论文的编排如下： 第一章是绪论，介绍排序相关知识和初步结论 第二章研究了前三类不需重排费用的可重排模型： 第三章研究带费用重排模型 关键词：排序，在线，可重排，算法，竞争比分析 a b s t r a c t t h i sp a p e ri n v e s t i g a t e so n l i n es c h e d u l i n gp r o b l e m sw i t hr e a s s i g n m e n to n t w oi d e n t i c a lm a d l i n e 8 ，w h e r ew ec a nr e a s s i g ns o m ej o b su n d e rg i v e nc o n d i t i o n s a f t e ra l lt h ej o b sh a v eb e e na s s i g n e d f o u rd i a e r e n tv e r s i o n sa r es t u d i e da n d a l g o r i t h m sa r ep r o p o s e d t h ef i r s ti st h a tw ec a nr e a s s i g nt h el a s tkj o b so f t h es e q u e n c e ，w h o s el o w e rb o u n dr e m a i n s3 2 ，w h e r e i saf i n i t en u m b e r t h e s e c o n di st h a tw e 湖r e a s s i g nt h el a s tj o bo fe a c hm a c h i n e o p t i m a la l g o r i t h m w i t hc o m p e t i t i v er a t i o 以i sg i v e n t h et h i r di st h a tw ec a nr e a s s i g na r b i t r a r yk j o b s o p t i m a la l g o r i t h mw i t hc o m p e t i t i v er a t i o4 3i sg i v e n t h ef o u r t hi st h a t w ec a nr e a s s i g n a n y j o b b u t 讯t hs o m ec o s t ，w h i c h i s p r o p o r t i o n t o t h es i z e o f j o b ， t h ec o e f r c i e n ti s 口w eg i v et h el o w e rb o u n do fi ta n da n a l y s i st h ec o m p e t i t i v e r a t i oo fs o m es i m p l ea l g o r i t h m s t h ep a p e ri so r g a n i z e da sf o l l o w s ： t h ef i r s tc h a p t e rg i v e st h ep r e l i m i n a r i e st h a tw i l lb eu s e di nt h er e s to ft h e p 印e r t h es e c o n dc h a p t e rs t u d i e st h ef i r s tt h r e em o d e l st h a tr e a s s i g n m e n tw i t hn o c o s t t h et h i r dc h a p t e rs t u d i e st h em o d e lt h a tw ec a nr e a s s i g na n yj o bb u tw i t h s o m ec o s t k e y w o r d s ：s c h e d u l i 丑g ，o n - l i n e ，r e a s s i g n m e n t ，d e s i g na n da n a l y s i so fa l g o r i t h m ， c o m p e t i t i v er a t i o 第一章绪论 1 1 排序简介 排序( s c h e d u l i n g ) 问题是组合优化领域的一类重要问题，产生的背景是机 器制造，后来被广泛应用于计算机科学，运输调度，生产管理等领域从普通 的生产部门的计划安排，运输调度，学校课程表的制定，到宇宙飞船的复杂庞 大的飞行计划，都要用到排序的理论和算法，排序问题的研究已经成为运筹学 方向的一个非常活跃的分支捧序事实上就是利用一些机器( m a c h i n e ) 、处理 器( p r o c e s s o r ) 或者资源( r e l l r c e ) ，最优地完成一批给定的工件( j o b ) 或者任 务( t a s k ) 根据实际背景的不同，在执行任务或者加工工件过程中，可能需要 满足某些限制条件，比如任务的到达时间、截止时问、加工顺序、资源对加工时 间的影响等 1 9 1 而所谓的最优完成指的是使指定的目标函数达到最优，其中目 标函数可以根据实际需求的不同而改变 在排序问题中，处理器的数量和种类，任务或工件的限定条件、资源的种 类和性能等情况是错综复杂的，目前通常的文献都沿用g r 8 b a m 【12 】中提出的三 参数表示法来描述排序问题，它是由三个域组成：q 吲7 其含义如下： a 域表示机器的数量，类型和环境，它可以是 1 ：单台机器( s i n g l em a c h i n e ) ， p r o ：m 台同型平行机( i d e n t i c a lp a r a l l e lm a c h i n e s ) ， q m ：m 台同类平行机( u n i f o r mp a r a l l e lm a c h i n e s ) ， 胁n ：m 台不同类平行机( u n r e l a t e dm a c h i n e s ) ， f r o ：m 台处理器流水作业( f l o w s h o p ) ， o r e ：m 台处理器自由作业( o p e ns h o p ) ， j m ：m 台处理器有序作业( j o bs h o p ) 口域表示任务或者工件的性质、加工要求和限制，资源的种类、数量和对 加工的影响等约束条件它可以同时包含多项，常见的项有任务的不同到达时 间( r e l e a s e dt i m en ) ，加工过程可中断( p r e e m p t i v e ) 、任务的相关性( 一般优 先约束p r e c ，链c h a i n ，入树i n t r e e ，出树o u t r e e ) 、机器故障( b r e a k d o w n ) 等等 第一章绪论 2 ，y 域表示要优化的目标函数，包括最大完工时间( g ，。) ，最小完工时 间( c k 。) ，总完工时间( q ) ，加权总完工时间( 嘶q ) ，最大延误( l ) ， 总误工( d ，) 等等 例如对于下面这个经典的排序问题：给定一个工件的集合j = ，五，厶) ， 工件正的加工时间为a ，需要将它们安排在m 台同类平行机尬，m 2 ， 上加 工，目标函数是极小化最大加工时间，那么用上面的记号就可以简单地将这个 问题表示为a 圳l g 事实上，如果我们记 i1 ，如果工件 分配在 母上， 叫一10 其它 则此问题等价于如下定义的整数线性规划问题： r a i ng m 扎t x o = 1 ，i = 1 2 ，佗 j f f i l n 鼽，j = 1 2 。m i f f i l = 0 或1 ，i = 1 ，2 ，n ，j = 1 ，2 ，m 其中第一个约束表示每个工件仅分给一台机器加工，第二个约束表示第j 台机 器上加工的工件的总加工时间不超过g 。因此可以看出排序问题其实是一类 特殊组合优化问韪，在许多优化问题模型中都可以找到它的原型，之所以将它 们单独作为一类问题来研究，除了由于它有着非常广泛的应用背景以外，问题 本身具备的特殊性也是一个重要因素，而寻找一个晟优排序就是要充分利用这 些特殊性质因此，作为运筹学一门新兴的学科分支，排序论在近几十年内正被 越来越多的学者深入地研究，在国内也产生了大量的相关文献 在经典排序文献中，我们根据排序者在排序时掌握的工件信息的多少把排 序问题分为离线排序，在线排序两类在离线问题中，全部工件的所有信息在排 序时均已知，排序者可以充分利用上述信息对工件进行安排而对于在线问题， 我们假设工件的信息是逐个释放的，即只有把当前到达的工件全部安捧完毕才 会得知下一个工件的信息，另外工件加工是不可改变的，即一旦排序者将工件 安排给某台机器加工，在其后的任何阶段都不能以任何方式加以改变 第一章绪论3 随着排序和实际的发展，又产生了新的一类排序，半在线排序2 8 ，2 9 1 半 在线排序是介于在线排序和离线排序之间，即排序者一方面不可能知道工 件的所有信息，但拥有比经典在线模型更多的信息或有更大的排序自由度， 并且工件安排加工后不可更改半在线排序主要可以分为两类，第一类半在 线模型是指排序者掌握后续工件的部分信息，第二类排序是指已安排的工 件的加工进程可通过某种方式加以改变目前研究较多的是第一类半在线模 型3 ，4 ，7 ，8 ，1 3 ，1 4 ，1 5 ，1 6 ，1 8 ，2 4 ，2 5 ，2 6 1 ，如已经工件总加工时间( k n o w n 眦m ) ，已知工件最大加工时间( k n o w nl a r g e s tj o b ) ，工件加工时间在一区间 内( i n t e r v a l ) ，工件加工时间非增( n o n - i n c r e a a i n gj o b ) 等以及它们之间的复 合第二类半在线模型主要有带缓冲区( b u f f e r ) ，两个平行处理子系统( t w o p a r a l l e lp r o c e o m ) 等【1 8 ，2 7 】 求解离线和( 半) 在线问题的算法分别称为离线算法和( 半) 在线算法，对 于( 半) 在线算法，我们采用竞争比分析来衡量算法的有效性，它属于最坏情况 分析对于在线问题的算法a ，i 己g a ( i ) f f i c ( i ) 分别表示算法a 解实例，所得的 目标函数值和相应问题离线情形的最优目标值，对于极大化排序问题，则称 c a = i n f c 1 1 6 * ( 1 ) 。c 4 ( j ) ，v ，) 为在线算法a 的竞争比；对于极小化排序问题，则称 c a = i n f c i l c a ( i ) c c ( nv l 为在线算法a 的竞争比若称在线问题的下界为c ，则是指该问题不存在竞争比 比c 小的在线算法为了得到问题下界，一般可以通过给出一系列实例，使得任 何在线算法都不能很好的求解所有实例来得到若算法a 的竞争比等于该问题 的下界，则称a 为最优算法从竞争比的意义上看，它是指在线问题可能得到的 最好结果 第一章绪论 4 1 2 可重排在线排序 在经典排序中假设工件加工后不可重排，但在实际生活中未必如此考虑 下面实例：一个服务器，其存储设备由若干存储器组合，当信息文件到来时，必 须当即安排其存储在某个存储器上，为保持文件读取的完整性，同一文件都必 须存储在同一存储器上，同时为了高效性我们需要保持各个存储器的平衡，即 有必要将文件在各个存储器上进行调整，但受c p u ，网速等的影响我们的调整 有一定的限制，另外重排也有可能产生一定费用对于这类当工件到来时必须 确定它将在那台机器上加工，当所有工件都安排完毕后，我们可以在一定的条 件下对工件进行重排，称此类排序其为可重排排序可重排排序虽然是一个较 新的领域，但在实际中有很大的用处，目前研究也有初步进展在本论文中，我 们主要研究四类可重排在线排序模型，第一类是我们可以重排整个工件序列中 的最后k 个工件，第二类是我们可重排全部工件安排完毕后每台机器上的最后 一个工件，第三类是可以重排任意有限个工件，在第四类模型中，我们研究带费 用重排问题，即可以在工件安排完毕后重排任意工件，重排费用为工件加工时 间的口倍，目标函数为m a k e s p a 和重排费用之和对于这几类模型，我们分析了 问题的下界，并设计了一些算法 可重排捧序也可视作第二类半在线排序的一种，但与已知的其他半在线模 型又有差别在带缓冲区的半在线模型 18 1f 2 7 1 中，假设在机器系统之外存在一 个长度为k 的缓冲区，当工件到达时可以立即安排到某台机器上加工，也可以 将其暂时安置在一个缓冲区中当缓冲区中已存放的工件数为时，新到达的 工件若需暂时安置在缓冲区中，则缓冲区的一工件必须取出并立即在某台机器 在加工在两个并行子系统半在线模型18 1 中，机器系统包括一台中央处理器和 两个并行处理子系统，每个子系统即为一组平行机器集，每个工件到达后，中央 处理机将其复制后分别传给两个子系统，两个子系统独立安排该工件后互相通 报有效信息全部工件加工完毕后，中央处理器从两个子系统中得到的排序中 选择好的那个作为我们的结果在有界可重排排序【2 2 1 中，即当任一新工件到来 时，需要立即安排到机器上加工，但同时最多可以重排已安排工件中总加工时 间不超过此工件加工时间口倍的工件集而在我们的模型中，重排只能在所有 的工件加工完毕后才能进行 第一章绪论 5 1 3 相关结果 在众多排序问题中，平行机排序是其中最活跃的分支之一，有不少文 献进行了研究并得到了丰富的结果最早的是1 9 6 6 年g r a h a m 在关于平行机排 序的奠定性文件【1 1 1 中提出了求解尸饥i i g 一问题的l s ( l i s ts c h e d u l i n g ) 算 法，即按工件到达顺序将它们安排在能使其最早完工的机器上加工，l s 的 竞争比为c 正8 g o ”2 1 m 在l s 算法提出二十余年后，f 菌g l e ，k e r n 和m d r a l lf x 0 j e 明了当m = 2 ，3 时，l s 算法是最优的在线算法在这之后，寻 找m 4 时的最优在线算法或改进已有结果的工作从未停止过【l ，2 ，5 ，1 7 r u d i n 和c h a n d r a s e k a r a nf 2 0 1 给出了当仇= 4 时问题的下界为 3 ，降低了 问题下界和已知算法之间的差距。f l e i s c h e r ，w a h l 在10 1 中改进了问题的算 法，当m + c l o 时其竞争比为l + ( 1 + l 2 ) 2 j 若a 将p 1 ，p 2 安排在不同机器上，则第三个工件舶= 2 和最后k 个加工时间都为e 的工件依次到达，那么 罟熹一；。一0 ) 因此算法a 的竞争比至少为3 2 定理得证 口 第二章无费用可重排 8 2 2 重排每台机器的最后一个工件 在此节中，我们研究问题p g ，即当所有工件安排完毕之后我们可以重捧每 台机器上的最后一个工件首先我们证明问题的下界为以，然后设计出最优算 法r e 定理2 2 问题的下界为、，伍 证明对于求解问题尹e 的任意算法a ，考虑下面实例：开始到达的两个工件分 别g p l = 1 ，p 2 = 以若算法a 安排这两个工件在同一台机器上加工，不妨假 设在尬上，那么翔= ( 2 一v 国2 接着到来若a 安排朋也在尬上加工，则接 下来到来最后的工件m = e ( e 是一个无穷小的正数) ，当p 4 被安捧在尬上加 工时，我们只能重排工件似，当p 4 在 毛上加工时，我们可以重排船和p 4 对于 这两种情况，目标函数c “都至少为p l + 仇= 1 + 压，此时最优值口= 以，那 么有 瓦c a 1 - 4 - _ _ 娑 以 ，1 一 反之若舶被安排在肘j 上加工时，接下来依次到来最后两个工件m = 以2 和岛= e 无论工件肌，船如何安排和重排，c 。至少1 + 以，而最优值c = 1 + 以2 + e ，那么有 罢掣以( 。o ) 石声再虿磊。w 婶。” 若a 安排p l ，见在不同的机器上加工，那么接下来依次到达最后两个工件阳= 1 + 以和p = 此时c a 至少为p l + p 3 = 2 + 以。伊= 1 + 以+ e 因此有 等巢讵( 。o ) 万声再而1 “博1 w 口 现在我们给出问题p f 的最优算法r e 算法分成两阶段，前一阶段是排序， 即当新工件到来时，如何安排工件给某台机器，后一阶段是重排，即所有工件到 来安排完毕之后，如何重捧以得到更好的目标函数值具体思路如下：在排序阶 段保持两机器负荷相对大小在一定范围内，同时避免将比较大的工件安排在负 第二章无费用可重排9 荷大的机器上加工，在重排阶段则重排可重排的工件，尽量使两机器的负荷相 差最小 为了简便，我 f i a l i = 础 聊，聊) ，岛= 血 坤，聊) ，i = 1 ，n 算法r e 1 ( 排序) 当新工件b 到来时，若q ( v 压+ 1 ) ( 琶+ a ) 并且a 以耳，将a 安排在当前负荷大的机器上加工，否则安排a 在当前负荷小的机器上加 工 2 ( 重排) 假设， 分别是捧序阶段结束后两台机器上的最后一个工件，不妨 假设u 比口先到达( 若某台机器没有加工工件，则 为一个虚工件) 用，b 分别表示“，口中较大和较小的工件，即口= m a x t ， ，b = m i n u ， 依 次将口，b 安排到能使它们先开始加工的机器上加工( 若t = 时，则表 示t ，b 表示口1 引理2 3 在算法r e 中，：觏是当前要加工的工件，刖有q 以易，l = 1 ，馆 证明我们用数学归纳法来证明此引理对于前两个工件，由算法可知，引理显 然成立假设当工件a 到来时，l i 压巧若n 安排在负荷大的机器上加工， 那么由算法得知 球1 = l i + p l v i l ；+ a v 2 l ；= 乳纩1 若鼽安排在负荷小的机器上加工，由算法可得二i ( 应+ 1 ) ( 岛+ a ) 或肌 v 压日对于前一种情况， l p l = l i2 ( 以+ 1 ) ( l i + 鼽) = ( 以+ 1 ) l 1 , s l i + 1 对于后一种情况， l r l = 砭+ a 如+ 以l i 2 , s l i = 厄尹1 综上，我们有研+ 1 以罐1 命胚得证 口 第二章无费用可重捧 不失一般性设让，口分别是尬， 如上的最后一个工件假设t 表示和口之 间的所有工件加工时间之和( 不包括和u ) 显然这些工件都安排在肘；上加 工，即有懈= 聊+ ，孵= 聊+ t 由引理2 1 n - - j 知，自从第一个工件加工 之后，两台机器的负荷不可能相等，即 卵m 和m 牙除非工件序列中 只有一个工件u 时 矸= 劈，而此时算法r e 显然得到最优解 引理2 4 当聊 蟛时，g 衄缈以 证明因为口安排在负荷大的机器上加工，由算法可知 埘+ t s ( 以+ 1 ) ( 岈+ + 口) 并山s 以( 孵+ 力 又因为 埘 埘+ t = 嵋 蟛= 蟛+ 正 那么n 重排在m 上加工 若 卵+ o 蟛+ t ，那么6 将安排在 五上加工，那么有 m 1 = w + 卅b 2 ( 岬+ d ) 2 ( 啤+ t ) = 2 ( 以+ 1 m 并且 m 2 = 蟛+ t ( 以+ 1 ) ( 岬+ t + 口) = ( 以+ 1 ) ( 聊+ 口+ 6 ) = ( 以+ 1 ) m 若聊+ 口蚜+ 死那么6 将安排在上加工由婶+ “ b = 因此有 并且 尬= 聊+ 口= 埘+ 钉 ( 噬+ t ) + 以( 坶+ t ) ( 讵+ 1 ) ( 坶+ t + 6 ) = ( 以+ 1 ) 尬 = 蝣+ t + b 埘+ o + b 2 ( 埘+ o ) = 2 尬 肘j = m t + t 并 且口在负荷小的机器上加工，则由算法可知 砰+ u ( v 压+ 1 ) ( 劈+ t + 口) 或 者口 、2 ( 矸+ t ) 情形1 l 矸 ( v 3 + 1 ) ( m 孑 i - t + v ) m t + m t + 可 可得珏= a 6 = 口由于 朋 + 口= 矸+ 朋警+ t 那么b 被重排到尬上加工因此 m = 埘+ = m t + t 蜂+ t + = 埘+ t + b = 尬 又由引理2 1 可得 2 j 聊那么有 旦竺 v 3 ( m + ) 由可 以( 聊+ t 正) i t l , 可知 = a 6 = i , 由于 埘+ o = 埘+ 埘+ t 埘+ t 第二章无费用可重排 则6 被重排到 毛上加工，那么有 “= m ? + 并且肘j = 肘+ t + 若婀 ( 以+ 1 ) ，则 ( 以+ 1 ) + t + t ) 一聊，再由引理2 1 得到的蜂 以聊， 我们可得 竺 丝：业 e 秒口 ，+ 而百顽峦筝丽 1 + 而i 而1 = , i 若尬( , i + 1 ) m 2 ，由引理1 1 可得g 船口以若 m 2 ，那么 有 尬 m 2 = 肘+ t + u 朋7 + u + 2 ( m + u ) 矸一 劈0 可得知工件 必然存在因为t ，安排在负荷小的机 器m 2 上加工，由算法有 埘+ = 蚪 ( 压+ 1 ) ( 蟛+ 埘) = ( 以+ 1 ) ( 孵+ d 或者 伽 ( 以+ 1 ) 岬= ( 以+ 1 ) ( 埘+ u ) 由假设聊+ u 啤+ t t 叫可知后者不会出现因此有 孵+ t ( 以一1 ) ( 峭+ t ) ( 以一1 ) ( 埘+ 以埘) = 埘 后一个不等式是由于工件“安排在负荷较大的工件上加工，这和假设m v 伍( u r - t - u ) 子情形3 1 肋 + 口 ( 以+ 1 ) ( m + t + ) 当蜂+ t + 聊时，b 被重排到肘j 上加工因为m s ( 压+ 1 ) ( 劈+ t ) ， 那么我们可得 尬= 聊( 以+ 1 ) ( 孵- 4 - 札) ( 以+ 1 ) ( 叼- i - t + 口- i - 6 ) = ( 以- i - 1 ) 并且有 m 2 = 蠼+ t + 口+ b 2 ( 埘+ t + o ) s2 埘= 2 m 聊时，b 被重排到尬上加工，则有m l = 矸+ b ， 毛= 朋詈+ t + 口若m 1 5 尬，由 筹：三嚣紫 枷 可得u = a 6 = ，因此有 尬= 坶+ t - i - u 埘+ - i m ? ( 以+ 1 ) m i 若 毛，则有 m 2 m = 岬+ 6 以( 聊+ 缸可得口= 秽 t = b 再由 垅+ t + 口口 以( 岬+ t ) 岬 可知b 被重排到 以上加工因此有 = 嗍+ t + 2 v 伍( m r + t ) 埘+ t = 尬 若( 以+ 1 ) 尬，由引理1 1 可知c 船口以否则辄 ( 以+ 1 ) ( 孵+ ) 一( 蜂+ t ) ，再由引理2 坷得聊+ t = 懈以蟛= 以( 蟛+ t ) ，那么 有 o r e 曼鱼：生堡! ! 伊口口 + 而丽鬻禺丽 ，+ 丽南= 以 综上则有伊5 伊以，即算法r e 的竞争比为压 综合定理2 1 和2 5 可得，算法r e 是p 目的最优算法，竞争比为压 口 第二章无费用可重排 2 3 重排有限个任意工件 在本节中，我们研究新的可重排模型p a ，当所有工件安排完毕之后，我们 可以重排任意有限个工件我们首先给出问题p 的下界为4 3 ，然后我们设计出 算法r a ，在算法r a 中，至多只需重排一个工件，但其竞争比达到了问题的下 男- 4 3 ，即为最优算法，同时也意味着重排的工件由一个增加到有限的女个时， 并不能使竞争比得到改善 定理2 6 问题p t 的下界为4 3 证明对于求解问题只t 的任意算法a ，考虑下面实例：开始到达的是3 凡个加工 时间都为1 的工件，经过算法a 排序后，假设两台机器的负荷分别为工l 和岛， 不失一般性，我们假设n 是偶数并且l l 1 , 2 当l 1 2 时，由安排在m j 上加工可得 碍+ 暑， 2 碍，那么有 z 2 ( 懈+ s + r + 可) 一嗍22 ( 啷+ y ) 一鸸 3 蟛 霎cs 警= 华兰3 二zz - = 。 当m 1 m 2s2 m 1 时，由引理1 1 可得e 肌e 。s4 3 当 2 ( 嗍+ f ) 并且由 假设肘 2 哪即m ；+ y + z 2 ( m + s + r ) 将这两个不等式相加，我们 有2 z 嗍+ y + 删+ s + 2 r 那么可得 m 2 尬= 砰+ s + r + 矿 2 x 2 ( 朋考+ z ) = 2 m 2 再由引理1 1 有g r 口s4 3 至此我们证明了定理 口 综合定理2 6 和2 7 ，我们可知见4 是问题只4 的最优算法，其竞争比为4 3 第三章带费用可重排 在前面几节中，我们研究的各种重排模型都是无费用的，但是在实际生活 中，有不少重排需要付出一定的代价，因此也就产生一些费用在我们下面考 虑的模型中，我们假设工件安排后可以重排任意工件，重排费用与工件的加工 时间成正比，比例系数为口，目标函数是m a k e s p a n 和重排费用之和，记该问题 为七当q 1 时，重排可能减少的m a k e s p a n 不小于重排费用，因此重排没有 任何意义，此时模型就等价于在线排序模型，那么问题的下界为3 2 ，l s 为此时 的最优算法；当a = 0 时，由于无重排费用，我们可以在工件全部到达后任意 重捧并且不改变目标函数值，则此时模型等价于离线排序模型下面我们仅考 虑0 口 1 时的情况 3 1 问题的下界 引理3 1 问题死的下界至少为 m ，= ：象”：荔驾： 证明对于求解问题0 的任意算法a ，我们用对手法来证明此引理 当o 1 + 丝2 q 伊1 若a 将p 1 ，仡安排到不同的机器上加工，则再来的两个工件为翔= p 4 = 以+ 1 若a 安排阳，p 4 在同一台机器上加工，则可将p 4 重排到另一台机器上得到更优 的m a k e s p a n 。即 c 4 = m m l + 2 ( 以+ 1 ) ，1 + 讵+ 1 + ( 讵+ 1 ) n = 2 以+ 2 + ( 扼+ 1 ) a 第二章带费用可重排1 9 那么有 c a g ! 生! ! 丝1 2 竺 以+ 1 ，以 2 1 + t 口 若册，p 4 安排在不同的机器加工时，接下来到达最后的一个工件p s = 2 压，不妨 假话b 。，翔，船安排在蛆上加工，那么算法a 在重排中有四种不同的选择，或者 不重排，或者将p l 重新安排到 如上加工，或者将p 3 重排至肘；，或者同时将珊重 排至 毛，p 2 重排至m 上加工，则 c a = m “3 以+ 2 ，3 以+ 1 + o ，2 讵+ 3 + ( 以+ 1 ) q ，2 以+ 2 + ( 2 + 以) q = 2 以+ 2 + ( 2 + 扼) n 万c a = 塑学一雩。万2 刁i 广。1 十t “ 综上可得当o 口s3 2 j 时砭的下界为1 + 宰口 当3 2 i n 1 + 望2 。 c 1 若a 将p 1 ，仡安排到不同的机器上加工，则再来两个工件翔= 肌= 击若a 安 排船，m 在同一台机器上加i ，则 = 叫+ 熹，嵩) = 篙 那么有 害= 誊= 1 + 墨杀= 鲁= + 兰u 7 一 。一l 否则若p 3 ，p 4 安排在不同的机器加工时，接下来到来最后的一个i 件船= ( 2 + 2 c r ) ( i o ) ，那么 = m i n 等+ 口击+ 3 i - - - - - l q ) = 百4 + 3 a - a 2 第二章带费用可重排 2 0 则有 万：荽叫r3ca3 1 4 - c 等， 一= 一= i f y 一一1 二4 4 1 一a 综上可得3 2 v 伍 c ( 晚) d 两式相加则有 懈+ 蟛= m n + 尬l + m n + 2 c ( 观) 聊+ 聊 出现矛盾，假设不成立，因此引理得证口 第二章带费用可重排 特别的，当0 2 为最优排序时，由引理我们可知，对于排序阶段的任意排序， 都存在一个重排策略，使得算法的竞争比不大于14 - 口由于p 2 g 。是n p 完 全问题，不存在多项式时间的最优排序算法，因此在多项式时间之内也不 存在重排策略将某一排序结果重排成最优解。但p 2 i g 。存在f p r a s ( f u l l p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) 2 3 ，即存在时间复杂性为0 ( 一e ) 的算 法w m f t ( e ) ，使得d c y l + e 因此我们可以设计如下算法： 算法日 1 当0 口 1 2 时 ( a ) 将所有到达工件都安排在机器尬上 ( ”对固定的e ，用w m f t ( e ) 算法对所有工件进行排序，记决定m a k e s p a n 的机器上的工件集合为五 ( c ) 将尬不同于正的工件重新安排到m j 上加工停止 2 当1 2 a 1 时，用l s 算法对当前到达的工件进行排序停止 定理3 3 算法日的竞争比为 ) ： ，( 1 札) ( 1 + e ) ， l 互。 0 q j 1 i 1 a 1 证明当o n 1 2 时，不妨假设正中所有的加工时间为肘：，由算法可知重排 工件的总加工时间不大于肛，则有 因此 尬+ 尬o ( 1 + n ) ( 14 - e ) 口 吕坠警堂- ( 1 刊( 1 + e ) 当1 2 q 1 时，显然有c h c + = g 8 伊3 2 口 下面我们考虑在排序阶段用l s 安排工件加工，然后通过任一重排策略进行 重排，记此类算法为n l s ，我们研究一下它们竞争比的下界 第二章带费用可重排 引理3 4 n l s 的竞争比不优于 如，= 塞i 麓 a l ，?l + 3 a ，。 证明当0 口1 3 时，考虑如下实例：依次到来的四个工件加工时间分 别为p l = l ，见= p 3 = 1 2 ，肌= 1 ，不妨假设经过l s 排序后p lp 4 在m 1 上加 工，p 2 ，船在m 2 上加工，在各种重排策略中，将m 重排至m 2 ，p 3 重排至m 1 上加工 是最优策略，此时的m a k e s p a n 为c l s = 3 ( 1 + o ) 2 ，而俨= 3 2 ，则c l 5 俨= 1 + 口 当1 3 口 1 时，考虑如下实例：依次到来的四个工件加工时间分别 为p l = 1 ，见= 崔，p 3 = 告，p 4 = 盖，不妨假设经过l s 排序后p l ，内在m 上 加工，p 2 ，p 4 在 如上加工，不重排时的m a k e s p a n 为c l s = 警，在各种重排 策略中，将n 重排至m 2 ，p 2 重捧至 毛上加工是最优策略，此时的m a k e s p a n 也 为c l s = 等，而c = 尝，则有 竺：冀：一1 + 5 a若2 盘1 - a2 雨五 口 对于经典模型p 2 a 。，若不能重排时，l s 是最优算法，但是在能重排 的情况下，由引理3 4 可知，在排序阶段用l s 算法是非常不好的选择，特别是 当0 o 1 3 时，效果不比将所有工件安排到一台机器上加工好当口较大 时，9 ( o ) 与问题的下界也有较大的差距，寻找砭的非平凡算法是一件非常有意 义的工作如图所示，( a ) - 与h ( a ) 之间存在着很大的差距，不断设计新的算法， 寻找问题的更好下界，减少两者的差距，这是我们所要改进的目标。若能找到 算法使其竞争比与问题下界相等，也就达到了最终目的。 第二章带费用可重排 图3 1 ：不同界的曲线 参考文献 1 】a l b e r ss ，b e t t e rb o u n d sf o ro n - l i n es c h e d u l i n g ，s i a m 正c o m p u 2 9 ( 1 9 9 9 ) p p 4 5 9 4 7 3 【2 】a l b e r ss ，o nr a n d o m i z e do n l i n es c h e d u l i n g ，p r o c e e d i n g so lt h e3 4 t ha c m s y m p o s i u mo nt h e o r yo fc o m p u “n g , m o n t r e a l ，2 0 0 2 ，p p 1 3 4 1 4 3 3 】a z a ry a n de p s t e i nl ，o n - l i n en l a 幽ec o v e t i n g ，s c h e d u l i n g1 ( 1 9 9 8 ) ， p p 6 7 7 7 4 】a z a ry a n dr e g e vo ，o n l i n eb i ns t r e t c h i n g ，t h e o r e t i c a lc o m p u t u t e r 黝 e 胧，2 6 8 ( 2 0 0 1 ) ，p p 1 7 4 1 1 5 】b a r t a ly ，f i a ta ，h k a r l o f fa n dr v o h r a ，n e wa l g o r i t h m sf o ra l la n c i e n t s c h e d u l i n gp r o b l e m ，正c o m p u t 跏t 咖s c 5 1 ( 1 9 9 5 ) ，p p 3 5 9 3 6 6 【6 c h e nb o ，v a nv l i e ta ，w o e g i n g e rg ，a no p t i m a la l g o r i t h mf o rp r e e m p t i v e o n - f i n es c h e d u l i n g j o p e r a t i o n sr e s e a r c h 工e 钟e 舟，( 1 9 9 5 ) ，p p ：1 2 7 - 1 3 1 me l t e i nl ，b i ns t r e t c h i n gr e v i s i t e d ，a c t ai n f o r m a t i o n 3 9 ( 2 0 0 3 ) ，p p 9 7 1 1 7 【8 】e p s t e i nl ，f a v r h o l d tl ，o p t i m a ln o n - p r e e m p t i v es e m i - o n l i n es c h e d u l i n go i l t w or e l a t e dm a c h i n e s ，p r o c e e d i n g so ，t h e2 7 t hm f c s , 2 0 0 2 ，p p 2 4 5 2 5 6 9 】f a i g l eu ，k e r n ，w ，w u r a , i i ，g ：o nt h ep e r f o r m a n c eo fo n - l i n ea l g o r i t h m f o rp a r t i c u l a rp r o b l e m a c t a 回b e r n e t i c a , 9 ，( 1 9 8 9 ) p p ：1 0 7 - 1 1 9 【1 0 】f l e i s c h e r ，r ，w a h l ，m ，o n - l i n es c h e d u l i n gr e v i s i t e d ，j o u r n a lo ，s c h e d u l i n g 3 ，( 2 0 0 0 ) p p ：3 4 3 - 3 5 3 1 1 1 】g