（运筹学与控制论专业论文）机器具有准备时间的排序问题.pdf

机器具有准备时间的排序问题 摘要 排序问题是一类重要的组合最优化问题，现在已经成为运筹学研究的一个非 常活跃的分支，是运筹学中相当具有生命力的一部分。排序问题的一大特点是： 模型繁多，适用于某一模型的算法，只要将模型的条件稍加变化，该算法即可能 不适用。经典的排序问题通常是假设所有的机器都是可以同时开始加工工件的， 但在实际生产中机器不定可以同时开工。机器具有准备时间的排序问题是经典 排序问题的推广，越来越引起研究者的兴趣。本文首先介绍了排序问题的定义、 表示方法和分类，以及对于机器具有准备时间的排序问题的研究现状，然后对机 器具有准备时间的排序问题进行了进一步的讨论。 首先介绍了有关机器具有准备时间的排序问题的一些研究成果，然后分别对 机器具有准备时间的同速机排序问题和机器具有准备时间的恒速机排序问题这 两大类问题进行了介绍和研究。在本文的第二章中，对第一类问题进行了讨论， 并且从两方面分别进行了研究。第一方面研究了任务具有链约束的排序问题，主 要讨论了任务的加工不允许中断，任务间具有链约束，机器具有准备时间的同速 机排序问题，目标函数是极小化最大完工时间，并将凹丁算法应用到了该问题 中得出了最优值的一个下界，利用具体例子对算法的应用做出解释，并且用实例 说明了该界是紧界。第二方面研究了关于4 。算法和它的界，主要讨论了任务的 加工不可中断，机器具有准备时间的同速机排序问题，目标函数是极小化最大完 工时间，将一。算法应用到本问题中得出了一个界，并用数值例子做了说明，但 此界不是紧的，因此，有待于进一步研究。在本文的第三章中，对第二类问题进 行了讨论，主要讨论了任务的加工不可中断，机器具有准备时间的恒速机排序问 题，目标函数是极小化最大完工时间，对一种特殊情况，给出了一个l p t 算法 的界，并用数值例子做出了说明。 关键词：排序，准备时间，界，链，最大完工时间 s c h e d u l i n gp r o b l e mw i t hn o n s i m u l t a n e o u s p r o c e s s o ra v a i l a b l et i m e a b s t r a c t s c h e d u l i n gp r o b l e mi sa ni m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m , h a v e a l 呐n o wb e , c o m et h es t r a t e g yl e a r n sar e s e a r c hv e r ya c t i v eo ft h eb r a n c h , i nt h e s t r a t e g yt h a tl e a r nt oh a v eap a r to fv i t a l i t y ag r e a tc h a r a c t e r i s t i c so ft h es c h e d u l i n g p r o b l e mi s ：t h em o d e li sn u l n l o u s ，b ea p p l i c a b l et os o m ec a l c u l a t ew a yo f o n em o d e l ， a sl o n g 嬲c h a n g et h ec o n d i t i o no fm o d e ls f i 曲u ym o r e t h a tc a l c u l a t ew a yn a m e l y o b s o l e s c e n t t h ec l a s s i c a ls c h e d u l i n gp r o b l e mu s u a l l yi ss u p p o s ea l lm a c h i n e sc a l l s t a r tp r o c e s sa j o bi nt h em e a n t i m e ，b u tt h em a c h i n ec a ns t a r tw o r k i nt h em e a n t i m e n o tn e c e s s a r i l yi na c t u a l l yt h ep r o d u c t i o n s c h e d u l i n gp r o b l e m 、v i t hn o n s i m u l t a n e o u s p r o c e s s o ra v a i l a b l et i m ei st h ee x p a n s i o no ft h ec l a s s i c a ls c h e d u l i n gp r o b l e ma n d m o r ea n dm o r ec a l l s et h er e s e a r c h e r s i n t e r e s t i nt h i sp a p e r , w ei n l r o d u c et h e d e f i n i t i o na n de x p r e s s i o na n dc l a s s i f i c a t i o no fs c h e d u l i n g , a n db a c k g r o u n do f s c h e d u l i n gp r o b l e m 埘t hn o n s i m u l t a n 0 0 u sp r o c e s s o ra v a i l a b l et i m e t h e ns c h e d u l i n g p r o b l e m 谢mn o n s i m u l t a n c o u sp r o c e s s o ra v a i l a b l et i m ec a r r y 0 1 1af u r t h 9 1 rd i s c u s s i o n w ef i r s ti n t r o d u c e ds o m er e s e a r c hr e s u l t so fs c h e d u l i n gp r o b l e m 、i t h n o n s i m u l t a n e o u sp r o c e s s o ra v a i l a b l et i m e ，t h e nw ei n t r o d u c ea n dr e s e a r c ht h e s c h e d u l i n gp r o b l e mw i t hn o n s i m u l t a n e o u si d e n t i c a lp r o c e s s o ra v a i l a b l et i m ea n d s c h e d u l i n gp r o b l e mw i t hn o n s i m u l t a n e o u su n i f o r mp r o c e s s o ra v a i l a b l et i m e i n c h a p t e r2 ，t h ef k r s tp r o b l e mi sd i s c u s s e d , a n dc a r r i e do nar e s e a r c hr e s p e c t i v e l yf r o m t h eb o t hs i d e o nt h eo n eh a n d ，w es t u d i e ds c h e d u l i n gp r o b l e mw i t hn o n s i m u l t a n e o u s p r o c e s s o ra v a i l a b l et i m eo fc h a i n sc o n s t r a i n t s ，m a i n l yd i s c u s s e dt h ep r o c e s so ft a s k c a n tb r e a ko f f , t h et a s kh a sc h a i n sc o n s 廿a i n t so fs c h e d u l i n gp r o b l e mw i t l l n o n s i m u l t a n e o u si d e n t i c a lp r o c e s s o ra v a i l a b l et i m e ，t h eo b j e c t i v ef u n c t i o ni st o m i n i m i z et h em a k c s p a n , a n da p p l i e dl p t a l g o r i t h mt ot h ep r o b l e m , t h e nw eg e ta o p t i m i z a t i o nd e s c e n db o u n d a r y ，w eu s ee x a m p l et oe x p l a i na l g o r i t h ma n de x p l a i n e d b o u n di st i g h t o nt h eo t h e rh a n d ，w es t u d i e dt h eb o u n do f a 砬a l g o r i t h m , w em a i n l y d i s c u s s e dt h ep r o c e s so ft a s k c a n tb r e a ko f f , s c h e d u l i n g p r o b l e m w i t h n o n s i m u l t a n e o u si d e n t i c a l p r o c e s s o ra v a i l a b l et i m e ，t h eo b j e c t i v e f u n c t i o ni st o m i n i m i z et h em a k e s p a n , a n da p p l i e d 如a l g o r i t h mt ot h i sp r o b l e m , t h e nw cg e tt h e b o u n do f a 廿a l g o r i t h m , t h e nw ei l l u s t r a t et h e mb ye x a m p l e s ，b u tt h i sb o u n di s n tt i g h t t h e r e f o r es t a ya tt h ef l l r t h e l r e s e a r c h i nc h a p t e r3 ，t h es e c o n dp r o b l e mi sd i s c u s s e d w em a i n l yd i s c u s s e dt h ep r o c e s s o ro ft a s k 啪tb r e a ko f f , s c h e d u l i n gp r o b l e mw i t h n o n s i m t d t a n e o u su n i f o h np r o c e s s o ra v a i l a b l et i m e ，t h eo b j e c t i v ef u n c t i o ni st o m i n i m i z et h em a k e s p a n w ed i s c u s s e dt h ep a r t i c u l a rc a s e ，a n dw eg e tab o u n do f l p t a l g o r i t h ma b o u tp r o c e s s o rs p e e d , t h e nw e i l l u s t r a t et h e mb ye x a m p l e s k e y w o r d ：s c h e d u l i n g - r e a d yt i m e - b o u n d ，c h a i n s ，m a k e s p a n 机器具有准备时间的排序问题 第一章引言 排序( s c h e d u l i n g ) 问题也称调度问题，是一类重要的组合最优化问题。它 广泛的应用于管理科学、计算机科学和工程技术等很多领域，假若有几件事放在 眼前需要去做，人们便会比较轻重缓急排个工作顺序：假若要从事一件较为复杂 的工作，就需要安排一个顺序( 或时间表) 。加工零件需要排序、组装成品需要 排序、工程建筑需要排序、人员安排需要排序等等，排序问题是生活中一类带有 普遍性的问题。过去处理此类问题，大多采用两种方式：一种是根据以往经验， 必要时作些修改，另一种是事物并不复杂，作些考虑即可奏效，排序问题不成其 为一门学问。自从第二次世界大战以后，各种大型企业逐渐兴起：规模庞大，结 构复杂，计算不周即可造成重大损失；而且产品更新很快，新产品的生产、销售 等没有成法可资参考，此时各种新的组合优化问题便涌现出来，排序问题便是其 中之一。虽然排序学科只是2 0 世纪5 0 年代初期才开始形成，但在近5 0 年来得 到了广泛而深入的研究，现在已经成为运筹学研究的一个非常活跃的分支，是运 筹学中相当具有生命力的一部分。 一、排序问题的定义和描述 排序问题是一类重要的组合最优化问题。若干个工件要在一些机器上进行加 工，如何安排机器和工件，使得某些要求( 目标函数) 达到最优，这就是所谓排 序问题p - 4 。它是利用一些处理机( p r o c e s s o r ) 、机器( m a c h i n e ) 或资源( r e s o u r c e ) ， 最优的完成一批给定的任务( t a s k ) 或作业( j o b ) 。在执行这些任务或作业时需 要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、 资源对加工时间的影响等。最优的完成指的是使目标函数达到最小，而目标函数 通常是对加工时间的长短、机器的利用率的描述。在排序问题中，机器的数量和 种类，任务或作业的顺序、到达时间、完工限制，资源的种类和性能等情况是错 综复杂的，很难用精确的数学描述给出一般的排序定义。在本文中，我们用如下 方式来描述排序问题：给定h 个任务的任务集r = 五，正，瓦 和m 台机器的机器 集p = 侣，最，p 册) 。排序问题指的是在一定条件下，为了完成各项任务，把p 中的机器分配给r 中的任务，使目标函数达到最优。 排序问题基本上由机器的数量、种类与环境，以及任务或作业的性质和目标 函数所组成1 5 - z o l 。只有一个机器的排序问题称为单机( s i n g l ep r o c e s s o r , s i n g l e m a c h i n e ) 排序问题，否则称为多机排序问题。在多机排序问题中，如果所有的 机器都具有相同的功能，称它们为同类机或平行机( p a r a l l e lp r o c e s s o r s ) 。 机器具有准备时闯的排序问题 同类机按处理速度又分为三种类型：如果所有的机器都具有相同的速度，称 之为同速机( i d e n t i c a lp r o c e s s o r s ) 如果机器速度不同，但每个机器的速度都是 常数，不依赖被加工的任务，称它们为恒速机( u n i f o r mp r o c 冶s s o l - s ) ：如果机器 的速度依赖被加工的任务，它们被称为变速机( u n r e l a t e dp l o c 君s s o r $ ) 。 多机排序问题又可以分为同顺序作业或流水作业( f l o ws h o p ) ，异顺序作业 ( j o bs h o p ) 和自由顺序作业或开放作业( o p e ns h o p ) 。 排序问题中的约束条件，主要指的是任务或作业的性质以及它们在加工过程 中的要求和限制。下面的数据描述了任务的一些性质： 任务的加工时间向晕是乃= 和i j , p 2 j p 町) ，其中p 是任务乃在机器p 上 所需要的加工时间。对同速机有p 。= p j , f - 1 ，2 ，m ，对恒速机有 p f = p ，i b j ，f = 1 , 2 ，m 。其中p ，是标准的加工时间( 一般是速度最慢的机器的 加工时间) ，b j 是机器只的速度因子。 到达时间( a r r i v a lt i m e ) 或就绪时问a ，是任务已经准备好可以被加工的时 间。如果所有的任务的就绪时间相同，取a ，= 0 ，j = 1 , 2 ，行。 工期( d u e d a t e ) d ，表示对任务r 限定的完工时间。如果不按期完工，应受 到定的惩罚。绝对不允许延误的工期称为截止期限( d e a d l i n e ) 。 优先因子w 是一个权，它表示任务r 相对于其他任务的重要程度。 任务被加工时的一个重要约束是可中断的( p r e e m p t i v e ) 或不可中断 ( n o n p r e e m p t i v e ) 。如果排序问题中，每一个任务在加工时的任一时刻都可暂停 加工，加工该任务的机器可去加工任何其他任务，以后可在任何时刻在任意机器 上重新继续加工，这种排序问题称之为可中断排序。任何任务都不允许中断的排 序问题称为不可中断排序。 加工任务时的另一重要限制是任务之间的优先约束( p r e c e d e n c ec o n s t r a i n t s ) 。 在优先约束中有三种重要的特殊情况：如果每个任务最多有一个先驱和一个后 继，优先约束图称为链( c h a i n s ) 。如果每个任务最多有一个后继，优先约束图称 为入树( i n t r e e ) 。如果每个任务最多有一个先驱，优先约束图称为出树( o u t t r e e ) 。 我们用c = q ，c 2 ，g ) 表示任务的完工时间( c o m p l e t i o nt i m e ) ，要极小化 的目标函数总是完工时间c ，的函数。在排序问题中，目标函数主要有下面几种： c 。：最大完工时间 y c ，：总完工时间 y w c ：加权总完工时间 工。：最大延误时间 y ，：总误工时间 f w ，t j ：加权总误工时间 2 机器具有准备时间的排序问题 u ：总误工数， _ u j ：加权总误工数等 排序问题的三参数表示法 机器、任务或作业和目标函数三要素组成了排序问题。机器的数量、类型和 环境有近十种情况，任务或作业和资源约束条件更是错综复杂，再加上度量不同 指标的目标函数，形成了种类繁多的排序类型【4 】。我们用c n - a h a m 等人首先使用 的三元组来描述排序问题的类型，这样能大大简化排序问题的表示。 三元组记号由三个域组成：口i p l y 。本文所讨论的排序问题都是用口旧，三 参数表示法来描述的。下面介绍的就是目前国际上使用的口i 剧y 三参数表示法。 1 参数a = q 口：描述机器的情况。参数e 庐，p ，q ，r ，0 ，f ，以描述机器的 类型： 矿( 矿可以省略) 表示单台机器 p 表示同型号机器( 同速机) q 表示同类型机器( 恒速机) 盅表示不同类型机器( 变速机) d 表示自由作业机器( 开放作业) ，表示流水作业机器( 刚顿序作业) ，表示有序作业机器( 异顺序作业) 参数口： 矽，k ) 反映机器的数目：( 妒可以省略) 表示机器的数目不指定， 可以是任意整数。 2 参数p 表示工件或工件的性质、加工要求和限制，资源的种类、数量和 对加工的影响等约束条件，它可以包含很多项，可能的项主要有： 口，表示工件有不同的准备时间或就绪时间； j ，表示在工件丁，之前的安装时间( s e t u pt i m e ) ； d ，表示工件有不同的完工时间限制，即工期； p r m p 表示允许中断抢先n i ： p r e c 、c h a i n s 、仕e e 表示工件的相关性：p r e c 表示一般优先约束，c h a i l l 5 表示优先 关系是链状的，仃c e 表示优先关系是树状的。 m v t ( n o w r i t ) 指被加工的工件不允许在两个相邻的机器之间等待。 随着排序问题的不断发展，的内容也在不断的发展变化，如在线问题、成 力嘭 v i ， f c l q ，l 机器具有准备时间的排序问题 组问题以及本文主要讨论的工件的加工依赖于工件的准备时间的排序问题等等。 3 参数，表示目标函数，排序的目标函数是一个一维实数。通常是考虑所 谓的正则( r e g u l a r ) 目标。 同速机排序问题的研究现状 随着现代工业的发展，经典的排序模型已被突破，新的模型层出不穷，吸引 了越来越多的理论工作者和实际工作者【1 l 1 1 。可控排序、多目标函数、成组分批 排序、同时加工排序、准时排序和窗时排序、资源受限排序、随机排序、模糊排 序、应用排序等等，本文所研究的机器具有准备时间的排序问题就是一种新型排 序。 排序问题是一类重要的组合最优化问题，排序问题的一大特点是：模型繁多， 适用于某一模型的算法，只要将模型的条件稍加变化，该算法即可能不适用。经 典的排序问胚通常是假设所有的机器都是可以同时开始加工工件的，但在实际生 产中机器不一定可以同时开工有的机器可能正在加工另外一个排序问题的工 件，有的机器加工前可能还要做清洗等准备工作，这时机器就不能立即开始加工。 我们把这种机器称为不能同时开工的机器，或称为是需要准备时间( 就绪时间) 的机器。本文讨论机器不是可以同时开始加工工件的排序问题，简称为机器具有 准备时间的排序。机器具有准备时间的排序问题是经典排序问题的推广，越来越 引起研究者的兴趣m l 。李忠义( 】7 1 首先提出和研究了这种排序问题。李忠义、何 勇和唐国春f j q 发现这种排序问题有可能存在不起作用( i n a c t i v e ) 的机器，这是 由于机器的准备时间太迟，以至于来不及加工工件。在分析算法的性能时要把这 种不起作用的机器区分开来。本文以工件的完工时间为目标函数，使最大完工时 间c 一为最小。这个目标函数是力求使各台机器结束加工的时间尽可能接近，从 而提高机器的利用效率【i 。1 ，因而具有重要的现实意义。 如果所有机器的准备时间口o ( i = 1 , 2 ，肌) 都相同( 等价于准备时间都等 于零，也可以称为不需要准备时间的机器) ，那么问题p m ，口。i ic 。和跏，口川c o 就成为经典的排序问题p m0 c 。和劬c 皿“。由于后面的两个问题是n p 困难 的岬1 ，所以问题砌，口，l l c 。和跏，q0 c 。也是胛困难的，因此，寻找性能较 好的近似算法就成为研究机器具有准备时间的排序问题的重点。 对于排序问题中的几种近似算法的界已经有了很多结果。 对于经典的排序问题p 圳i c 二，g r a h a m 给出了关于上s 算法1 2 1 】的一个界为 芒器= 2 _ 1 肌，g r a h 锄还给出了关于凹r 算法瞄1 的一个界为 4 机器具有准备时间的排序问题 端= 詈一磊1 。在船算法的基础上，k n u 血和日e 胁锄提出了厶1 算 法， 在此之后有了关于a 。算法的一个界纠为： 掣s 1 + m a x c 二 1一三l一再1m “2 1 + 毛+ ! 1 + k t ，七= 川毛+ 屯 其中c o ( 岱) 表示的是应用l s 算法得到的时间表长，c 。( 凹丁) 表示的是应用 “7 算法得到的时间表长，c o ( 以) 表示的是应用如算法得到的时间表长， c 一( 0 p r ) 表示的是排序的最优时间表长。 珂于硼l 器具硐准备町1 日j 阴诽厅l 叫咫，孕思义百无强出相计冗j 运一口j 题，开 肋凹r 算法运用到问题帆忆中，得到岩器吾一击。李忠义还 出t m l p r 算法，得到篇s 詈。后来，李忠义、何勇和唐国春发现 这种排序问题有可能存在不起作用的机器，这是由于机器的准备时间太迟，以 至于来不及加工工件。因此，对上面的结论加以改进，得到了 兽器争丽1 ，其中棚不起作用的机器，在这里还得到了最优时 mh 口，+ 罗p 。 间表长为( 卯乃2 型_ m 一丘 。对于问题q m ，a 0c 麒， 有 丽c 一( l p t ) 绺南一：学一 有2 台恒速机具有准备时间，任务加工不可中断的情况，给出了一个与机器加工 速度有关的凹7 算法的界。如果机器只的加工速度为1 ，机器最的加工速度为 螂 1 ) ，对于问黝口h ，有岩器等，其中机器只的准备时间l 【l ，r ， o 机器具有准备时间的排序问题 为a ，( i = 1 , 2 ) 。 四、本文工作 在本文里，我们考虑这样的问题：机器具有准备时间的排序问题，以工件的 完工时间为目标函数，使工件的最大完工时间为最小。本文主要以同速机具有准 备时间的排序问题和恒速机具有准备时间的排序问题为主要研究对象加以研究， 目标函数为极小化最大完工时间。机器具有相同开始加工时间的排序问题已是 n p 一难问题，如果机器具有准备时间，则问题更为复杂。在第二章我们将要考 虑机器是同速机的具有准备时间的排序问题。其中从两个方面来讨论：首先是任 务具有链约束的机器具有准备时间的同速机排序问题。在这里，本文的主要工作 是将机器具有相同开始加工时间的排序问题转化为机器具有准备时间的排序问 题。接下来研究了p m ，a 0c 。问题的彳。算法的界，这里本文的主要工作是将问 题p mi lc 。的结论应用到问题p m ，a zi lc 。中，结果结论仍然成立。在第三章我 们将要考虑机器是恒速机的具有准备时间的排序问题。在这里主要研究了对于问 题q m ，a 1 i c 一( m 2 ) 所给出的一个与机器加工速度有关的工p r 算法的界。在这 一章中，本文的主要工作是将问题q 2 , qi f c 。转化为有坍台恒速机的具有准备时 间的排序问题。 6 机器具有准备时间的排序问题 第二章机器具有准备时间的同速机排序问题 一、问题p m ，a si c h a i n s i c 。 ( 一) 、引言 这里讨论任务的加工不允许中断，任务间具有链约束，机器具有准备时间的 同速机排序问题，目标函数是极小化最大完工时间。将凹r 算法应用到该问题 中得出了最优值的一个下界，并得到了一个界，利用具体例子对算法的应用做出 解释，并用实例说明了该界是紧界。这里所涉及的算法结论虽然不能直接得到最 优排序方案，但可减少枚举算法和分枝定界的计算量，较快得到最优排序方案。 对于同速机排序问题，如果目标函数是最大完工时间，即使任务间不存在优先约 束，问题也是p 一难的1 2 4 1 ，常用的求解方法是启发式算法。当任务间存在优先 约束时，即使优先约束是最简单的链形约束，机器具有准备时间的排序问题也是 n p 一难的。因此，寻找性能较好的近似算法就成为研究任务具有链约束的机器 具有准备时间的同速机排序问题的重点。 ( - - ) 、模型的一般描述 首先给出凹丁算法。 l p t 算法： 1 ) 对所有的任务按加工时间不增的顺序排列( 列表) ， p ，p ，+ l ( ，= 1 , 2 ，n 一1 ) a 2 ) 依次从列表中取出任务，在当前时刻该任务排在哪个机器上完工时间早， 就把该任务排在哪个机器上加工。如果有多个机器的完工时间相同，则安排 到下标小的机器上加工，即：设任务l 在当前时刻排在机器只上的完工时间 为c j ( f = l ，2 ，m ，= 1 ，2 ，砷。若c , j = m i n c # 1 f = 1 , 2 ，m ) ，则把任务l 安排 到机器p 上加工。 下面给出模型的一般描述： 设有 n 台机器，机器集记为p = 仍，e 2 ，只) ，n 个任务的任务集记为 t = 五，r 2 ，l ) ，机器毋的准备时间记为口。0 ( f - 1 ，2 ，m ) ，任务一的加工时 间为p ，0 u = 1 , 2 ，r ) ，任务加工不可中断，任务间具有链形优先约束，加工 时链不可中断，即同一个链的任务必须连续加工，目标函数是极小化最大完工时 7 机器具有准各时阀盼徘序闯题 同。该问题用三参数表不法口】记为： p m ，qi c h a i n s lc 。 ( 1 ) 问题( 1 ) 是 俨一难的，不存在多项式算法。求解问题p 圳ic 。的常用方法是 工s ( l i s ts c h e d u l i n g ) 算法和卯r ( l o n g e s tp r o c e s s i n gt i m ef i r s t ) 算法。 李忠义田把凹r 算法运用到问题砌，口。l l c o ，本文又将凹r 算法运用到 p m ，qlc h a i n sc 。，得到一些结论。 ( 三) 、l p t 算法 为了讨论方便，下面设n 个任务形成k 个平行链： 三i ：互l 专互2 寸一互q ， 岛：瓦一易哼辛五 ， k ：瓦l 斗瓦2 _ _ k 第，个链含有哪个任务，n ，= n , l = l ，2 ，k 。任务毛的加t 时间为 f 。i p f ，f = 1 ，2 ，七；，= 1 ，2 ，刀，。第? 个链工，的加工时间记为p t = 艺既，= 1 , 2 ，k 。 - l 不妨假设m 台机器是以准备时间非减的次序编号矾s a 2 a m ；因为我 们所研究的问题是加工时链不可中断，所以我们将同一个链的任务看成一个整体 任务加工，问题就转化成有m 台机器，k 个任务的机器具有准备时间的排序问题， k 个工件是以l p t 序编号，即按加工时间非增的次序排列工件， p 。p 22 p 。，当有机器可以开始加工或有机器结束前面工件的加工要出现 空闲时，就把排在前面的还需要加工的工件安排到这台机器上加工。 1mkn 引理2 1 对于问题( 1 ) ，圭( 口f + 艺乃) 是最优值的下界， 即 c 二既去( 善口- + 善善p 。) a 1 mi o 证明：问题p mo c 。的最优值c 二“有一个下界是去骞p ，那么把机器的准 机器具有准备时间的排序问题 备时间a j 看成加工时间为a 的特殊工件。这些工件的全体与原有的工件集组成一 个新的工件集，将这些工件分配到m 台不需要准备时间的同速机上加工，则问题 ( 1 ) 的一个最优值下界就转化成p mi ic 一的一个最优值下界。 即 c 二去( 善q + 善善乃) 1t几 证毕。 定理2 1 对于问题( 1 ) ，用c 二和c 二分别表示由l p t 算法得到的目标函 数值和问题的最优值，则苦茎三一石1 。 证明：用工表示运用l p t 算法时最后完工的工件所在的链。此链的加工时 间为p ，我们分别证明当办s 1 2 c 一 ，有乏三一丽1 ；当砟 1 2 c 一 ， 由凹r 算法得到的排序就是最优排序。用表示链的开始加工时间。由卯r 算法可知链工，被安排到最先出现空闲的机器上加工。在三，开始加工之前，没有 机器出现空闲，因而由引理2 1 可得： r - i t |n | n rn ， 口f + 艺p p ( q + 艺p f ) 一艺p 口肌c 二一p d s ，s 旦型 mm，纷 吒一翌吒也 ( 1 ) 若b 互1 c 一，则有： c 蚰= b c l 一告帽= 矗+ ( 1 一去) 耶矗+ ( 1 一一1 j 1l 眦m坍埘z = c 三一寺丘 ( 2 ) 若刃 1 2 c 一 ，则在最优排序中没有机器加工两个或两个以上编号小于等 于r 的链，否则，最优值将大于c l ，因而，册。因为n = 1c 。，所以至少 有，台机器的准备时间小于等于昙c 二“，否则最优值将大于c 二。由于 9 机器具有准备时间的排序问题 口口“1 ，f = 1 , 2 ，m - i ，所以口j ；c 二“o ，) 。 由于至少有r 条链的加工时间大于圭c 二n ，并且a i 4 ，所以c 二瓤 口，+ p ，= c 。 因而当n 昙c 二“时，由上，r 算法得到的排序就是最优排序，定理得证。 l p t 算法的时间复杂性为o ( k l o g k ) + o ( k l o g m ) ，是多项式时间的算法。下 面给出一个数值例子，此实例说明三一亡：黾l p t 算法的紧界。 z z m 例2 1 考虑问题尸4 ，a 。ic h a i n s l c 。，其中m = 4 ，h = 1 0 ，工件的加工时间分 别为：p l = 1 ，p 2 = 1 ，p ，= 2 ，p 4 = 1 ，p 5 = 3 ，p 6 = 2 ，p 7 = 3 ，p s = 1 ，p 9 = 3 ，p 1 0 = 1 。 工件之间满足下面的链约束关系： 五寸正斗瓦， 五一兀寸疋专瓦， 写一 由算法所得的时间表长c 。= 1 1 ，最优排法c 二| x = 8 ， n 一8 = 上拥 一 立2 m 玺巳 以 所 机器具有准备时间的排序问题 在此最优排法中，机器b 的准备时间比较长，对这个排法来讲不加工任何 工件，这种机器称为对于这个排法是不起作用的( i n a c t i v e ) ：反之，如果机器对 于某一个排法至少加工一个工件，那么这台机器称为对这个排法是起作用的 ( a c t i v e ) 。 二、问题p m ，a l0 c 一 ( 一) 、引言 对于机器是同速机的排序问题砌0 c 。，文献1 9 1 证明了此问题是p 一难 的。对于这个问题，k n u t h 和k l e i t m a n 提出了一h 近似算法。g r a h a m 已经证明了 机器没有准备时间的关于一。算法的界是1 + ，并且当keo ( m o d m ) 2 1 1 时， 此界是紧的。文献嘲给出了机器没有准备时间的关于4 。算法的另外一个界是 1 + m a x l一土1一再1m ，- “2 1 + 毛+ 去1 岫 ，其中k = 册+ k 2 ，并且证明了此界是紧的。 本文讨论了机器具有准备时间的关于4 。算法的界。 先给出模型的一般描述： 设有m 台机器，机器集记为p = 只，b ，己) ，押个任务的任务集记为 t = 五，疋，l ，机器只的准备时间记为q 0 ( j = 1 , 2 ，聊) ，任务l 的加工时 间为p ，0u = 1 , 2 ，”) ，目标函数是极小化最大完工时间。用三参数表示法问 题可记为： p m ，a 0 c 一 ( 二) 、以算法 g r a h a m 提出了关于问题砌0 c 。的l s 近似算法，文献中给出了船算法 立啮 机器具有准备时间的排序问题 的界为2 一一1 。 m 岱算法： 1 ) 把工件任意排成一个列表工。 2 ) 当有机器可以开始加工工件时，就从三中依次取可以加工的工件排在这台 机器上加工。 如果工件列表是按工件加工时间非增的顺序排列，则为凹r 算法，g r a h a m | 2 1 】 已经证出它的界是昙一圭。对于机器具有准备时间的排序问题，李忠义n 7 1 首先 jj 州 提出和研究了它，并且把凹r 算法运用到问题p 埘，口0c 。中，得到问题的界是 3l 22 m 在船算法基础上，k i n 曲和k l e i u n a n 提出了另外一个近似算法，一算法。 厶算法： 1 ) 对于一个整数| 0 ，选取七个加工时间最长的工件。 2 ) 把这k 个工件按照最优排法排在m 台机器上加工。 3 ) 剩余的疗一k 个工件按照l s 算法排在掰台机器上加工。 l 一! 硼了栅贿裥脯舡帅瞅坻靴胁是硇 文献1 在此基础上作了改进，证明了机器具有相同开始加工时间的关于爿。算法 的一个界是1 + m a 】【 ，其中t = m k l + 如。 下面研究把4 。算法应用于问题砌，口i lc 。中去，所得到的界。 为了简便，下文中我们把k 个加工时间较长的工件称为大工件。 令c 一( s ) 是应用a t , 算法得到的排序的最大完工时间，c 二表示排序的最优 完工时间，c 0 ( 墨) 表示把盂个大工件排在所台机器上加工的最优完工时问。 令大工件的个数七= 肌岛+ k 2 ( 七，是一个非负整数，k ：是一个正整数) 。为了 以后证明方便，在这里我们引入两个变量矿和工，并且令： 1 2 喜 立屺 机器具有准备时间的排序问题 p = 巴孥p ， 善= c 。( s ) 一p ， 贝0 有c 。( s ) = x + p 。 ( 2 ) 我们假设工件r ，是最后完工的工件，对于a 算法，因为当有机器空闲时， 就从列表工中依次取可以加工的工件排在这台空闲机器上加工。所以在 c 。( s ) 一p ，之前无机器空闲。 下面对l 按两种情况分别进行讨论，得到c 二所需要满足的条件，这个条件 将在以后的证明过程中用到。 ( a ) 如果l 属于大工件，则有c 皿( s ) = c o ( 墨) = c 二a ( b ) 如果一不属于大工件，即j k + l ，p ，s p ， $ l j 有x = c 一( 回一p c 。( s ) 一p ，因为前面提到在c 二( s ) 一p ，之前无机 器空闲，所以在x 之前也无机器空闲， 即有 则 a + q m x + p ， ，- li _ l a + q c 二生 竺旦：h 。( 3 ) mm 由于定理证明过程较长，本文将定理的内容分成三个小的引理分别进行证 明。若三个引理结论都成立，则定理的结论也就随之成立。这里将定理分成三个 引理的依据是按时间x 的取值来划分的。 分别当x ( 毛+ 1 ) p ，x ( 毛+ 1 - m 兰i ) ，和心+ 1 一m 当i ) p x ( 七+ 1 ) p 一尤，一以 时，如果引理结论都成立，则得出无论z 为何值，结论均成立，因此定理的结论 成立。 z 删有警外蔫 证明：根据( 2 ) 和( 3 ) ，即c 。( s ) = x + p 和c 二缸x + 告，则有： 塑 巫：量：圭：竺 矗。z + 工+ 蔓屿 机器具有准各时间的排序问题 l 一11 一! 1 + 旦i _ p = 1 + 旦i _ 。 ( 毛+ d p + 卫 1 + 毛+ i l m ，玎 1 一上 骢z _ 姗锄小南mp 删有警外昔 一石， o 一一 l + 最 证明：对于- ：g t 件的个数k = m k j + 七2 ，当屯0 时，则至少有一台机器膨，加 i ( 七l + i ) 个大i 件i ( 1 s i s k ) 。因为p j p + ( 1 i k ) ， 贝0 有c 二c m ( s ) 2 ( k l + 1 ) p + 口( 毛+ 1 ) p + q 。 根据( 2 ) c z ( s ) = x + p ，则有： 垡翌s 三旦：( k i + 1 - m - - - 芝2 ) p * + p c 二。( 七1 + 1 ) p + 口，。( 毛+ 1 ) p ：竺竺：垂! 。+ 生1 m mi 。 一k ，一耙， = = - - - - - = 一= = - - - 一 ( + 1 ) p 1 + 毛 引理2 4 如果( 毛+ i - 二- ) p x ( k l + 1 ) p ，则有： ，玎一以 ! 掣1 + 咄 c 二一 一m 一去， 2 l + 向+ 土l + k 证明：我们可以假设前m 台机器，每台机器至少加工k j + 1 个大工件，余下 的m m 。台机器，每台至多加工k 个大工件。 首先我们来看证明过程中所需要用到的三个结论： ( a ) 一定有一台机器至少加工t + 2 个大工件。 否则在前码台机器上共加工m i ( k l + 1 ) 个大工件， 因此 k s 所1 ( 女l + 1 ) + ( i n 一所1 ) k z = m k l + m i m + t 2 ，矛盾。所以有一台机器吖，至 少加工k l + 2 个大工件，则有c 二旺( 七l + 2 ) p + 4 ，。 ( b ) 可以判断m ，k ，。 1 4 机器具有准备时间的排序问题 若m i 屯，因为c 二( k l + 2 ) p + 口，所以有： 里掣s 一三墨 x + p 这与( 2 ) 式矛盾，因此乃不在已经加工完毛+ 1 个大工件的机器上加工。 根据( a ) 、( b ) 、( c ) 三个结论，有： p ，+ 口i ( m - m 1 ) 工+ p + m l ( k l + 1 ) p ，+ 口 气生i l ( m - m i ) x + p + m l ( k + 1 ) p + 宝口 ji：l m m x +