（运筹学与控制论专业论文）预知复合信息半在线排序问题算法研究.pdf

摘要 摘要 机器排序和机器覆盖经常在实际运用中出现，比如在网络通信中通道分配均 衡问题，大型的并行计算问题，柔性生产系统中任务排序问题，等等这篇论文主 要研究了m 台平行机的复合半在线排序问题考虑了半在线机器覆盖问题，这个 问题最先i 扫d e u e r m e y e r 等提出应用于维持飞行器燃气涡轮发动机的运转和基于 提高网络服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) 而产生的带宽分配同时还考虑了 最先由a z a r 和r e g e v 提出的在线b i ns t r e t c h i n g l h - j 题，以及机器带准备时间的半在 线排序问题这些问题都具有着一定的现实背景，针对每个问题都分析了下界并 设计了相应的半在线算法，有的算法是最优算法全文共分为七章 第一章是绪论部分，主要介绍一些组合优化以及算法设计与分析方面相关的 概念和预备知识 第二章简要综述了近年来与本文相关的在线与半在线平行机排序问题的若 干成果，并简单说明了一下本文的一些主要结果 第三章研究了两台同型平行机半在线排序问题，也即事先预知复合信息：所 有工件大小总和和最大工件大小的半在线排序问题( p 2 l s u m m a x l ) 尽 管p 2 1 s u m & m a x a m z 具有竞争比为：的最优算法，但这是针对最坏情况进行分 析所得到的结果，并不理想，其实很多时候能够得到竞争比更好的算法因此这章 主要分析- j p 2 1 s u m m a x l c m 船当参数r = 印霉t 取不同的值时问题的下界并 设计了相应的算法，下界与算法的竞争比均是关于r 的函数当r = ：时有竞争比 为的最优算法当丢r 1 时给出了最优算法，算法的竞争比为 博莲 第四章主要研究了预知工件大小按非增排列到达，目标为极小化s t r e t c h f a c t o r 的半在线b i ns t r e t c h i n g i h - 题也即预知工件大小按非增排列到达和离线状态 下最优目标值，目标为c m a z ( m a k e s p a n ) 的平行机排序问题对于m 台机器的情 形，证明了问题的下界至少是訾，并设计了竞争比至多为1 + 罴兰的半在线算法 对于e 3 l o p t d e c r i g 一，则改进了算法，给出竞争比至多为；的算法 第五章主要研究了已知工件大小上界为c + 七的平行机排序问题，根据是 摘要 否已知最优目标值的不同模型，分别针对两个目标g 霉和i n 进行了分析对 于p m l 七一b o u n d e d l c 仇们，证明了当m k + 1 时l s 算法为最优算法，竞争比 为1 + 石m - - 万1 ，当m k + 1 时下界至少为1 + 由对于p m l o 嘶k b o u n d e d l c m ， 证明了下界至少为1 + 互雨1 同时针对两台机的情况设计了竞争比为1 + 赤的 最优算法o b 2 对于p m i 忌一b o u n d e d l 打证明了l s 算法为最优算法，竞争比 。_ ，m k 鬲对于p 仇i o 讲k b o u n d e d l c m i n ，证明了下界至少为1 + 1 ，并y 2 # - f 竞争比为1 + m 万- - 1 的算法 第六章研究了三台机机器带准备时间的半在线m a c h i n ec o v e r i n g i h - j 题p 3 ，n | i 竹对于预知所有工件加工时间总和和最大工件加工时间的复合 半在线问题，给出了竞争比为；的最优算法 第七章为后记，简要总结了本文的工作，讨论了将来可以进行的研究方向以 及一些有待研究的公开问题与模型 关键词：排序，算法设计与分析，半在线，竞争比 一一 a b s t r a c t a b s t r a c t m a c h i n es c h e d u l i n ga n d c o v e r i n gp r o b l e m sm a yo c c u ri nm a n ya p p l i c a t i o n ss u c h a sl o a db a l a n c i n gi nn e t w o r kc o m m u n i c a t i o nc h a n n e la s s i g n m e n t , p a r a l l e lp r o c e s s i n g i nl a r g e - s i z ec o m p u t i n g ，t a s ka r r a n g e m e n ti nf l e x i b l em a n u f a c t u r i n gs y s t e m s e t c i n t h i st h e s i s ，w es t u d yt h es e m i o n l i n es c h e d u l i n gp r o b l e m so nm p a r a l l e li d e n t i c a lm a - c h i n e sw i t hc o m b i n e dp a r t i a li n f o r m a t i o n w e s t u d yt h es e m i o n l i n em a c h i n ec o v e r i n g p r o b l e m , w h i c hw a sf i r s tp r o p o s e db yd e u e r m e y e re t a 1 a n dh a sa p p l i c a t i o n si nt h e s e q u e n c i n go fm a i n t e n a n c ea c t i o n sf o rm o d u l a rg a st u r b i n ea i r c r a f te n g i n e sa n db a n d - w i d t ha l l o c a t i o no np a r a l l e ll i n k sm o t i v a t e db yi s s u e so fq o s w ea l s oc o n s i d e rt h e s e m i - o n l i n eb i ns t r e t c h i n gp r o b l e m ，w h i c hw a sf i r s tp r o p o s e d b ya z a ra n dr e g e v , a n d s c h e d u l i n gw i t hn o n s i m u l t a n e o u sm a c h i n ea v a i l a b l et i m e s a l lp r o b l e m sa r i s ei nv a r - i o u sa p p l i c a t i o n s f o re a c hp r o b l e m , w eg i v el o w e rb o u n d sa n dp r e s e n ts e m i o n l i n e a l g o r i t h m s ，w h i c ha r eo p t i m a li ns o m ec a s e s t h et h e s i si ss p l i tu pi n t os e v e n c h a p t e r s i nc h a p t e r1 ，w ei n t r o d u c es o m ep r e l i m i n a r yc o n c e p t sr e l a t e dt od e s i g na n da n a l - y s i so fa l g o r i t h m i nc h a p t e r2 ，w es h o wt h em o d e l sc o n s i d e r e di nt h i st h e s i s ，a n ds u r v e y t h er e l e v a n t r e s u l t so fo n l i n ea n ds e m i o n l i n ep a r a l l e lm a c h i n e ss c h e d u l i n gp r o b l e m s t h e nw e p r e s e n tt h em a i nr e s u l t so ft h i st h e s i s i nc h a p t e r3 ，w es t u d yt h es e m i o n l i n ev e r s i o no fs c h e d u l i n go nt w o p a r a l l e li d e n t i c a lm a c h i n e s ，w h e r et h et o t a lp r o c e s s i n gt i m eo fa l lj o b sa n d t h ep r o c e s s i n gt i m eo f t h el a r g e s tj o ba r eb o t hk n o w ni na d v a n c e ( p 2 1 s u m & m a x q 抛z ) e v e n t h o u g ht h e r e e x i s t sa l lo p t i m a ls e m i 。o n l i n ea l g o r i t h mf o rp 2s u m & m a x 们w i t h c o m p e t i t i v er a t i o ；，t h er e s u l ti sn o tg o o d ，b e c a u s e i tw a sa t t a i n e dw h e no n l yf o c u so nt h ew o r s tc a s e a l g o r i t h mw i t hb e t t e rc o m p e t i t i v er a t i oc o u l db er e a c h e df o rm o s tc a s e s i nt h i sc h a p t e r w ef o c u so ns u c ht o p i c ：i fw ec a ng e tb e t m ra l g o r i t h m sf o r p 2 1 s u r n m a x l g 加zi n t e r m so ft h ep a r a m e t e rr = 劫m 口z t f o rd i f f e r e n tv a l u e so f r ，w es h o wl o w e rb o u n d s a n dd e s i g na l g o r i t h m s b o t ht h el o w e rb o u n d sa n d c o m p e t i t i v er a t i o so f t h ea l g o r i t h m s a r eg i v e na sf u n c t i o n so f p a r a m e t e rr f o rt h ec a s er = ，w es h o wa no 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 o 石7 w h e n 两7 r 1w ea l s od e s i g no p t i m a la l g o r i t h m s ， 一一 a b s t r a c t t h ec o m p e t i t i v er a t i oi s f 孚，i f 2 r ， i f l 【丁4 - - i ，i f i 3 1 l 品g v n ( r a ( 7 r ) = i 号f r 1 o a p t ( j ( ) i ) nv ，) ) 而对于( 半) 在线问题，任意实例的信息并不是事先完全知晓，而是在处理的过 程中逐步知晓，所以一般情况下对于( 半) 在线算法性能的衡量，是将算法解得 的目标值和离线状态下该实例能够得到的最优目标值相比较同样取其下界，称 为( 半) 在线算法a 的竞争比 定义1 3 6 ：如果7 r 是一个极小( 大) 化( 半) 在线问题，是任意的实例设a 是 求解7 r 的一个( 半) 在线算法用a ( ，) 和0 尸丁( ，) 分别表示算法a 解实例，所得 的目标函数值和离线状态下的最优目标值则( 半) 在线算法a 的竞争比 ( c o m p e t i t i v er a t i o ) 定义为， r a ( 丌) = 1 n f r 1 l 蔷gw ) 一5 一 第一章绪论 ( r a ( 丌) = i 妒1 o 删p t ( i ) - r ，w ) ) 定义1 3 7 ：如果7 r 是一个( 半) 在线问题，j 是任意的实例则问题7 r 的下界 ( l o w e rb o u n d ) 定义为， p ( 7 f ) = s u p p ( 7 r ) l i r a p ( 7 r ) ，v a j 如果7 a ( 7 r ) = p ( 7 r ) ，则称算法a 对于问题丌来讲是最优的( o p t i m a l ) 定义1 3 8 ：如果某问题有一系列的近似算法 a ) ，对于任意给定的e 0 ， a ) 是 一个多项式时间算法，r a 。1 + e 则称它为多项式时间近似方案( p o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e ) ，简记为p t a s 进一步，如果 a ) 的时间复杂性是 关于输入一长度以及的某个二元多项式，则称它为完全多项式时间近似方 案( f u l l yp 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 ) ，简记为f 刀a s 例如，离线状态下p m i | g m o z 存在多项式时间近似方案( p t a s ) 4 9 并且当机 器数m 固定时，存在完全多项式时间近似方案( f p t a s ) 6 2 另外，两台平行机排 序问题p 2 1 1 c m n z 存在最坏情况界为靴4 l 】的一个线性时间的有效近似算法由于 某些组合优化问题本身固有的难度以及最坏情况界的估计需要很强的数学基础 和技巧，导致很多情况下无法证明某些算法的最坏情况界，而实际问题又迫切 需要给出一些求解方案，在这样的情况下，有了启发式算法的概念 定义1 3 9 ：启发式算法是一个基于直观或经验构造的算法在可以接受的花 费( 一般指计算时间、占用空间等) 下给出待解组合优化问题每一个实例的一个 可行解，该可行解与最优解的偏离程度不一定事先可以预计 评价启发式算法的性能主要分为两类，一类是评价该算法占用的时间、空 间( 分别称为时间复杂性和空间复杂性) 等；二是分析该算法的效率，算法效率往 往采用大规模的随机数据进行实验验证，从平均的角度以及最坏的角度来进行 衡量 1 4 排序问题算法设计与分析 排序问题的算法( a l g o r i t h m ) 是指事先制定的一个执行策略，对该排序问 题的任何一个具体实例，按照这个执行策略可以得到一个可行的，达到一定目 一6 一 第一章绪论 的的排序排序问题有离线、在线与半在线之分，解决离线问题的算法称为离 线算法，而对应于( 半) 在线问题设计的算法就是( 半) 在线算法经典的离线算 法和( 半) 在线算法有解平行机排序问题的p t ( l a r g e s tp r o c e s s i n gt i m e ) 算 法【1 8 ；3 5 1 和l s ( l i s ts c h e d u l i n g ) 算法【3 6 】由于在离线问题中，事先预知工件的 全部信息，因此l p t 算法先将所有工件从大到小排列，然后依次将它们安排在能 使其最早完工的机器上加工而对于在线问题，在排序的过程中后续工件的信息 并未( 完全) 知晓，因此己s 算法只是将工件按到达的先后顺序依次安排在能使 其最早完工的机器上加工相对于在线问题，事先预知的部分信息有利于设计出 性能更好的( 最优) 算法，这就是这篇文章所所感兴趣的问题在上个世纪，半在线 排序问题就得到了广泛的研究【5 l ；4 5 ；9 ；4 4 ；1 5 1 ，同时预知两种信息的复合式半 在线排序问题也得以研究【6 9 ；2 1 1 已经证明，本论文讨论的排序问题都是n p - 难的，因此本论文的主要 工作是近似算法的设计与性能分析( 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 ) 来衡量 对于任意的排序问题实例( m ，歹) 和算法a 记c a ( m ，7 ) ( 或c a ) 为算法a 所得 到的目标值，记c + ( m ，歹) ( 或c + ) 为离线状态下能得到的最优目标值对于 极大化目标的排序问题，算法a 的竞争比定义为：使得任意实例( m ，y ) 满 足c a ( m ，了) c c + ( m ，了) 的最小常数c 对于极小化目标的排序问题，算法a 的 竞争比定义为：使得任意实例( 朋，歹) 满足c + ( 州，歹) c c a ( 州，7 ) 的最小常 数c 若一个( 半) 在线排序问题的任意算法的竞争比至少为p ，则称这个问题的 下界( 1 0 w e rb o u n d ) 为p 若一个( 半) 在线算法a 的竞争比与问题的下界相等，则称 这个算法是最优的( o p t i m a l ) 上面所定义的算法称为确定性算法( d e t e r m i n i s t i c a l g o r i t h m ) ，而近年来，组合优化问题的研究又增加了随机算法这一新的工具所 谓随机算法( r a n d o m i z e d a l g o r i t h m ) 是指在算法执行过程中可以作出随机选择的一 类算法有关随机算法可参i n m o t w a n i 和r a g h a v e n 的专著 5 8 对应的排序问题随 机下界可利用y a o 氏定理 7 9 】得到排序问题的随机下界不会小于确定性的下界， 而最好的随机算法的竞争比则不会大于任何确定性算法的竞争比因此，如果存 在一个确定性算法，它的竞争比与该问题的随机下界相等，在这种情况下，可以说 研究该问题的随机算法是没有意思的相对确定性算法而言，随机算法在排序中 的应用虽逐渐增多，但还远未成熟若不特别说明，文中所涉及的算法均为确定性 算法 一7 一 第二章半在线排序问题综述 第二章半在线排序问题综述 排序问题是组合优化领域中的一类重要问题，在生产管理与调度，网络通信， 理论计算机科学等方面有着广泛的应用而这篇论文所研究的平行机半在线排序 问题是排序问题中最活跃的分支之一我们在资料所及范围内，首先针对本论文 所涉及的模型做一下介绍，然后说明一下各模型已有的结果关于平行机半在线 排序综述可以参阅文献 4 6 ；4 7 ，其涵盖了2 0 0 1 年前的半在线排序的主要结果 2 1 预知单一信息的半在线模型 首先介绍一下本文中所涉及到的几个问题的具体描述本章只介绍不可中断 的排序模型，也即工件在加工过程中不允许中断，必须一次性完成加工，关于可中 断的排序模型可参阅文献 1 4 ；6 3 ；5 0 ；2 5 等 【l 】平行机排序问题 3 5 ；3 6 】 平行机排序问题( m u l t i p r o c e s s o rs c h e d u l i n gp r o b l e m ) 是个经典的在线排序问 题，最早由g r a h a m 3 5 ；3 6 提出，【3 5 ；3 6 也是关于平行机排序的奠基性文献具体 的问题可以描述为：给定工件集了和机器集m ，工件集歹中有一系列具有正a n y _ 时间的工件，每个工件就用其加工时间大小p 1 ，p 2 ，加来表示，机器集m 包 含m 台同型平行机m ，m 2 ，工件会一个一个的到达，到达后需要立即安 排到某台机器上加工，加工过程不允许中断，而且安排当前到达工件时对后续工 件的信息并不知晓我们需要将所有的工件安排到所有的机器上加工，目标函数 是要求极小化工件最大完工时间( m a k e s p a n ) ，其中其中工件最大完工时间为最后 一个完工工件的完工时间如果机器不带准备时间，m a k e s p a n 也即加工最晚完工 工件的机器的负载( 1 0 a d ) ，这里的负载是指该机器所加工的所有工件的加工时间 总和该问题可以记为p m ii a m 茁 【2 】机器覆盖问题 2 0 】 机器覆盖问题( m a c h i n ec o v e r i n gp r o b l e m ) 最早i 扫d e u e r m e y e r 等 2 0 】提出，具 体的问题可以描述为：给定工件集了和机器集m ，工件集了中有一系列具有正加 工时间的工件，每个工件就用其加工时间大d p 1 ，现，来表示，机器集m 包 含m 台同型平行机尬，m 2 ，工件会一个一个的到达，到达后需要立即安 排到机器上加工，加工过程不允许中断，而且安排当前到达工件时对后续工件的 信息并不知晓我们需要将所有的工件安排到所有的机器上加工，目标函数是要 一8 一 第二章半在线排序问题综述 求极大化最小机器负载，其中机器的负载( 1 0 a d ) 是指这台机器所加工的所有工件 的总加工时间机器覆盖问题可以记为p 仇| i n 以上所提及的两个问题都是在线平行机排序问题，不同的地方是考察的目标 函数， i i 考察的目标函数是极小化最大机器负载，【2 】考察的目标函数是极大化最 小机器负载尽管目标函数有所区别，但是目的都是一致的，也即希望资源分配的 尽可能的公平相对于上述在线模型，预知单一信息的半在线模型也得到了广泛 的研究，现将部分相关模型及其背景总结如下： 预知离线状态下最优目标值( 记为o p t ) 这个半在线模型i 扫a z a r 和e p s t e i n 8 最早提出。假设离线状态下最优目标值 预知，但是不知道最优解( 最优排序) 该模型包含了在线b i ns t r e t c h i n g i h - j 题【9 】，在 线b i ns t r e t c h i n g i h 题最先f l 了a z a r 和r e g e v 提出研究这类模型的相关文献有【2 4 】等 预知工件总加工时间( 记为s u m ) ， 该模型i 刍k e l l e r e r 等 5 1 1 首先提出，假设所有工件的总加工时间预知广义在 线b i ns t r e t c h i n g 1 5 也即预矢h s u m 的半在线排序问题研究这类模型的相关文献 有 3 9 ；3 ；1 5 ；6 】等 预知最大工件加工时间( 记为m a x ) h e 和z h a n g 在 4 5 1 考察了这个模型，假设最大工件的加工时间预知研究这类 模型的相关文献有【3 9 ；7 3 ；5 7 ；7 8 等， 预知工件按加工时间大小非增排列( 记为d e c r ) 该模型由a z a f 和e p s t e i n 【8 】最早提出，假设所有工件按加工时间大小非增排列 到达研究这类模型的文献还有【6 3 ；3 0 等 预知工件加工时间上界为譬( 记为七一b o u n d e d ) 在【2 7 】中，e p s t e i n 最先考察了这个模型给定一个正整数七，如果预知离线状 态下的最优目标值伊，则所有的工件的大小都不超过譬；如果c + 的值未知，记当 前到达所有工件中最大的工件为阳，则预知c k p o 预知工件加工时间具有上下界( 记为t i g h t l y g r o u p ) 该模型f l j h e 和z h a n g 4 5 首先提出，假设所有工件的加工时间位于有限区 间p ，r p ，其中p o 和r 1 是已知常数研究这类模型的文献还有 3 8 - - 4 0 1 等 o r d i n a l 半在线模型( 记为o r d i n a l ) o r d i n a l 半在线模型是l i u ，s i d n e y 和v a nv l i e t 5 5 首先提出的在该模型中，我 们只知道某工件的加工时间在由所有工件的加工时间重排组成的有序集中 一9 一 第二章半在线排序问题综述 的位置，而不知道其确切大小且所有工件的安排必须在零时刻作出并且不 能改变此后t a n 和h e 对该模型做了大量的研究工作，研究这类模型的文献还 有【4 2 ；6 7 ；6 8 ；7 0 等 其他的半在线模型还有己知最后一个工件最大的半在线排序【8 3 】，带缓冲 区( b u f f e r ) 的在线排序【5 1 ；8 1 或是预知不精确的半在线信息的模型 7 1 ；7 2 等针 对部分相关模型，我们将所知的最好结果已列入表一 表一：平行机排序问题部分模型结果 g 饥 问题下界算法竞争比问题下界算法竞争比 o n l i n em = 2 3 2 一l m 3 1 】2 1 m 3 5 】 m 7 6 】m 7 6 】 m 4 1 8 s 6 0 1 9 1 5 1 6 1 】 m = 2 4 3 9 】 2 一鬲1 8 】 2 一土f 8 】 m 。 o p t m = 3 ，4 4