（运筹学与控制论专业论文）工件具有相似长度的半在线排序问题.pdf

摘要 本硕士论文由三章组成，主要讨论两类在m 台平行机器上加工的工件具有相似 长度的半在线排序问题第一个问题是对于在m 台同型机器上加工，具有相似长度， 即工件的加工时长在【1 ，r 】内的情况，通过对l s 算法的分析，得出了改进的最坏情 况性能比第二个问题是考虑工件在m 台同类机器上加工，有到达时间，具有相似 长度，提出了一个新的算法，并得出了相应的最坏情况性能比 第一章介绍了问题研究的背景和该领域的研究现状，主要介绍了一下最坏情况 性能比，机器的分类，等基础知识 第二章分别从两个方面对l s 算法在第一种情况下的最坏性能比进行分析，得 到了改进的结果 第三章对于第二个问题，构造新的算法，证明其最坏情况性能比 关键词：最坏情况性能比，到达时间，相似长度 a bs t r a c t t h i st h e s i so fm a s t e ri sc o m p o s e do ft h p e ec h 印t e r s w bm a i l l l ys t u d yt w op r o b l e m so fs e m io n l i n es c h e d u l j n gw i t ht h ej o b1 e n g t hj n f1 ，r 】o nmp a r a l l e lm a c h i n e s t h ef i r s tp r o b l e mc a nb ef o m a l l yd e 丘n e da l sf o l l o w s as e q u e n c eo fj o b sj st ob e s c h e d u l e do nm p a r a l l e li d e n t i c a lm a ( h j n e s i nt 址ss e m io n - l i n es j t u a t j o n ，t h ej o b s s r e l e a s et i m e sa 弛n o m a l l yn o n d e c r e a u s i n g w es t u d yt h ec o m p e t m v er a t i oo fa 1 缈 r i t h ml st h e no b t a i nab e t t e rr e s u l t t h es e c o n dp r o b l e mw _ es t u d yt h es i t u a t j o na s e q u e n c eo fj o b si st ob es c h e d u l e do nmp 甜a j l e lu n i f o r mm a c h j n e s i nc h a p t e rl ，i n t r o d u ( e st h eb a c k g r o u n do ft h ep r o b l e m r e s e a r c h j n ga n dt h e r e c e n td e v e l o p m e n to ft h er e s e a r c hi nt h j sf i e l d b e s i d e s ，w ，e 百v eb a s i cn o t i o no f c o m p e t i t i v er a t i o n ，甜g o f i t h ml s ，a n ds 0o n i nc h 印t e r2 ，、艴m a j n l ys t u d yt h ec o m p e t i t i v er a t i o no fa l g o r i t l l i i ll sf 如mt w o d j h 色r e n ts i d e s 锄d1 7 l 陀o b t a i ns o m er e s u l t s i nc h 印t e r3 ，w e 舀v ean e wa l l g o r i t h mf o rt h es e c o n ds i t u a t i o n 锄dp r o v et h e c o m p e t i t i v er a 土i o n k e yw o r d s ：c o m p e t i t i v er a t i o n ，a r r i v a jt i m e s ，s i m i l a rl e n 昏h s i i i 工件具有相似长度的半在线排序问题 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品 成果对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：7 麦；罩 勿。7 1 年6 月弓日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件 和电子版，允许论文被查阅和借阅本人授权湖南师范大学可以 将学位论文的全部或部分内容编人有关数据库进行检索，可以 采用影印，缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打”，) lrilrl 五，、 月月年年 砰文卅彳 期期 日日 丁 亏祷 考 ，一 隐镶 李 名名 签签 者师作导 工件具有相似长度的半在线排序问题 1 绪论 排序问题是组合优化中一类重要的问题，有着广泛的实际应用背景， 在生产管理和调度，网路通讯及理论计算机科学等方面有着广泛的运用 人们对各类排序问题的研究越来越深入，并且取得了一系列好结果 1 1 问题产生的背景 从最优化的角度来说安排时间表( s c e d u z i 哪) 是为完成若干项任务而 把所需要用到的人、财、物等资源按时问进行最优分配，最优排序，和最 优调度我们应该把“排序理解为两种涵义：狭义的涵义是安排次序；广 义的涵义是安排时问表排序领域内许多早期的工作是在制造业的推动 下发展起来的，所以在描叙排序问题时很自然会使用制造业的术语虽然 排序问题在许多非制造业的领域内取得了相当有意义的成果，但是制造 业的术语任然经常在使用，因而，往往把资源称为机器，把任务称为工件 有时工件可能是由几个先后次序约束相互联系着的基本任务所组成这 种基本任务称为工序例如，对门诊病人到医疗诊所看病的排序问题也描 叙成为“工件 在“机器”上“加工的过程排序论中的“机器 和“工 件”已经不是机器制造业中的“车床 和“车床加工的螺丝”，已经从“车 床 和“螺丝 等具体的事物中抽象出来，是抽象的概念“机器 和“工 件 与“车床和“螺丝”的关系是“一般”与“特殊”，“抽象 与“具 体 ，理性“与“感性，“理论”与“经验 ，“概念 与“感觉 的关系 排序论中的“机器”可以是数控机床、计算机c p u ( 中央处理器) 、医生、 机场跑道等“工件”可以是零件、计算机终端、病人、降落的飞机等例 如，计算机科学并行计算机的出现，促进排序论中对多台平行机的深入研 究；反过来，排序论中的平行机可以应用到具体的计算机科学并行计算机 中去，平行机排序的成果在一定程度上推动并行计算机的发展 】 湖南师范大学2 0 0 9 届硕士学位论文 因此，在排序论中，工件是被加工的对象，是要完成的任务；机器是提 供加工的对象，是完成任务所需的资源；安排时间表是在一定的约束条件 下对工件和机器按时问进行分配和安排次序，使某一个或某一些目标达 到最优 l s 算法是目前考虑工件在平行同型机器上加工的在线排序问题中所 使用的最简便和常用的算法，它是由g r a h a m 【1 】在1 9 9 6 年提出的这个算 法把工件总是安排在使得最后完工时间最小的机器上当机器的到达时间 都足零，且不允许中断加工，目的是最小化最后完工时问时，这就是一个 经典的n p 难题【2 】了，我们把这个问题表示为p i | 对于这个问题， g r a h 锄证明l s 算法的最坏情况性能比是2 一去此后新的算法不断提 出，这些算法的最坏情况性能比被证明比l s 算法要好一点 3 ，4 ，5 ，6 】 f 8 谢e ，k e r 礼e 2 和t u r b 礼【7 】在1 9 8 9 年证明了l s 算法对于两台机器和三 台机器来说是最优的在线排序算法这即是说，对于p i | ，当m = 2 和 m = 3 时任何一个在线排序算法的最坏情况性能比都分别不会小于；，和 ；近年来新的半在线问题不断的出现，在 8 】中考虑的是工件的加工时长 不增的情况，并且对m = 2 和m = 3 的情况提出了最优的在线算法，他们 的最坏情况性能比分别是和；在【9 】中讨论了两台机器上具有缓冲器 的半在线排序问题，只要缓冲器有空闲，则就可以将当前的工件根据算法 安排在机器上或足缓冲器上，并证明了最优的半在线算法的最坏情况性 能比为这个结论在【l o 】中也被独立的证明了对于工件有任意的到达 时间的半在线问题r m 9 e n 夕勘和日“e i c 牡e 几日仳o n 夕【1 1 】证明了l s 算法 的最坏情况性能比为3 一去并且这个比值足紧界在【1 2 】中讨论的是已知 所有工件的加工时长的半在线问题在 1 3 ，1 4 】中探讨了工件具有相似长 度，工件加工时长不增等半在线排序问题在1 5 ，1 7 ，1 8 ，1 9 1 中更多的半 在线排序问题被提出和研究 2 工件具有相似长度的半在线排序闯题 1 2 预备知识 排序问题一般可描述为给定一个工件集，要在特定的机器集上加工， 在满足一系列约束条件的前提下，给出一个工件的加工方案，使得给定的 目标函数达到极大或极小近年来，由于时间生产的需要，对于工件有到 达时间，且工件具有相似长度的半在线排序问题引起了大家的注意 到达时间：所谓工件的到达时间是指每一个工件都有它到达的时间 ，其中j = 1 ，2 ，m 只有在到达时间之后工件才能在机器上加工， 所以到达时间也就是工件可以开始加工的时问显然工件从零时间开始 加工，是工件有到达时间的一种特殊情况 相似长度：工件中加工时长最长的工件和加工时长最短的工件加工 时间之比为一常数r ，则我们说工件具有相似长度，在本文中表示为工件 的加工时长在【1 ，州内 根据确定排序时了解的工件信息的多少，常将排序问题分为在线和离 线离线排序指的是在排序前，工件所有的信息都已知；而在线排序指的 是，工件一个一个到达，只有在到达后才知道它的所有信息而介于两者 之问，即在排序前只知道部分工件的信息称为半在线排序例如，有无到 达时间，是否具有相似长度，是否允许中断加工等 3 湖南师范大学2 0 0 9 届硕士学位论文 近似算法和最坏情况性能比 由于绝大多数排序问题是p 难题，其最优解往往很难找到，而且实 际应用中往往也没有必要去找到最优解，只需找到满足一定要求的启发 式解或近似解因此研究排序问题主要有两个方向一是对p 问题，即可 解问题，寻找多项式时间算法来得到问题的最优解，或者对于p 难题在 特殊情况下寻找有效算法二是设计性能优良的启发式算法和近似算法 当然无论是启发式算法还是近似算法都应该是多项式时间的算法实际 上n p 难题可解情况的多项式时间算法往往是可以作为n p 难题本身的 启发式算法和近似算法衡量一个算法的”优良”程度有三种办法：数值 算例计算，最坏情况分析和概率分析这三种办法各有优点，也各有不足 之处在理论分析( 最坏情况分析和概率分析) 之前进行大量的算例计算 是非常有用的方法一则可以对理论分析给出估计和提供思路再则可以 与已有的算法进行实际比较目前理论上用的最多的是算法的最坏情况 分析，顾名思义最坏情况分析是分析算法在最坏的情况下的性态因此， 通常用最坏情况分析得出的最坏情况性能比来衡量在线或半在线算法的 优劣 ，为最小化问题，记j 是这个优化问题的一个实例，p 是所有实例的 全体；并记，( ，) 是实例，的最优目标函数值( 即最优值) 向( ，) 是算法 日的目标函数值如果存在一个实数r ( r 1 ) ，对于任何j p 届( ，) r 厂( n 那么称r 是算法h 的一个上界如果不能确定算法是否有界，或者能够 确定算法的上界是无穷大时，这个算法称为启发式算法当r 是有限数 时，这个算法称为近似算法对于使上式成立的最小正数r 称为是算法 的最坏情况性能比表示为 一u p 锵 4 工件具有相似长度的半在线排序问题 机器的分类 机器可以分成两大类：通用平行机和专用串联机对于不允许中断加 工的情况来讲，一个工件在m 台平行机上的加工是只需要在这m 台机器 中的任何一台机器上加工一次；一个工件在m 台串联机上的加工是需要 在这m 台机器中的每一台机器上都加工一次平行机又可以分成三类：同 型机、同类机和非同类机同型机指机器具有相同的加工速度同类机是 指机器具有不同的加工速度，而且这个速度不依赖于工件非同类机是指 机器随加工工件的不同速度也不同串联机也可以分成三类：每一个工件 以特定的相同的机器次序在这些机器上加工的流水作业；工件依次在机 器上加工的次序并不指定可以任意的自由作业和每一个以各自特定的机 器次序进行加工的异序作业本文所涉及的机器主要是平行机里面的同 型机和同类机 5 工件具有相似长度的半在线排序问题 1 3 本文的主要工作 本硕士论文的主要工作为：一是考虑工件的到达时间不减且工件的 加工时长在【1 ，川内，分析l s 算法的一个最坏情况性能比我们得出的主 要结论 i1 十紫+ 警， 1 冬r ； 冗( m ，l s ) 1 + 生掣，i 2 二是考虑在m 台同类机器上加工，工件的加工时长在【l ，r 1 内，提出了一 个新的算法，并得出了新算法的最坏情况性能比为 冗4 + 辈掣 7 工件具有相似长度的半在线排序问题 2 工件具有相似长度且到达时间不减的半在线排序问题 2 1引言 当工件到达时间不减r 日髓和日c 日让o n 9 【1 4 】给出了l s 算法的一个 最坏情况性能比r ( m ，l s ) = 2 一去，当不考虑工件的到达时间只考虑工件 的加工时长在【1 ，计内，y 日e 和g z 九o n 9 【1 2 】给出了一个当r 2 时的l s 算法的一个最坏情况性能比基于上述问题和思想，本硕士论文的主要工 作为：考虑工件的到达时间不减且工件的加工时长在f 1 ，r 】内，分析s 算 法的一个最坏情况性能比，并得出了相似的结论 9 丁件具有相似长度的半在线排序闷题 2 2对l s 算法的最坏情况性能比的分析 首先我们介绍一下什么是l s 算法 定义1 设三= 歹- ，歹2 ，矗) 是一个工件集合，工件也0 = l ，2 ，n ) 的到达时间为，加工时问为乃有m 台机器可以同时加工工件，算法a 是一个启发式算法令c ( l ) 表示按照算法a 排序工件最后完成加工 的时间，磷翟( 三) 表示按照离线的最优算法排序工件最后完成加工的时问 那么算法a 的最坏情况性能比根据定义可得： 跏，a ) 唧黜 定义2 设易是当前要加工的工件，它的到达时间为吩，加工时间为 殇机器必存在一个空闲时间陬，正】可以加工工件易，当它满足以下两 个条件： 1 机器尬在时间m ，死】段是空闲的并且有工件在肱上加工，开始 加工时问是正 2 乃一m o z 乃，吩) 渤 l s 算法 第一步：设厶是机器尬的加工完成时间，重排机器使得l ，l 2 k ，厶是一个新到的工件，它的到达时间为，加工时长为肌 。 第二步：如果存在一些机器有空闲m ，乃】可以加工工件厶，选择其中 五最小的机器加工工件，开始加工时问为m n z 乃，r n ) 否则，转入第三步 第三步：令s = m n z ，l t ，工件在地上加工，开始加工时间为s 湖南师范大学2 0 0 9 届硕士学位论文 定理2 1 当工件有到达时间且到达时间不减，工件的加工时长在【l ，r 1 内，l s 算法的最坏情况性能比是： 跏瑚，拦r 1 r i 2 本文通过分情况讨论来证明定理假设存在一个工件集合l = d 。，歹：，a ) 对于任何工件序列三，当l l 三i ，定理2 1 式都成立，但对于l 本身定理 2 1 式是不成立的，我们称l 是一个最小反例，其中l li 表示l 中工件的 个数下面的讨论基于l 是最小反例的情况展开 情况1 首先我们讨论r 2 的情况设在l s 算法排序中至少存在一 个空闲 q ，6 】，口 6 ，其中6 为所有空闲中末端值最大的一个的下面我们 证明当62r 时，有 r ( m ，硐1 + 譬+ 譬 ( 1 ) 设集合a 表示工件乃的集合，其中易表示在l s 算法中在6 点后才 能加工完成的工件令b 是a 的子集，且b 中的工件的开始加工时间要 不晚于o 定义s ( 易) o = 1 ，2 ，礼) 表示工件易在l s 算法中的开始加工 时间，则集合b 我们可以表示为： b = 易1 6 一乃 口对于 乃a b 如果有巧 6 和吩 s ( 易) 同时成立，我们将推出矛盾 令曩表示在l s 算法中工件乃安排前第必台机器的完工时间根 据条件在l s 算法中，至少有一个机器在 n ，6 】段是空闲的，设这台机器为 舰。；另设舰。，表示工件乃安排在这台机器上由于乃 s ( 易) 且乃根据 算法第三步安排，所以有o s ( 如) = 砭 12 工件具有相似长度的半在线排序问题 另一方面，由于有巧 o ，在三s 算法中 至少存在一个工件以有s ( 乃) 口，且s ( 占) 一巧= h ，s ( 易) 】是在。之 前的一个长度为的时问段因为在五安排之前，没有工件的到达时间 大于吩，事实上s ( 易) 一巧= o 且s ( 如) = m 饥【0 卜= 1 ，2 ，m ) 所以这 个时间段所有的机器都在加工工件此外，在【6 ，l ，】这个时间段中所有的 机器都足在加工工件的，并且在任意一个时间段至少有一台机器是在加 工工件的，根据这些结论我们得出了离线最优算法的又一个下界： 程( 驼堕型址芋必 ( 3 ) 由( 2 ) ( 3 ) 两式我们可得： 2 铝翟( 驼型出攀 ( 4 ) 1 3 湖南师范大学2 0 0 9 届硕士学位论文 变形得： 2 m 谨( l ) 2 m ( l 1 + ) 一( m 一1 ) 6 2 ( m 一1 ) 鳓 因为r n 6 ，所以可得： c 2 2 ( ) 6 + 对于最小反例而言显然有 c ( l ) = l 1 + 孙 根据上面的式子我们得出最坏情况性能比为： 砩鑫( l ) l 1 + p n 一：= 一 职擘( l )嚷髻( l ) ! 里盟星墨2 ! 竺二1 2 1 兰! 竺二1 2 堡 一 2 m ( 碟名( 上，) ，( m 一1 ) ( 6 + p n ) ( 仇一1 ) p n 1 + 专蘸巅矛+ 赢捅 ，( 仇一1 ) ( 6 + ) ( m 一1 ) 鳓 1 + 专蘸未斧+ 赢翁 l + 譬+ 蒜啬 当6 r 时， ，( m 一1 ) ( m 一1 ) 1 + 气+ 荔再筠 因为1 + + 踹是关于的增函数，所以： 黜外掣+ 掣 ( 1 ) 式得证 当在l s 排序中没有空闲出现，则我们可以把这种情况看作是6 = o 的 特殊情况来讨论，6 = o l r ，下面我们接着证明 工件具有相似长度的半在线排序问题 当6 ( ，一1 ) c 2 詈( 己) ( r 一1 ) 七 从而有( 七一1 ) r 七所以有 r 击 ( 9 ) r 西 ( 9 ) 对于七来说由是减函数，因此对于所有l i 克来说( 9 ) 式都成立， 即有 ( i 一1 ) r 7 七+ r 一七一l 变形得 后+ 1 r 七 所以 c 2 2 ( l ) ( 七+ 1 ) r 七c 景蠹( l ) 从而推出了矛盾 根据佗的不同取值我们分两种情况进行讨论在接下来的分析中首先 我们来定义一些字符，令& j 表示按照l s 算法工件功安排后机器舰上 加工工件的集合；表示按照离线最优算法算法工件岛安排后机器舰 上加工工件的集合l ( s ) 表示集合s 中所有工件的加工时长之和，其中 ( i = 1 ，2 ，m ) 情况1 1 当n = m k ，由结论1 可知i s 。俨m i = i 岛扩m l = = 1 护m l = 愚一1 ，= u 墨1 & ，n m u p n m + l ，一m + 2 ，) 由结论2 可知i s n i = l $ ，n i = = l 踮， l = 忌，j = u 銎。爰n 1 r 工件具有相似长度的半在线排序问题 引理2 1 对于任意的注1 ，2 ，m ，存在某个歹 1 ，2 ，m ) 使得 i & 扩mu 加n 鬈n i 【警j 证明：我们只需证明i = 1 的情况，当i = 2 ，m 时证明过程相似现用 反证法证明，当引理不成立时我们有 慨加mu n 露n i 【掣j 一1( 1 1 ) 其中歹 1 ，2 ，叫l ，显然( 1 1 ) 式是歹= 1 ，到j = m ，这m 个式子的通式， 把这m 个式子连加起来得： i 一mu n 耶m 【半j - m = m 【等j 七一l 由此我们可得l & ，n m i 七一2 ，这与i ，n m i = 七一1 矛盾，所以引理得证 在l s 算法中纯m + l + 2 ，p ( m ) m 分别在不同的机器上加工，肌决 定最后的加工完成时间，由此我们得到： 韶( l ) 躁，j = 1 ，2 ，m ( 1 2 ) 砩鑫( l ) = m a x z ( & ，疗一m ) ，z ( 岛，n m ) ，z ( 岛，n m ) ，+ ( 1 3 ) 假设第i 台机器决定了l s 算法的最后完成时间，就有： c 怒( l ) = z ( & ，n m ) + 因此存在某个歹使得： 斑( ) 一韶( l ) z ( j s ；f ，n m u 慨) f ( n ) 17 湖南师范大学2 0 0 9 届硕士学位论文 由引理2 1 可知在集合& m mu 如n 和鬈n 中，最多有一l 警j 个不同 的工件又因为 尼一l 幽l 七一生 蛐 所以 一mu 协沪z ( j 5 ：；：n ) 坠掣 又因为有铝孑( 三) 七从而有： 躺外掣 情况1 2 当n = ( 七一1 ) m + 危时，其中1 九 和s n 中，最多有七一( 【鲁j 一1 ) 个不同 的工件又因为 忌嘉j - 1 ) 七一1 一条导南 所以， 慨一 u 帆) ) _ f ( s n ) 冬坠等型七 又因为有磷翟( l ) 后从而有： 躺外掣 由情况1 1 和情况1 2 的分析，我们得出结论，当b r 时，有r ( m ，l s ) 1 + 迎掣，( 7 ) 式得证 由1 式我们有当6 ，时，r ( m ，工s ) 1 + 掣+ 半，由7 式我们有 当6 r 时，兄( m ，l s ) 1 + 垃掣，显然，对于，来说，秒= 1 + 岩+ 岩 是常数函数，而可= 1 + 虹掣是增函数易得当，= 三时， 1 + 譬+ 掣 所以当1 r i 时1 + 虹掣1 + 竽+ 孚；当i 2 时有 r ( m ，三s ) 2 一去 ( 1 6 ) 湖南师范大学2 0 0 9 届硕士学位论文 由( 5 ) 式可得： 2 mc ：昭( l ) 2 m ( l l + 弧) 一( m 一1 ) 6 2 ( m 一1 ) 2 m ( l l + 鳓) 一2 ( m 1 ) 6 2 ( m 1 ) ( 1 7 ) 所以： c 茏鑫( 三) 三1 + 铝擘( l )勰嚣( l ) 2 m g 2 罂( l ) + 2 ( m 一1 ) 6 + 2 ( m 一1 ) p n 二 2 m 暌翟( l ) 2 m 嘤( l ) + 2 ( m 一1 ) ( 6 + ) 二 2 m 碟翟( l ) 外锗 外鬻 m l = ：i lj 2 的情况，2 一去在【l4 】中也被证明是紧界我们的初衷是将r r p 表示在五之前 就已经开始加工的所有工件的集合因为机器从。时开始就加工工件，所 以驴不是空集令l 一= l l o 显然对于l s 算法l 一和l 有相同的最后 完工时问，而对于最优算法三一的最后完工时间不会大于l 的最后完工时 间，所以对于l 一而言最坏情况性能比不小于l ，因此l 一对于( 1 8 ) 也是 不成立的，另一方面，三一是l 的子集，所以对于任何旧i i l l ，( 1 8 ) 式都 成立，所以l 一也是一个最小反例，这与l 是最小反例矛盾所以单台机 上没有一个空闲是大于r 的 下面我们来证明定理3 1 ：令a r 表示所有空闲中最大的空闲由引理 3 1 可知a 1 假设在整个l s 排序中存在后个空闲，钍；，纯分别表示第i 2 3 湖南师范大学2 0 0 9 届硕士学位论文 个空闲和紧跟在后加工的工件江1 ，2 ，后则有 则有 戤lt = 1 ，2 ，礼 ( 1 9 ) 七 谨( l ) ( u t + 鼽) ， ( 2 0 ) = 1 憩( l ) 妻n ， ( 2 1 ) 由上面可得： 铝鑫( l ) ，l 1 + 礴酉面两蓼面 圣! 堡圣垒! 竺 一 铝髻( l ) 外蕊 l + ；叁! 丝 一 。笔1 ( “f + 鼽) 弋、片 1 + 一每i 三! 竺 一 。怎l ( 乱i + 1 ) 因为1 + 赫对于冬- 来说是增函数，而且有冬。地七a r 所以 有 1 + 黑 = 1 + 鼎 因为1 + 晶对于q 来说是增函数，而且有口1 所以有 1 + 南 即是菇鹇1 + 南，定理得证这个定理的证明出自【1 l 】，此处仅为引 用 工件具有相似长度的半在线排序问题 下面介绍新的算法首先我们定义几个符号；三4 ( 七) 和己( 尼) 分别表示 在最优算法中和新算法中第七个工件完工时所有机器中的最大的那个完 工时间我们给定一个参数a ，令a ( 七) 坛表示第t 台机器，s ；表 示第l 台机器的加工速度，其中( i = 1 ，2 ，m ) 我们将机器按速度从慢 到快的顺序排列好，尬和 分别表示机器加工速度最慢和最快的机器， s 。s 2 5 m ，所以机器下标越小表示机器的加工速度越慢我们的目 的是安排工件使得l ( 七) 尽可能的靠近a 算法l 第一步：当工件七到达的时候，如果把它放在任何一台机器上加工都 使得工件在此台机器上加工后它的最后完工时间大于( 1 + 珥字) a ，则我 们说算法失效，算法终止否则，转入第二步 第二步：如果存在一些机器中有空闲可以加工工件，使其完工时问不 大于( 1 + 等掣) a ，则令这些机器中最慢的一台机器为尥，转入第三步否 则，转入第四步 第三步：在所有加工完工件七后完工时问都不大于( 1 + 等孚a ) 的机 器中令速度最慢的一台机器为坛，令c = m i n 口，耐，将工件安排在必上 加工，我们说算法有效，重复第一步 第四步：在所有加工完工件七后完工时问都不大于( 1 + 珥字a ) 的机 器中令速度最慢的一台机器为坛，把工件放在舰上加工，我们说算法有 效，重复第一步 第五步：当所有工件安排后，算法没有失效，我们说算法总是有效 在接下来的讨论中，在不产生歧义的情况下我们都将己( 七) 和l ( 忌) 分 别用更加简单的符号矿和三来表示f i ( 歹) 表示工件j 加工完成后第i 台 机器上的完工时间鼽( 歹) 表示工件歹放在第i 台机器上的加工时间方便 起见，我们定义一个性能比p ：算法1 接受先前定义的参数a ( 人l + ( 七) ) 2 5 湖南师范大学2 0 0 9 届硕士学位论文 并且使得所有机器的最后完工时问都不会超过肚也就是说，当a a ，显然有l a ； 情况2 ：当r 一a ，因此从a 时开始到皿中每台机器上的最后一个工 件加工完成中间都是没有空闲的，而且每台机器上的这一段时间都大于 a 这是因为厶之2 a ，所以厶一7 一 a ，因此能得出 云 ai ： + 1 ， + 2 ，m( 2 5 ) 由( 2 5 ) 式司知 p & + 1 人+ s a + + s m 人 ( 2 6 ) 讵雪j 最 所以 r 吣 中j & 黝) f 鱼堡! 鱼! 曼墨! 竺! 竺竺! 垒兰! ! 垒：垒垒 s t ，+ l + s 口+ 2 + s m = a 即有口 人，这说明在霍中的机器上的工件中至少有一个，设为s ，s 皿，在离线最优算法中是安排在虫外的，即安排在机器i 上，其中i u 根 据我们的假设有 a ( s ) a( 2 7 ) 2 7 湖南师范大学2 0 0 9 届硕士学位论文 。因为i ，这说明机器i 的速度不快于机器v 的速度，所以有 仇( s ) 鼽( s ) 人( 2 8 ) 另一方面，s 是j 之前的工件且l 不属于霍，因此 l ( s 一1 ) l u 一1 ) 三号 竽人 ( 2 9 ) 所以： k ( s 一1 ) + m ( s ) 呈写 孚a + 人 ( 3 。) 这说明工件s 按照算法1 应该安排在机器v 上，也就是说s 不应该属于 皿矛盾，定理得证 当我们已知一个很好的a 的时候，所谓很好是说a 非常接近+ ，算法 1 是一个不错的算法下面我们提出算法2 ，目的是在a 未知的情况下，利 用算法l 作为算法的一部分，对工件进行排序算法2 分成九个阶段，定 义表示第i 阶段的a 值 算法2 第一步：a 的初始值为。即a o = o ， 第二步：当第一个工件到达时，令这个工件安排在最快的机器上的加 工时间表示a 。的值调用算法1 ，当算法1 总是有效，算法终止；否则， i = 2 ，转入第三步 第三步：第t 阶段开始，九= 2 a ，调用算法1 ，当算法1 总是有效，算 法终止：否则，i = i + 1 ，重复第三步 显然，算法2 是分阶段来进行的，在每一个阶段里，所有来的工件都 是独立安排在这个阶段里，只有当算法1 失效的时候，此阶段结束，进入下 一个阶段 2 8 工件具有相似长度的半在线排序问题 定理3 2 算法2 的最坏情况性能比为4 + 等铲 已知“表示第h 阶段的a 值，令k 表示在第h 阶段中所有工件安 排后的最大完工时间， 。删表示最后一个阶段因为算法1 的性能比p 为 ( 1 + 堑暑笋) ，且a = 人j l l = 2 2 a _ i 一2 = = 2 一1 a l 我f 有 f h p 八h = p 2 一1 a 1 因此， l = ：竺彳k 2 t 。雠p 人1 当胁耐 1 时，因为，r a 一l ，所以， l 一，= 等 从而有， l 2 。武p a l 2 p a 。“4 pl + 即有 三4 p 己+ 当危f t ：1 时，这说明算法2 在第一阶段就结束了，所以 l = pl + 4 pl 所以总有二4 p 厶，即 去鲫= 4 + 等譬 定理得证 本章我们主要讨论了工件在同类机器上加工工件的半在线排序问题， 提出了一个最坏情况性能比为4 + 等挚的新算法当r 趋向于无穷大时 4 + 等孚= 2 0 ，这与【1 9 】中的结论是一致的但我们认为这个算法的最坏 情况性能比还是偏大的，我们希望在以后的研究中能够找到最坏情况性 能比更小的算法 2 9 参考文献 【1 】g r a h a m ，r l ，b o u n d s 五。rc e r t a i ni 矾l t i p r o c e s s i n ga n o m a l i e s ，b e 船跏e m 九【m 】 4 5 ( 1 9 6 6 ) ，1 5 6 孓1 5 8 1 【2 】g a r e y ，m r & d s j o h 璐o n ，竹印札e r s 口仃dt 竹t m c t 0 6 诎纫：a 则i d e ot e 绕e d 删 西p c d 仃巾l e t e n e s s i m 】，s a i ln a n c i s c o ：n e e m a n ，1 9 7 9 【3 】a l b e 瑙，s ，b e t t e r 6 d t n d s 加r 伽“，l es 娩砒胁够【m 1 ，p r o c 2 9 t ha n n l l a la c ms y m p o nt l l e 0 呵o fc o m p u t i n g ，( 1 9 9 7 ) ，1 3 m 1 3 9 【4 】b a r t a l ，y a f i a t & a k a r l o f f r v - 0 1 1 r 8 ，、7 台伽8 匆d 以跣m 加r8 托口n c i e 疵s c e d 珏厶 l 叼p 加6 z e m m 】，p r o c 2 4 t ha n n u a la c ms y m p o nt h e o 珂o fc o m p u t i n g ，( 1 9 9 2 ) ， 5 1 5 8 【5 】g 甜a 和i b o s ，g & g w b e g i n g e r ，a 仃d 竹一如n es c 九e 砒屁n 9 e t n s “ct 历饶6 e t t e r 伽d 倦t c 口s e m i d 忱口竹g m o m s 如s c 九e 如托哪【m 】，s i a mj c o m p u t 2 2 ( 1 9 9 3 ) ，3 4 吼3 5 5 【6 】k a r g e r ，d r s j p l l i l l i p s e 1 1 0 m g ，a6 e t t e r 幻o n t ，i m 如rn nn 竹c l e n ts c e d t 如哪 o ? 9 d n t m 【m j ，j a l g 2 0 ( 1 9 9 6 ) ，4 0 m 4 3 0 7 】f a i 斟e ，u & w k 锄& g 口】r a n ，o nt h ep e r f o r m a n c eo fo n l i n e 赳g o r i t h m f o rp a r t i c u l a rp r o b l e m s j 】，a c 缸 6 e 仃1 9 ( 1 9 8 9 ) ，1 0 7 一1 1 9 【8 】l i u ，w p j b s i d n e y & a v l i e t ，o r d i n a la l g o r i t h m sf o rp a l r a l l e lm a c l l i i l e 鼬h e d u l - i n g 【j 1 ，l 二i p e r 。r e s 工e 托1 8 ( 1 9 9 6 ) ，2 2 3 2 3 2 【9 】k e l l e r e r ，h v k o t o v m r s p e r a n z a z t u z a ，s e m io n - l i n ea l g o r i t h i 璐f ；d r t l l ep a n i t i o np r o b k m 【j j ，( 枷r 冗三e 玩2 1 ( 1 9 9 7 ) ，2 3 5 - 2 4 2 1 0 】z h a j 塔，g ，as i i n p l es e m io n u l l ea 培o r i t h mf o rp 2 c m a xw i t hab u 妇e r 【j 】，埘 p 脚。l e 缎6 l ( 1 9 9 7 ) ，1 4 5 - 1 4 8 【1 1 】r d n g h e n g ，l i & h h u e i - c h u e n ，l i s ts c h e d u l i n gf o rj o b sw i t ha u r b i t r a ur e l e a s et i m e s 蛐ds i m i l 盯l e n 垂h s 【j 】，t 7 d t 仃l 叫d ，& 九e d 钍断w ，v ，0 1 6 ( 2 0 0 7 ) ，3 6 5 3 7 3 【1 2 】h e ，y g z h a n g ，s e m io n 一1 i i l es c h e d u l i n go nt w oi d e n t i c a lm a u c l l i n e s 【j