（管理科学与工程专业论文）柔性flow+shop启发式调度算法的渐近最优分析.pdf

。串圈斜爹投菇太擎博士学位论文 柔牲f l 。ws i l o p 启发式调度算法的渐近屉优分析 摘要 调度问题在柔性制造系统、现代物流、计算机科学等领域中非常重要，但绝 大多数调度问题是n p h a r d 问题，几乎不可能有多项式时间复杂度的最优求解算 法，大量研究工作主要集中在近似算法的设计和分析。而调度问题的规模一般较 大，分析其近似算法的绝对性能比往往很困难，有时甚至不可行。因此，研究近 似算法的渐近性能比就显得很有必要。 对于目标函数为作业加权完成时间和的单机、平行机、f l o ws h o p 、j o bs h o p 调度问题，可以基于加权最短处理时间的启发式算法获得渐近最优解。本论文的 目的就是研究这种渐近最优的简单经验规则是否也适合更复杂的调度问题。 首先，本论文研究了同速处理机中心的柔性f l o ws h o p 加权完成时间调度问 题。针对该问题的每个子问题，本文研究了两个基于瓶颈处理机中心的( 有效作 业) 加权最短处理时间的启发式算法，并使用机器模型分组和概率分析方法，证 明了它们是渐近最优的。 其次，本论文研究了恒速处理机中心的柔性f l o ws h o p 加权完成时间调度问 题。针对该问题的每个子问题，本文研究了两个基于瓶颈处理机中心的( 有效作 业) 加权最短处理时间需求的启发式算法，并使用单机松弛和概率分析方法，证 明了它们是渐近最优的。 再次，本论文研究了恒速处理机中心的随机柔性f l o ws h o p 加权完成时自j 调 度问题。针对这个问题，本文研究了基于瓶颈处理机中心的加权最短期望处理时 间需求的启发式策略，并再次使用单机松弛和概率分析方法，证明了该策略是渐 近最优的。 最后，在总结全文的基础上，对今后的研究提出了建议和展望。 关键词：柔性f l o ws h o p 调度；启发式算法；算法分析；渐近最优分析 。幸圈窀警趣，l 大誊博i 学位论文 中英文摘要 a b s t r a c t s c h e d u l i n gp r o b l e m sa r ev e r yi m p o r t a 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 ， m o d e ml o g i s t i c s ，c o m p u t e rs c i e n c ea n do t h e rf i e l d s u n f o r t u n a t e l y ，m o s to ft h e ma r e n p - h a r d ，w h i c ha r ea l m o s th a r d l yp o s s i b l et oa t t a i nt h eo p t i m a ls o l u t i o n sb yu s i n gt h e a l g o r i t h m so fp o l y n o m i a lt i m ec o m p l e x i t y a sar e s u l t ，n u m e r o u se f f o r t sh a v eb e e n m a d et od e v o t et ot h ed e s i g na n da n a l y s i so fa p p r o x i m a t i o na l g o r i t h m s d u et ot h e l a r g es i z eo fs c h e d u l i n gp r o b l e m s ，t h e ya r er a t h e rd i f f i c u l t ，a n de v e ni m p r a c t i c a l ，t o a n a l y z et h ea b s o l u t ep e r f o r m a n c er a t i oo ft h e i ra p p r o x i m a t i o na l g o r i t h m s t h e r e f o r e ， i ti sv e r yn e c e s s a r yt os t u d yt h ea s y m p t o t i c a lp e r f o r m a n c er a t i oo fa p p r o x i m a t i o n a l g o r i t h m s a st ot h ew e i g h t e dc o m p l e t i o nt i m es c h e d u l i n gp r o b l e m so fs i n g l em a c h i n e ， p a r a l l e lm a c h i n e ，f l o ws h o p ，a n dj o bs h o p ，t h ea s y m p t o t i c a l l yo p t i m a ls o l u t i o n sc a nb e o b t a i n e db yt h eh e u r i s t i c sb a s e do nw e i g h t e ds h o r t e s tp r o c e s s i n gt i m e t h ep u r p o s eo f t h i sd i s s e r t a t i o ni st r y i n gt op r o v et h a tt h es i m p l er u l e o f - t h u m bc a l lb ea p p l i e dt o m o r ec o m p l i c a t e ds c h e d u l i n gp r o b l e m s f i r s t ，t h ed i s s e r t a t i o nc o n s i d e r st h ef l e x i b l ef l o ws h o pw e i g h t e dc o m p l e t i o nt i m e s c h e d u l i n gp r o b l e mw i t hi d e n t i c a lm a c h i n e sa te a c hs t a g e f o re a c hs u b p r o b l e mo f t h ep r o b l e m ，i te x p l o r e st w oh e u r i s t i ca l g o r i t h m sb a s e do nt h ew e i g h t e ds h o r t e s t p r o c e s s i n gt i m e ( a m o n ga v a i l a b l ej o b s ) o fb o t t l e n e c ks t a g e ，a n ds h o w st h a tt h e ya r e a s y m p t o t i c a l l yo p t i m a lb yu s i n gt h em e t h o d o fm a c h i n em o d e lg r o u p i n ga n d p r o b a b i l i s t i ca n a l y s i s t h e n ，t h ed i s s e r t a t i o nr e s e a r c h e st h ef l e x i b l ef l o ws h o pw e i g h t e d c o m p l e t i o n t i m es c h e d u l i n gp r o b l e mw i t hu n i f o r mm a c h i n e sa te a c hs t a g ef o re a c hs u b p r o b l e m o ft h i sp r o b l e m ，i tf i g u r e so u tt w oh e u r i s t i ca l g o r i t h m sb a s e do nt h ew e i g h t e ds h o r t e s t p r o c e s s i n gr e q u i r e m e n t ( a m o n ga v a i l a b l ej o b s ) o f b o t t l e n e c ks t a g e ，a n db yu s i n gt h e m e t h o do fs i n g l em a c h i n er e l a x a t i o na n dp r o b a b i l i s t i ca n a l y s i s ，p r o v e st h a tt h e ya r e a s y m p t o t i c a l l yo p t i m a l t h i r d ，t h ed i s s e r t a t i o ns t u d i e st h es t o c h a s t i c f l e x i b l ef l o w s h o pw e i g h t e d 。幸圈错孽投森大学博士学位论文 柔髓f i 。ws h 叩启发式铡度算法的渐近最优分析 c o m p l e t i o nt i m es c h e d u l i n gp r o b l e mw i t hu n i f o r mm a c h i n e sa te a c hs t a g e f o rt h e p r o b l e m ，i tw o r k so u tt h eh e u r i s t i cp o l i c yb a s e do nt h ew e i g h t e ds h o r t e s te x p e c t e d p r o c e s s i n gr e q u i r e m e n to fb o t t l e n e c ks t a g e ，a n da g a i nb yu s i n gt h em e t h o do fs i n g l e m a c h i n er e l a x a t i o na n dp r o b a b i l i s t i ca n a l y s i s ，p r o v e st h a tt h i sp o l i c yi sa s y m p t o t i c a l l y o p t i m a l f i n a l l y ，t h ed i s s e r t a t i o ns u m su pt h eo v e r a l lw o r k s ，a n dg i v e ss o m er e s e a r c h p r o p o s a l so f t h ek e yp o i n t so nt h ei s s u ei nt h ec o m i n gs t a g e ， k e y w o r d s ：f l e x i b l ef l o ws h o ps c h e d u l i n g ；h e u r i s t i ca l g o r i t h m ；a l g o r i t h ma n a l y s i s a s y m p t o t i c a l l yo p t i m a ta n a l y s i s l i i 。幸圈斜孽技寐天簪博【学位论文柔性f 1 。ws h 。p 启发式调度算法的渐近_ 娃优分析 第一章绪论 调度问题在柔性制造系统、现代物流、计算机科学等领域中非常重要，但绝 大多数调度问题是n p h a r d 问题，有的甚至是强n p h a r d 问题，它们几乎不可能 有多项式时间复杂度的最优求解算法。而有效的调度系统能使现代商业领域增加 产出、减少周转时间、减少库存，最终减少生产费用、增加利润和客户满意度， 所以调度系统性能的好坏对这些行业的高效运作有着重要影响。 本章首先描述调度问题和算法性能比的概念，然后简要叙述本论文研究的问 题，以及相关调度问题的研究现状，最后简述本论文的研究动机、结果和本论文 结构。 1 1 调度问题概念 调度问题是指作业或任务如何占用有限资源的决策过程，其目标为使某一函 数最优，而目标函数通常是对加工时间的长短、资源利用率的描述。它是一类重 要的组合最优化问题。 本论文研究机器调度问题，是指如何分配作业在机器上进行加工处理，以使 某一目标函数最优。作业在机器上加工时需要满足一定约束条件，如作业的到达 时间、作业的加工顺序、作业加工时是否允许抢占、资源对作业加工时涮的影响 等。 调度问题可以分为确定性调度问题和随机性调度问题。如果调度决策时作业 参数都是己知的，没有不确定性，则称该问题为确定性调度问题：如果调度决策 时至少一个作业参数( 如作业加工时间、作业准备时问等) 是随机的、不确定的， 则称该问题为随机性调度问题。 为便于叙述，本论文使用通用的三元组符号口j jy 来描述调度问题的类型 【1 ，即从处理机、作业和目标函数三个要素来描述调度问题。 a 域表示处理机的数量、类型和环境，主要有： 1 ( s i n g l ep r o c e s s o r ) ：指只有一个处理机。 p ( i d e n t i c a ! p a r a l l e lp r o c e s s o r s ) ：指所有的处理机都具有相同的速度。 幸图斜誊援，t 又簪博小学位论文 第一章绪论 q ( u n i f o r mp a r a l l e lp r o c e s s o r s ) ：恒速平行机，指处理机的速度不同， 但每个处理机的速度都是常数，不依赖于被加工的任务。 r ( u 眦e l a t e dp a r a l l e lp r o c e s s o r s ) ：变速平行机，指处理机的速度领带被 加工的任务。 如果平行机的数目为一固定常数m ，则上述三个平行机问题依次表示为 p m 、q m 、r m 。 f ( f l o ws h o p 机器模型) ：指作业需要在多个处理机上加工，每个作业 在所有处理机上的加工序列相同，且每个作业必须在每个处理机上加工。 0 ( o p e ns h o p 机器模型) ：指作业需要在多个处理机上加工，每个作业 在所有处理机上的加工序列任意，且每个作业必须在每个处理机上加工。 j ( j o bs h o p 机器模型) ：指作业需要在多个处理机上加工，每个作业在 处理机上有自己的加工序列。 如果多个处理机的数目为一固定常数w ，则上述三个车间调度问题依次 表示为f m 、o m 、j m 。 胁( f l e x i b l e f l o ws h o p 机器模型) ：指有s 个处理机中心，每个处理机 中心由平行机组成，每个作业有s 个工序，每个工序需要在每个处理机中心 的机器上加工处理，且每个作业的加工序列相同。 口域表示作业的性质、加工要求和对加工的限制等约束条件，它可同时 包含多项，也可为空，如，、p m t n 、p r m u 、p a r a l l e l 分别表示有非平凡的 作业到达时间、作业加工时允许中断、车间作业调度中作业按排列方式加工、 柔性车间作业调度中作业允许同时在一个处理中心的几个处理机上并行处 理。 如果问题为随机性调度问题，则在相应的随机变量后加上符号s t o c h ， 如随机作业处理时间x ，表示为x ，s t o c h - y 域表示目标函数。常见目标函数有：制造跨度c 。、加权完成时间和 哆c ，、最大延误l 。等。本论文仅研究目标函数为加权完成时和 w ，c ，( 或加权完成时间期望和研w ，c ，】) 的调度问题。 2 。中圈斜誊投谆大筝博：i 学位论文柔陀f 】。w 。h o p 启发式调度算法的渐近最优分析 1 2 算法性能比 根据计算复杂性理论，除非n p = p ，n p - h a r di 司题不日 能有求冥最优解的多 项式时间算法；强n p h a r d 问题甚至不存在求其最优解的伪多项式时间算法 2 、 3 1 。这导致了大量研究工作主要集中在近似最优算法的设计与分析。 评价近似算法有效性的重要工具是分析算法的性能比。本论文主要讨论算法 的虽坏性能比和渐近性能比。 定义i - i ：设h 为近似算法，c u ) 为某一类确定性调度问题集，为c u ) 中 任一调度问题实例，z ( ，) 为问题的最优目标值，z “( ，) 为使用近似算法求 解问题，所产生的目标值则近似算法矗在问题类c o ) 从郫定义可知，最坏性能比给出了近似算法h 所求问题目标值与最优 目标值之间可能发生的最大相对偏离，这种算法最坏性能比一般只能对规模：r i n d 、 的调度问题才可获得。因而，设计和分析求解大规模调度问题的算法渐近性能比 就显得非常必要。 定义卜2 ：近似算法h 在问题类c ( ，) 上的渐近性能比尺： 4 1 定义为： 月= i n 啦脚+ ，w c ( 加 m 哿纠， 这里l ，i 为问题，的输入参数长度。 如果问题类c ( ) 为随机性调度问题，则渐近性能比r ：定义如下： 定义1 _ 3 ：近似策略h 在随机性问题类c ( ，) 上的渐近性能比尺： 5 】定义为：， r = i n f 1s ne z * , v ie c 圳蛉亿黜驯 由r 7 , 定义可知，对于问题类c ( ，) 中的“充分大”实例，渐近性能比冗；刻 画了近似算法( 或策略) h 所求问题的目标值与最优目标值之问可能发生的最 鱼主塑垒量垫壅查鲎堕：! 兰些笙兰 塑二! 堑鲨 大相对偏差。如果一个算法( 或策略) 的渐近性能比为1 ，则称该算法( 或策略) 为渐近最优的。 1 。3 研究问题 本论文主要研究以下三个调度问题： 1 同速处理机中心的柔性f l o ws h o p 加权完成时问调度问题； 2 恒速处理机中心的柔性f l o ws h o p 加权完成时间调度问题； 3 恒速处理机中心的随机柔性f l o ws h o p 加权完成时间调度问题。 下面具体描述这三个问题。 1 3 1 同速处理机中心的柔性f i o ws h o p 加权完成时间调度问题 在同速处理机中心的柔性f l o ws h o p 加权完成时间调度问题中，有一，t 个作 业的集，= 1 , 2 ，n ) 需要依次加工在固定的s 个处理机中心上，第i 个处理机中 心由，。个同速机组成。作业( j ) 在处理机中心i ( i = 1 , 2 ，j ) 的处理时间为 p ， 0 ，权重为w ，0 和到达时间为0 0 。作业直到到达时才能加工处理，且 每个作业必须依次通过s 个处理机中心。目的是确定一个作业加工序列，以使所 有作业的加权完成时间和，。q 最小，这里q 为作业删- f b 。 根据作业参数的约束条件不同，同速处理机中心的柔性f l o ws h o p 加权完成 时间调度问题可分为以下三个子问题。使用调度问题通用符号，三个子问题表示 如下： ( 1 ) 如果所有作业到达时间_ 相同，则该调度问题表示为： 鼢( p m i = l ip m 2 = f 2 ，一，p m ，一，) w j c j ； ( 2 ) 如果作业到达时间，不同，则该调度问题表示为： m ( j p m 、= f 1 ，p m 2 = ，2 ，p m ，= f ，) i ，i w ，c ，； ( 3 ) 如果作业到达时问r ，不同，并且作业加工时能同时抢占式地加工处理在 鲤斜蕾技寐太学博卜学位论文柔性f 】。w 。h 印启发式调度势法的渐近瑶优分析 相应处理机中心的任一处理机子集上，则该调度问题表示为： 胁( m 12 i i , p m 2 = ，2 ，p m 。= ，) ir ，p m t n ，p a r a l l e l i i v j c ，。 1 3 2 恒速处理机中心的柔性f l o ws h o p 加权完成时间调度问题 在恒速处理机中心的柔性f l o ws h o p 加权完成时间调度问题中，有一h 个作 业的集j = 1 , 2 ，”) 需要依次加工在固定的s 个处理机中心 c = m l ，m 2 ，m ，) 上，第f ( f = 1 , 2 ，j ) 个处理机中心m ，由1 个恒速机 聊j l ，m 啦，m “) 组成，机器t n “的速度为s a 不失一般性，假定 5 s ，2 8 “ 0 。作业j ( j j ) 在处理机中心i ( i = 1 , 2 ，s ) 的处理时间需求 为p 。 0 ，权重为w ，0 和到达时间为0 0 。作业直到到达后才能加工处理， 且每个作业必须依次通过j 个处理机中心。目的是确定一个作业加工序列，以使 所有作业的加权完成时间和。，w ，c ，最小，这里c ，为作业，的完成时间。 根据作业参数的约束条件不同，恒速处理机中心的柔性f l o ws h o p 加权完成 时间调度问题可分为以下三个子问题。使用调度问题通用符号，三个子问题表示 如下： ( 1 ) 如果所有作业到达时间r 相同，则浚调度问题表示为： f f s ( q m ，= 0 跏：= ，：，q m ，= f ，) j j w ，c ，； ( 2 ) 如果作业到达时间r j 不同，则该调度问蹶表示为： f f s ( q m = i i , 劬：= b - - ，q m 。= f 、) w c ： ( 3 ) 如果作业到达时问r ，不同，并且作业加工时能同时抢占式地加工处理在 相应处理机中心的任一处理机子集上，则该调度问题表示为： f f s ( q m l = f l ，跏2 = f 2 ，q m ，= f ) ir j , p m t n ，p a r a l l e l l w 。c 。 鱼主璺塑望垫塞查兰塑：! ：兰垡垦苎 垂堡! ! ! 兰! ! 旦塾些型竺兰鲨塑塑里堡堡竺堑 相麻处理机中心的任一处理机子集上，则该调度问题表示为： 脓( m 1 = ，- ，m 2 = o ，m 。= 1 ) h p m t n ，p a r a l l e l f w ，c ，。 1 3 2 恒速处理机中心的柔性f l o ws h o p 加权完成时间调度问题 在恒速处理机中心的柔性f l o ws h o p 加权完成时可调度问题中，有一n 个作 业的集i ，= 1 , 2 ，”) 需要依次加工在固定的s 个处理机中心 c = ，m 2 ，t ，m ， 上，第羽= 1 , 2 ，j ) 个处理机中心m ，由。个恒速机 ”u ，”，) 组成，机器“的速度为。不失一般性，假定 ，2 0 ，作业，( ，) 在处理机中心彬= 】，2 ，j ) 的处理时间需求 为p 。 0 ，权重为叶0 和到达时间为r 。0 。作业直到到达后才能加工处理， 且每个作业必须依次通过j 个处理机中心。目的是确定个作业加工序列，以使 所有作业的加权完成时间和。，w ，c j 最小，这旱c ，为作业，的完成时间。 根据作业参数的约束条件不i 刊，恒速处理机中心的柔性f l o ws h o p 加权完成 时问调度问题可分为以下三个子问题。使用调度问题通用符号，三个子问题表示 如下： ( 1 ) 如果所有作业到达时削0 相同，则该调度问题表示为： f f s ( q m 。= ，劬! = o ，西，= ) f i w ，q ； ( 2 ) 如果作业到达时间0 不同，则改调度问题表示为： f f s ( q m = f ，q m ：= f ，鲫、= ，。) iri w ，c ，； ( 3 ) 如果作业到达时问_ 不l 刊，并且作业加工时能同时抢占式地加t 处理在 相应处理机中心的任一处理机子集上，则该调度问题表示为： f f s ( q m l = i i , q m 2 = f 一，q m ，= ，、) o ，p r o m ，p a r a l t h w ，cj 。 f f s ( q m l = ，1 ，= f 2 ，q m 、= ，、) r i , p m t n ，p a r a l l e l l w ，c ，。 5 鱼生塑垒鐾墼查查茎堡。! 篁堕堡兰 笙二要堑堡 1 3 3 恒速处理机中心的随机柔性f i o ws h o p 加权完成时间调度问题 在恒速处理机中心的随机柔性f l o ws h o p 加权完成时间调度问题中，有” 个作业的集i ，= 1 , 2 ， 需要依次加工在固定的s 个处理机中心 c = m ，m ：，m ，) 上，第i ( i = 1 , 2 ，s ) f 个处理机中心m ，由f ，个恒速机 m u ，聊，2 ，m 组成，机器m “的速度为s 。不失一般性，假定 5 5 啦s 0 。作、j i l j ( j j ) 在处理机中心i ( i = 1 , 2 ，r - ，s ) 的随机处理时间 需求为x 。 0 ，权重为w ，0 ，所有作业的到达时间相同。在这种随机调度问 题中，随机处理时间需求x 。的期望值e 工。 己知，它的实际值直到加工完成时 才知道。目的是确定一个可行的调度策略，以使所有作业的加权完成时间期望和 e 【j e 3 w ，c ， 最小，这里c ，为作业，的完成时间。 使用调度问题通用符号，恒速处理机中心的随机柔性f 1 0 ws h o p 加权完成 时间调度问题表示为： f f s ( q m l = 1 1 ，劬2 = ，2 ，o n ，= ， ) h s t o c h ie l 艺w j c _ ， 。 本论文研究的确定性和随机性调度问题都是强n p h a r d 问题。因为确定性 i h 题f 2 i l c ，已是强n p h a r d 问题【6 】；而寻找随机性调度问题的最优策略等价 于求解一个相应的确定性调度问题 7 】，因此，恒速处理机中心的随机柔性f l o w s h o p 加权完成时间调度问题也是强n p h a r d 问题。 1 4 研究现状 本节概述与本论文研究问题相关的调度问题的研究现状和进展，主要集中在 目标函数为加权完成时间和的确定性调度问题和目标函数为加权完成时间期望 和的随机性调度问题。 1 4 1 确定性调度问题 确定性调度问题从算法的最坏性能比、渐近性能比两个方面展丌，主要包括 垒塑塑至垫查查至堡：! 兰竺堡兰 鲞堡! ! ! 尘! ! 生丝些塑壁竺鲨箜塑望壁垡坌塑 单机、平行机、f l o ws h o p 、柔性f l o ws h o p 凋度问题。 1 4 1 1 最坏性能比 1 单机调度问题 众所周知，问题1j w j c ，可由加权最短处理刊i b j ( w s p t ，w e i g h t e ds h o r t e s t p r o c e s s i n gt i m e ) 经验规则( r u l e o f - t h u m b ) 求得最优解【8 ，但这个结果不能扩 展到一般情况，因为即使作业权重都相等，问题l oi c ，已经是n p h a r d 的 9 。 对于问题1 i ol w i g j ，o o e m a n s e ta 1 1 0 基于线性规划( l p ，l i n e a r p r o g r a m m n g ) 和随机独立口点算法获得了1 6 8 5 3 一近似算法，运行时间为 o ( n l o g n ) ；a f r a t ie ta 1 1 1 利用几何取整( g e o m e t r i cr o u n d i n g ) 和时间拉 r g ( t i m e s t r e t c h i n g ) 两种变换技术，给出了问题1i ，l w ，c ，的多项式时问近似算法策略 ( p t a s ，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 4 ) ，即1 + g 近似算法。 而对于抢占式问题1 i o ，p m t n l c ，它可由最短剩余处理时问( s r p t ， s h o r t e s t r e m a i n i n gp r o c e s s i n gt i m e ) 经验规则求得最优解【】2 ，但这个结果也不 能扩展到一般权重的调度问题，因为1o ，p m t ni w ，c ，是强n p h a r df n n 1 3 1 。 s c h u l za n ds k u t e l l a 1 4 1 研究了i h 题l l o ，p m t n i w j c j ，他们在随机独立口 点算法基础上，给出了一个更简单的算法分析，并产生了比1 4 6 6 【1 5 】更好的算 法性能比4 1 3 。 2 ，平行机调度问题 对于作业同时到达的平行机调度问题，同速平行机问题尸i i c ，可按最短处 理时间( s p t ，s h o r t e s tp r o c e s s i n gt i m e ) 经验规则求得其最优解【1 6 】；变速平行 机问题尺i i c ，可由二分匹配法( b i p a r t i t e m a t c h i n g ) 求得最优解 1 7 。但上面结 果也不能扩展到一般平行机调度问题，因为作业权重不同的同速平行机调度问题 p i i w j c ，已是强n p h a r d 问题 1 8 。 对于作业非同时到达的平行机调度问题，方面，c h e k u r ie ta 1 【1 9 利用抢 鱼主塑垒兰垫窭盎至堡 ：兰竺丝兰 翌二至堑堡 占式单机松弛方法获得了同速平行机问题po c ，的一个性能比为28 5 一近 似算法：h a l le ta l 2 0 基于线性规划设计了变速平行机问题r i oj w ，c ，的一 个性能比为1 6 3 的离线算法：s k u t e i i a 2 1j 利用半萨定规划( s d p , s e m i - d e f i n i t e p r o g r a m m i n g ) 给出了问题r l ，l w ，c ，的一个2 - 近似算法。另一方面，a f r a t ie t a 1 i i 利用几何取整和时i 司拉伸变换技术，设计了平行机调度问题 p w ，c j 、p h p r n t n t z w c 、月w c 、r m r ，p i n t n i 一q 的多项式时间近似算法策略。 由于目标函数为加权完成时间和的调度问题基本上都是n p h a r d 问题，有些 甚至是强n p h a r d 问题，这就意味着它们几乎不可能存在多项式时间的算法。因 此，研究人员将重点放在了设计具有常数因子的近似算法上。 p h i l l i p se ta l _ 2 2 在这方面首先取得了突破，获得了多个n p h a r d 单机、平 行机加权完成时间调度问题的常数因子近似算法。他们设计的近似算法的基本思 路是：首先松弛问题以构造易于求解和分析的线性规划；然后利用线性规划解为 基础产生问题的一个作业排序，作业按照产生的作业排序进行列表式调度；最后 根据获得的问题目标值的上下界计算近似算法的最坏性能比，即松弛问题解和列 表式调度所产生的目标值之比，这一计算过程通常使用作业到作业( j o b t o j o b ) 的比较方法。 在p h i l l i p se ta l 2 2 之后，许多研究人员运用类似方法，不断改进问题的松 弛方法、线性规划构造方法和算法分析方法，结果在许多调度问题取得了实质性 研究进展。有关单机、平行机加权完成时间调度问题的近似算法的最坏性能比研 究情况见表1 1 ，具体算法及算法分析详情见相关的参考文献。 表1 1 ：单机、平行机调度问题的近似算法的最坏性能比情况一览表 离线 在线算法 问题 确定性随机性 算法时间复杂性 参考文献 算法 算法算法 l ir ，1 c ， 2 02 o 0 i l o gn 1 p h i l l i p se ta l 2 3 】 l lr ji c 15 8 2 015 8 2 0o l ”l o g lc h e k u r ie ta l _ 1 9 】 ijr ，j w ，c ， 1 6 + s求解线性规划 p h i l l i p se ta l 2 3 1 l o i w j c ， 31 631 6 0 f n l o g 月1 c h e k u r ie ta l 1 9 1 1 lr j w ，c 。33 + o ( ，( 1 f n l o gh )h a l le ta 1 2 0 1l i ，i w ，c ， 2 8 8 5 42 8 8 5 4 o ( h l o gn 1 c h a k r a b a r t ie ta l 2 4 。幸圈锘等投毒犬分博1 学位论文柔性f i 。w 。h o p 启发止洲度剪：往的渐近最仇分析 t ir ，i w c ， 2 o 2 0 o ( j i l o g 月) g o e m m l s 1 5 1 h l w c ， 1 6 8 5 3 1 6 8 5 3 0 ( n l o gj ，) g o e m a n se ta 1 1 0 i lri w j c ， 1 十 o ( 2 “”+ t o g 。】la f r a t ie ta l 1 1 】 lh p m t n l w c ， 8 + co ( t 7 l o g t ) p h i l l i p se ta l 2 3 【i7 j ，p j l w i c ， 2 o 求解线性规划 h a l le ta l 2 0 】 1i ，j 、p m t n l c ， 1 4 6 61 4 6 6 0 ( h l o g 月1 g o e m a n se ta 1 2 5 l h p r o m 一c 4 1 3 4 3 o f t o gn ) s c h u l z ，s k u t e l l a 1 4 j l i o ，p m t n l c ， 1 + o ( 2 7 m “，t + l o gn 】 a f r a t ie ta l i 1 1 州w c ， i 2 1 o e ”l o g ) k a w a g u c h i ，k y a n 【2 6 p i i w s c ， l + 0 ( 【 t i ，f ) jj + ，l o gn ) s k u t e l l a ，w o e g i n g e r 2 7 p mr ，1 ec ， 6 06 oo ( ”l o g ”) p h i l l i p se ta 1 【2 3 】 p m r ，i c ， 3 5o f n l o g )c h a k r a b a r t ie ta 1 2 4 p m r ， c ， 2 8 53 1 m 0 月i o gn )c h e k u r ie ta 1 1 9 】 p m i ，i c 2 0 2 ，0 o ( i o g 月) s k u t e l l a 2 8 p m l o l w i c ， 2 4 + 求解线性觌划 p h i l l i p se ta l 。 2 3 】 p mr ，f w ，c ， 4 1 m4 + 0 ( f ( m i ，fj n + h t o g j h a l le ta 1 【2 0 p mj o i w c ， 2 8 9 + a 2 8 9 + o ( n l o g ) c h a k r a b a r t ie ta 1 【2 4 p m lr i w s c j2 02 0 0 ( 月i o gn 】 s k u t e l l a 2 8 p jr j i w ，c ，l + o c ( m + 1 ) ”“。1 + l o gh ) a f r a t ie ta 1 【1 1 p m i - ，p t n t n i c j 2 0 2 ，0 o ( n l o gh ) p h i l l i p se ta 1 2 3 ? m l o ，p m m l 叶e 3 o 求解线性规划 h a l le ta 1 2 0 ? r n lo ，p m t n 叶q2 02 o 0 ( 月i o gh ) s k u t e l l a 【2 8 】 p 峙p m m l q 1 + o ( 2 ”o 。1 n + h l o gn 1a f r a t ie ta 1 1 1 r l i ew ，cj 1 6 3求解线性规划 h a l le ta 1 2 0 】 r f f w j c ， 1 5 + 求解半正定规划 s k u t e l l a 【2 8 】 r l p m t n f 叶c 8 + 求解线性规划 p h i l l i p se ta 1 2 3 】 r i p m t n i w c j 2 + 求解半正定规划s k u t e l l a 2 8 】 r i ， w ，cj 1 6 广3求解线性规划 h a l l e t a l 【2 0 l r ir ，i w j c ，2 + 求解半正定规划 s k u t e l l a 【2 8 】 r ml ，i w j c ， 1 + d ( ，m ，1 ，印p o t y 月) )a f r a t ie ta 1 【1 1 r i - ，p m t n i 1 ，c j8 + 求解线性规划 p h i l l i p se ta 1 2 3 刷，p m o li e w ，c ， 3 + 求解半f 定规划s k u t e l l a 2 8 】 r m ir ，p m t n i w ，c ， 1 + 0 ( f ( m ，1 f ) + n l o gn 】 a f r a t ie ta 1 1 1 注：，? 为问题规模大小；满足0 f 0 ，权重为w ，0 ，所有作业到达时问相同。所有作业按照相同路径依次 通过处理机中心1 到j ，并且每个作业一次只能在某个处理机中心的一台机器上 加工处理，不能同时在一个以上的处理机中心进行加工：任何作业工序加工过程 中不允许中断；处理机中心的任一处理机能够加工任一作业的相应工序，但每个 机器一次只能加工一个作业；相邻的处理机中心之问作业存储单元没有限制。问 题的目标是确定一个可行作业调度序列，以使所有作业的加权完成时间和 w ，c ，最小，这儿c ，表示作业，的完成时问。 本章将该问题记为只。设z ( 只) 为只的最优目标值；z “( 只) 为只由启发式 算法h 产生的目标值。 4 。幸圈斟爹技未失筝博f j 学位论文梁性f l 。w 。h 。p 启发式训度算法的渐近最优分析 2 1 2 问题的启发式算法 针对问题只，本节使用瓶颈优先原理和分组机器模型方法给出基于瓶颈处理 机中心的加权最短( 平均) 处理时问的两个启发式算法。所谓瓶颈优先原理，指 为使启发式算法产生的目标值尽可能的接近最优解，优先排序同速处理机中心的 柔性f l o ws h o p 机器模型中加工能力最弱的处理机中心的作业工序。所谓瓶颈处 理机中心，是指机器数最少、加工能力最弱的处理机中心。 首先，基于柔性f l o ws h o p 机器模型的瓶颈处理机中心构造一个与问题只关 联的同速平行机调度问题砌l i w ，c 。，记为耳，这里g 为瓶颈处理机中心的 序号，它满足，。= r a i n 。；，( 为简便，已m = l , i ) 。具体构造如下：鼻”有一打个 作业的集n ，= 1 ，2 ，盯) ，作、j k j ( j ) 的权重w j - 9 1 q 题8 中作业( ，) 的权 重相同，处理时间p ，与问题置中作业j 在处理机中心g 的处理时间相同，即 p ，= p 。设z ? ( 鼻”) 为问题邱加工在速度为m 的单机上的最优目标值；z ：( 邱) 为问题邱加工在速度为l 的蜥个同速平行机上的最优目标值。 为叙述简便，本论文设陋 - 1 , 2 ，女) 表示一个符号集，除非另有醢明。 其次，按照瓶颈处理机中心分组同速处理机中心的柔性f 】o ws h o p 机器模型t 分成m 组：g 1 ，g2 ，g 。g7 ， 聃一1 有s 个处理机中心，每个处理机中心只 有一台机器的柔性f l o ws h o p 机器模型组成；g 为一特殊柔性f l o ws h o p 机器模 型，它有s 个处理机中心，处理机中心f 有，一f 。+ 1 个机器组成。不失般性， 假设g7 ( ， 聊】) 与同速平行机上机器，( ，f 卅 ) 一一对应；月i r a ) 为在同速平 行机z 或g7 上加工处理的作业数，拧= ： 7 。 启发式算法如下： 问题