（运筹学与控制论专业论文）m台同类机覆盖问题的lpt算法.pdf

摘要 摘要 本文主要研究若干种特殊情形同类机排序问题，目标函数是最大化机器最小 完工时间，这样的问题又常被称为机器覆盖问题。本文主要研究的是所有机器中 只有一台机器的加工速度与其他机器加工速度不同这一特殊情形。所研究的算法 是l p t 算法，该算法首先将所有工件按加工时间大小从大到小排列，然后将工 件安排在当前负载最小的机器上加工。全文共分为三章： 第一章是绪论部分，主要介绍相关排序问题，近似算法和竞争比分析等基本 概念。 第二章主要考虑了机器加工速度分别为1 ，1 ，s 以及1 ，s ，s ( s 1 ) 的三台 机排序问题，给出了l p t 算法的参数界以及s 取一定范围时的参数紧界，并给 出了上述两个问题的常数紧界。 第三章主要研究机器加工速度为1 ，1 ，1 ，s 的m 台同类机覆盖问题，证明了当 m 4 时，s 取一定范围时的l p t 算法参数紧界。 关键词：同类机排序，离线，最坏情况界 a b s t r a c t t h i sp a p e rm a i n l ys t u d i e su n i f o r mm a c h i n es c h e d u l i n gp r o b l e m s ，a n dt h e o b j e c t i v ef u n c t i o ni st om a x i m i z et h em i n i m u mf i n i s h i n gt i m e t h i sp r o b l e mc a na l s o b ec a l l e dm a c h i n ec o v e r i n gp r o b l e m i nt h i sp a p e rw em a i n l yf o c u s0 nt h i sk i n do f p r o b l e mt h a to n l yo n eo ft h e s em a c h i n e sh a sp r o c e s s i n gs p e e dw h i c h i sd i f f e r e n tf r o m t h eo t h e r s t h ea l g o r i t h mt h a tw es t u d yi st h ef a m o u so f fl i n ea l g o r i t h ml p t t h i s a l g o r i t h mf i r s ts o r ta l lt h ej o b s 晰t 1 1n o ni n c r e a s i n gj o bs i z e ，t h e np r o c e s st h ej o b so n e b yo n e o nt h em a c h i n et l l a tc u r r e n t l yh a v em i n i m u ml o a d i nc h a p t e r1 ，w ef i r s ti n t r o d u c eb a s i cn o t i o n so fs c h e d u l i n gp r o b l e m ，a p p r o x i m a t i o n a l g o r i t h m sa n dc o m p e t i t i v ea n a l y s i s i n c h a p t e r2 , w em a i n l ys t u d y3u n i f o r mm a c h i n e ss c h e d u l i n gp r o b l e m sw i t h p r o c e s s i n gs p e e d so f1 ，l ，sa n d1 ，s ，s 埘t l ls l ，a n dw ep r o v et h el p ta l g o r i t h m s p a r a m e t r i cw o r s tc a s er a t i oa n dg i v et h et i g h tb o u n d 、航t hsi ns o m er a n g e f u r t h e r m o r e ，w eh a v et h ec o n s t a n tt i g h tb o u n d so f b o t hp r o b l e m s i nc h a p t e r3 ，w ei n v e s t i g a t es c h e d u l i n gp r o b l e m s 埘t hmu n i f o r mm a c h i n e s ，w h e r ew e h a v ep r o c e s s i n gs p e e d so f1 ，1 ，s ( s 1 ) w r ep r o v et h a tt h i sp r o b l e mt h et i g h tb o u n d w i t hsi ns o m er a n g ew h e nm 4 k e y w o r d s ：u n i f o r mm a c h i n es c h e d u l i n g ，o f fl i n e ，w o r s tc a s eb o u n d s i i 历台同类机覆盖问题的l p t 算法 第一章绪论 1 1 排序问题介绍 排序( s c h e d u l i n g ) 问题是一类重要的组合优化问题，在许多优化问题模型 中都可以找到它的原型。问题产生的背景是机器制造，后来被广泛应用于计算机 科学，运输调度，生产管理等领域。从普通的生产部门的计划安排、人员调度， 学校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和 算法，排序问题的研究已经成为运筹学方向的一个非常活跃的分支。近年来排序 问题得到了运筹学界，计算机科学界，管理学界和工程学界的广泛关注，排序问 题的研究在近几十年内正被越来越多的学者深入地研究，在国内外也产生了大量 的相关文献 1 7 。 排序事实上就是利用一些处理器( p r o c e s s o r ) 、机器( m a c h i n e ) 或者资源 ( r e s o u r c e ) ，最优地完成一批给定的任务或者作业。习惯的，我们把要完成的任 务叫做工件( j o b ) ，i 件集用 以，以，以) 来表示，把要完成的任务所需资源叫 做机器( m a c h i n e ) ，相对应的机器集可用 m ，m ：，帆 来表示，工件以的大小 用仍来表示。根据实际背景的不同，机器在执行任务或者加工工件过程中，可能 需要满足某些限制条件，比如任务的到用达时间、截止时间、加工顺序、资源对 加工时间的影响等。而所谓的最优地完成指的是使指定的目标函数达到最小，其 中目标函数也可以根据实际需求的不同而改变。 在排序问题中，处理器的数量和种类，任务或工件的限定条件、资源的种类 和性能等情况是错综复杂的，目前通常的文献都沿用g r a h a m 1 2 】中提出的 口i 少1 7 三参数表示一个具体的排序问题，其中口，和厂分别表示处理器、任 务、目标函数三个域的性质以及满足的条件，下面是它们具体的含义。 口域表示处理器的数量、类型和环境。只有一台机器的排序问题称为单机 ( s 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 s ) 和车间排序。平行机是指所有机器都有相同的 功能，可分为：所有机器对所有工件具有相同加工速度的同型机( i d e n t i c a l ) ，具 有不同加工速度但此速度不依赖于所加工工件的同类机( u n i f o r m ) 以及随所加 m 台同类机覆盖问题的u y r 算法 工工件而变的变速机( u n r e l a t e d ) ，可分别用p ，q ，r 来表示。车间排序也可分为 三类：每个工件以特定的相同加工次序在机器上加工的流水作业( f l o w s h o p ) ， 工件依次在机器上加工的次序是任意的自由作业( o p e ns h o p ) 以及每个工件以各 自的特定次序在机器上加工的有序作业( j o bs h o p ) 。本文主要考虑的是同类平行 机多机排序问题。 域表示任务或者工件的性质、加工要求和限制，资源的种类、数量和对加 工的影响等约束条件。它可以同时包含多项，常见的项有任务的加工过程可中断 ( p r e e m p t i v e ) 、在线加工( o n l i n e ) 、机器故障( b r e a k d o w n s ) 等等。在经典排 序问题中，我们常常根据排序者在排序时掌握信息的多少来把排序分成在线( o n l i n e ) 和离线( o f f l i n e ) 两类。在在线问题中，有两个基本假设：( 1 ) 工件的信息是 逐个释放的，即工件z + 。的信息只有在工件以，以，以被安排后才知道。( 2 ) 工 件加工次序不可改变，即一旦排序者将工件安排在某个机器上加工，在其后的任 何阶段不可改变。而对于离线问题，全部工件的信息都已知，排序者可以充分利 用这些信息来安排工件。本文研究的是离线问题。 7 域表示要优化的目标函数，包括最大完工时间( c m 。) 、最小完工时间 ( c m i 。) 、完工时间总和( q ) 、加权完工时间总和( q ) 等，即与所有 优化问题一样，问题总是在满足所有条件的可行解集合中寻找一个使得目标函数 尽可能小的解作为问题的一个最优解，本文主要研究的是目标函数为极大化最小 完工时间( q 。) 的问题，该问题又常被称为覆盖问题。 小台同类机覆盖问题的l p t 算法 1 2 近似算法和竞争比分析 对于一个具体问题可能会有不同的算法求解，我们希望寻找解问题的最有效 算法。通常都用算法执行的时间作为衡量算法有效的标准，也就是说把能最快得 到最终结果的算法称为最有效算法。而为了排除计算机速度和操作系统等因素， 一般又总是用算法中所含的基本运算( 加、减、乘、除、比较等) 次数表示算法 所用的时间。上个世纪7 0 年代建立起来的计算复杂性理论，使得p n p 的猜想 越来越为更多的人所接受，随之而来的问题是对于所谓n p 一难问题就不可能存 在多项式时间内找到最优解的算法。也就是说，随着问题规模的扩大，对这种 胛一难问题的每一个实例要用统一的算法找出最优解，从计算时间上来看是不 可能的。从而一个自然的想法是放弃对最优解的寻找，取而代之的是寻找某种性 能保证的可行解，称为近似解，以换取可接受的计算时间，这就是所谓的近似算 法( a p p r o x i m a t i o na l g o r i t h m ) 的思想。在经典的求解平行机排序问题中，离 线和在线问题的近似算法分别是l p t 算法 1 4 和l s 算法 1 3 。 如何衡量一个近似算法的好坏? 一个重要的标准就是把算法所得到的解与 最优解进行比较，看两者之间的差别有多大。离线近似算法的好坏一般用最坏情 况界( w o r s tc a s er a t i o ) 来衡量，下面给出确切定义。 定义1 2 1设彳是求解一个排序问题的离线近似算法。对于一个工件集合 矿，记c 一为算法得到的目标函数值，而c 代表离线问题的最优值。对于覆盖问 ，1 题，定义最坏情况界为髟= i n f r l i 寻，) 。 o 乙 由上可知，求解问题的算法时间复杂性和算法最坏情况界则衡量了一个算法 的好坏。如果一个离线算法的最坏情况界恰好存在实例达到算法界，则这个算法 界已经在某种意义上达到了最好，也就是通常所称的紧界。通常在设计出问题的 近似算法以后，首先要对算法界进行估计，然后判断所得的界是否是为紧，希望 所得算法界是紧界。 m 台同类机覆盖问题的l p t 算法 1 3 研究问题 本章主要研究了朋台同类机覆盖问题，目标函数是极大化机器最小完工时 间，该模型假设如下：有刀个彼此独立的工件，= 以，以，以 ，需要在聊台机 器m ，m 2 ，坂上加工，坞( = l ，2 ，肌) 的加工速度为，不失一般性可假设 岛是 - - s i n 1 。工件以的加工时间为b o = l ，2 ，甩) ，从而在机器呜上的加 工时间为易，i = 1 ，2 ，力，歹= 1 ，2 ，m 。我们用弓表示机器鸩上的所有加工工 件的大小之和，则弓0 表示机器鸠上的完工时间大小，j = l ，2 ，m ，则有目 标函数值彬= 嗍黔 所研究的算法是l p t 算法，该算法首先将所有工件按加工大小从大到小排 列，然后要求按照工件大小顺序依次到达，并将到达工件在当前负载最小的机器 上加工。即我们可得到工件大小顺序为a 仍见，算法依次将工件b 安排 在当前机器负载最小的机器上加工。工件加工时不允许中断，机器在有未安排加 i i 件时不允许空闲，工件一旦安排好后不允许以任何方式加以改变。 对于同类机排序问题，通常考虑两种类型的最坏情况界：一种是把问题的最 坏情况界都看作为机器速度而，是，的函数，称为参数界；另一种是考虑参数 界在任意s ，屯，取值时的极大值，称为常数界。本文将分别考虑问题的参数 界，常数界。 对于砌0 。问题，w o e g i n g e r 1 8 j 正g ) tl s 算法的最坏情况界为m ，其中 该算法是指将到达工件安排到当前负载最小的的机l l l 上；l ；i l ；i i 。d e u e r m e y e re ta 1 【7 】 证明了l p t 算法的最坏情况界不超过昙，c s i r i k e ta 1 【6 】进一步证明了l p t 算法 的紧界为竽等。陈思霞【3 】证明了对于跏0 问题，l s 算法的最坏情况界为 3 m l ” 0 。对于跏0 c m i 。问题，a z a r 和e p s t e i n 【l 】证明了l p t 算法的常数界为m ，上 述界是s l 时的最大值，x cs 的所有取值未必是紧的。对于q 2 0 c m i 。问题，c h e ne t 坍台同类机覆盖问题的l p t 算法 a 1 【4 】证明 l p t 算法的参数紧界。 跟本文相关的是目标函数为极小化最大机器完工时间的问题，对于这种问 题，l p t 和l s 算法的含义与上面是不同的，它们是将工件安排在最早完工的机 器上加工。对于研台同型机问题砌0 0 ，g 协锄【1 4 】证明了l p t 算法的紧界 为i 4 一_ 1 ， 1 3 i i e b 凋7l s 算法的界为2 一土。而对于跏0 0 问题，c h 0 和s a h n i 5 j3 mm ” 证明了对于机器加工速度不同的一般情况，l s 算法的最坏情况界为 ( 1 + j ) 2 ，m = 2 ，对于j ：而 ：屯：1 的特殊情形，l s 算法的常 1 1 + 4 2 m 一2 2m 3 数紧界为3 4 ( 朋+ 1 ) ( 研3 ) 。特殊的，x 4 f f ：a 3 1 l c e ，丑= s 2 = s 1 ，邑= 1 这种 情形，蔡圣义【2 】证明了l s 算法参数界为m i n 塞等，等) ，并证明了当s 3 时， l s 算法是参数最优算法。闵啸【1 6 】证明了当墨= s s 2 = 邑= 1 时，l s 算法的参数 i 丝1 2 时，l s 算、法是解娴题的参数最优算法。 对于q 2l i c 雠，e p s t e i ne ta 1 8 i i en y jtl s 算法的参数紧界为 1 + 5 s 是= 岛= = = l ，g o n z a l e ze ta 1 【1 l 】证明了l p t 的算法常数界为 曼+ 1 7 ) 4 in22。k。vacs【15】证明了对于qoc嗍，s：置是：岛：sm：1问2 i3 一1 ( 2 m ) m 2 。 叫一 1 题的l p t 算法紧界为( 1 + 3 ) 2 。 等孚 m 台同类机覆盖问题的l i t 算法 1 4 论文综述 这篇论文考虑的是机器加工速度不同的同类机排序问题，具体研究了几种特 殊情形的排序问题。第二章主要研究了两种情形：在机器速度为s = s l s 2 = s 3 = l 时，q 30 问题的三p 丁算法参数界为 ，- 等翔钲警时， 点龄半时 并证明当s 墅学时，算法界为紧界，并进一步可知该问题常数紧界为3 。 在机器加工速度为s = 岛= s 2 邑= 1 时，q 30 问题的p 丁算法参数界为 g ( s ) = _ 2 + i 3 s 当se ( 1 ，6 耐 1 + 2 s 一1 生当s ( 6 ，7 】时 3 + 6 s 、。1 二生当s e ( 7 ，佃) 时 s + 2 、7 7 证明明当s ( 7 ，佃) 时上述界为参数紧界，并进一步给出该问题常数紧界为2 。 第三章主要研究的是m ( m 4 ) 台同类机的一种特殊情形，其中机器加工速度 为s = 岛 s 2 = 邑= = = l ，o m l l c m 面问题的三尸丁算法界当s 聊沏一1 ) 时，该问 题可得参数紧界为。 s + ，行l m l l m 台同类机覆盖问题的l p t 算法 第二章三台同类机覆盖问题 2 1 j = 墨 s 2 = s 3 = 1 时l p t 的参数界 定理2 1 0 3 i l f m 问题，其中s = s i s 2 = s 3 = 1 时，三p 丁算法参数界为 们胁a x 黪刮篓2 s + 3 釉, 1 s 华 厂( s ) ，则 乙 c 胛 ，下面分三种情况讨论。lsj 情形1 c 胛= 五。 自( 1 籼 高，c 轰2 警坷鹕毋纠2 删c - 2 怕 即有 五+ 瓦2 + s 一而1 ( 2 ) 令研表示机器m 上最后个工件的大小，f l 了l p 丁算法孽质知互五，即有 研互一s 五 ( 3 ) m 台同类机覆盖问题的l p t 算法 子情况1 乏墨。 由( 2 ) 式得2 互五+ 五2 + s 一7 i 1 两，代入( 3 ) 以及由五 万1 两得 易兰小赤一志= 丝铲。 看工件p t 至u i x _ z 日u 秽l 器朋3 上全少有一个i 仟加工，则此工件先十所剑达。 由t - f ( s ) 娑，所以有 s+z 互易丝铲高， 这与巧 7 苦相矛盾。 若i 件乃到达之前机器心上没有工件加工，则研必为机器m 上最后一个 i 件，即有易= a ，否则易将被安排在心_ t , n i 。 此时如果机器鸠上有多于两个的工件加工，我们考虑鸠上最后一个i 件 b ，由机器鸠上有i 件先于只到达，从而a 五，同时由l p t 性质，五一只互， 即有五b + 五 2 1 3 而3 ，所以c 号导 等等 三，所灯半 华 s + 2 - - - - 壳) “) 若机器鸩上有多于两个工件加工，记最后一个工件为只，则类似的我们有 b 乃，互一只五，所以互= 乏一a + 忍2 五，结合厂( s ) 孳! 手 了，从而 五三五 三( 兰+ 1 一面b ) 万1 两，这与五 高相矛盾。 若机器m 2 _ i ：r 有i - 个工件加工，由凹r 算法知：互= 易。 此时若机器m 上只有a 一个工件加工，则互= a ，正= 岛，五 万1 两，与上面 类似可知c 主+ 1 一面丽1 7 j s + 万l ，这与( 5 ) 矛盾 情形2 c 胛= 互。 不妨假设互 五，若坞上多于两个工件，与情形1 类似得证。 若坞_ k r 有一个工件p 3 ，互扔见= 墨，与假设互 五相矛盾。 情形3 c l p t - = 亨 高。 子情形1 z 正 令b 表示机器鸩上最后一个工件，f l jl p t 算法知疋一仍 亨 志。 若鸠上有至少两个工件，则五一只易 7 b 亨，矛盾。从而机器m z 上只有 a 唯一一个工件加工，正= 耽。 此时若机器坞上只有p 3 一个工件加工，此时工件安排顺序为，工件 见，仇，p 。在机器m 上加工，工件仍在鸠上加工，工件办在鸠上加工。 令瓦= 鼽+ 岛+ + 岛， 由( 1 ) 知写+ p l 。互 1 + 兰一面希，可得 瓦 惫有 2 s ， 鱼鱼墨 鱼鱼墨 垃 l ，这与假设c ：1 相矛盾。 1 + s l + sl + s 若在最优排序中，5 1 2 1 ： p ；在m 上加工，而见在m 上加工，马不在m 上加 工，不妨假定此时见在坞上加工，令巧d 表示工件集 胁，a ，岛) 之中的工件 埘台同类机覆盖问题的l p t 算法 在最优排序中在m 上加工工件的大小之和，露2 表示工件集 只，见，岛) 之中 的工件在最优排序中在鸩上力h i i 件的大小之和，此时要使c = 1 ，则必有 露2 1 ，从而瓦瑟2 1 ，仍局= 互一磊 五一1 ，考虑最优排序中机器m 上的 目标值大小 c 旦翌2 型 鱼丝墨二翌2 互二! 鱼互二! 互二! 2 ( zs l 型_ _ 0 主苦得到，这与假设c = 1 相矛盾。 若在最优排序中，工件岛，岛在m 上加工，见不在m 上加工，同上可得结 论成立。 若在最优排序中，工件届，仍，见都在m 上加工，则由厂( s ) i 3 5 i 可得 只一p 1 一p 2 一见 c 上生一 2 ：墨 鱼一! 一兰 1 ，这与假设c ：1 相矛盾。 2 4 f ( s ) 2 4 若机器坞上有两个以上工件加工，令乃表示坞上最后一个工件的大小， i 扫l p t 算法性质知乃五一所 亨 7 b ，即有五= 马+ 互一乃 页1 万，机器坞上只有见一个工件加工，互= 见，而由 假定知乃= 见 乏仍，即岛 仍，这与见仍相矛盾。 综上可知，算法参数界得证。下面举例说明上述算法界在s 墅学时是 紧的。考虑工件集合 a = p 2 = 见= s ，p 4 = a = 3 ) ，凹丁算法将工件p 1 ，p 4 ，a 安 排在机器m 上加工，将工件仍，p 3 分别安排在机器鸠，m 3 上加工，此时有 c l p r ：s + 6 ，而最优排序是把工件a ，岛，岛安排在机器m 上加工，将工件风，见 分别安排在机器鸩，鸠上加工，此时有c = 3 ，我们有 奚：三：旦。_ 72 而2 赢。 _ 推论2 1 对q 3 l c 血问题，其中s = 岛 s 2 = 黾= l 时，三刀算法常数界为3 ，且界 为紧的。 证明：由定理2 1 的证明可知( s ) s 3 = 1 时l p t 的参数界 定理2 2 对q 3 i i 问题，当j = 墨= 8 2 s 3 = 1 时，三尸丁算法参数界为 如，= 一 筹，羔去) - 且当s ( 7 ，佃) 时上述界为参数紧界。 2 + 3 s 当s ( 1 ，6 耐 1 - i - 2 s 、7。 里生当s ( 6 ，7 】时 3 + 6 s 、7。 戋兰i s e ( 7 ，佃) 时 让明：令2 i ，7 j ，r 3 分别表不上仟刀上元毕町，秽l 器朋l ，朋2 ，朋3 上刀【k e z 仟阴大_ 、 之和，不失一般性，假定c ：1 ，则有c 凹r ：m i i l 互，墨，正、 。下面用反证法证 ls sj 明定理。若芸g ( s ) 不成立，即有导 g ( s ) ，c 胛 夏1 万，分三种情形讨 论如下。 情形1 c 脚= t 3 1 + 2 s i 1 五，即有 执 一1 怕一j 一一上：堡型! 坐! 二! ! 料芝怕一丽一孬2 秀蒿_ 历台同类机覆盖问题的l p t 算法 若工件研到达之前机器鸠上至少有一个工件加工，由于此工件先于功到 达，贝| j 由g ( 啦筹筹硎脯五研紫 嘉，这与假 设五 主五相矛盾。 若工件p j 到达之前机器鸭上没有i 件加工，则m 上最多只有一个i 件加 工，即有a = a 。此时若机器鸠上g k 有一个工件加工，即有瓦= p 2 ，此时易 得c i ，这与假设c = 1 相才盾。看机器肘2 上有两个或两个以上工件加工，b 表示机器鸠上最后一个工件，由三p 丁算法性质得墨乃， 易五一b 如互 南，即有 互= 易+ 互一p j 见峒刊州乃刊高+ 去= 嘉， 同时又有五 詈署，无论如何安排工件， g l s ， l +s + l s + l i 1 都必有c 冬丛 型啦 1 ，这与假设c ：1 相矛盾。 l + s1 + s 子情形2 互 丽1 ，这 与假设五 - - p 见= b = 互，与假设石 而s + 4 可得 乃母弦一赤一去= 丝铲 去。 若机器鸠上至少有两个以上工件加i ，则有五一乃乃 夏l 万，故按照l p t 算法知，马应在m 上加工，矛盾。从而机器鸠上只有一个工件加工，乃= 岛。 而由凹丁算法知，机器鸩上至少有一个工件仍先于见达到，从而有 互段岛= 互丢+ s 一赤。 由于g ( s ) 言等 而3 s ，所以有譬去+ 1 一南 主万，故而机器鸩上也 只有仍一个工件加工，五= 觑，所以可得 这与假设互 五。 巧a 见= 互1 2 + j 一赤 高， 与子情形2 相类似，我们有互 圭+ j 一赤，易为鸠上最后一个工件，由 三p 丁性质得互一易石，b 五一互j 1 + s 一赤一言= i 1 + s 一去。 若机器鸩上有3 个或以上工件加工，则易丢( 正一只) s 丢石，互 l + 2 s - t 一乃 l + 2 j 一言s 一吾i s 万= 1 + 2 s 一瓦a 丽s ，l p t 算法性质并结 1 5 讲台同类机覆盖问题的l p t 算法 锄啦瓮 云2 + - 5 s ，可得乃哥 m s 一鑫一击 丽1 ，所以机 器坞上只有见一个工件加工。 考虑鸩上前两个i 件仍，砍 ，我们有岛见= 五1 + 2 s 一丽5 5 ， 巩只j 1 + s 一瓦3 丽5 ，所以互一易仍+ r ，+ 2 s 一丽5 s + 三+ s 一嘉 主j s 其中最后一个不等式有g ( s ) l 得到，这与鸩上有3 个及以上i 件相矛盾。 l + z s 若机器鸩上有2 个工件加工，则b 互一易石， 互2 r , ， t 3 l + 2 s - t - 一互 l + 2 s 一言s 一；2 ( s s ) = l + 2 s - 9 3 ( s s ) ，l p t 算法性质并且结合 g ( s ) 言罢可知，乃五一亨 1 + 2 s i 3 5 万一夏1 五 i l 两，从而机器坞上只有 p 3 一个工件加工，此时三尸r 算法排序可以确定，即工件a ，岛，见安排在机器 m 上加工，p 2 ，p 4 在鸩上加工，p 3 在坞上加工。 由 岛= 互 1 + 2 s 一夏3 s 万 ， 则 a 仍岛 1 + 2 s i 3 5 万 ，且有 岛仍a 五 赤。 令巧2 见+ 风+ + 办，则有巧= 互一局 夏s 万一1 2 s + 夏3 s 万= 夏a s 万一l 一2 s 。 下面考虑问题的最优排序。若最优排序中工件岛，仍，见，仇都在m 或鸠上 加工，记巧为在最优排序中在机器坞上加工的工件大小之和，则有巧巧1 ， 由a + 东= 互 高，可知a2 互一瓦高一1 ，见a 二妥得到，这与假设c = l 相矛盾。 j+z 若机器鸩上只有仍一个工件加i ， 则有a 互 主， 五 正= 仍马 击可得到 ， s c 互掣：旦 盟 互时的情形。 对鸩上只有一个工件p 2 加工的情形，我们有互= p 2 ，然而正a p 2 = 正， 此时机器m i 上也只有一个i 件a 加工。 若鸩上也只有一个工件加工，此时即得到最优解，问题得证。 若坞上有两个工件加工，此时若最优排序中工件a ，见仍在机器m ，鸠上 加工，l p t 算法可得最优解，问题得证；若最优排序中工件岛不在机器m 或鸩 上加工，删 有乃五一岛 季 去，五= 五一乃+ 乃 击+ 嘉= 南， 舳如，筹一确c h n 黔) 血n 岛，爿“这 与假设c = 1 相矛盾。 若坞上有三个以上工件加工，则有n 三( 乃一乃) 丢 瓦b ， z ：z 一矽i + p ； 上+ j 二：_ 丢，此时若最优排序中工件a ，仍仍在机器 五= 五一乃+ 岛 丢，可得c + 亨 1 ，邑= 1 ，三p 丁算法将工件a ，段安排在机器m 上加工，工件仍，岛安 排在机器鸩上加工，工件岛安排在机器坞上加工，c 肼= 1 s + f 2 ，而最优排序 是将局，p 2 安排在m 上加工，岛，鼽在鸩上加工，岛安排在坞上加工，我们有 c 1 ，所以可知导= 1 = 景，算法界为紧界。 _ 推论2 2x 寸q , l l c 曲问题，其中s = 焉= 而 墨= 1 时，三p r 算法常数界为2 ，且界 为紧的。 证明：由定理2 2 证明可知g ( s ) s 22 岛2 1 ， s ：屯 岛= l 时l p t 算法常数紧界分别为2 和3 ，可见加工速度的不同可能 会使算法界有所差别。 小台同类机覆盖问题的l p t 算法 第三章m 台同类机覆盖问题 3 1 特殊情形绒0 吒。问题的l p t 算法界 定理3 1 对跏0 c 血问题，当m 4 ，s = 岛 s 2 = s 3 = = = l ，k s _ r e ( m - i ) 时 l p t 算法有参数紧界办( s ) i 品而m s 证明：令五，五，乙分别表示在工件加工完毕后机器m ，鸩，坂上加工工件的 大小之和，工件既，巩，既分别表示机器m ，鸠，心上加工的最后一个工件 的大小。不妨设c = 1 ，下面用反证法证明结论成立。若结论导办( s ) 不成立， 即有吕 ? ( s ) ，c 胛 志c = 志，有以上假设我们可知 下面分三种情形讨论如下。 子情形1 机器鸠，鸠，帆上均有2 个以上工件加工。 由三p r 算法性质知 乃一 亨 志， 歹= 2 ，3 ，所，则有 乃= + 乃一b _ 2 m - 2 + s ，所以我们有 、 s + m m l l m 一1 + s c + 互墨= 二 巫s 二巫2 竺二! ! ，竹一l + sm l + s 1 ， 乙 一d j 一o 一 一厅 ， ，、 ，” 等等，故可知 ，竹一七 监2 ：三 。， m - k 厅( s ) 这与假设c = l 相矛盾。 若机器m 上不止一个工件加工，则令瓦表示l p t 算法排序中机器m 上除 了a 之外所有其他工件的大小之和，即有五= a + 瓦，此时考虑最优排序。 若工件a 在最优排序中也在m 上加工，我们令丁表示l p t 算法中在机器 坂+ ，坂上加工的工件在最优排序中在m 上加工的工件大小之和，显然当 k = m 时，鸠小，坂为空集，t = o 。令，1 k - i 表示仍，岛，a 中有， 个工件凡，饩，既在最优排序中在m 上加工，巧5 表示瓦工件中在最优排序中 不在m 上加工的工件大小之和。在最优排序中，工件集 仍，乜，级” a ，以) 中的七一1 一歹个工件至多在七一l 一台机器上加工，考虑机器鸭小，坂上的剩余 工件以及在l p t 排序中在m 上加工的工件在最优排序中不在m 上加工的所有 工件，所有这些i 件在最优排序中至少要在m 一后+ 歹台机器上加工，所以有 m 台同类机覆盖问题的l p t 算法 瓦+ 1 + + 乙一丁+ 碚3 聊一k + y ，贝u r o 露5 m - k + j + t 一( 瓦+ l + + 乙) 。故 而a 。五一t o 1 1 1 一巧曲 而s 一( 胧一后+ 歹+ 丁一( 互+ - + + 乙”，同时我们有 色 一以a 志一( 聊一七+ 歹+ ，一( 瓦+ + 一+ 乙) ) ， 考虑最优排序中机器m 上的加工工件大小之和五，则由乃 丽2 五， ，= k + l ，m ，我们可得 c 互：垒墨二堡：! 垒：丝：! ：丝三圣二盈：塑三 sss m ( 聊一1 ) 时，根据上式右端项i ( j 瓦+ 1 i ) ( 2 面m i - j 2 k 百+ 丽s ) ，我们有 ( j + 1 ) ( 2 m - 2 k + s )j ( 2 m 一2 k + s ) s - - ( 歹+ 1 ) ( m 一七+ 歹)s + _ ，( 朋一七+ j - 1 ) ：! 三竺二三查丛兰二丛! 塑 o ， = 一7 lj ( s + ( 一，+ 1 ) ( ， 一k + 歹) ) ( s + ( ，竹一k + 歹一1 ) ) 从而上式右端项关于_ ，为增函数，所以我们可得要使结论成立则必须有 r t l 台同类机覆盖问题的l p t 算法 办( s ) k ( 2 m - 2 k _ + _ - s ) ，2 七所，下面我们来说明此式成立。 s + k ( m 一1 ) 一 当七：所时，k ( 2 m - 2 k + s ) ：竺- _ 一，上述不等式成立。 s + k ( m 一1 )s + m m 一1 ) 当2 k m 一1 时，由 m s s + m ( m - 1 ) k ( 2 m 一2 k + s ) 一( 聊一后) ( s 2 2 k s 一2 k m ( m 一1 ) ) s + k ( m - 1 )( s + 朋( 所一1 ) ) ( s + k ( m 一1 ) ) 其中当j m ( m 一1 ) 4 ( m 一1 ) 时，s 2 2 k s 一2 k m ( m - i ) 0 ，所以当2 k m - 1 时， j 五k ( 2 m - 2 k + s ) ，结论成立，即有当所4 ， s m ( m - 1 ) ， 2 后朋， s + m ( m 一1 1s + k ( m 1 ) l j k - 1 时，办( s ) = i 品m 而si ( j 瓦+ 万1 ) ( 面2 m 而- j 2 k 瓦+ 丽s ) ，此时根据( 7 ) 我们有 c - t o 。m - k + j - l + t 一( 瓦“+ + 乙) ，从而 a 5 互一t o 而s m j j + ，一1 + r 一( 瓦+ t + + 7 ：，) 考虑最优排序中机器m l 上的加工工件大小之和石，则与上述情形类似可得 c 互：墨二堡：鱼：垒三 m 台同类机覆盖问题的u y r 算法 璺墨二盈：亟! 二鱼互一露。+ ( ，一1 ) 见+ 丁。 s 。：t-tom+(j-i)(tl-to(3)+t：j(t,-tom)+t ss 尘壶二竺二! 二兰二! 二三：二坚二二竺二三 i ( j 瓦+ 万1 ) ( 面2 m 石- i 2 i k + 砑s ) i j 巧( 2 而m = - 2 瓦k 而+ s ) ，结合( 8 ) 我们可得，c 1 ，这与假设c l 相矛盾。 情形2 c l p t = 乙 志。 子情形1 机器m ，m 2 ，坂一，上均有两个以上工件加工。 d f ll p r 算法知 s 乃一 乙 志， 即有弓 丽2 ，= 2 ，3 ，肌一1 ，同 时华乙 等等，可得 m 台同类机覆盖问题的l p t 算法 c 互墨= 互 m - i + s 蕊s + l + ( m 一2 ) + i z l 办( s ) 、7 21 + 办( s )办( j ) + s， 一1 1 ，这与假设c = 1 相矛盾。 子情形2 机器m 上只有一个工件p l 加工，机器m ：，m 。一l 上有机器只加工一个 工件。 由l p t 算法性质知：存在2 g 等，我们可得 c 羔圣立：圣 m q 巫21 ：二! 二! ：二巫1 等搿， 2 k m 一2 。 情形3 c t 剧r = t j 丽1 ，2 肌一1 。 我们约定若霉= 乃o j f ) ，则令c 胛= 乃。 考虑乃 t ，j + l s m 的情形，若丝上只有一个工件加工，即瓦= 见， 则有乃乃见= i ，这与假设弓 c 相矛盾。对所有其他情形，与情形2 相类 似的我们可证结论成立。综上可知，算法界得证。下举例说明上述算法参数界为 紧界。给定工件集 p j = = = s ，+ ，= = p 2 肿。- - m ，l p t 算法是将工件 a ，p m 小，仍州安排在m 上加工，p 2 ，岛，分别安排在机器鸩，心，以上 所台同类机覆盖问题的l p t 算法 加工，c 胛：s + m ( m - 1 ) ，而最优排序是将工件a ，仍，安排在m 上加工， s + ，埘，仍肼一，分别安排在机器鸠，坞，坂上加工，有c + = 朋，从而 c m嬲 c 胛s + m ( m - 1 ) s + m ( m - 1 ) s 册台同类机覆盖问题的l p t 算法 参考文献 【l 】ya z 碣l e p s t e i n ，o n l i n em a c h i n ec o v e r i n g ，i np r o c o ft h e5 t ha n n u a l e u r o p e a ns y m p o s i u mo na l g o r i t h m s ( e s a 9 7 ) ，19 9 7 ，2 3 3 6 【2 】蔡圣义，三台同类机在线排序问题一种特殊情况的研究，系统工程理论与实 践，7 ，2 0 0 6 ，4 1 4 6 【3 】陈思霞，m 台同类机在线排序问题研究，浙江大学硕士学位论文，2 0 0 7 【4 】x yc h e n , l e p s t e i n ，z yt a n , s e m i o n l i n em a c h i n ec o v e r i n gf o rt w ou n i f o r m m a c h i n e s ，m a n u s c r i p t ，2 0 0 8 5 】yc h o ，s s a h n i ，b o u n d sf o rl i s ts c h e d u l e so nu n i f o r mp r o c e s s o r s ，s i a mj c o m p u t ，9 ，1 9 8 0 ，9 1 - 1 0 3 【6 】j c s i r i k ，h k e l i e r e r , a n dgw o e g i n g e r , t h ee x a c tl p t - b o u n df o rm a x i m i z i n gt h e m i