（运筹学与控制论专业论文）平行机上工件有到达时间的在线和半在线排序问题.pdf

摘要 排序问题是经典组合优化的问题，在线和半在线排序是排序论当 前研究的热点问题之一。本文主要讨论工件有到达时间的一些在线 和半在线模型，并分析算法下的竞争比。全文共分为三章。 第一章是绪论部分，主要是介绍组合优化中排序问题，竞争比分 析和近似算法等基本概念，总结近几年来出现的在线和半在线模型 及有关的结论。 第二章考虑同型平行机器上工件到达时间任意且工件加工时间 单调不增的问题，目标函数为极小化最大机器负载的在线模型。根据 l s 算法，证明l s 算法的最坏性能比不大于2 一丽1 ，并且当m = 1 时， 这个界为紧界。 第三章考虑工件到达时间不减，机器加工速度为s ；= 1 ( i i m 一1 ) ，s m = s 1 的在线排序。目标函数为极小化最大机器负载的 在线模型，主要讨论两个问题：1 ，当m = 2 时，当其中1 台机器的 加工速度为1 而有一台机器的加工速度为8 1 时，证明l s 算法的 最坏性能比不大于2 ；2 ，当其中m l 台机器的加工速度为1 而有 一台机器的加工速度为8 l 时，证明l s 算法的最坏性能比不大于 r a i n 1 + s + r 坠n - - 1 ，2 + 再m 而- i ) 。 关键词：在线和半在线排序；竞争比；空闲时间；平行机 a b s t r a c t t h i st h e s i si sc o m p o s e do ft h r e ec h a p t e r s i tf o c u s e so ns o m em o d e l so f o n - l i n es c h e d u l i n go rs e m i - o n l i n es c h e d u l i n go np a r a l l e lm a c h i n e sf o rj o b sw i t h r e l e a s et i m e sa n dm a i n l ya n a l y z et h el sa l g o r i t h mc o m p e t i t i v ep e r f o r m a n c e r a t i o t h ei n t r o d u c t i o no ft h eb a c k g r o u n da n dh i s t o r yo fs c h e d u l i n gp r o b l e ma n d c o m p e t i t i v er a t i oa n a l y s i s ，a p p r o x i m a t i o na l g o r i t h m si sb r i e f l ya d d r e s s e di n c h a p t e r1 ab r i e fs u m m a r yo fo n l i n em o d e l sa n dt h e i rr e s u l t sw h i c ha p p e a r e d i nr e c e n ty e a r si sg i v e n i nc h a p t e r2 ，w es t u d yt h es e m io n - l i n es c h e d u l i n go i li d e n t i c a lm a c h i n e s f o rj o b sw i t ha r b i t r a r yr e l e a s et i m e s w ea s s u m et h a tt h el i s to ft h ep r o c e s s i n g t i m e so fa l lj o b sc o r r e s p o n d i n gt oj o bl i s tla r en o n - i n c r e a s i n g ，i e , p l i 0 2 p n t h eo b j e c t i v ei st of i n das c h e d u l et om i n i m i z et h em a k e s p a n w e p r o v e dt h a ta l g o r i t h ml sh a sao m p e t i t i v er a t i oo f2 一丽1 a n dw ea l s os h o w e d t h a tt h i si sat i g h tb o u n dw h e nm = 1 i nc h a p t e r3 ，w ec o n s i d e rt h eo n - l i n es c h e d u l i n go nu n i f o r mm a c h i n e sf o r j o b sw i t hn o n - d e c r e a s i n gr e l e a s et i m e sa n da r b i t r a r yp r o c e s s i n gt i m e s i ti s a s s u m e dt h a t 舰h a sas p e e d8 i ，w h e r e8 i = 1 ( 1 i m 一1 ) ，8 m = s 1 t h e o b j e c t i v ei st of i n das c h e d u l et om i n i m i z e st h em a k e s p a n w ep r o v e dt h a t t h ea l g o r i t h ml sh a sac o m p e t i t i v er a t i oo f2f o rm = 2a n dau p p e rb o u n do f m i n 1 + i ：s 示m j ，2 + i m 丽- 1 ) f o rg e n e r a lm m a c h i n e s k e yw o r d s ：o n l i n ea n ds e m i o n l i n es c h e d u l i n gp r o b l e m ，c o m p e t i t i v e r a t i o ，m a k e s p a n ，p a r a l l e lm a c h i n e i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：与而尸 少i 。年9 月2 7 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存和汇编本学位论文 本学位论文属于 l 、保密口，在年解密后适用本授权书 ， 2 、不保密因 y ( 请在以上相应方框内打”) 作者签名：匀而酮p 加卜年岁月刁日 翩躲和巧御年广月2 ) 日 平行机上工件有到达时间的在线和半在线排序问题 1 绪论 1 1组合优化简介 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 又称离散优化或组合规划， 是组合最优化的简称，主要研究的是可行解是离散或是可转化为离 散的问题。从最广泛的意义上说，组合规划与整数规划这两者的领 域是一致的，都是指在有限个可供选择的方案的组成集合中，选择 使目标函数达到极值的最优子集。它的一个通俗定义是指在离散的、 有限的数学结构上，寻找一个( 或一组) 满足约束条件并使其目标函 数达到最小或最大的解。其正式定义如下： 定义1 1 1 【2 9 】组合优化问题是一个极小( 大) 问题，它由下述三部 分组成： ( 1 ) 一个实例集合； ( 2 ) 对每一个实例i ，有一个有穷的可行解集合s ( j ) ； ( 3 ) 目标函数，它对每一个实例门阳每一个可行解集合盯s ( ，) ， 赋以一个有理数f ( i ，盯) 。 如果该问题是极小( 大) 化问题，则实例，的最优解为这样一个可行 解仃s ( j ) ，它使得对所有的盯s ( ，) ，都有，( ，矿) ，( ，盯) ( 或 f ( i ，盯+ ) f ( i ，矿) ) 。 组合优化是运筹学的一个重要分支，它是一门古老又年轻的学 科，在生活中也有广泛的应用，著名数学家费马( f e r m a t ) 、欧拉( e u l e r ) 等也都对它们进行对相关的研究。组合最优化发展的初期，研究一 些比较实用的基本上属于网络极值方面的问题，如广播网的设计、开 1 硕士学位论文 关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自 从拟阵概念进入图论领域之后，对拟阵中的一些理论问题的研究成 为组合规划研究的新课题，并得到应用。二十世纪后半叶，伴随着 工业科技革命和现代管理科学的发展，特别是计算机技术突飞猛进 和在各行业的广泛应用，组合优化已壮大成为一门新兴的学科分支。 一些百年前数学家们偶然想到的问题和方法，现在已经在网络通信、 物流管理、交通规划等领域发挥了重要作用，这是他们当时所不曾 想到的。这正预示了此学科的巨大发展前景。现在应用的主要方面 仍是网络上的最优化问题，如最短路问题、最大( 小) 支撑树问题、 最优边无关集问题、最小截集问题、推销员问题等。 常见的组合优化问题有划分问题( p a r t i t i o np r o b l e m ) ，排序问题 ( s c h e d u l i n gp r o b l e m ) ，装箱问题( b i np a c k i n gp r o b l e m ) ，背包问题( k n a p - s a c kp r o b l e m ) ，指派问题( a s s i g n m e n tp r o b l e m ) ，旅行售货问题( t r a v e l - l i n gp r o b l e m ) ，斯坦纳最小树( s t e i n e rm i n i m a lt r e ep r o b l e m ) 等。网络中 的组合优化问题还包括最短问题( s h o r t e s tp a t hp r o b l e m ) ，最小生成树 问题( m i n i m a ls p a n n i n gt r e ep r o b l e m ) ，最大流问题( m a x - f l o wp r o b l e m ) ， 最小费用流问题( m i n - c o s tf l o wp r o b l e m ) 等。尽管大部分组合优化问 题可以转化为整数规划( 或混和整数规划) 问题，但由于整数规划的 求解同样也是困难的，而组合优化又涵盖甚广，因此人们致力于研 究各个问题的组合结构，试图找到一些好的性质和有针对性的求解 方法。组合优化问题全貌参见f l 一3 1 。在此，只对本文研究的排序问 题作一下介绍。 1 2排序问题 排序问题是组合优化领域中的一类重要问题，在生产管理和调 度、网络通信、理论计算机科学中有着广泛的应用，它与理论计算 机科学和离散数学也存在着密切的联系。它是组合优化中一类有着 2 平行机工件有到达时间的在线和半在线排序问题 重要理论意义和广泛实际背景的问题，从关于它的第一篇文章发表 ( s m j o h n s o n ，1 9 5 4 ) 【4 】到现在已经有5 6 年，从两台机器、同顺序的一 个简单问题开始，到今天关于千姿百态问题的研究，近几十年来，排 序问题得到了运筹学、工程学、管理学和计算机科学的极大关注，并 且随着对经典问题研究的日趋深入，大量具有实际背景的新问题不 断涌现，使排序问题极具有生命力和研究价值。几十年的发展不可 谓不大，不可谓不快，可以这样说，对排序问题的研究正进入成熟 期。其所以如此，主要是由于在生产实际中所涉及的排序问题可以 说是无处不在，而排序问题的好坏常会对经济、时间、工效等产生很 大的影响。虽然在有些情况，不管排序好坏，照样可以进行生产，但 如果有好的排序方法可以采用，所产生的经济效益则可能是令人吃 惊的，不少的例子可以说明这一点。由于生产规模日愈庞大，生产管 理日愈复杂，其中自然就会出现许多新的排序问题有待高明之士去 解决。这就使得这门学科日愈得到重视，使之具有广阔的前景。 经典的排序问题可以这样描述：给定m 台机器尬，尬， 及工件集j = ，j 2 ，厶，且工件五的加工时间为鼽( i = 1 ，2 ，几) ， 各工件之间相互独立。机器和工件均可在零时刻开始加工，而且每 个工件只可在任意一台机器上不中断地加工一次。目标函数为极小 化最大机器负载，这里的机器负载是指在该机器上加工的工件的加 工时间之和。 排序问题按照静态( s t a t i c ) 和动态( d y n a m i c ) ，确定性( d e t e r m i n i s t i c ) 和非确定性( n o n - d e t e r m i n i s t i c ) 可以分为四类。对于静态的确实性排 序问题，我们习惯上用三参数法来表示。1 9 6 7 年c o n w a y 等首先提出 用四个参数来表示排序问题，1 9 7 9 年g r a h a m 等提出改用三参数即用 口俐7 来表示一个排序问题。其中q ，卢，7 分别代表特定的机器环境， 工作特征和最优准则。 机器环境用来描述机器的数量，不同机器之间的关系等与机器 3 硕士学位论文 有关的性质。机器可以分成两大类：通用平行机和专用串联机。对于 不许中断加工的情况来讲，一个工件在m 台平行机上加工只需要在 m 台机器中的任何一台机器上加工一次即可；一个工件在m 台串联 机加工则需要在这m 台机器中的每一台机器上都加工一次。常见的 平行机类型有： 同型平行机( i d e n t i c a lp a r a l l e lm a c h i n e s ) ，即所有的机器的加工 速度一样，通常用p 表示。若写成，则表示系统中共有m 台同型 平行机且m 为固定常数； 同类平行机( u n i f o r mp a r a l l e lm a c h i n e s ) ，即机器有各自不同的 速度，但任意工件在不同机器上的加工时间有着相同的比例关系，通 常用q 表示。 不同类平行机( u n r e l a t e dp a r a l l e lm a c h i n e s ) ，即机器的加工速 度不同，且工件在不同机器上的加工时间没有比例关系，通常用r 表示。 串联机也可以分为三类： 流水作业( f l o ws h o p ) ，即每个工件以特定相同的机器次序在机 器上加工。 自由作业( o p e ns h o p ) ，即工件在机器上加工的次序可以是任意 的。 异序作业( j o bs h o p ) ，即每一个工件以各自特定的机器次序进行 加工。 工件特征一般是指工件的各种加工信息，包括工件的加工时间， 工件的到达时间，工件之间的加工顺序，工件和其开始加工时间的 依赖关系，工件加工时间是否允许中断以及中断恢复后再加工时是 否要接受惩罚等等。在经典排序文献中，我们根据排序者在排序时 掌握工件信息的多少把排序问题分为离线( o f f - l i n e ) ，在线( o n - l i n e ) 4 平行机工件有到达时间的在线和半在线排序问题 和半在线( s e m io n - l i n e ) 三类。在离线问题中，全部工件的所有信 息在排序时均已知，排序者可以充分利用上述信息对工件进行安排。 而对在线问题，其基本假设有以下两条： ( 1 ) 工件的信息是逐个释放的。即某个工件的信息只有在排序者 对此工件之前的所有工件作出安排后才会被排序者所知； ( 2 ) 工件加工顺序不可以改变，即一旦将工件安排给某台机器加 工，在其后的任何阶段不能以任何方式加以改变。 最优准则通俗的讲，就是以什么为目标函数。常见的是机器数 给定的，对完工时间这一目标寻求最优。按全部机器的完工时间可 以分为两类：一类是使最后一台完工机器的完工时间达到最小，简 称极小化最大机器完工时间，通常用c = m a x c m 表示，另一类 是使最早一台完工机器的完工时间达到最大，简称为极大化最小机 器完工时间，通常用c m ；n = m i n c m 。按全部工件的完工时间可分 为两类：一类是使最后一个完工工件的完工时间达到最小，简称为 极小化最大工件完工时间，通常用g m = m a x c j 表示，另一类是 使最早完工工件的完工时间达到最大，简称极大化最小工件完工时 间。通常用；n = m i n c j 表示。在机器准备时间为0 时，显然有 g ( m ) = c k ( ，) ，n ( m ) = c 毛n ( j ) 。因此在不引起混淆的情形 下常用g m 或；n 表示目标函数。有关排序问题的综述，可参见 5 8 】。 1 3 近似算法 定义1 3 1 1 9 算法( a l g o r i t h m ) 是一系列解决问题的清晰指令， 也就是说，能够对一定规范的输入，在有限时间内获得所要求的输 出。一个算法应该具有五个重要特征：( 1 ) 有穷性；( 2 ) 确切性；( 3 ) 输 5 硕士学位论文 入；( 4 ) 输出；( 5 ) 可行性。 算法可分为基本算法、数论与代数算法、排序算法，随机化算法 等。宏泛的分为三类：( 1 ) 有限的，确定性算法；( 2 ) 有限的，非确定算 法；( 3 ) 无限的算法。 定义1 3 2 1 1 0 1 对于一个组合优化问题，如果给定任意一个实 例，算法a 总能找到一个可行解仃s ( ，) ，那么就称a 为的近 似算法( a p p r o x i m a t i o na l g o r i t h m ) ；如果进一步这个可行解的目标 值总等于最优解值，则称a 为最优算法( o p t i m a la l g o r i t h m ) 。 定义1 3 3 9 】算法的时间复杂性是指关于实例输入长度n 的函 数，( n ) ，用来表示算法的时间需要，对每一个可能的输入长度，它是 指在最坏的情况下该算法解此输入长度的实例时所需时间( 基本运 算步数) 。即对于输入长度相同的所有实例，把算法对这些实例的最 坏情况作为时间复杂性的度量。 如果存在一个多项式函数p ( 佗) ，使得算法的时间复杂性为d ( p ( 礼) ) ， 那么称该算法为多项式时间算法，否则称为指数时间算法。通过几 十年来人们在计算复杂性方面的研究，现今p p 的猜想已被基 本接受。所谓的n p h a r d 问题就是不可能在多项式时间算法内找到 最优解。从而，一个自然的想法就是放弃对最优解的寻找，而把研究 的重点转向寻找能在较短时间( 多项式时间) 内得到接近于最优解的 可行解，称为近似解。这种寻找近似解的算法也就是近似算法。 定义1 3 4 9 】n 是一个极小( 大) 化问题，i 是任意实例。设a 是 兀的一个近似算法，c a ( j ) 和伊p 丁( ，) 分别表示算法a 解实例i 所得 的目标函数值和相应问题离线情形下的最优目标值。在不引起混淆 时分别简记作c a 和c o p t ，记p a = 蔷；，则称 掣= s u j p 端 jl i j 6 平行机工件有到达时间的在线和半在线排序问题 为近似算法的最坏性能比。 求解离线和在线问题的算法分别称为离线算法和在线算法。其 中，l s ( l i s ts c h e d u l i n g ) 算法和l p t ( l a r g e s tp r o c e s s i n gt i m e ) 算法分别 是经典平行机排序问题的在线和离线算法。对排序问题的在线( 半 在线) 算法，我们用竞争比分析( c o m p e t i t i v ea n a l y s i s ) 研究它们的性能 保障，它属于最坏情况分析。 定义1 3 5 1 1 1 1 对极小化排序问题。称 c a = i n f c l p a c ，v j 为在线算法a 的竞争比( c o m p e t i t i v er a t i o ) 。同样的，对极大化排序问 题，称 c a = s u p c l l p a c ，v ，) c 为在线算法a 的竞争比。 称在线( 半在线) 问题( 极小化目标或极大化目标) 的竞争比下界 ( 简称为下界，l o w e rb o u n d ) 为c ，若不存在该问题竞比小于c 的在线 ( 半在线) 算法。同样可以定义在线( 半在线) 问题的竞争比上界( 简 称为上界，s u p p e rb o u n d ) 为e ，若不存在该问题竞比小大于c 的在线 算法。算法a 的竞争比等于该问题的下界或上界，则称a 为最佳 ( o p t i m a l ) 算法。这是从竞争比意义上来说，一个在线( 半在线) 问题 可能得到的最好结果。 定义1 3 6 【9 】启发式算法是一个基于直观或经验构造的算法，在 可以接受的花费( 指计算时间，占用空间等) 下给出待解决组合优化 问题每一个实例的一个可行解。该可行解与最优解的偏离程度不一 定可以事先预计。 评价启发式算法的性能只要分为两类，一是看算法占用的时间， 空间等；二是分析算法的效率。算法效率往往采用大规模的随机数 7 硕士学位论文 据进行实验验证，从平均的角度以及最坏的角度来进行衡量。 1 4 论文概述 本文主要研究了工件有到达时间在线和半在线排序问题，在线排 序主要考虑同类平行机上在线排序问题，可描述为：给定m ( m 2 ) 台 机器，记机器集为m = m ，m 2 ，) ，工件集j = ，j 2 ， ) ，s i 表示第i 台机器舰的加工速度，工件乃的长度为殇，到达时间为r ， 工件五可以放在任何一台机器坛上加工，在机器地上的加工时间为 譬，j = 1 ，2 ，n ，i = 1 ，2 ，m ，工件是逐个地到来，仅在当前工件安 排后才知下一个工件的全部信息，一旦开始加工则不允许中断，机 器在没有安排工件或工件没有到达时就是空闲的。本文主要针对同 类平行机当8 严i ( i i 仇一1 ) ，8 m = 8 1 的情况。 半在线排序问题考虑的是同型机器上的半在线排序问题，可描述 为：给定机器集m = 舰，m 2 ， ，2 ) ；工件集j = ，j 2 ， 厶) ，工件相互独立，工件如的长度为殇，到达时间为，所有工件逐 个地到来，且只需在其中一台机器上加工一次，安排当前工件时只 知道后面的工件加工时间不大于当前工件的加工时间，机器在没有 安排工件或工件没有到达时就是空闲的。本文主要针工件有到达时 间且工件的加工时间单调不增，机器没有加工速度的情况。 在第二章中，我们主要讨论工件到达时间任意的半在线排序问 题，我们假设工件加工时间单调不增，即p 。沈，根据著 名的l s 算法，当m 台机器时得到最坏性能比不大于2 一赢1 ，并证明 当仇= 1 时这个界为紧界。 在第三章中，我们主要讨论工件到达时间不减的在线排序问题， 即r l p 2 ，机器的加工速度为8 产i ( i i m 一1 ) ，s m = 8 1 ，对相同平行机的工件有任意到达时间的在线排序，当其中m 一1 台 机器的加工速度为1 ，而有一台机器的加工速度为8 l 时，证明列表 8 平行机工件有到达时间的在线和半在线排序问题 算法( l s 算法) 最坏性能比不大于m z n 1 + 外8 仇m 刈2 + 鬲m 两- 1 ) 。当其中一 台机器的加工速度为1 ，而有一台机器的加工速度为s 1 时，证明列 表算法( l s 算法) 是最坏性能比不大于2 。 9 平行机上工件有到达时间的在线和半在线排序问题 2 同型机上工件有到达时间且加工时间不增的半在线排序 2 1引言 由在线和离线的定义可以看出，从排序者对工件信息的了解程 度来看，它们分属两个极端情形。在实际问题中，出现这两种情况的 机会并不多，大量存在着的问题是排序者一方面不可能知道工件的 所有信息，另一方面可能掌握着比经典在线模型更多的信息或有着 更大的排序自由度，因而使问题变得比离线相对“困难 一些，但比 在线相对“容易”一些，即可能得到比在线算法性能更好的算法。因 此1 9 9 6 年提出了难度介于在线和离线之间的模型，称为半在线排序 问题。 何勇，杨启帆，谈之奕在文【1 l 】中将半在线问题分为三类： ( 1 ) 第一类半在线模型：不满足在线基本假设( 1 ) 工件的信息是 逐个释放的( 即某个工件的信息只有在排序者对此工件之前的所有 工件作出安排后才会被排序者所知) 的半在线模型，即排序者掌握 后续工件的部分信息。如已知工件总加工时间，已知工件最大加工 时间，工件加工时间在一个区间，工件加工时间非增，已知实例最优 解值等。 ( 2 ) 第二类半在线模型：不满足在线基本假设( 2 ) 工件加工顺序 不可以改变( 即一旦将工件安排给某台机器加工，在其后的任何阶 段不能以任何方式加以改变) 的半在线模型，即已安排的工件的加 工进程可通过某种方式加以改变。如带缓冲区，两个并行处理子系 统等。 ( 3 ) 第三类半在线模型：不能列入前两类的半在线模型。如已知 1 】 硕士学位论文 工件加工时间序等。 本章考虑工件集l = ，j 2 ，厶) 中的所有工件满足工件加工 时间单调不增，即p 。p 2 p n 且工件到达时间任意的同型平 行机问题。目标为极小化机器最大负载。 同型机且工件到达时间为零在线排序问题，g r a h a m 在文【1 2 】最先 提出了著名的三s 算法，并证明了l s 算法的竞争比为2 一去。1 8 9 8 年f a i g e ，k e r n ，t u r a n 在文【1 3 】证明了当m = 2 ，3 时厶s 算法为解此问 题最优在线算法。1 9 9 3 年g a l a m b o s w o e g i n g e r 在文【1 4 】证明了当m 4 时l s 算法的竞争比下界为1 + 以，又对于m 4 的情况，1 9 9 4 年 b a r t e l e t a l 在文【1 5 】进一步证明得到竞争比下界为1 8 3 7 。c h e n e t a l 在 文 1 6 】提出了m l s 算法优于l s 算法。 同型机上工件到达时间为零且加工时间单调不增的半在线问题， 对p 仇i n d 仡一i n c r e a s i n g 歹d 6 f g 妣的半在线问题，1 9 6 9 年g r a h a m 在文【17 】 得到l s 算法的竞争比为2 一磊1 。2 0 0 0 年s e i d e ns , s g a l lj , w o e g i n g e rg 在 文【1 8 】中得到当m = 2 时，l s 算法为最佳算法；当m ：3 时，问题的 下界到少为鼍乎。对p m ，r i n o n i n c r e a s i n g 歹d 6 i g m 的两种目标下 半在线问题，即机器带有准备时间的半在线问题，1 9 9 1 年l e ecy 在 文【1 9 】得到l s 算法的竞争比为；一去；谈之奕，何勇在文 2 0 】证明 了当m = 2 时，l s 算法为最佳算法；当m = 3 时，问题的下界至少 为学。 对于工件到达时间不为零同型机器在线排序问题，这种模型首先 由l i h u a n g ( 2 0 0 4 ) 在文【2 1 】提出的，在这篇文章中得到以下结论：1 ，l s 算法得到竞争比为3 一去并证明了算法是紧的。2 ，当m 2 时提出了 一种优于l s 算法的m l s 。3 ，证明了在启发式算法中，没有一个算法 得到的界会小于2 。 工件有到达时间的半在线排序问题，2 0 0 7 年r o n g h e n gl i h u e i - c h e nh u a n g 在文【2 2 】中提出了工件加工时间相近的问题，即p 1 2 平行机工件有到达时间的在线和半在线排序问题 【1 ，r 】，r 1 ，根据著名的三s 算法，证明了对任意的m 2 ，当r 旦m 时最坏性能比不大于一鬲一；，当sr 器时最坏性能比不大于- - 1 3 1 1 1 1 + 南+ 业m ( 1 + 2 r ) ，并证明了当m = 1 时的最坏性能比不大于1 + 南 且此界为紧界。当m = 2 时，证明了l r n i a t 。因此： b a 7 + p z j + 让1 了r 1 - 一a 7 1 ) ， 目标为极小化机器最大负载。 对于同类机工件到达时间为零的问题，该问题由g o n z a l e z 等人1 9 7 7 年 在文【2 3 】中第一次提出，对于在线情形，关于一般机器数1 1 1 ，1 9 8 0 年c h o ， y s a h n i ，s 在文【2 4 】得到当1 = 8 1 8 2 8 m ，m = 2 时l s 算法 的竞争比为学，m 3 时竞争比为1 + 挈，当s 。= s 。= = s m l = 1 ，s m 1 ，m = 2 时的竞争比为学，m 3 时竞争比为3 一熹 2 0 0 0 年b e r m a n 等人在文【2 5 】得到竞争比为3 + 锈5 8 2 8 ，并证明 问题的下界为毒潦4 3 1 1 。此外，关于机器数1 1 1 取较小的值时，也 有一些零星的结果。例如：当1 2 1 = 2 ，e p s t e i n 等人在文 2 6 证b j j 了l s 是可 能存在的最好的在线算法，其竞争比为i n i n 等，兰譬) ，这里的s 为) j n - r 速度较快的机器与加工速度较慢的机器两者的加工速度的比值。而 当m = 3 ，闵啸在文【2 7 】考虑了s 。= 8 ，8 2 = 8 。= l 这一特殊情形，他证明 了l s 算法的竞争比为m i n 等，曼芋) ，并证明了当s 2 时，l s 算法是可 能存在的最优的在线算法。当m = 3 时，2 0 0 6 年蔡圣义在文 2 8 i 正n 了 当s 。= s 2 = 8 1 ，s 3 = 1 这一特殊情形下的q 3 l i g m ，l s 算法的竞争比 曲m ；n f t 绁2 8 + 1 ，龇2 81 j ，同时证明当s 3 时，l s 算法是可能存在的最好的在 线算法。 关于同类机工件有到达时间的问题，何晓琼在文f 2 9 】考虑了s 。= 2 1 硕士学位论文 8 ：= s m 一1 = 1 ，s m = 8 1 的情况，证明了当机器数为m 时l s 算 法的竞争比为3 + 黜，当m = 2 时得出竞争比为2 + i 1 并证明了 l s 算法是紧的。 平行机工件有到达时间的在线和半在线排序问题 3 2 q m l i z 问题 定义：l = r ，b ，r ) ，s 1 = s 2 = = 8 m - l = 1 ，s m = s 1 工件 有到达时间且r 1 r 2 他r n 引理3 2 1 ：阢馏( l ) 一警( 1 i m ) 证明：因为对于任何一个工件a ，都有 假设p i 是紧跟在第i 台机器最后一个空闲区间的工件，那么阢 n ，又r n + 堕8 c 徽o p z t ( l ) ，所以 阢o p t ( l ) 一警 定理3 2 1 ：在l s 算法下，如果8 1 = 8 2 = = 8 1 = 1 , s m = 8 1 ，r 1 r 2 r 3 r n ，则 躺卿哪+ 南 2 + 熹) 证明：假设肌是最后一个工件。我们不妨设的完工时间既为 c l s ( l ) ，由l s 算法，我们有 则 s + m s q l m s z ( l ) ，鼠+ c 勉( l ) ，i = 1 ，2 ，m 一1 l s ( 眺些鼍蔫掣 因为阢表示在三s 算法下第i 台机器上面的空闲总和。由引理3 2 1 ， 可以得到阢+ p t l j 3 u 门懈o p t ，z = 1 ，2 ，m h t + 它 s u c 。w ) + 譬+ 一些塑擎 c 景乏( l ) + 一馏( l ) 2 4 平行机工件有到达时间的在线和半在线排序问题 整理得 c 曩毛( l ) 日f 一| m + 2 铭o p t ( l ) 否则若m 在o p t 算法下没有安排在上，则有p n c 2 p t ( l ) 并 且有 c 景乞( l ) 凰+ 陬凰+ c 2 翟( l ) 甄+ 2 c 2 2 ( 三) 一，i = 1 ，2 ，m 一1 不管什么情况都有 c 曩乞( 三) 凰一+ 2 o p t ( l ) 对于m 有，s 诺鑫( l ) s + 则 s u 一，v r ；$ - 1 ( t + 2 c 岩器。( l ) 一) 苒嚣了砑焉亿丁一 盟型显哿警罐瑟垃业些 饕1 乃+ 答1u i + s u + 2 ( m 一1 ) c 景器( l ) 一( m 1 ) k 再丽j 面需甄可一 f 堕竺型鲻o 此p t 出型坚坐戮o p 酷t 等茬并希p o 越p t 旦尘坐= 三监o 丝五p t 盟，s m 一1 ， j ( s + m 1 ) c 鬻器。( l ) u 二 二l 业业鲻o p t 南蔫擞o p t 前2 删o p t ，s 1 工件有到达时间且r 1 t 2 r a r n ，则 黜2铝罄( 三) 二。 证明：情况1 ：碟鑫( 己) = f 1 设工件只是l s 算法下尬上最后一个工件也是工件集最后一个 工件( 如果工件只后面还有其他的工件来的话，在l s 算法下我们可 以去掉工件只后面的工件，对于砩鑫( l ) 没有改变它的值，对于原 来的c m a o p t ( l ) 变小了，因此对于竞争比将比原来的竞争比要大，因 此，我们可以假设工件只是最后一个工件) ，即r 是尬上最后一 个工件。 情况1 1 ：r 磷翟( l ) 在o p t 算法下，工件r 一定安排在上加工，并假设t 是o p t 算法下移出机器的工件和，因此在o p t 算法下有： o p t ( 驼马一i t 一巩 - t - 譬 在l s 算法下，工件r 安排在机器上m 加工，而没有放到机器 上加工，由l s 算法得： f 2 + 等c 景：( l ) 又t 是在o p t 算法下移出机器尥的工件和，而机器尬的加工速度 为8 1 = l ，所以有t 嚷翟( l ) ，由引理3 2 1 知道巩锈翟( l ) 一争， 把结论 pd 岛+ 譬c 景乞( 已) ，t o p t ( l ) ，观c m a x o p t l ) 一孕 2 6 平行机工件有到达时间的在线和半在线排序问题 代入磷翟( l ) 如一吾一巩+ 譬可有： o p t ( l ) f 2 一r 。一巩+ 争 l s ( l ) 一牮一( 锱o p t ( l ) 一譬) l s ( l ) 一掣o p t 一馏( l ) + 争 又由r 磷翟( l ) 得 啪o p t ( l ) c 景盘( l ) 一旦星幽8一c 紧o 凹p t ( l ) + p _ 。a l s ( l ) 一垡盛8 丑盟一咪o 们p t ( l ) + 华 整理得：鳄翟( l ) 砩鑫( l ) 一嚷翟( l ) ， 即 嗽( l ) o 碾丽i z 情况1 2 ：r 暖鍪( l ) 在l s 算法下，工件r 安排在机器尬上加工，而没有放到机器 上加工，由l s 算法得局+ 譬q l m s ( l ) ， 整理得： s 足s c 鬻l s ( l ) 一r 式子两边同时加上只= c 恐( 己) f 1 + s f 2 c 景乞( l ) 4 - s c 鬻