（运筹学与控制论专业论文）关于同类机半在线排序问题的若干研究.pdf

摘要 所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排 加工次序，使一个或多个目标达到最优它可以分为经典排序和现代排序相 对于经典排序而言，现代排序是非经典的、新型的排序近几十年来，有关现 代排序的研究有了很大的发展，新的排序模型也不断涌现常见的现代排序模 型有可控排序、成组分批排序、多目标排序、在线排序和半在线排序等等 第一章，主要介绍了排序的产生背景、发展，及其一些符号等相关的基础 知识 第二章，考虑已知工件最大加工时间的同类机半在线排序问题，目标为极 小化机器最大负载对于三台特殊同类机问题，当s 。= s 。= s 1 = s 2 ，并且最 大加工时间已知时，给出了竞争比不大于百4 s + 2 ( 1 2 ) 的半在 线算法 第三章，讨论了两台同类机的半在线问题，目标为极小化工件最大完工时 间对已知所有任务总加工时间和最大任务加工时间的半在线问题，给出了竞 争比为丽4 s + 2 的最优半在线算法 关键词：运筹学排序问题半在线竞争比 a b s t r a c t s c h e d u l i n gi st oa s s i g nj o b sp r o c e s s e do nm a c h i n e su n d e r8 0 m ec o n s t r a i n t ss u c ht h a t o n eo rm u l t i - c r i t e r i aa t t a i nt ot h eo p t i m u m i tc a nb ed i v i d e di n t oc l a s s i c a ls c h e d u l i n g a n dm o d e r ns c h e d u l i n g c o m p a r e dw i t ht h ec l a s s i c a ls c h e d u l i n g ，t h em o d e r ns c h e d u l i n g i sn o n c l a s s i c a la n dn e w - t y p e t h e r eh a v eb e e nm o r et h a nt e nm o d e r ns c h e d u l i n gm o d e l s w h i c ha r ew i d e l yd i s c u s s e do v e rt h el a s tt w e n t yy e a r s ，s u c ha 8t h es c h e d u l i n gw i t hc o n t r o l - l a b l ep r o c e s s i n gt i m e ，t h eb a t c h i n gs c h e d u l i n g ，m u l t i c r i t e r i as c h e d u l i n g ，o nl i n es c h e d u l i n g ， s e m i o n - f i n es c h e d u l i n ga n ds oo n i nc h a p t e r1 ，s o m en o t a t i o n ，d e f i n i t i o n sa n db a s i cb a c k g r o u n di n f o r m a t i o na b o u tt h e s u b j e c ta r ei n t r o d u c e d i nc h a p t e r2 ，w ec o n s i d e rt h es e m i - o n - l i n es c h e d u l i n gp r o b l e m so nu n i f o r mm a c h i n e s ， w h e r et h el a r g e s tp r o c e s s i n gt i m eo fa l lj o b si sk n o w ni na d v a n c e t h eo b j e c t i v ei st om i l l - i m i z et h em a x i m u mm a c h i n ec o m p l e t i o nt i m e i ft h e r ea r et h r e eu n i f o r ms p e c i a lm a c h i n e s a n dt h es p e e do fm a c h i n e sa r eg i v e nb y8 1 = 8 3 = 821 = 8 2 ，w ep r o v i d ea na l g o r i t h m w h o s ec o m p e t i t i v er a t i oi sn o tg r e a t e rt h a n 百4 s + 2 ( 1 2 ) i nc h a p t e r3 ，w ec o n s i d e rt h es e m i - o n l i n et w ou 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 s ， w h e r et h eo b j e c t i v ei st om i n i m i z et h em a x i m u mj o bc o m p l e t i o nt i m e f o rt h es e m i o n l i n ew i t hk n o w nt o t a lp r o c e s s i n gt i m ea n dl a r g e s tp r o c e s s i n gt i m e a no p t i m a ls e m i - o n - l i n e a l g o r i t h mw i t hc o m p e t i t i v ev a t i o 赢4 s + 2i sp r e s e n t e d k e yw o r d s ：o p e r a t i o n a lr e s e a r c hs c h e d u l i n gs e m i - o nl i n ec o m p e t i t i v er a t i o 2 第一章绪论 第一节基础知识 排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器或资 源最优地完成一批给定的任务或作业在执行这些任务或作业时需要满足某些 限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工 时间的影响等最优的完成指的是使目标函数达到最优，而目标函数通常是对 加工时间的长短、处理机的利用率的描述 在排序问题中，处理机的数量和种类，任务或作业的顺序、到达时间、完 工限制，资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出 一般的排序定义我们用如下的方式描述排序问题： 给定7 , 个任务集 t = 正，t 2 ，死) ， m 个处理机的处理机集 p = 尸l ，恳，p m ) ， 和s 种资源的资源集 r = r 1 ，r 2 ，r 。) 排序问题指的是在一定条件下，为了完成各项任务，把p 中的处理机和r 中 的资源分配给t 中的任务，使目标函数达到最优 排序问题基本上是由处理机的数量、种类与环境以及任务或作业的性质和 目标函数组成 一处理机 只有一个处理机的排序问题称为单处理机排序问题，否则称为多处理机排 序问题 在多处理机排序问题中，如果所有的处理机都具有相同的功能，称它们为 同类机或平行机 同类机按处理的速度又分为三种类型：如果所有的处理机都具有相同的速 度，称之为同速机；如果处理机的速度不同，但每个处理机的速度都是常数， 不依赖被加工的任务，称它们恒速机；如果处理机的速度依赖被加工的任务， 它们被称为变速机 多处理机的另一种情况是多类型机多类型机指的是m 个处理机具有不 同的功能在多处理机环境中，被加工的任务需要在不同的处理机上加工在 这种情况下，把任务称为作业设有作业集，= ，如，厶) 每个作业如有嘶 道工序矸，马一，工序指的是作业在某处理机上被加工的这部分任务 如果每个作业需要在每个处理机上加工，即= m ，j = 1 ，2 ，m 而且每 个作业的工序也相同，即在处理机上加工的顺序相同，把这种多类机的环境称 为同顺序作业或流水作业 如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称 之为异序作业 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把 它称为自由顺序作业或开放作业 在多处理机中，还有一种更复杂的情况，这就是柔性流水作业，它是流水 作业和平行机的推广在柔性流水作业中，有8 类处理机，第j 类有s j 个平 行机，每个作业有8 道工序，每道工序需要在每类平行机中的一个处理机上加 工，且每个作业的加工顺序相同 为方便起见，我们把同顺序作业、异顺序作业、开放作业、柔性流水作业 通称为车间作业 二任务和作业 排序问题中的约束条件，主要指的是任务和作业的性质以及它们在加工过 程中的要求和限制下边的数据描述了任务的一些性质 ( 1 ) 加工时间向量 任务的加工时间向量是p j = 0 l j ，p 2 j ，蛳) 其中肋是任务乃在处理 机只上所需要的加工时间对同速机有黝= 功，i = 1 ，2 ，m ，对恒速机有 2 p q = p j b j ，i = 1 ，2 ，m 其中胁是标准的加工时间( 一般是速度最慢的处理机 的加工时间) ，b i 是处理机最的速度因子 在车间作业的排序问题中，作业乃的加工时间向量是p = ( p l j , p t 一，p 哪) 其中舶是工序在对应的处理机上的加工时间 ( 2 ) 到达时间 到达时间或准备时间吩是任务乃已经准备好可以被加工的时间如果所 有的任务的准备时间相同，取巧= 0 ，j = 1 ，2 ，乱 ( 3 ) 工期和截止期限 工期由表示对任务乃限定的完工时间如果不完工，应受到一定的惩罚 绝对不准许延误的工期称为截止期限 ( 4 ) 优先因子 优先因子是一个权重，它表示一项任务相对于其他任务的重要程度 任务被加工时的一个重要约束是可中断或不可中断如果排序问题中，每 一个任务在加工时的任一时刻都可暂停加工，加工该任务的处理机可去加工任 何其他任务，以后可在任何时刻在任意处理机上重新继续加工，这种排序问题 称之为可中断排序任何任务都不允许中断的排序问题称为不可中断排序 加工任务时的另一个重要的限制是任务之间的优先约束在优先约束中有 三种重要的特殊情况：如果每个任务最多有一个前任和一个后继，优先约束图 称为链如果每个任务最多有一个后继，优先约束图称为入树如果每个任务 最多有一个前任，优先约束图称为出树 三目标函数 我们用c = ( g ，g ，g ) 表示任务的完工时间，要极小化的目标函数总 是完工时间g 的函数在排序问题中，目标函数主要有下面几种 ( 1 ) 时间表长 时间表长定义为。= m a x g ) 它等于最后一个被加工完的任务的完工 时间小的时间表长意味着处理机有高的利用率 ( 2 ) 平均加权流程时间 3 平均加权流程时间是f = 哟乃e w j ，其中f j = g r 1 是任务乃的流程 时间 、 ( 3 ) 最大延误 最大延误定义为l 。= m a x l j ，其中i j = 0 一d j 是任务乃的延误时间 ( 4 ) 加权总误工 加权总误工是d = e w e ，d j 其中功= m a x 9 一奶，0 ) = m a x l j ，o ) 是任务的 误工时间 ( 5 ) 加权误工任务数 加权误工任务数是u = e 屿其中 r ：心地， l 0 ，i fc j d j 是对任务误工的单位惩罚 四排序问题的分类 在排序问题中，如果所有的数据在进行决策之前都是已知的，排序问题称 为确定性排序问题如果有的数据，例如加工时间，准备时间和工期，在做决 策时是未知的，它们是一些随机变量，但它们的分布是已知的，这样的排序问 题称为随机排序问题无论是确定性排序还是随机排序，我们都假设： ( 1 ) 任务或作业和处理机都是有限的 ( 2 ) 在任一时刻，任何处理机只能加工一个任务或一道工序 ( 3 ) 极小化单一目标函数在随机排序中，极小化目标函数的数学期望 下面我们主要说明确定性排序的分类 处理机、任务或作业和目标函数三要素组成了排序问题处理机的数量、 类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加 上度量不同指标的目标函数，形成了种类繁多的排序类型我们用g r a h a m 等 人首先使用的三元组来描述排序问题的类型这样能大大简化排序问题的表 示 4 三元组记号由三个区域组成：o 俐7 它们具有下边的含意 o 区域表示处理机的数量、类型和环境它可以为 1 ：单处理机 p m ：i n 个同速机 q 。：m 个恒速机 风，：m 个变速机 f m ：m 个处理机，流水作业 o m ：m 个处理机，开放作业 j m ：m 个处理机，异顺序作业 f 只：s 类处理机，柔性流水作业 卢区域表示任务或作业的性质、加工要求和限制，资源的种类、数量和对 加工的影响等约束条件它同时可以包含多项，可能的项主要有： 巧任务有不同的达到时间如果卢中不出现r l ，说明r j = 0 ，j = 1 ，2 ，佗 s j t ：表示在乃和耳之间的安装时间如果甄是第一个被加工的任务， 表示对死的安装时间，如果互挹最后一个被加工的任务，s 扣表示乃加工后 清理现场的时间如果安装时间与处理机b 有关，安装时间要多一个下标i ， 即8 沙如果卢区域不出现s m 则所有的安装时间都是零 p r m p ：加工时可中断如果p 区域不出现p r m p ，表示加工时不可中断 p r e c ，c h a i n s ，i n t r e e ，o u t t r e e ：表示任务的相关性，分别表示一般优先约束、 链、入树和出树如果p 区域中不出现这些项，任务集是无关的 ，y 区域表示要优化的目标函数，它可以是 g 。：时间表长 g ，c a ：总完工时间，加权总完工时间 三。：最大延误 5 d j ，ew j d j ：总误工，加权总误工 ，e w j u j ：误工任务数，加权误工任务数 五排序问题的算法和复杂性 排序问题是一类组合优化问题求解排序问题的基本思路：应用或借鉴求 解其它组合最优化问题的方法，充分利用排序问题本身的特殊性质以确定满 足约束条件的最优排序有些排序问题可以直接转化为其它的组合最优化问题 求解我们要分析一个排序问题是否是n p h a r d 的，以便知道求解此问题的 难度，为求解提供一些有益的启发求解这类问题有两种基本方法：一种是分 枝定界法、动态规划法等巧妙的穷举法求出它们的精确最优排序这种算法计 算量大，只有对规模较小的问题才是可行的；另一种方法是求出它们的近似最 优排序，各种局部搜索法和启发式算法都是很有效的这类算法计算量小，并 能满足一定的实际需要为了知道所得到的近似最优排序与最优排序的近似程 度，分析误差界是使用这类方法不可缺少的工作，也是富有技巧性的工作 6 第二节排序问题在我国的引人与现状 早在6 0 年代，中国科学院越民义先生就注意到排序问题的重要性和在理 论上的难度，他在1 9 6 0 年就编写了国内第一本排序理论的讲义7 0 年代越民 义和韩继业开始研究同顺序流水作业f l p e r m g 。问题，并且取得了杰出的成 绩1 9 7 5 年发表在中国科学上的论文中，他们提出可行线和可行和的概 念，得到根据两个工件的工时来确定相邻加工次序的最佳条件国外1 9 7 6 年以 后才发表m = 3 时的同样结果他们的成果受到国内外学术界的重视以后他 们提出s z w a r c 最优消去法准则更为广泛的消去准则和关于完工时间的下界表 达式以此为基础，他们设计出算法，并通过大量实例计算，表明此算法的效 率优于国外的算法他们的论文“排序问题中的一些数学问题”带动了国内对 排序问题的学习和研究近年来，越民义先生在国外讲学期间研究p | | g 。排 序问题c o f f m a n 等人在1 9 7 8 年提出p o g 。问题的m u l t i f i t 近似算法，证 明最坏情况下此算法的上界不会超过1 2 2 ，并猜测精确上界是曹= 1 1 7 6 1 9 8 4 年f r i e s e n 证明上界不会超过1 2 0 ，并给出上界是普= 1 1 8 1 的实例越民义 证明此算法的精确上界就是蔫，从而结束了多年来对于m u l t j f j t 算法的研 究越民义和韩继业的研究成果接近和达到了国际先进水平在越民义和韩继 业的倡导和带动下，国内的排序研究有了较大的发展 林诒勋老师多年来研究排序的基本想法是寻找有效的工具他认为最基本 的方法是在文献【l 】1 中总结的置换法他在国内最早深入研究延误问题的文【2 】2 中也是采用这种方法其次，他以序结构的观点来处理排序问题，也是很有特 色的他采用的第三个方法是把排序纳入数学规划的框架 张峰【3 】研究误工问题的可控排序张峰，陈峰、唐国春 4 】等研究离散加 工时间可控排序，得到2 一近似算法与g 近似算法吴志图、蔡小强、郑大昭， l a i n 等【5 研究加工时间可控，使完工时间方差为最小的排序问题，提出一个 拟多项式时间算法和两个启发式算法 郑大昭、吴志图、原晋江、刘朝晖等【6 】证明，即使工件前后约束是由若干 7 条链组成的，无限容量同时加工排序问题也是强n p 一困难的郑大昭、原晋 江，杨爱峰【7 】等研究工件有前后约束、有不同就绪时间、有相同加工时间的 单台机器同时加工排序问题，对于在不同的条件下的几个不同的目标函数提出 多项式时间算法或近似算法原晋江、刘朝晖，郑大昭、吴志图等f 8 】证明，单 台机器无限容量使m a k e s p a n 为最小的问题是困难的，并给出p t a s ( 多项式时 间近似方案) 原晋江、杨爱峰、郑大昭等证明单台机器相同加工时间使最大延 迟为最小的同时加工排序问题是多项式时间可解的 y e u n 9 ，o g u z ，郑大昭等【9 】研究两阶段流水作业窗时排序问题，证明使提前 和延误的总和为最小的排序问题是强n p 一困难的，并提出分支定界算法 对有基数约束的平行机排序问题，何勇、谈之奕、z h u ，姚恩瑜等【1 0 】研 究使机器最小负载为最大的三个算法的最坏情况界；对两台机带机器有不同就 绪时间的m a k e s p a n 问题，季敏和何勇【1 1 】给出最坏情况界为；的线性时间近 似算法 对带机器费用的在线排序问题，d o s a 和何勇【1 2 给出改进的算法，并对所 有工件加工时间都不大于1 时，给出竞争比为i 4 的最好算法对已知工件最大 加工时间和已知工件从大到小到达的两个机器费用的半在线排序问题，d o s a 和何勇【1 2 l 给出竞争比均为2 的算法何勇和蒋义伟【1 3 ，1 4 】研究了工件加工时 间在一个区间内的可中断半在线排序问题，对两台同类机和m 台同型机均得 到最好算法谈之奕和何勇【1 5 】研究使机器的最小载荷为最大的平行机o r d i n a l 半在线排序问题，给出两个近似算法族，它们是渐近最好的，并且对固定的m ， 最坏情况界与问题的上界非常接近 张国川、蔡小强、w o n g 等【16 】研究使m a k e s p a n 为最小的资源受限排序， 证明算法的最坏情况性能比不超过；或者2 ，还给出在线算法万仲平，何炬 林、唐国春【1 7 】等把不确定资源约束下的结构项目排序问题，利用机会约束置 信度等转化为确定性规划问题，并提出二阶段算法原晋江和孙玉芹【1 8 ，1 9 】研 究第1 目标是最大延误丁k 和第2 目标是误工工件个数的第1 类多目标 排序问题 8 第三节半在线排序问题 由在线和离线的定义可以看出，从排序者对工件信息的了解程度来看，他 们分属于两个极端情形在实际问题中，出现这两种情况的机会并不多大量 存在的问题是排序者一方面不可能知道工件的所有信息，另一方面可能掌握着 比经典在线模型更多的信息或有着更大的排序自由度，因而使问题变得比离线 相对困难些，但比在线相对容易些这样便可能得到比在线算法更好的算法 我们把不完全满足在线排序问题的两条基本假设，难度介于在线和离线之间的 模型称为半在线模型 在实际需要的大力推动和理论工作者的不懈努力下，自1 9 9 6 年半在线概 念( 其实对其它的组合最优化问题，如装箱、网络优化也有相应的概念) 提出 后的近十年间，各种不同的模型不断涌现，初步形成了排序研究的一个新的分 支何勇等【2 3 ，2 4 】把半在线模型分为3 类把不满足在线基本假设( 1 ) 的半在线 模型，即排序者掌握后续工件的部分信息，称为第一类半在线模型；把不满足 在线基本假设( 2 ) 的半在线模型，即已安排的工件的加工进程可通过某种方式 加以改变，称为第二类半在线模型；不能列入这两类的半在线模型统称为第三 类半在线模型为描述排序问题方便起见，我们将表示各半在线模型的记号写 在三参数表示法的第二个区域中尽管半在线模型不完全满足在线模型的两条 假设，但它与在线之间只是程度上的差别，在后续工件信息不完全已知这一点 上是相同的，而与离线问题有着本质的区别我们仍用竞争比分析法来研究近 似算法的性能和问题的下界若在给定的机器环境和目标函数下，求解半在线 排序问题的算法的竞争比严格小于相应在线问题的下界，则说明此时该半在线 模型是有价值的反之，若半在线问题的下界等于相应在线问题的最优算法的 竞争比，则说明此时该半在线模型不会使问题变得更为简单，因而没有价值 当然，半在线排序问题研究的意义并不局限于其本身，某些半在线模型的研究 可为在线和离线问题的研究提供新的思路和方法，使这些经典问题取得突破 根据实际情况的不同，我们可以提出不同的符合要求的半在线模型尽管 9 半在线排序问题出现的时间很短，然而已有十多个不同的模型出现下面我们 对其中主要的两种模型作简要的介绍 1 已知工件总加工时间( k n o w ns u m ) 假设所有工件的总加工时间t = m 已知该模型由k e l l e r e r ，k o t o v ，s p e r a n z a 和t u z a 在研究p 2 h g 。时首先提出并研究的，是目前已有结果较多的半在线 模型之一 算法凰 ( 1 ) 将工件安排在尬上加工，直至存在工件珊，使得2 ( 尬) + p j 吾 ( 2 ) 若f ( ) 4 - 乃可2 t ，则将p j 安排在尬上加工，将剩余工件全部安排在 上加工，停止 著z ( 尬) + 巧 孚，则将力安排在尬上加工，将剩余工件全部安排在尬 上加工，停止 该算法的思想类似于文【2 5 】中求解p 2 0 瓯。离线问题的线性时间近似算 法该文设计出一个子过程通过它们的复合给出了近似比为酱的算法风 就是该子过程的特殊情形 定理1 3 1 ：算法日3 是求解p 2 k n o w ns 啪i g 。的最佳算法，其竞争比为j 4 值得注意的是，上述算法也是求解p 2 1 k n o w ns u mj c 。妯的最佳算法，文【2 6 】 证明了下面的定理 定理1 3 2 算法风是求解p 2 1 k n o w n 跏m l c m ；。的最佳算法，其竞争比为2 算法凰经过适当修改后可以用来求解p 2 ，r i k n o w ns m | 。文 2 7 】给出 了算法p s u m ，其竞争比仍为i 4 且为此时的最佳算法( 两种目标下) 对q 2 k n o w t ts “m i g 。，文【2 8 】给出了竞争比为讵的算法s u m ，同时证明了问题的下界 为 2 学对上述各种情形得到的算法的竞争比均严格小于相应在线问题的下 界，说明已知工件总加工时间有利于近似算法的设计 文【2 9 】把上述模型推广到p m l k n o w n8 “m i g 。，m 3 的情形，给出了竞争比 为2 1 的近似算法当m = 3 ，4 时，该算法竞争比要比最佳在线算法竞争比 1 0 小对m 5 ，寻求此时竞争比严格小于已知最好的在线算法，进一步地，小于 在线问题的下界的近似算法，将是一项很有意义的工作 2 已知工件最大加工时间( k n o w nl a r g e s tj o b ) 假设所有工件中加工时间最大的工件的加工时间已知，即p m 。= m a x l 町0 = 1 ，2 ，竹) 已知，文【3 0 】首先讨论了这一模型并给出了求解p 2 1 k n o w n l a r g e s t j o b l c m 。 的最佳算法p l s 算法p l s ( 1 ) 将工件安排在尬上加工，除非出现下列情形之一： a 当前工件的加工时间为尸m 。； b 将当前工件安排在舰上加工，尬的负载将大于2 p m 。； ( 2 ) 将当前工件安排在尬上加工，按l s 算法加工剩余工件 定理1 3 3 算法p l s 是求解p 2j k n o w nl a r g e s tj o b l c m j 。的最佳算法，其竞争 比为； 事实上，p l s 也是求解p 2j k n o w nl a r g e s tj o b i c k p 2 ，r i k n o w nl a r g e s tj o bj q 的最佳算法【2 6 ，2 7 而对p 2 ，r _ i l k n o w nl a r g e s tj o b l c ，对p l s 稍作修改得到的新 算法m p l s 即为最佳算法，竞争比仍为；【2 7 】对q 2 k n o w nl a r g e s tj o b c m i 。，文 【2 8 】给出了竞争比为；的算法m l s ，而该问题的下界为、，石 另外，还有工件加工时间位于一区间内( i n t e r v a l ) 、已知工件加工时间非增 ( n o n i n c r e a s i n gj o b ) 、工件分两批到达( t w o b a t c h ) 、已知实例最优解( k n o w n 倒一 i m u m ) 、带缓冲区( b u f f e r ) 、已知工件加工时间序( o r d i n a l ) 等等半在线模型 可以预见，随着研究的不断深入，将会有更多的半在线模型出现 最后指出一点，并不是所有的部分信息都是有利于算法的设计的例如在 p 2 1 0 n l i n e l c 一中，预先知道工件从小到大到达的半在线情形不会改变原先在线 问题的下界因此这种半在线模型是平凡的，其意义也是有限 第四节近似算法与竞争比 鉴于7 0 年代建立起来的计算复杂性理论【2 0 】以及几十年来人们在这方面 的各种工作，现今p n p 的猜想已为绝大多数人所接受；而给出此猜想的证 明，也已成为对整个人类智慧的一大挑战国际数学界将此问题列为二十一世 纪最根本的几个大问题中的一个如果我们接受p n p 的猜想，那么对于所 谓的n p h a r d 问题就不可能存在多项式时间内找到最优的算法也就是说，随 着问题实例的规模的增大，对这种n p h a r d 问题的每一个实例要用统一的算 法找出最优解从计算时间上来看几乎是不可能的因此一个自然的想法就是放 弃对最优解的寻找，而代之以寻找具有某种性能保证的可行解成为近似解，从 而换取计算时间这也就是所谓的近似算法( a p p r o x i m a t i o na l g o r i t h m ) 的思想 近似算法的好坏可以从两方面来看一是算法的计算时间，二是算法得到 的近似解的解值与最优解的解值的接近程度这里，接近程度用最坏情况界 w o r s t c a s er a t i o 来刻画：假设是求解极大化目标排序问题的某一近似算法，称 p a = s u p p i a ( i ) p o p t ( 1 ) ，v i 为算法a 的最坏情况比，其中a ( i ) 和o p t ( ) 分别表示算法a 解实例，所得 的目标函数值和实例，的最优解值如果近似算法a 还是所谓的在线算法，则 这时将算法a 的最坏情况比特别地称为竞争比( c o m p e t i t i v er a t i o ) ，其中o p t ( i ) 是指相应离线问题的最优解值竞争比常用符合c a 表示，即 c a = s u p c u a ( i ) c o p t ( i ) ，v i 如果在线算法a 的竞争比为c ，也称4 是c c o m p e t i t i v e 的 从性能比的可能性上来看，在线问题和离线问题的一个很大的区别在于： 对离线问题，如果不考虑时间要求，由于排序问题是组合优化问题，原则上用 枚举法总可以得到最优解也就是说，如果给你足够多的时间，原则上存在最 坏情况比为1 的离线算法；但对大多数在线问题，竞争比为1 的在线算法在一 】2 般情况下是不存在的对于在线问题，以极大化目标问题为例，在研究过程中 常常要给出所谓在线问题的上界( u p p e rb o u n d ) ，称c 为问题的上界，如果对该 在线问题不存在竞争比大于c 的在线算法上界可以通过给出一系列实例而说 明对任何在线算法都不可能同时很好地解决它们的全部来得到上界表现了由 于部分信息的缺失而给算法设计带来的本质上的困难，这是在线问题固有的性 质如果在线算法a 的竞争比等于在线问题丌的上界，则称a 是解问题丌的 最好的( o p t i m a l ) 算法这是因为，从竞争比的角度来看，不可能存在比a 更好 的在线算法 下面介绍一下什么是在线算法对于具体地一个排序问题，根据问题所涉 及到的信息对排序者( s c h e d u l e r ) 开放的程度，可以将该问题大体上分为离线和 在线两种情况对离线问题，排序者在排序之前知道工件的全部信息于是基 于工件全部信息已知情形下设计的算法就称为离线算法但是，在实际问题 中，常常是在排序进行过程中后续工件的信息是未知的，排序者只能就当前已 有的工件进行排序并且由于问题的实际背景，常常是排序者一旦对某个工件 作出安排就不允许改变为与离线问题区别，这种问题称为在线问题相应地 解决这种问题的算法称为在线算法最经典的离线算法和在线算法就是解平行 机排序问题的肼t 算法【2 1 】和l s 算法【2 2 】 以上对最坏情况比，竞争比和上界的定义都是针对极大目标问题而言的 对极小化目标，可以平行地给出相应的概念：称 p a = i n f p l l a ( i ) p o p t ( i ) ，v ，) 为算法a 的最坏情况比；如果近似算法a 还是所谓的在线算法，则这时将算 法a 的最坏情况比特别地称为竞争比，用符号c a 表示，即 c a = i n f csl l a ( i ) c o p t ( i ) ，w ) 称c 为极小化目标在线排序问题的下界，如果对该在线问题不存在竞争比 小于c 的在线算法 1 3 第二章三台同类机的半在线排序问题 第一节相关介绍 本章讨论已知最大加工时间的半在线排序问题，目标为极小化机器最大负 载下面的结果是关于目标函数为极小化机器最大负载在线问题 对于同型机问题，g r a h a m 在解p m 0 g 诅x 问题时提出了解在线问题的著名 的l s 算法，l s 算法将当前工件安排在能使其最早完工的机器上加工g r a h a m 证明了l s 算法竞争比为2 一磊1 1 9 8 9 年，f a i g l e ，k e r n ，t u r a n 证明了当m = 2 ，3 时算法三s 为解此问题的最佳在线算法；对m 4 ，文f 4 l 】证得己s 算法得竞争 比下界为1 + 去= 1 7 0 7 b a r t a le ta 1 进一步证得其竞争比下界为1 8 3 7 在文 4 1 】 发表后人们开始把目光投向m 4 的情形当m 4 时，c h e ne ta 1 给出了竞 争比好于l s 算法的在线算法m l s 当4 m 2 0 时其提供的算法是至今最好 的，但对足够大的m ，类似于l s 算法，其竞争比也趋2 g a l a m b o s 和w o e g i n e r 在1 9 9 3 年给出r l s 算法并证明其竞争比为2 一鬲1 一e m ，其中e 。 0 为只同m 有 关的数应该说g a l l a m b o s 和w o e g i n e r 给出的r l s 算法比l s 好，但还是很接 近2 真正在竞争比意义上严格小于2 的近似算法是在1 9 9 5 年由b a r t a le ta 1 给 出，他所给的近似算法的竞争比为2 一嘉1 9 8 6 随后，k a r g e r e ta l 给出了竞 争比为1 9 4 5 近似算法在1 9 9 7 年，a l b e r s 证得当m 8 0 时p m | 。问题的竞 争比下界为1 8 5 2 ，并给出了竞争比为1 9 2 3 的近似算法显然这中间的间隙已 足够小 对于同类机问题，q 。i l g 。可描述为：给定m ( m 2 ) 台机器，记机器集为 m = 尬，m 2 ，d 机器坞具有加工速度野又给定工件集i = p ，p 2 ， ， 并且同时也用戤( i = 1 ，2 ，佗) 表示这个工件的长度如果考虑的是在线问题， 则工件就以上面的顺序逐个地到来工件纯可以放在任意一台机器坞上加 工，一旦开始加工则不允许中断，其所需加工时间为a 唧目标是在一切可 能存在的排序中找出最后完工的工件的完工时间尽可能早的排序该问题由 g o n z a l e z 等人【3 1 】在1 9 7 7 年第一次提出对于离线情形，已经知道，当机器数 1 4 m 作为参数输入时，问题是强n p 一难的；而当m 固定时，问题是n p 一难的后 来，h o c h b a u m 等人给出了该问题离线情形的多项式时间近似方案对于在线情 形，关于一般的机器数m ，目前最好的结果是b e r m a n 等人 3 2 1 得到的他们给 出了竞争比为3 + 帕z5 8 2 8 的在线算法，并证明问题的下界为i 而3 3 1z 4 3 1 1 此 外，关于机器数m 取较小的值时，也有一些零星的结果例如：当m = 2 ，e p s t e i n 等人证明了l s 是可能存在的在线算法，其竞争比为班n r 2 8 + 1 ，半 ，这里s 为加 工速度较快的机器与加工速度较慢的机器两者的加工速度的比值而当m = 3 ， 闵啸 3 3 】考虑了s 。= s 1 ，8 。= s 。= l 这一特殊情形他证明了l s 算法的竞争 比为m i n 专等，学) ，并证明了当s 2 时，l s 算法是可能存在的最好的在线算 法这里需要说明一下，所谓在线算法的效果，通常是以竞争比来衡量的对 在线算法a 和实例，用a ( i ) 和o p t u ) 分别表示在线算法a 解实例，给出的 目标函数值和相应的最优目标值算法a 的竞争比定义为 c a = i n f c a ( 1 ) e o p t ( i ) ，v ， 由此可见，就竞争比的定义来看，对排序问题q 。l l 瓯。的在线算法的竞争 比研究，可以不妨假设各台机器的加工速度分别为s 。s 。28 。一t = 1 因此闵啸所考虑的特殊情形并不是对三台机器的两台机器的加工速度作出限 制，而仅仅对某一台的加工速度作出限制或者说闵啸考虑的模型是针对三台 同类机中有两台机器加工速度一样，而另一台机器的加工速度较快这一特殊情 形蔡圣义在文【3 4 】考虑的模型与闵啸的模型类似，也是针对三台同类机中有 两台机器加工速度一样，只是另一台机器的加工速度比其它两台要慢，不失一 般性，设三台机器的加工速度分别为s ，= s 。= s 1 ，勘= 1 他证明了在这一特 殊情形下的q 3 0 g 。，该问题记为q 3 i s - = s 。= s 8 。= i i g 。，l s 算法的竞争比 为m i n ；措，3 旁 ，同时证明当s 3 时l s 算法是可能存在的最好的在线算法 本文也讨论三台同类机问题，三台机器分别记为尬，尬，m 3 ，速度分别为 s 1 ，8 。，8 3 ，且s ，= s 。= s 1 ，s 2 = 1 已知工件最大加工时间的半在线排序问题， 给出了竞争比不大于警( 1 2 ) 的算法 1 5 第二节主要结果及证明 本节考虑已知工件最大加工时间的三台同类机半在线问题三台同类机机 器分别记为舰，尬，m s ，三台同类机机器的速度分别为s 1 s 2 ，8 3 ，且s ，= 8 3 = 8 1 ，s 。= 1 目标函数为极小化最大机器完工时间此模型简记为q 3 l p m 。i 。本 节给出了竞争比不大于4 s 。+ ，2 ( 1 2 ) 的算法用f ( 尬) 0 = l ，2 3 ) 表示加工过程中某阶段机器舰的负载，即当前已分给机器尬加工的工件的 总加工时间与速度的比值用。表示当前需要安排的工件及其所需加工时间 用p m 。表示最大的加工时间 算法a 步1 ：如果l ( m t ) + ； 寺；，则把当前工件z 放在机器上加工，否则转 步2 ； 步2 ：如果f ( ) + 茹 平，则把z 放在机器上加工，否则转步3 ； 步3 ：如果z ( 舰) + ；争，f ( ) + 茹挚，则转步4 否则，若z p m 。， 则在机器尬，上按l s 算法安排工件z ；若z = p m 。，如果z ( 尬) + ； 2 争z ， 则把放$ 在机器慨上加工，如果 ( 尬) + ；2 争x 转步4 ； 步4 ：在机器尬，m 2 ，坞上按l s 算法加工，即把工件z 安排在能使其最 早完工的机器上加工 重复执行以上各步直到不再有新工件到为止，在执行算法过程中，如果 存在多台机器同时可以安排工件z ，则把它安排在从未安排过工件的机器上加 工若不存在这样的机器，则把工件z 安排在速度最大的机器上加工 引理2 2 1 1 不论加工进行到哪一阶段都有： ( 1 ) f ( 舰) 一z ( 帆) 挚0 = 2 ，3 ) 成立， ( 2 ) f ( 坛) 一z ( 尬) 尸m 。( i = 1 ，3 ) 成立 2 当f ( ) 2 平时，不等式t ( m d 一：( ) 虽尹a = 1 ，2 ) 成立 引理2 2 2 ：若z 是按算法a 步4 安排在机器坞上加工的工件，则z + 1 6 s l ( m 1 ) 2p m “，z + f ( ) 2 每“ 引理2 2 3 ：设最后一个工件r 到来之前各机器z ( 舰) ( i = 1 ，2 ，3 ) 的负载分 别为f ( 尬) ，z ( 尬) ，t ( v 1 3 ) ( 1 ) 如果z ( ) 之虽，则；i ( 2 ( 胁s + i ) + 1 ) m a x ( 1 ) ( 制m i ( ) 胁, l ( m ) + 2 i ) 争，则丽( 2 f ( m 尬+ 1 ) ) l 刊( m ( 3 ) 两干瓦 业3 s 证明：( 1 ) 根据引理1 和引理3 的已知条件可得， 因此 从而 8 ( 2 ( m ) 一f ( 飓) ) s 半5 民“s 尬 d ( 2 8 + s ) z ( 尬) 2 ( s t ( m 1 ) + f ( m 2 ) + s t ( m 3 ) + r ) ( 2 s + 1 ) f ( 矗) 4 s + 2 s z ( m 1 ) + f ( 尬) + 5 f ( 坞) + 只、 3 s ( 2 s + 8 ) z ( 尬) 2 ( s l ( m t ) + z ( 如) + s t ( m 3 ) + r ) 从而 ( 2 s + 1 ) 1 ( m 2 )，4 s + 2 s z ( m 1 ) 十z ( 耽) + s f ( m 3 ) + r 、3 s ( 2 ) 易知此时在机器尬上至少有两个工件不失一般性，设安排在机器 尬上的头两个工件按其加工时间大小排列为z ，y y p m 。) 下面分两种 情形来证明 情形1 ：挚 l ( m 3 ) 孥 显然，z f 删。且工件z 安排在机器m 3 上加工是执行算法步4 的结果， 因此由弓i 理2 知z + 鲥( 尬) ，茹+ l ( 坞) 22 冬一 由y z 进一步可得y + s t ( m , ) 22 p m 。y + f ( ) 2 $