（基础数学专业论文）在线排序与路由安排.pdf

摘要 本文主要完成了两方面的工作 1 平行批在线排序算法的研究。 在过去的四十年里，生产系统的调度计划研究得到了显著的成果，从而产生了一个专门的 学科排序。在诸多的排序成果中，所研究的模型很多是确定性的。在这类模型里，主要的假 设就是输入的实蒯的所有参数均是事先已知并且不会再发生变化的。但是，实际中的生产环境 受很多不确定因素的影响，输入的实例的参数并不是全部事先确定，而是在排序的过程中逐一 知道的。近年来，针对这一类型排序模型的研究逐渐发展出“在线排序”这一学科分支 本文着重讨论在线环境中的若干平行批排序问题。此时，在线环境是指输入的实例中，只 有当工件到达时才知道它相应的信息( 如：加工时间、到达时间等) 。平行批排序模型来源于半 导体制造中对集成电路芯片煅烧的工序排序问题。在这类模型里，每个工件都有一个加工时间， 机器可以同时加工b 个工件，每一批的加工时间等于该批次里所有工件中加工时间最氏的加工 时间。 1 1 单机、平行批、分组工件的在线排序问题。 在这个模型里，待加工的工件分为多个不兼容的组，不同组中的工件不能放在同一批中加 工。对批容鼍无界的情形，我们给出了使得完下时间尽最小的竞争比是2 的在线算法，并证明 该算法的性能已最具竞争性：对批容量有界的情形，针对同一目标函数，我们给出了竞争比也 是2 的在线算法，并证明当批容最小小于1 0 0 时，性能最好的算法竞争比大于1 9 8 0 2 ，非常接近 于2 。 1 2 单机、平行批、批容量无界、优化最大完工时间的在线排序问题。 对该排序问题，z i m n g 等人( g z h a n g ，x c a ia n dc k w o n g ，o n - l i n ea l g o d t h m sf o rm i n i m i z - i n g m a k p a n o i l b a t c h p r o c e s s i n g m a c h i n e s ，n a v a r e s e a r c h l o g i s t i c s , 4 s ( 2 0 0 1 ) ，2 4 1 2 5 8 ) 和d e n g 等 人( x d e n g , c k p o o ha n dy z h a a g ，a p p r o x i n m t i o na l g o r i t h m si nb a t c h m gp r o c e i n g ，j o u r - n a lo fc o m b i n a t i o n a lo p t i m i z a t i o n ，7 ( 2 0 0 3 ) ，2 4 7 - 2 5 7 ) i 眄组作者分别独立地给出了同一个竞争比 为鸥掣的在线算法，并证明不存在竞争比更小的在线算法。但是，他们的算法不是弱渐进最优 的( 这里称一个算法是弱渐进最优的，如果工件的最长加工时间与最优值的比值趋于0 时，由算 法得到的可行排序的日标函数值与最优值的比值趋于1 ) ，我们设计了一个算法，在保证其竞争 比不大f 躅掣的情况下，使得它是弱渐进最优的。 1 3 单机、平行批、带序约束且加工时间均为1 的工件在线排序问题。 考虑批容鼍有界、且工件序约束图的各个分支都是链的模型，以优化最大完工时问为目标， 我们给出了竞争比为怕的在线算法，并说明，当6 3 时，所有具有稠密特征( 只要当前机器处于 闲置状态，并且至少有6 个独立工件( 即相互之间没有序约束的工件) 待加工，则立刻开始一批工 件的加工) 的在线算法的竞争比至少是、，5 。考虑工件序约束任意的情形，对于批容量无界的情 形，以优化最大加权完工时间或优化加权完工时间和为目标，我们均得到竞争比为，学的最优 在线算法；对于批容量有界的情形，以优化最大完工时闻为目标，我们给出了竞争比是2 的在线 算法。 2 边赋权环网络路由负载问题。 在现代通讯中，光纤的应用大大地提高了传输的速度，并使网络传输的数据类型多样化 为了提高光纤的利用率，网络的路由选择问题是当前研究的热点。网络有各种各样的拓扑结构， 其中环是常见的一种。环上分布有若干个点，相邻的点间有边相连，点与点之间有相互传递信息 的请求。信息传递的途径只有两种可能：沿着顺时针或逆时针方向。对于每一条边，它的负载是 指传递时经过它的信息最的总和。要考虑的问题是：如何传递信息，使得展终负载最大的边的 负载达到最小。s c h r i j v e r 等人在他们的文章( a s c h r i j v e t ，p d s e y l n o t l r ，a n dp w i n k l e r ，t h er i 醒 l o a d i n gp r o b l e m ，s l a m d i s c r e t e m a t h ，1 1 ( 1 9 9 s ) ，1 - 1 4 ) 中做了以下工作：( 1 ) 证明信息请求可 任意分割传递时，问题是多项式时间可解的；( 2 ) 证明信息请求不可分割传递时，问题足n p - 困 难的，并给出了近似算法；该锋法所求出的可行解的目标函数值不超过最优值的3 d 。2 ，其 中d 。是环中点对间要传递的最大信息量。 在本文所讨论的拓扑结构一环中，每一条边都有一个非负权重，每一条边的加权负载等于 它的权重与其负载的l 整数的乘积。我们要考虑的问题是：如何传递信息，使得最终加权负载 最大的边的加权负载达到最小。我们得到如下结果：( 1 ) 证明信息请求可任意分割传递时，问题 是多项式时间町解的：( 2 ) 证明信息请求叮整分割传递时，问题是多项式时间可解的；( 3 ) 对于信 息请求不可分割传递的情形( 问题是p - 困难的) ，给出了多项式时间逼近方案( p t a s ) 。 关键词：捧序：在线；平行批；分组；序约束；路由；圆环；负载 l l a b s t r a c t t h i sd i s s e r t a t i o ni sc o n c e r n e dw i t hp a r a l l e lb a t c hs c h e d u l i n gp r o b l e m su n d e ro n - l i n es e t t i n g a n dr i n gl o a d i n gp r o b l e m s i np a r a l l e lb a t c hs c h e d u l i n gm o d e i s ，t h eg i v e nm a c h i n ei sap a r a l l e lb a t c hp r o c e s s i n gs y s t e m w h i c hc a np r o c e s su pt ob ( b22 ) j o b ss i m u l t a n e o u s l y ab a t c h a l lj o b si nae o m n l o nb a t c h s t a r te n dc o m p l e t ea tt h es a l v et i m e mp r o c e s s i n gt i m eo fab a t c hi se q u a lt ot h em a x i m u m p i n c h i n g t i m e a m o n g t h e j o b s i n t h e b a t c h f o r a n ys p s c i a l j o b i i s t ，b a t c h e s e v e n t u a l l y f o r m e d a r e r e q u i r e dt ob eap a r t , i o no ft h es e to fa l lj o b sg i v e n w ef i r s tc o n s i d e rt h es i n g l em a c h i n ep a r a l l e l b a t c hs c h e d u l i n gp r o b l e mw i t hf a m i l y j o b su n d e ro n - l i n es e t t i n gi nt h es e n s et h a tw e c o n s t r u c to u r s c h e d u l ei r r e v o c a b l ya st i m ep r o c e e d sa n dd on o tk n o wo ft h ee x i s t e n c eo fa n yj o bu n t i li t sa r r i v a l o 珊o b j e c t i v ei st om i n i m i z et h em a x i n l u n lc o m p l e t i o nt i m eo ft h ej o b sf m a k e s p a n ) w bd e a l w i t ht w ov a r i a n t s ：t h eu n b o u n d e dm o d e lw h e r et h em a c h i n ec a nh a n d l ei n f i n i t en u m b e ro fj o b s s i m u l t a n e o u s l ya n dt h eb o u n d e dm o d e l f o rt h eu n b o u n d e dc a s e w ep r o v i d ea no n - l i n ea 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 o2a n dp r o v et h a tt h er e s u l ti st h eb e s tp o s s i b l e f o rt h eb o u n d e dc 8 8 e ，w - e a l s op r e s e n ta no n - l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i o2a n ds h o wt h a t ，f r o maw o r s t c a s ep o i n t o fv i e w ，t h eb e s to n - l i n ea l g o r i t h mf o rt h ep r o b l e mc o n s i d e r e dc a n n o ta c tm n c hb e t t e rt h a nt h i s a l g o r i t h mw h e nt h ec a p a c i t yo ft h em a c h i n ei sl a r g e rt h a n1 0 0 w et h e nc o n s i d e rt h eo n - l i n es c h e d u l i n gp r o b l e mo f j o b sw i t hr e l e a s ed a t e so na s i n g l ep a r a l l e l - b a t c h i n gm a c h i n ew h i c hv a i lp r o c e s si n f i n i t ej o b sa tat i m e t h es c h e d u l i n gp r o b l e mi n v o l v e s a s s i g n i n ga l lj o b st ob a t c h e sa n dd e t e r m i n i n gt h es t a r t i n gt i m e so ft h er e s u l t e db a t c h e si ns u c ha w a yt h a tt h em a x i m u mc o m p l e t i o nt i m eo ft h ej o b s ( m a k e s p a n ) i sm i n i m i z e d i nl g z h a n g ，x c a i a n dc k w o n g ，o n - l i n ea l g o r i t h m sf o rm i n i m i z i n gm a h e s p a no nb a t c hp r o c e s s i n gm a c h i n e s ，n a v a l r e s e a r c hl o g i s t i c s ，4 s ( 2 0 0 1 ) ，2 4 1 - 2 5 s ia n df x d e n ga n dy z z h a n g ，a p p r o x i m a t i o na l g o r i t h m s i nb a t c hp r o c e s s i n g ，j o u r n a lo fc o m b i n a t o r i a lo p t i m i z a t i o n ，7 ( 2 0 0 3 ) ，2 4 7 - 2 5 7 1 ，t h et w og r o u p s o fa u t h o r si n d e p e n d e n t l yg a v eas a m eo n - l i n ea 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 ( 怕+ 1 ) 2a n d p r o v e dt h a tt h eo n - l i n ea l g o r i t h mi st h eb e s tp o s s i b l e i nt h e i ra l g o r i t h m ，aj o b ( w h i c hh a st h e m a x i m u mp r o c e s s i n gt i m ei nab a t c h 、w i t hr e l e a s ed a t era n dp r o c e s s i n gt i m epw i l lb ed e l a y e d u n t i lt i m e ( 1 + a ) r + 印i f p o s s i b l e ，w h e r en = ( 怕一1 ) 2 i nt h i sd i s s e r t a t i o n ，w ed e r i v eam o d i f i e d o n - t i n ea l g o r i t h mf o rt h es a m ep r o b l e mi nw h i c haj o bw i t hp r o c e s s i n gt i m epw i l lb ed e l a y e do n l y u n t i lt i m e 印i fp o s s i b l e w es h o wt h a tt h em o d i f i e do n - l i n ea l g o r i t h ms t i l lh a sc o m p e t i t i v er a t i o ( 5 + 1 ) 2 ，a n di sa s y m p t o t i c a l l yo p t i m a li naw e a k e n e dv e r s i o n t h i r d l y , w ec o n s i d e ro n - l i n es c h e d u l i n gp r o b l e mo fj o b sw i t hp r e c e d e n c ec o n s t r a i n t s ，u n i t p r o e s 鹤i n gt i m e sa n dr e l e a s ed a t e lo nas i n g l ep a r a l l e lb a t c hm a c h i n e t h er e l e a s ed a t e sa n d p r e c e d e n c er e l a t i o n so f j o b sr e m a i n 曲o v f nu n t i lt h e i ra n i v a l s o u ro b j e c t i v ei st om i n i m i z et h e n l a x i i n u l nc o m p l e t i o nt i m eo ft h ej o b s w ef i r s td e a lw i t ht h ec a s ei nw h i c ht h ec a p a c i t yo ft h e m a c h i n ei sb o u n d e da n dt h ep r e c e d e n c ec o n s t r a i n t sa r ec h a i 8 w ep r o v i d ea no n - l i n ea l g o r i t h m w i t hac o m p e t i t i v er a t i on o tg r e a t e rt h a n 3f o rt h i sc a s e w et h e nd e a lw i t ht h ec a s ei nw h i c h t h ep r e c e d e n c ec o n s t r a i n t sa r ea r b i t r a r y f o rt h eu n b o u n d e dm o d e l ，w ed e r i v ea no p t i m a lo n - l i n e a l g o r i t hw i t hc o m p e t i t i v er a t i o ( 、5 + 1 ) 2t om i n i m i z et h em a x i m u nw e i g h t e dc o m p l e t i o nt i m eo r t h et o t a lw c i g h t e dc o m p l e t i o nt i m e ；f o rt h eb o u n d e dm o d e l w ed e v e l o p o n - l i n ea l g o r i t h mw i t h ac o m p e t i t i v er a t i on o tg r e a t e rt h a n2t om i n i m i z et h em “e s p a na n ds h o wt h a tt h ec o m p e t i t i v e r a t i oo fa n yo n - l i n ea l g o r i t h mf o rt h i sm o d e li sn o ts m a l l e rt h a n ( 怕+ 1 ) 2 f i n a l l y , w ed e a lw i t ht h ew e i g h t e dl i n kr i n gl o a d i n gp r o b l e m s i nt h e s ep r o b l e m s ，w ea r eg i v e n a nn - n o d eu n d i r e c t e dr i n gn e t w o r ke a c ho f w h o s el i n k si sa s s o c i a t e dw i t haw e i g h t ；t r a f l l cd e m a n d s d f j a x eg i v e nf o re a c hp a i ro fn o d e si nt h er i n g t h e1 0 8 do fal i n ki st h es n no ft h ef l o w sr o u t e d t h r o u g h t h e l i n k a n d t h e w e i g h t e d l o a d o f i t i s t h e p r o d u c to f i t s w e i g h ta n d t h e u p p e r i n t e g e r o f i t s l o a d t h ea b j e e t i v eo ft h ep r o b l e mi st of i n dar o u t i n gs c h e m es u c ht h a tt h ei n 脚m mw e i g h t e d l o a do nt h er i n gi sm i n i m i z e d w ec o n s i d e rt h r e ev a r i a n t s ：i 1d e m a n d sm a yh es e n ti ne i t h e r d i r e c t i o n s ，c l o c k w i s eo rc o u n t e r c l o c k w i s e tw i t hd e m a n ds p l i t t i n g ；i i ) d e m a n d sa r ea l l o w e dt ob e s e a ti ne i t h e rr o u t a b u tr e s t r i c t e dt ob ei n t e g r a l l ys p l i t ；i i i ) e a c hd e m a n dm u s th ee n t i r e l yr o u t e d i ne i t h e ro ft h et w od i r e c t i o n s w ep r o v et h a tt h ef i r s tt w ov a r i a n t ea r ep o l y n o m l a l l ys o l v a b l e f o r t h et h i r do n e ，w h o s en p - h a r d n e s sc a nh ed r a w nf r o mt h er e s u l ti n s c o s a r e sa n di s a n i c e ，a n o p t i m i z a t i o np r o b l e mr e l a t e dt ob a l a n c i n gl o a d so ns o n e tr i n g s ，t e l e c o m m u n i c a t i o ns y s t e m s ， 3 ( 1 9 9 4 ) ，1 6 5 - 1 8 1 1 ，w ed e r i v eap 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 ) k e yw o r d s ：s c h e d u l i n g ；o n - l i n e ；f a m i l y ；p r e c e d e n c e ；b a t c h ；m a k e s p a n ；r i n gl o a d i n gp r o b l e m ； w e i g h t e dl o a d ；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 l v 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄袭 等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切法律 责任和法律后果，特此郑重声明。 学位论文作者：缎压绣 2 0 0 6 年4 月2 目 第一章绪言 1 1排序研究背景 捧序论又称为时间表理论，是运筹学的一个分支，是组合优化这门学科的一个 重要的组成部分。排序论实际上是讨论如何按时问进行资源分配，以达到某个目标 的理论。资源的形式多种多样，可以是车间里的机器、飞机的跑道，也可以是建筑 工程队、计算机的处理器等；要完成的任务可以是产品加工过程中的工序、飞机的 起飞与降落，也可以是工程组建过程中的阶段、计算机程序的运行等；每个任务可 能有不同的特点与要求，例如最早开工时间、工期等，任务与任务之间可能还有先 后顺序的要求；要达到的目标也各种各样，例如使得最后完工的任务的完工时间达 到最小、误工的任务数达到最小等。尽管在实际中资源和任务的形式多样，在排序 模型里，资源可以抽象为“机器”，任务可以抽象为“工件“，而排序就是在一定的 约束条件下对工件和机器按时间进行分配和安排次序。现实中的很多问题实际上是 排序问题。排序己成为加工、制造业中的一个很重要的决策问题，同时也是服务业 中常要解决的关键问题：它为企业降低成本、提高利润提供了行之有效的方法。在 当前的竞争环境下，是否有效地对资源进行分配成为企业能在市场中生存与否的关 键。 不过，无论是从理论的角度，还是从实际应用的角度，排序都是很难解决的问 题。从理论的角度而言，与组合优化的其他分支一样，排序中的很多问题也是p _ 困 难的，这意味着除非尸= p ，否则这些问题没有多项式时间算法。从应用的角度而 言，排序问题的困难主要在于实际中的实例牵涉到诸多因素，并且很多信息不是确 定的，于是人们在研究排序问题时往往作一一定的假设。根据f r e n c h 5 1 和p i n e d o 7 7 ， 经典排序问题中有以下假设： ( 1 ) 不允许中断抢先； ( 2 ) 不允许取消工件的加工； ( 3 ) 各个工件的加工时间不会随着排序的变化而变化； ( 4 ) 机器允许有空闲时间： ( 5 ) 在同一时刻一台机器至多能加工一个工件； 1 ( 6 ) 一个工件在任何时刻至多在一台机器上加工； ( 7 ) 机器在整个排序的加工过程中不会出现故障； ( 8 ) 约束条件事先已知且排序过程中不会变更； ( 9 ) 不具随机性，特别地： ( a ) 待加工工件数已知并不会再发生变化； ( b ) 待加工工件的加工时间已知并不会再发生变化； ( c ) 各个工件的到达时间已知并不会再发生变化； ( d ) 定义一个具体问题的其他参数均已知并不会再发生变化。 近十几年来，排序理论中研究的模型得到了快速的发展，很多模型突破了上述假设， 例如突破( 5 ) 的模型有分批排序、资源受限排序等，突破( 9 ) 的模型有随机排序、模糊 排序，等等。除( 5 ) 和( 9 ) 以外，在本论文中所讨论的模型符合上述假设。 本文中，与假设( 5 ) 不同，机器可以同时加工多个工件。这类排序问题称为平行 批排序问题。在这个模型里，同时加工的工件所构成的集合称为一批，每一批的加 工时间等于此批次里所有工件中加工时间最长的加工时间。由于平行批加工可以大 大地提高效率，降低生产成本，平行批排序在很多工业制造中得到了有效的应用。 例如在大规模集成电路的生产中，成品检验阶段要把集成电路放在烘箱中试验集成 电路是否能够在一定的温度下经受烘烤，烘烤的时间根据客户的不同要求而定。一 个烘箱可以同时烘烤多个集成电路，一批集成电路的烘烤时间为其中所需时间最长 的集成电路的烘烤时问，并且在烘烤过程中不能移走或者加入任何集成电路。由于 烘烤所需要的时间比检验过程的其他步骤需要的时间要长得多，所以合理地安排烘 烤顺序具有重要意义。 在平行批排序闷题中，机器可以同时加工的最大工件数称为该机器的批容量。 根据容量的大小，平行批排序问题可以分为两类。第一类是批容量有界的情形，此 时机器能够同时加工的工件数有限：第二类是批容量无界的情形，此时机器能够同 时加工无限多个工件。 实践中降低生产成本的另一种方法是：一台机器加工多种类型的工件。不过机 器从加工一种工件转换到加工另种工件时有时可能需要一定的安装时间，具有这 种特征的排序问题称为分组工件排序问题。 在排序问题中，如果模型符合假设( 9 ) ，即实例的所有信息在开始排序前就已经 2 知道，则称该模型是离线排序模型。作为假设( 9 ) 的突破，根据问题的实例在开始排 序前已知的信息( 如工件的个数、到达时间、加工时间等) 的多少，还有另外两类：在 线排序和半在线排序。如果实例中的工件的信息是逐个释放的，并且在决定当前工 件如何加工的时刻，对其后到达的工件的信息一无所知，同时一旦决定当前工件的 安捧后以后就不能更改，则称该排序模型为在线的。如果在开始排序前只知道实例 中工件的一部分信息，则称该排序模型为半在线的。本文的重点之一是在线排序。 在线排序分为两种：( 1 ) 列表在线排序：工件被排成一个队列，然后逐个释放。 一个工件只有当队列中排在它前面的工件都安排好后( 安排在哪台机器和哪个时间 段确定) 才知道这个工件的信息；( 2 ) 时间在线排序：每个工件均有一个到达时间( 事 先也是未知的) ，随着时间的增长过程机器安排工件加工，在任何时刻只知道当前 已到达的工件信息。在线排序又分为可预测的和不可预测的模型，在不可预测的情 形下，工件的加工要求只有加工完后才知道。组合起来，目前常被人们研究的在线 排序共有四种：列表可预测在线排序、列表不可预测在线排序、时间可预测在线排 序、时间不可预测在线排序。 在线排序的研究具有相当重要的现实意义，因为很多源于生产组织、网络通讯、 理论计算机科学的排序模型都具有在线的特征。例如在上述提到的集成电路的生产 过程中，如果要检测的集成电路是随时到达的，此时决策者就得决定：当前要检测 的集成电路中，哪些是要立刻放入烤箱中开始烘烤，哪些是要留待以后再检测的。 如何决策将直接影响生产的效率。研究在线排序，设计出高性能的在线算法，会对 这类生产活动起到重要的指导作用。 1 2网络路由选择的负载问题研究背景 采用w a v ed i v i s i o nm u l t i p l e x e d ( 简称w d m ) 技术的光纤网络广泛地应用于通 讯中。w d m 网络的带宽是通过将光纤划分成若干条信道、每种信道支持一种波长 而得，每种波长可以传输一组信息。尽管目前w d m 网络已经具有强大的信息传递 能力，但是仍然有很多优化问题有待解决。在研究网络优化问题时，人们通常用图 来表示光纤网络的拓扑结构。图的项点表示系统的元件，如路由器、存储器、波长 转换器等。图的边( 弧) 表示元件之间的物理连线或者一段光纤的信道。信息传递时 3 需要安捧传输路径，此外还需要给各组信息赋予相应的波长，其中要求：同时经过 同一段光纤的两组信息不能具有同样的波长。路径和波长的安排称为路由选择和波 长分配( r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t ，简称r a w ) 问题。 研究r a w 问题具有重要的现实意义。在实践中，单纯就光纤本身而言，它的容 量是无限的，可以同时传递大量的信息。但是现实中可用的波长的数量却相当有限， 这成为网络传递信息能力有局限的主要原因之一。m i h a i l 【7 2 】等人曾经指出在当前 的技术条件下，理论上可用的波长数量是3 0 - 4 0 种，实践中可用的数量更少，并且在 短期之内不可能增大很多。要增强光纤网络的信息传输能力，合理地选择路由和分 配波长显得尤其重要。 如果没有波长转换器，那么一个光波信号在从其源点到其终点的整个传递过程 必须保持同一种波长。此时r a w 可以抽象为图论中的路径安排和染色问题。r a b a n i 8 2 称之为最小路染色问题( m i n i m u mp a t hc o l o u f i n gp r o b l e m ，简称m p c p ) 。如 果信息在点与点之间进行传递，则m p c p 的一个实例实际上可用一个图g 和n 组顶 点对( 1 ，矗) ，( 如，矗) ( 不一定互不相同) 进行描述：每组顶点对之间有一组信息 要传递；实例的一个解将给出礼条路，其中第z 条路连接( 砝，矗) ，并且每条路均着有 一种颜色，满足有公共边( 弧) 的路颜色不能相同的要求；m p c p 的优化目标是使得 解中用到的颜色达到最少。图的点染色问题可以多项式归结到m p c p 的予问题一路 染色问题，这说w j m p c p 是一个p - 困难问题 5 2 卜没有波长转换器的网络的设计 不依赖于光学元件，所以它比较可靠且易于操作。但是它有很大的局限性，主要是 因为，即使传递为数不多的信息它也需要大量的波长，因此这种类型的网络结构不 宜在大规模网络中使用。 如果有波长转换器，那么一个光波信号从其源点到其终点的传递过程中可以变 化波长，此时每段光纤支持若干种波长，且顶点具有接收和转发的功能。此时r a w 问 题实际上是考虑如何安排路径，使得经过一条边( 弧) 的最大次数( 称为阻塞程度) 达 到最小的问题，此时需要的波长数量等于阻塞程度。在这种模型里，只要求信息在 通过同一条边( 弧) 时波长不一样，相对于没有波长转换器的网络，它需要的波长 数量要少得多，与此同时在这类网络中波长分配问题变得相当简单，因此，有波长 转换器的网络适用于大规模网络的构建。 同步光纤网络( s y n c h r o n o u so p t i c a ln e t w o r k ，简称s o n e t1 是其中一种有波长 4 转换器的网络，它是很多大规模网络的局部结构。s o n e t 环是一个重要的技术标准， 它的传输速度达到2 4 8 8 3 2g b p s 。s o n e t 由光纤连接增删复选机( a d dd r o pm u l - t i p l e x o r ，简称a d m ) 或数字交接系统( d i 酣a 1c r o a sc o n n e c ts y s t e m ，简称d c s ) 而 成。a d m 的作用是复合、转换和分离光波信号。d c s 的作用与a d m 的作用相似。s o n e t 环状的网络结构可以使i m 礁问题变得相对简单。此时网络的结构是对称的，它 上面每个点的作用、地位相同，网络易于维护、管理。在环状网络中进行通信时，信 息可以沿着逆时针或者反时针两个方向传递。如果环上有其中的一个点( 边) 出现 故障，信息可以沿着避开这个故障点( 边) 的方向传递。之所以很多大规模网络的 局部结构采用了s o n e t 环，主要是因为它的自我防护能力可以避免网络中的某个 点( 边) 的故障会导致整个网络的服务中断的情况发生，从而提高了整个网络的可 靠性。 对于网络中的任意一条边，它所支持的波长数量称为该边的容量。对于一个给 定的s o n e t 环而言，它的每一条边的容量都一样，因而可以将一条边的容量定义为 环的容量。确切说来，不是光纤本身而是a d m 的处理能力限制了网络的容量，不过 效果都一样：每个s o n e t 环都有一个容量g ，限制通过每一条边的信息组数不能超 过c 。构建环网络的费用是其容量的递增函数。因此，研究s o n e t 环路由选择的负 载问题，对降低成本、提高网络的利用率有重要的指导意义。 1 3概念与符号 1 3 1排序的概念与符号 描述一个工件易的特征有以下参数： 加工时间鳓； 到达时间勺； 权重奶； 交货时间出； 给定一个实例的排序，可以得到的以下参量： 乃的开工时间町； 5 以的完工时间伤； 以的延迟时间岛= 仍一而； 出的提前时间易= m “t 而一g ，o ) ； 易的延误时间乃= m “ c ；一而，o ； 易误工指示函数值码：如果o d j ，那么码= 1 ，否则= 0 ： 工件批b 的开工时问8 ( b ) ； 。工件批b 的加工时问p ( b ) = 。m ，。a x 。p j ； 工件批b 的完工时间c ( b ) ； 目标函数值，j = ，( c j ) 。 其它参数： 机器的容量b ； 机器的台数m ； 待加工的所有工件构成的集合了； 待加工的总工件数n ； 不同工件组的个数h ； 属于第i 组的丁件集无； 最小完工时间c ； 由算法h 得到的排序的完工时问c ； 最小完工时问和7 ； 由算法h 得到的排序的完工时间和t c h 最小加权完工时间和w t c ： 由算法日得到的排序的加权完工时间和w t c h 。 根据【1 9 】和【5 6 】，排序问题均可用三参数法简单记为a 俐7 。 1 o 描述机器的环境 6 机器可以分为两大类：平行( p a r a l l e l ) 机和串联( d e d i c a t e d ) 机。平行机又可以分 为3 类：具有相同加工速度的恒n ( i d e n t i c a l ) 机，具有不同加工速度但其速度不依赖 于工件的一致( u n i f o r m ) 机和随加工的工件不同加工速度也不同的无关( r e l a t e d ) 机。 串联机又可以分为3 类：每个工件以特定的相同的机器次序在这些机器上加工的流水 作q l ( f l o ws h o p ) 、工件依次在机器上加工的次序并不指定可以任意的自由作j k ( o p e n s h o p ) 和每个工件以各自特定的机器次序进行加工的异序作业( j o bs h o p ) 。 q l ，p q ，r ，0 ，e ， ，其中 a = l 表示单台机器； 口= p 表示恒同机； a = q 表示一致机； n = 臁示无关机； n = 0 表示自由作业机器； n = f 表示流水作业机器； 口= j 表示异序作业机器。 如果表示机器类型的字母有数字下标，则表示机器的台数为该数字。 2 p = 风仍岛角风风岛表示工件的各种加工要求与特征。 参数伪 d n l i n e ，o n l i n e l i s t ，o n l i n e l i s t n c l v ，o n l i n e n d v 描 述工件是否在线： 角= 0 ，l 一“与岛= r j 一起表示工件是时间在线； 角= m l i n e l i s t 表示工件是列表在线； 历o nl i n el i s t n e l v 表示工件是小可预测的列表在线： 历= 口n l i n e n e l v 与岛= 吩一起表示r t 件是不可预测的时间在线。 参数侥描述工件的到达时间： 统= 吩表示工件的到达时问不同，如无此约束表示工件的到达时间都是o 。 岛描述工件是否有截止期限( d e a d l i n e ) ： 岛= 也表示工件有截止期限。 7 参数屈描述工件加工是否可以中断抢先： 尻= p m t n 表示工件可以中断抢先，如无此约束表示工件不可以中断抢先。 参数傀 c h a i n ，p r e c ) 描述工件的先后约束： 风= c h a i n 表示工件的先后约束是链状； 风= 矿e c 表示工件存在某种先后约束。 参数风描述工件的加工时间： 风= 乃= 1 表示每个工件的加工时间都是1 ； 其它参数岛 f a m i l y ，p b a t c h ： 岛= f a m i l y 表示工件分组； 厮= p b a t c h 表示机器是平行批处理机。 3 1 描述排序所要优化的目标 通常7 g 。，q ，哟g ，死。，乃，l 。) ，其中： c k 。最后完工的工件的结束时刻； o 各个工件的完工时间之和： 屿。各个工件的加权完工时间之和； 2 1 m 。最大延误时间； 乃延误时间之和； 工件的误工数： 奶砺工件的加权误工数； l 。1 = 件的最大延迟。 1 3 2 环路由负载问题的概念与符号 。环状网络有两种不同的模型，一种是无向环，另一种是有向环。两种模型均可 以用图来表示：无向环可用无向图r = ( k c ) 表示，其中顶点集合y = 1 ，2 ，n ) ， 8 它当中的点按顺时针排列，边集合c = ( 1 ，2 ) ，( 2 ，3 ) ，一1 ，扎) ，( 1 ) ) ；有向环 可用有向图碍= ( v ，c ，) 表示，其中顶点集合= l ，2 ，n ) ，它当中的点按顺时 针排列，编号相邻的顶点问有两条方向相反的弧。 是定义在r = ( k c ) ( 或彤= ( v 7 ，c ，) ) 上的点对集合，如果( i ，j ) k ，那 么表明顶点i 与j 之问有信息要传递。i n j z n 的- - + 信息请求可用非负整数函，来描 述，应，f 表示它们之间要传递的信息组数。在无向环里，给每个信息请求安排的路由 是一条无向路；在有向环里，给每个信息请求安排的路由是一条有向路。在环状网 络里，信息传递的路由只有两种选择：顺时针或者逆时针。人们研究环路由负载问 题时，主要考虑了以下三种不同的模型： 信息请求可以任意分割成两部分，然后沿着不同的方向传递； 信息请求不能分割，一个信息要么全部沿着顺时针传递，要么全部沿着逆时针 传递； 信息请求可以分割成两部分，但要求每部分的信息量都是整数，然后沿着不同 的方向传递。 给定一个路由方案，一条边( 弧) i 上的负载( 1 0 a d ) 等于经过该边( 弧) 的信息组数， 记作厶。环路由负载问题( r i n gl o a d i n gp r o b l e m ，简称r l p ) 是关于环的r 、v a 问题 的一个子问题，它的确切定义是： 已知r = ( k c ) ( 或足一( v ，c ，) ) ，k , g l d ，( ( ，j ) ) 。要解决的问题是： 给每个信息请求确定一个传递方案，使得环上负载最大的边( 弧) 的负载达 到最小。 本文要讨论一种更一般的无向环状网络：环上的每条边i 都有一个非负权重毗。 给定