（运筹学与控制论专业论文）批调度与网络问题的组合算法.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果对本论文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识 到本声明的法律责任由本人承担 论文作者签名；垄! 壅兰日期。 关于学位论文使用授权的声明 本人完全了解山东大学有关保留使用学位论文的规定。同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅；本人授权山东大学可以将本学位论文全部或部分内容编入有 关数据库进行检索，可以采用影印，缩印或其他复制手段保存论文和汇 编本学位论文 ( 保密的论文在解密后应遵守此规定) 论文作者签名：耋堡型导师签日期，翌兰：竺 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 批调度与网络问题的组合算法 李曙光 ( 山东大学数学与系统科学学院，山东，济南2 5 0 1 0 0 ) 指导教师；李国君教授 中文摘要 优化是根据现状采取行动以获得最好( 或最优) 的结果组合最优化研究的是可 行解数目有限的离散优化问题在复杂性理论的框架下，我们希望能在输入规模的 多项式时间之内找到最优解运行在多项式时间之内的算法称为有效算法输出最 优解的有效算法称为精确( 或最优) 算法 当多项式时间精确算法很可能不存在时( 所谓的n p 难解问题) ，我们转而设计 有效的近似算法以得到次优解对于极小化同题，算法的近似比( 性能比) 定义为算 法给出的解的目标值与最优值之间的最坏情形比对于极大化问题，算法的近似比 ( 性能比) 定义为最优值与算法给出的解的目标值之间的最坏情形比近似比为p 的 算法称为p 近似算法通常用近似比来衡量算法的性能近似比越小，算法越好 一族算法 a 称为一个多项式时间近似方案( p t a s ) ，如果对于每一个给定的 正数厶算法a 是一个运行于输入规模的多项式时间之内的( 1 + 0 - 近似算法注意 到e 是给定的，因此算法的运行时间可以以任意方式依赖于1 e 如果运行时间也是 1 e 的多项式，我们就得到了全多项式时间近似方案( f p t a s ) 对于n p 难解问题和 所谓的强n p 难解问题来说，全多项式时间近似方案和多项式时问近似方案分别是 我们目前所能得到的最好结果 本文研究批调度和网络中的若干确定性优化问题，给出了有效的组合算法确 定性是指问题实例的所有参数均事先已知我们研究的问题大多是n p 难解的，所 给出的算法大多是多项式时间近似方案，其余的是精确算法或常数近似比算法下 面简略地描述所研究的问题，并给出主要结果和创新点 论文第一章介绍了研究的缘起和背景第二章至第五章是第一部分，给出了若 干批调度问题的组合算法；第六章至第八章是第二部分，给出了若干网络问题的组 合算法 1 s h j n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 一个典型的调度同题包含n 个工件和m 台机器在满足一定约束条件下，要将 工件安排在机器上进行加工目标是找到一个最优的安排最优性由依赖于问题的 目标函数所定义本文研究分批调度问题每台机器可以同时加工若干个工件，这 些工件构成一个批次这样的机器称为批机器将工件分批加工是为了提高效率t 分批加工比一个一个加工更快或成本更低 批调度问题有多种模式本文研究如下的煅烧模式给定n 个工件和m 台并 行同型批机器每个工件有一个加工时间，描述了在任意一台机器上加工该工件所 需要的最短时间每个工件还有一个释放时间，在该时间之前不能开始加工这个工 件一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者一个批 次的完工时闻等于它的开工时问加上它的加工时间同一批次中的所有工件有相同 的开工时间，也有相同的完工时间，即该批次的完工时间一个批次从开始加工到完 工，不允许向内添加工件或向外移除工件每个批次的加工都是连续进行的。即； 从开工到完工，没有其他批次可以在同一台机器上加工煅烧模式起源于大规模集 成电路生产过程中的煅烧操作调度问题 煅烧模式分为两类有界模式，每个批次最多可容纳的工件数目( 批容量) b 小 于工件的总数目n ，b 表示任一台机器能同时加工的工件的最大数目无界模式，每 个批次可容纳的工件数目没有限制，即b t 1 无界模式的一个例子，在干燥炉中 硬化一些化合物，干燥炉足够大因此批容量没有限制注意有界模式中b = 1 的情 形，就是经典的调度问题( 每台机器在任一时间至多加工一个工件) 因此，有界模 式的批调度问题，难度不低于经典的调度问题 集中研究工件释放时问不相同的调度问题这比所有工件同时到达的问题要难 得多研究三种调度目标t 极小化加权完工时闻和、极小化最大延迟极小化最大 完工时间记工件j 在一个调度中的完工时间为q 在第二章和第三章，我们研究极小化加权完工时间和的有界批机器和无界批机 器并行调度问题每个工件j 有正权加权完工时间和，顾名思义，是j 哟岛 这两个问题都是n p 难解的，并且前者是强n p 难解的在批调度的各种目标函数 中，极小化加权完工时间和是最难的之一对于这两个问题，我们均首次给出了多 项式时间近似方案有一点奇怪，在我们的算法中，那些处理批调度问题的技巧用 的并不多。反而更多地依赖于研究经典调度问题( b = 1 ) 所发展起来的技巧 第四章主要研究极小化最大延迟的有界批机器并行调度问题每个工件j 最好 2 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 能在它的交货期d j 之前完工最大延迟定义为m 8 玛 0 一由 这个问题是强n p 难 解的我们给出了第一个多项式时间近似方案所用技巧经过简单修改之后，就得 到( n p 难解的) 极小化最大延迟的并行机无界批调度问题的第一个多项式时问近似 方案当所有的由为0 时，最大延迟就是最大完工时间，m 8 x ，q 因此我们也得到 了求解极小化最大完工时间的有界批机器和无界批机器并行调度问题的多项式时间 近似方案 第五章研究了工件具有不同尺寸的单机批调度问题，目标函数是极小化最大完 工时间每个工件j 有一个尺寸丐( 0 ，l 】批机器可以将若干个工件作为一批同时 进行加工，只要这些工件的尺寸之和不超过1 工件尺寸不同的调度问题是批调度问 题的一般形式显然，此时我们不必考虑无界模式最大完工时间，正如上面所定义 的，是调度中所有工件的完工时间的最大者对于这个问题，我们给出了( 2 + e ) 一近似 算法，f 是任意小的正数算法的运行时问是o ( nl o gn ) + ，( 1 e ) ，隐藏在o ( nl o gn ) 中的常系数很小并且与e 无关当所有工件同时到达并且加工时间相同时，这一问 题就是经典的一维装箱问题一维装箱问题是强n p 难解的，近似比小于3 1 2 的近 似算法很可能不存在 除了批调度问题，我们还研究通讯网络中出现的优化问题通讯网络在我们的 社会经济生活中日显其重要性，因此关于网络设计与有效运营的优化问题受刭了学 界的普遍关注除去大量的实际应用之外，网络问题也有很多有趣的方法论特性 我们集中研究环网络作为一种流行的通讯网络，环网络引起了很多人的兴趣 在第六章，我们考虑环网络中的呼叫接纳控制i 可题给定一个环( 无向或有向) 和一组通讯请求每个请求用一对顶点( 无序或有p f ) 表示，并且有一个利润要在 无向环中实现个呼叫，需在环中指定该请求所对应的两个顶点之问的一条路要 在有向环中实现一个呼叫。需在环中指定该请求的源节点到目的节点的一条路环 ( 无向或有向) 网络呼叫接纳控制问题的日标是确定最大利润的呼叫子集，在环中实 现该子集中的每一个呼叫，使得经过每一边( 无向或有向) 的呼叫的数目不超过该边 的容量对于无向和有向环网络呼叫接纳控制问题，我们均首次给出了多项式时间 近似方案 在第七章，我们研究多纤w d m 网络中的利润极大化问题要在多纤w d m 网 络中实现一组传输请求，我们要为其中每一个请求安排一条路并分配一个波长，使 得任一链路上任一波长的使用次数不超过该链路上的光纤数给定一个波长数日有 3 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 限的多纤w d m 网络和一组传输请求，利润极大化问题的目标是要确定利润最大的 并且可以在网络中实现的那一部分传输请求第六章所研究的呼叫接纳控制问题， 是这一问题只有一个波长时的特例对于链网，我们给出了多项式时间精确算法 环网中的这一问题是n p 难解的，即使所有传输请求的利润均为1 时也是如此我 们给出了两个算法。近似比分别为2 和1 5 8 2 + e ，e 是任意小的正数对于环上各边 光纤数目相同的均匀模式，给出了1 5 8 2 - 近似算法这些结果也适用于有向链网与 环网注意在将多纤环网中的2 - 近似算法推广到有向多纤环网时，要求某一链路上 的两条有向边分别为顺时针和逆时针方向上容量最小的有向边 最后，在第八章我们引入了圈中扛区间的b 染色问题这一问题推广了w d m 环网络中几个熟知的优化问题圈代表环网络，颜色代表波长。扣区间代表客户请 求一个t - 区间，由圈上至多( t 1 ) 个区间构成。每个区间的两个端点都是圈上的 顶点要实现一个客户请求，需选择它所对应的扣区间中的一个区间并为其安排一 种颜色任意两个请求在实现时，所选定的两个区间如果在圈上有公共边，则不能 得到同一种颜色，否则会引起波长冲突给定一个圈、k 种颜色和若干个请求( 扛 区间) ，问题的目标是实现最大数目的请求我们给出了这一问题的一个3 0 4 2 近似 算法顺便也得到了链网中t 区问的b 染色问题的一个2 5 4 2 - 近似算法 关键词t 近似算法；多项式时间近似方案；批调度；网络；波分复用 4 s h a n d o n gu n i v e r s i t yd o o r a ld i s s e r t a t i o n c o m b i n a t o r i a la l g o r i t h m sf o rb a t c h s c h e d u l i n ga n dn e t w o r kp r o b l e m s l is h u - g u a n g ( s c h o o lo fm a t h s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ，p r c h i n a ) a d v i s o r ：p r o f l ig u o - j u n a b s t r a c t o p t i m i z a t i o ni st h ea c to fo b t a i n i n gt h eb e s t ( o ro p t i m a l ) 蛸l i l tu n d e rg i v e nc k - c u m s t s n 懈c o m b i n a t o r i mo p t i m i z a t i o ni sc o n c e n l o dw i t hd i s c r e t eo p t i m i z a t i o np r o b - l e m sw h i c hh a v eaf i n i t en u m b e ro ff e a s i b l es o l u t i o n s i nt h ef r a m e w o r ko fc o m p l e x i t y t h e o r y , w ew a n tt of i n dt h eo p t i m u mi nt i m et h a ti sp o l y n o m i a li nt h ei n p u ts i z e a n a l g o r i t h mt h a tr u n si np o l y n o m i a lt i m ei ss a i dt ob ee 炳c i e n t a ne f f i c i e n ta l g o r i t h mi s c a l l e de x a c t ( o ro p t i m a 2 ) i fi tp r o d u c e sa l lo p t i m a ls o l u t i o nt oap r o b l e m i nc a s w h e nap o l y n o m i a lt i m ee x a c ta l g o r i t h mi su n l i k e l yt oe x i s tf t h ee o - c a l l e d n p - i 删p r o b l e m s ) ，o n ei sc o n s t r a i n e dt od e s i g ne f f i c i e n ta p p r o x i m a t i o na l g o r i t h m s t h a ta r ea b l et of i n dp r o v a b l yn e a r l yo p t i m a ls o l u t i o n s t h ea p p r o x i m a t i o nr a t i o ( o r t h ep e r f o r m a n v er a t i o ) o fa l la l g o r i t h m ，f o rm i n i m i z a t i o np r o b l e m s ，i sd e 缸e da st h e w o r s t - c a s or a t i oo na n yi n p u ti n s t a n c eo ft h ep r o b l e mb e t w e e nt h ev a l u eo f t h es o l u t i o n p r o p o s e db yt h ea l g o r i t h ma n dt h eo p t i m a ls o l u t i o nv a l u e f o rm a x i m i z a t i o np r o b l e m s t h ea p p r o x i m a t i o nr a t i o ( o rt h ep e r f o r m a n c er a t i o ) i sd e f i n e da 8t h ew o r s t - c r u s er a t i o o na n yi n p u ti n s t a n c eo ft h ep r o b l e mb e t w e e nt h eo p t i m a ls o l u t i o nv a l u ea n dt h ev a l u e o ft h es o l u t i o np r o p o s e db yt h ea l g o r i t h m a na l g o r i t h mw i t ha p p r o x i m a t i o nr a t i op i sc a l l e dap - a p p r o x i m a t i o n 口幻o n 仇m t h ea p p r o x i m a t i o nr a t i oi st h eu s u a lm e n s l l r e f o rt h eq u a l i t yo fa l la p p r o x i m a t i o na l g o r i t h m ：t h es m a l l e rt h er a t i oi s ，t h eb e t t e rt h e a p p r o x i m a t i o na l g o r i t h mi s af a m i l yo fa l g o r i t h m s a i sc a l l e dap o l z n o m i a 2t i m ea p p r o x i m a t i o ns c h e m e ( p t a s ) 讧 f o re a c hf i x e de 0 ，t h ea l g o r i t h ma ci sa ( 1 + f ) - a p p r o x i m a t i o na l g o r i t h m r u n n i n gi nt i m et h a ti sp o l y n o m i a li nt h ei n p u ts i z e n o t et h a tei saf i x e dn u m b e r ， a n dt h u st h er u n n i n gt i m em a y d e p e n du p o n1 i na n ym a n n e r i ft h er u n n i n gt i m ei s 5 ! ! 型! 翌! ! ：竺竺竺里! 竺：! ! 里兰竺竺! ! ! p o l y n o m i a li n1 ca sw e l l ，t h e nw eh a v ea 加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 p t a s ) a tt h es t a t eo ft h ea r t ，f p t a s sa n dp t a s s a r et h eb e s tr e s u l t sw ec a l lo b t a i n f o rt h en p - h a r dp r o b l e m sa n dt h es o - c a l l e ds t r o n g l yn p - h a r d p r o b l e m s r e s p e c t i v e l y t h i st h e s i sd e v e l o p se f f i c i e n tc o m b i n a t o r i a la l g o r i t h m sf o rs o m ed e t e r m i n i s t i co p - t i m i z a t i o np r o b l e m so fb a t c hs c h e d u l i n ga n dn e t w o r k s d e t e r m i n i s t i cr e f e r st ot h e s c e n a r i oi nw h i c ha l lp a r a m e t e r so ft h ep r o b l e mi n s t a n c ea r ek n o w ni na d v a n c e m o r e t h a nh a l fo ft h ep r o b l e m sw es t u d ya r en p - h a r d m o r et h a nh a f to ft h ea l g o r i t h m s w ep r e s e n ta r ep 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 s ，a n dt h eo t h e r sa r ee x a c ta l g o - r i t h m so rc o n s t a n t - r a t i oa p p r o x i m a t i o na l g o r i t h m s b r i e fd e s c r i 【p t i o n so ft h ep r o b l e m s w es t u d ya n dh i g b l i g h t so fo u rr e s u l t sf o l l o w t h et h e s i sb e g i n sw i t ham o t i v a t i o n a lc h a p t e r t h i si sf o l l o w e db yt w op a r t s p a r ti ：c o m b i n a t o r i a la l g o r i t h m sf o rb a t c hs c h e d u l i n gp r o b l e m s ，c o n s i s t i n go fc h a p t e r s 2t h r o u g h5 ，a n dp a r ti i ：c o m b i n a t o r i a la l g o r i t h m sf o rn e t w o r kp r o b l e m s ，c o n s i s t i n go f c h a p t e r s6t h r o u g h8 at y p i c a ls c h e d u l i n gp r o b l e mc o n s i s t so fas e to fn j o b st h a ta r et ob ee x e c u t e do n as e to fma v a i l a b l em a c h i n e ss u b j e c tt oav a r i e t yo fc o n s t r a i n t s t h eg o a li st of i n da l l o p t i m a la l l o c a t i o nw h e r eo p t i m a l i t yi sd e f i n e db ys o m ep r o b l e md e p e n d e n to b j e c t i v e t h es c h e d u l i n gp r o b l e m sw es t u d yf a l lu n d e rt h ec a t e g o r yo fb a t c hs c h e d u l i n g w h e r ea m a c h i n ec a np r o c e s ss e v e r a lj o b ss i m u l t a n e o u s l ya sab a t c h s u c ham a c h i n ei 8c a l l e d ab a t c hm a c h i n e t h em o t i v a t i o nf o rb a t c h i n gj o b si sag a i ni ne f f i c i e n c y ：i tm a yb e c h e a p e ro rf a s t e rt op r o c e s sj o b si nab a t c ht h a nt op r o c e s st h e mi n d i v i d u a l l y t h e r ea r es e v e r a lm o d e lo fb a t c hs c h e d u l i n ga n dw ea r ei n t e r e s t e di nt h ef o l l o w i n g b u r n 一香nm o d e lw ea r eg i v e i las e to fn j o b sa n dm i d e n t i c a lp a r a l l e lb a t c hm a c h i n e s e a c hj o bi sa s s o c i a t e dw i t hap r o c e s s i n gt i m ew h i c hs p e c i f i e st h em i n i m u mt i m en e e d e d t op r o c e gt h ej o bo na n yo n eo ft h em a c h i n e s i na d d i t i o n ，e a c hj o bi sa s s o c i a t e dw i t h ar e l e a s et i m eb e f o r ew h i c hi tc a n n o tb ep r o c e s s e d t h ep r o c e s s i n gt i m eo fab a t c hi s d e f i n e da st h el o n g e s tp r o c e s s i n gt i m eo fa n yj o bi nt h eb a t c h t h ec o m p l e t i o nt i m eo f ab a t c hi se q u a lt oi t ss t a r tt i m ep l u si t sp r o c e s s i n gt i m e a l lt h ej o b si nt h es a n l eb a t c h b e g i np r o c e s s i n ga tt h e i n et i m e ，a n da r ed e e m e dt oh a v et h es a m ec o m p l e t i o nt i m e ， n a m e l y , t h ec o m p l e t i o nt i m eo ft h eb a t c h o n c et h ep r o c e s s i n gh a sb e g u no nab a t c h ， 6 s h m a d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n n oj o b s 啪b ea d d e do l rr e m o v e du n t i lt h ep r o e e i n gi sc o m p l e t e d t h ep r o c s i n g e a c hb a t c hi sc o n t i n u o u s ，i e ，o n c et h ep r o c e s s i n go no n eb a t c hs t a r t s ，1 1 0o t h e rb a t c h c a l lb es t a r t e du n t i lt h ef o r m e ro l l ei sf i n i s h e d t h i sm o d e li sm o t i v a t e db yt h ep r o b l e m o fs c h e d u l i n gb u r n - i no p e r a t i o n sf o rl s r g e8 c a l ei n t e g r a t e dc i r c u i tm a l a t f f s a t t t r i n g w ea n a l y z et w ov a t i a l a t o ft h eb u m - i nm o d e l i nt h eb o u n d e dm o d e t h eb o u n d b ( t h e 岫u l i in u m b e ro fj o b st h a t b ep r o c e s s e ds i m u l t a n e o u s l y0 1 1am a c h i n e ) f o re a c hb n t c hs i z ei se f f e c t i v e ，i e ，b 0c a nb ei n a d ea r b i t r a r i l ys m a l l t h eo v e r a l lr u n n i n gt i m eo fo u r a l g o r i t h mi so ( n l o g n ) + ，( 1 e ) ，w h e r et h em u l t i p l i c a t i v ec o n s t a n th i d d e ni no ( n l o g n ) i sr e a s o n a b l ys m a l la n di n d e p e n d e n to f n o t et h a ti fa l lj o b sa r er e l e a s e da tt h e s a m et i m ee n dh a v ei d e n t i c a lp r o c e 裙i n gt i m e st h e nt h ep r o b l e mi sj u s tt h ec l a s s i c a l o n e - d i m e n s i o n a lb i np a c k i n gp r o b l e m t h eb i np a c k i n gp r o b l e mi ss t r o n g l yn p - h a r d a n da ne f f i c i e n ta l g o r i t h mt h a tc a na c h i e v eab e t t e ra p p r o x i m a t i o nr a t i ot h a n3 1 2i s u n l i k e l yt 0e x i s t i na d d i t i o nt ob a t c hs c h e d u l i n gp r o b l e m s ，w ea l s os t u d ys e v e r a lo p t i m i z a t i o np r o b - l e m sa r i s i n gi nc o m m u n i c a t i o nn e t w o r k s d u et ot h ee v e r - i n c r e a s i n gi m p o r t a n c eo fc o m - m u n i c a t i o nn e t w o r k sf o ro u rs o c i e t ya n de c o n o m y , o p t i m i z a t i o np r o b l e m sc o n c e r n i n g t h ed e s i g na n de f f i c i e n to p e r a t i o no fs u c hn e t w o r k sa r er e c e i v i n gc o n s i d e r a b l ea t t e n t i o n i nt h er e s e a r c hc o m m u n i t y a s i d ef r o mt h e i rn u m e r o u sp r a c t i c a la p p l i c a t i o n s n e t w o r k p r o b l e m sa l s oh a v em a n yi n t e r e s t i n gm e t h o d o l o g i c a lc h a r a c t e r i s t i c s w ef o c u so nr i n g n e t w o r k s t h er i n gi sap o p u l a rt o p o l o g yf o rc o m m u n i c a t i o nn e t w o r k sa n dh a sa t t r a c t e d m u c hr e s e a r c ha t t e n t i o n i nc h a p t e r6 ，w ec o n s i d e rt h ep r o b l e mo fc a l la d m i s s i o nc o n t r o li nu n d i r e c t e da n d 8 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n d i r e c t e dr i n gn e t w o r k s g i v e nar i n g ( u n d i r t e do rd i r e c t e d ) a n das e to fc o m m u n i c a - t i o nr e q u e s t s e a c hr e q u e s ti sr e p r e s e n t e db yap a i ro fn o d e s ( u n o r d e r e do ro r d e r e d ) ， a n da s s o c i a t e dw i t hap r o f t t os a t i s f yar e q u e s ti nt h eu n d i r e c t e dr i n g ，w en e e dt o d e t e r m i n eap a t hb e t w e e nt h et w on o d e so ft h er e q u e s ti nt h er i n g t os a t i s f yar e - q u e s ti nt h ed i r e c t e dr i n g ，w en e e dt od e t e r m i n ead i r e c t e dp a t hf r o mt h es o u r c et ot h e d e s t i n a t i o no ft h er e q u e s ti nt h ed i r e c t e dr i n g t h eg o a lo ft h ec a l la d m i s s i o nc o n t r o l p r o b l e mi st od e t e r m i n ea n ds a t i s f yai n a x i l n n mp r o f i ts u b s e to ft h er e q u e s t ss u c ht h a t f o re v e r y ( 血e c t e do rd i r e c t e d ) e d g eo ft h e ( u n d i r e c t e do rd i r e c t e d ) r i n g ，t h en u m b e r o fs a t i s f i e dr e q u e s t st h a ta r er o u t e dt h r o u g ht h ee d g ed o e sn o te x c e e dt h ec a p a c i t yo f t h ee d g e w ep r e s e n tt h ef i r s tp t a s sf o rb o t ht h eu n d i r e c t e da n dd i r e c t e dc a s e 8 ， i nc h a p t e r7 ，w es t u d yt h ep r o b l e mo fm a x i m i z i n gp r o f i t si nm u l t i f i b e rw d m n e t w o r k s t os a t i s f yas e to fr e q u e s t si nam u l t i f i b e rw d mn e t w o r k w en e e dt o8 8 - s i g nap a t ha n daw a v e l e n g t hf o re a c hr e q u e s ts u c ht h a to na n yl i n kt h en u m b e ro f a n yw a v e l e n g t hu s e dd o e sn o te x c e e dt h en u m b e ro ff i b e r s g i v e nam u l t i f i b e rw d m n e t w o r kw i t hal i m i t e dn u m b e ro fw a v e l e n g t h sa n das e to fr e q u e s t s ，t h ep r o b l e mo f m a x i m i z i n gp r o f i t si st od e t e r m i n eas u b s e to fr e q u e s t sw i t ht h en l a x i n l u l np r o f i tt h a t c nb es a t i s f i e di nt h en e t w o r k n o t et h a tt h ec a l la d m i s s i o nc o n t r o lp r o b l e ms t u d i e di n c h a p t e r6i sj u s tt h es p e c i a lc a s eo ft h i sp r o b l e mw i t ho n l yo n ew a v e l e n g t h w ef o c u s o nd l a i n sa n dr i n g s f o rc h a i n s ，w ep r e s e n tap o l y n o m i a lt i m ee x a c ta l g o r i t h m t h e p r o b l e mf o rr i n g si sn p - h a r de v e nw h e na l lp r o f i t sa r e1 w ep r e s e n tt w oa l g o r i t h m s w i t ha p p r o x i m a t i o nr a t i o s2a n d1 5 8 2 + er e s p e c t i v e l y , w h e r ee 0 b em a d e8 x - b i t r a r i l ys m a l l w ea l s oc o n s i d e rt h eu n i f o r mv m 池n ti nr i n g sw h e r ea l le d g e sh a v et h e s a n l en u m b e ro ff i b e r sa n dg i v ea1 5 8 2 - a p p r o x i m a t i o na l g o r i t h m t h e s er e s u l t sc a l lb e a d a p t e dt od i r e c t e dc h a i n sa n dr i n g sa sw e l l w h e nt h e2 - a p p r o x i m a t i o na l g o r i t h mf o r r i n g si sg e n e r a l i z e dt ot h ed i r e c t e dr i n g s ，w er e q u i r et h a tt h e r ee x i s t sal i n kw h o s et w o d i r e c t e de d g e sa r er e s p e c t i v e l yt h ed i r e c t e de d g e sw i t hm i n i m u mc a p a c i t yi nc l o c k w i s e a n dc o u n t e r c l o c k w i s ed i r e c t i o n s f i n a l l y , i nc h a p t e r8w ei n t r o d u c et h ep r o b l e mo fk - c o l o r i n go ft - i n t e r v a l si na c y c l e ，w h i c hg e n e r a l i z e ss e v e r a lw e l lk n o w no p t i m i z a t i o np r o b l e m sa r i s i n gi nw d mr i n g n e t w o r k s c y c l e sr e p r e s e n tr i n gn e t w o r k s ，c o l o r sr e p r e s e n tw a v e l e n g t h s ，a n dt - i n t e r v a l s 9 s h a n d o n gu n i v e r s i 锣d o c t o r a ld i s s e r t a t i o n r e p r e s e n tr e q u e s t sf r o me h e n t s e a c ht - i n t e r v a lc o n