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

摘要 排序问题是组合最优化领域中的一类重要的问题。所谓排序就是指在一定 的约束条件下分配时间和资源去完成一些任务，使一个或多个目标达到最优。 近年来，在线排序和半在线排序是两个发展比较迅速的分支。在线排序是指 工件信息在到达之前是一无所知的，并且工件一旦被安排后就不允许改变离 线排序是指在工件安排之前就知道所有工件的信息。在现实生活中，有许多问 题既不是在线问题，也不是离线问题，而是介于两者之间的，这就是半在线问 题。在排序之前知道后面就绪的工件的部分信息。 同类机平行机排序问题是一个重要的平行机排序。一般地，问题可描述为： 设有一个工件集j = j 1 ，j 2 ，厶 包含n 个相互独立的工件，其中工件五的加 工时间用只来表示，工件需分给m ( r a 1 ) 台机器舰，尬，进行加工 机器尬的速度为s j ，j = 1 ，2 ，m 任意工件在不同机器上的加工时间有相同 的比例关系若工件只分给坞加工，则可用鲁个单位时间完成该工件。在传 统的经典排序问题中总假设机器均可以在零时刻加工工件，但我们知道在现实 生活中情况往往并非如此，比如说每台机器有一个准备时间只有在准备时间 之后机器才可以开始加工工件。这些问题称为带有机器准备时间的排序问题 本文主要讨论了具有机器准备时间的两台机器的半在线排序问题。其中s u m 代表所有工件的总加工时间，p m a x 代表最大工件的加工时间。本文的主要结 果如下： ( 1 ) 给出了排序模型q 2 ，r j s u m c m - n 的一个竞争比至少为盟2 8 + 1 的半在线算 法 ( 2 ) 给出了排序模型p 2 ，qj p m 。，s u m i c m t 。的一个竞争比为i 4 的最优的半在线 算法 ( 3 ) 给出了排序模型q 2 ，巧i p m a x ，s u mj c m ；。的一个竞争比至少为器的半在线 算法 关键词：同类机，在线排序，半在线排序，平行机，竞争比，机器具有准 备时间，总加工时间，最大加工时间。 a b s t r a c t s c h e d u l i n gi sa ni m p o r t m a n tp r o b l e mi nc o m b i n a t o r i a lo p t i m i z a t i o ni nw h i c hw ea s s i g n 8 0 m et a s k st ot i m ea n dr e s o u c e 8u n d e rs o m ec o n s t r a i n t s ，s u c ht h a to n e - o rm u l t i - c r i t e r i a a t t a i nt ot h eo p t i m u m r e c e n t l y , 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 ga r et w ob r a n c h e s d e v e l o p e df a s t e r o n - l i n es c h e d u l i n gm e a n st h a ta l lj o bi n f o r m a t i o ni su n k n o w nb e f o rt h e i r r e l e a s et i m e ，a n do n c eaj o bi ss c h e d u l e di tc a n n o tb ec h a n g e d o f f - l i n es c h e d u l i n gm e a n s t h a ta l lj o bi n f o r m a t i o ni sk n o w ni na d v a n c e i np r a c t i c e ，p r o b l e m sa r en o to n l yr e a l l yo n - l i n eo ro f f - l i n e ，b u ts o m e h o wi nb e t w e e n s u c hac a s ei sd e f i n e da ss e m i - o n l i n es c h e d u l i n g t h i sm e a n st h a tp a r t i a li n f o r m a t i o na b o u tj o b si sa v a i l a b l ei na d v a n c e a l g o r i t h m sf o ra s e m i - o n l i n es c h e d u l i n ga r ec a l l e ds e m i o n l i n ea l g o r i t h m s u n i f o r ma n dp a r a l l e lm a c h i n es c h e d u l i n gi sa ni m p o r t a n ts c h e d u l i n gp r o b l e m g e n - e r a l l y , t h ep r o b l e mc a nb ed i s c r e b e da sf o l l o w s ：t h e r ea r eas e tj = ，以， ) o f i n d e p e n d e n t j o b s ，w h e r ej ih a sp r o e s s i n gt i m e 只t h e j o b sm u s tb es c h e d u l e do nm ( m 1 ) p a r a l l ea n du n i f o r mm a c h i n e s w ea r eg i v e nas e to fm a c h i n e sm = 尬，地 ， a n d 彤i st h es p e e do fm a c h i n ei j ，j = 1 ，2 ，m e a c hj o bh a st h es a m ep r o p o r t i o n r e l a t i o no fp r o c e s s i n gt i m eo nd i f f e r e n tm a c h i n e s i nc l a s s i c ls c h e d u l i n gp r o b l e m s ，w eo f t e n a s s u m em a c h i n e sp r o c e s sj o b sa tt i m ez e r o b u ti np r a c t i c es i t u a t i o n sa r eo f t e nn o ts o ， s u c ha se a c hm a c h i n eh a sa na v a i l a b l et i m e m a c h i n e sc a ns t a r tt op r o c e s sj o b sa f t e rt h e a v a i l a b l et i m e w es a ys u c hp r o b l e ma sm a c h i n ew i t ha v a i l a b l et i m e i nt h i sp a p e r ，w ec o n s i d e rs e m i o n l i n es c h e d u l i n gp r o b l e m sa b o u tt w om a c h i n e sw i t h a v a i l a b l et i m e w ea s s u m es u mr e p r e s e n t st h et o t a lp r o c e s s i n gt i m eo fa l lj o b s ，a n d p m , r e p r e s e n t st 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 s t h em a i nr e s u l t si nt h i sp a p e r a r ea sf o l l o w s ： ( 1 ) f o rt h es c h e d u l i n gm o d e lq 2 ，r a s u m l c r m i n w eg i v eas e m i - o n l i n ea l g o r i t h mw i t h c o m p e t i t i v er a t i oa tl e a s t 丽a + 1 ( 2 ) f o rt h es c h e d u l i n gm o d e lp 2 ，r j s u m ，p h m l c m n ，w eg i v eas e m i - o n l i n ea l g o r i t h m w i t hc o m p e t i t i v er a t i oi 4a n di t i st h eb e s t n ( 3 ) f o rt h es c h e d u l i n gm o d e lq 2 ，r j l s u m ，p m 。i g i n ，w eg i v ea s e m i o n l i n ea l g o r i t h m w i t hc o m p e t i t i v er a t i oa tl e a s t 丽2 s + 2 k e yw o r d s ：u n i f o r mm a c h i n e ，o n - l i n es c h e d u l i n g ，s e m i - o n l i n es c h e d u l i n g ，p a r a l l e l m a c h i n e ，c o m p e t i t i v er a t i o ，m a c h i n ew i t ha v a i l a b l et i m e ，t o t a lp r o c e s s i n gt i m e ，l a r g e s t p r o c e s s i n gt i m e i n 第一章引言 1 1 排序的介绍 排序( s c h e d u l i n g ) 问题是一类重要的组合优化问题它的特点是利用一些处 理机( p r o c e s s o r ) ，机器( m a c h i n e ) 或资源( r e s o u c e ) ，最优地完成一批给定的任务 ( t a s k ) 或作业( j o b ) 在执行这些任务或作业时需要满足某些限制条件，如任务 的到达时间、完工的限制时间、任务的加工顺序、资源对加工时间的影响等， 最优完成任务指的是使目标函数达到最优。排序问题的产生于机器制造业，二 战以后，随着大型制造业的兴起，人们逐渐意识到排序问题研究的重要性。人 们普遍认为1 9 5 4 年j o h n s o n 完成了一篇关于两台机器同序排序问题的论文是第 一篇关于排序研究的文章近年来排序问题的研究有了新的迅速的发展。它在 计算机系统控制、硬件设计、机器加工制造业、生产计划调度的管理方面都有 着广泛的应用背景。在理论上，它又与算法设计和计算复杂性密切相关，并因 此引起了国内外的广泛关注 如果按数学分为理论数学和应用数学，那么排序论可以分为排序的理论部 分和排序的应用部分。排序理论部分又可分为经典排序和现代排序。b r u c k e r 和k n u s t 在c o m p l e x i t yr e s u l t so fs c h e d u l i n gp r o b l e m 中使用c l a s s i c a l 和e x t e n d e d 两个词来区别经典的和非经典的( 推广的) 两类排序问题。他们也用( 新型排 序) n e wc l a s s e s o fs c h e d u l i n g p r o b l e m s 来表示非经典的排序问题。因此，现代 排序就是非经典的新型的排序。相对经典的排序而言，现代排序就是突破了经 典排序的基本假设。根据1 9 9 3 年的e l l a w l e r ，j k l e n s t r a ，a h g r i n n o o yk a n 和d b s h m o y s 等的观点，经典排序有四个基本的假设( 见文献【1 】) ( 1 ) 资源的类型。机器是加工工件时所需要的一种资源。经典排序假设，一 台机器在任何时刻最多只能加工个工件；同时还假设一个工件在任何时刻至 多在一台机器上加工。作为这个基本假设的突破有成组分批排序，同时加工排 序，不同时开工排序和资源受限排序等。 ( 2 ) 确定性。经典排序假设决定排序问题的一个实例的所有( 输入) 参数 都是事先知道的和完全确定的。作为这个基本假设的突破有可控排序，随机排 序，模糊排序和在线排序，半在线排序。 ( 3 ) 可运算性。经典排序是在可以运算，可以计算的情况下的程度上研究排 序问题，而不去顾及如何确定工件的交货期，如何购置机器和配置设备等技术 上可能发生的问题。如果考虑实际应用中有关的情况和因素就是应用排序问 题。如人员排序和智能排序等。 ( 4 ) 单目标和正则性。经典排序假设排序的目的是使衡量排序的好坏的一 个一维目标函数的函数值为最小，而且这个目标函数是工件完工时间的非降函 数，这就是所谓的正则目标多目标排序，准时排序和窗时排序等是这个假设 的突破 在考虑一个组合优化问题的计算方案时，同时要对此算法进行计算复杂性 分析，以计算算法的效率及所研究问题的难易程度在计算复杂性理论中，存在 多项式时间算法的问题称为p 问题。此类问题是较为简单的问题。我们只需要求 懈其多项式时间算法就行了。对于大多数的问题而言，我们并不知道是否存在一 个多项式时间的算法，但是有这样的一类问题，如果其中一个问题能够在多项式 时间内解决，那么所有其他的n p 优化问题皆可以在多项式时间内解决。我们称 之为n p - h a r d 问题。对于此类问题一般情况下我们很难给出其多项式时间算法 也很难求出其最优解，因此在处理这类问题时我们只需要去找满足一定条件的 近似解就可以了。在研究排序问题时，对于此类问题一般是求出比较好的近似算 法。评价一个近似算法好坏，一般有三种方法：数值算例计算、最坏情况分析和概 率分析。用得比较多的是最坏情况分析中的竞争比分析( c o m p e t i t i v ea n a l y s i s ) 。 我们用g 表示在某种排序下工件以的完工时间j = 1 ，2 ，n 用厶表示机器 尬的当前的负载，i = 1 ，2 ，m 记锩m 。= m a x l t ，。= m a x c j 分别记为最大 机器完工时间和最大工件完工时间( 极小化目标) 在经典排序中总假设机器 是零时刻加工工件。此时有础。= 瓯。统称为机器的m a k e s p a n ，记为。而 当机器存在准备时间时两个未必相等。记瓯t 。= m i n 厶称为最小机器舰负载 ( 极大化目标) ，其中厶为当前已分子尬的加工工件的总加工时间( 如有准 备时间，还应加上机器准备时间) 与速度的比值。对于一个带有非负权重的优 化问题p ，假设存在一个多项式时间的近似算法a 对于问题p 的任何实例 9 j ，我们用c 4 ( nc o p ( j ) 分别表示算法a 解实例，的近似目标值和相应的离 线情形下的最优值。我们用吼来定义算法a 的竞争比。若对于m i n 型的( 极 大化) 优化问题，我们记r a = i 礼，f l 卑c o p 。( 1 ) 对于m a x 型的( 极小化) 情况下 吼2 s 印 誊器 一般情况下，觑越接近于1 ，说明该近似算法越好 3 1 2 在线排序和半在线排序 本文主要涉及到现代排序中的在线排序和半在线排序下面我们对这两个 模型作一下简单的介绍。 在经典的排序中，一般假设一个实例的所有的信息，包括工件的个数，到 达时间，加工时间等在开始排序前都是事先知道的这种情形我们称之为离线 ( o f f - l i n e ) 的。然而在现实生活中许多情况并非如此。决策者需要在所有信息到 来之前就必须进行决策若决策者( 1 ) 对后续工件的信息一无所知，甚至不知 道在其后有没有工件，( 2 ) 而且工件一旦安排就不能改变；此类问题我们称之 为在线( o n - l i n e ) 。根据工件到达的方式，在线排序可以分为两种： ( 1 ) 按序( o v e r - l i s t ) 在线排序：工件是排成一个表出现的一个工件只有在 表中排在其前面的工件都安排后才知道这个工件的相关信息 ( 2 ) 按时( o v e r - t i m e ) 在线排序：工件随着时间进行安排，在任何时刻只知道 已到达工件的相关信息它又可以分为两类第一类是工件的信息，如加工时 间在工件到达时就可知道。第二种是工件的信息只有在其被加工完之后才知 道 在实际问题中，除了在线和离线的两种情形外，还大量存在着另外的一种 情形。即决策者一方面不可能知道工件的所有信息，另一方面可能掌握着比经 典在线模型更多的信息或者说有更大的自由度。因而使问题变的比离线相对困 难一些，比在线相对来说可能会容易一些。我们把不满足在线排序问题的两条 基本假设，难度介于在线和离线之间的模型称为半在线( s e n t i o n - l i n e ) 的模型。 根据半在线排序问题中所知道的工件信息的不同可以分为以下几种情形。 ( 1 ) 不知道各个工件的加工时间，但知道工件是按加工时间非增的次序就 绪的。这种情况记为o r d i n a l ( 2 ) 有一个存储器可用来存放至多k 个工件，因此可以不必立即决定当前 工件的安排而可以把其放入存储器中，记为b u f f e r ( 3 ) 已知所有工件的总加工时间( s u m ) ，记为t o t a lp r o c e s s i n gt i m e ( 4 ) 已知所有工件中最大的工件加工时间( ) ，记为l a r g e s tp r o c e s s i n g t i m e 4 ( 5 ) 已知所有工件的加工时间属于一个区间囟，州，其中p 0 ，r 1 ，记为 i n t e r v a l 以上是几种常见的情形，当然还有就是以上几种情形的复合，一般情况下， 复合情况下的竞争比，要比单个情形下得到的竞争比要好一点，若不然，我们 就说知道这种复合信息的意义不大。由于在线问题和半在线问题( 除个别目标 函数外) ，一般不存在最优算法因此我们一般研究它们的近似算法。目前， 在排序研究中，评价一个近似算法优良程度时常见的有三种方法：数值算例计 算，最坏情况分析和概率分析这三种方法各有优点，也都有不足之处在理 论分析( 最坏情况分析和概率分析) 之前进行大量的算例计算是非常有用的方 法一则可以对理论分析给出估计和提供思路再则可以与已有的算法进行实 际比较。这在欧美的期刊是很常用的最坏情况分析是在分析算法在最坏情况 下的性态；概率分析是分析算法的平均性态。这方面在排序中运用还很少目 前在理论分析中的用的最多的是算法的最坏情况分析。 对于使目标函数c 为极小的( m a x ) 的优化问题，c 4 ( ，) 是算法a 的目标函 数值，如果存在一个常数r ( r 1 ) 对于，p 有c a ( ，) r c 。p ( n 那么称r 是算 法a 的一个上界，如果不能确定算法是否有界或确定算法的上界是无穷的大 时，这个算法称为启发式算法当r 是有限数时( 不是无穷大时) ，这个算法称 为近似算法，也就是说，近似算法是有界的启发似算法。用启发式算法和近似 算法得到的解分别成为启发式解和近似解。上式的r = s 即 三；法) 同理若目 标函数c 为极大化的( m i n ) 的情形，r = z 。n ，t 二c 石西a 法i ) 一般情况下，r 的值不是 1 另一方面，对于同一在线排序和半在线排序问题，我们可以设计出不同的在 线算法来区分它们的好坏我们的目标是设计出竞争比尽可能接近于1 的在线 算法 5 1 3 排序的记号 根据1 9 7 9 年，g r a h a m ，l a w e r 等人( 见文献 3 】) 提出的用三参数来表示一个 排序问题，在这里我们用三参数。俐，y 来表示。其中n 域表示机器状况，域 表示工件状况，r 域表示目标函数下面我们作一些介绍。 ( 1 ) ( 1 ) o t 域： n = 1 单台机器 n = p 相同的平行机 q = q 一致的平行机 o z = q 机器j 的准备时间 ( 2 ) 卢域： 卢= q 工件的到达时间 卢= d i 工件的工期 = “p j = p ”工件有相同加工时间 = p r e c 工件有序约束 卢= 已知最大工件的加工时间 卢= s u m已知所有工件总加工时间 p = p m 。，s u m已知最大工件的加工时间和所有工件的总加工时间。 p = n o n i n c r e a s i n gj o b已知工件是按加工时间分减的顺序来得。 卢= i n t e r v a l已知工件的加工时间在一个区间内。 p = o r d i n a l已知工件是按加工时间非增的次序来的。 p = b u f f e r已知有一个存储器，工件可以先放在里面，不用立即加工。 p = 0 2 一l i n e , r j 工件是按时间在线 = b 工件是成批加工的，批容量是b 卢= r e s t a r t s工件或批允许重启 ( 3 ) ，y 域： 我们先来介绍一些常见符号的含义： q 工件以的完工时间 6 岛= c j d j工件乃的延迟时间 乃工件以的延误时间 工件如的误工计数 一些常见的正则目标函数列举如下： ，y = c m 。最大完工时间，此处c m 。= m a x c j l lsj n ) ，y = l 。一最大延迟，此处l 。= m a x 易1 1 j 礼) ，y = c j 完工时间和 7 = w j c j加权完工时间和 7 = 乃误工时间和 ，y = t 如乃加权误工时间和 ，y = e 误工工件数 ，y = e w j u j 加权误工工件数 7 1 4 相关结果及本文的主要结果 本节我们主要介绍本文研究的排序模型以及现有文献中有关此类模型的相 关结果，最后列出本文的主要结果。 对于p | 1 c k ；。的确定性算法的研究已有相当的历史。对于离线的情形，d e u e r - m e y e r 等证明了l 尸t 算法的最坏情况界至少为；c r i r i k 证明了其确切值为4 坐m - 1 2 + w o e g i n g e r 给出了该问题的多项式时间近似方案；l i n 等给出了机器带准备时间 的l p t 算法的最坏情况界为磊2 r ；a j - - 1 对在线情形l s 的最坏情况界为击；而半在 线的情况a z a r 等给出了最优值。h e l l 7 对m = 2 的四个半在线的模型进行了 研究，并给出了最好的算法。对于半在线问题的研究是近年来才开始的且集 中在同型机( i d e n t i c a l ) 情形l i u ，s i d n e y 和v l i o t 提出了所谓的o r d i n a l 的半在线 模型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 1l 瓯i i l 的三个半在线模型及最佳 的近似算法。对其中有一个缓冲区( b u f f e r ) 的情形，z h a n g 也独立的给出了类 似的结果。h e 和z h a n g 1 2 1 提出了加工时间在给定区间内和已知最大工件加工 时间两个半在线模型。这些文献皆说明了最佳半在线算法比最佳在线算法的竞 争比好，这说明部分信息有利于设计更好的算法。随着研究的不断深入，新的 半在线模型也越来越多。 对于p 2 s u m c k t 。的模型，h e 给出了竞争比为；的最优算法。而对于p 2 l f k 。i c k ；。 的模型，h e 给出了竞争比为；的最优算法而对于同类机( u n i f o r m ) 的情形， t a n 和h e 给出了q 2 p m 。i c k 。模型的最坏情况界为以的近似算法。他们还给 出了p 2 l s u m c m a x 模型的最坏情况界为；的近似算法。对于已知只一，s u m 两种 复合信息的模型，h e 1 8 】等给出了p 2 l p m a x ，s u h i g 。的下界至少为；而对于 尸2 l r 。，s u m l c 矗t 。的模型，l 给出了竞争比为i 4 的最优的半在线算法。谭金芝 f 1 9 】把这种模型推广到同类机上，给出了q 2 i p 。，s u m c m t 。模型的竞争比至少为 2 。8 + 2 ，的半在线近似算法。 在实际问题中，由于机器通常情况下是连续加工工件的因此对于同一批 工件，机器开始加工的时间往往是不同的。因此，讨论机器具有准备时间情况 下的各种排序问题具有重要意义本文主要考虑了以下几种模型。 8 ( 1 ) q 2 ， j l s m n i c m ；。( 此时的吩在速度快的机器上) 我们给出了其竞争比至少 为丽s + 1 ( 2 ) p 2 ，r j s l l l l l ，p m 。l 我们给出了其竞争比仍然为i 4 的最优的半在线算 法。 ( 3 ) q 2 ，r j l s u m ，只i - n 我们给出了其竞争比为；爱的半在线算法。 9 第二章带有机器准备时间的半在线排序问题 2 1已知总加工时间的情形 本节将对半在线问题的研究拓广到机器有准备时间的同类机情形设机器 集m = 尬，尬) ，其中机器舰的准备时间为n ，速度为s ；不失一般性，设 8 。= 1 ，1 r 则将以后到达的工件安排在尬上 ( 2 ) 若2 r 丽t + s r 转( 4 ) ，( 5 ) ( 4 ) 若l ( ) + 譬堑2 s + 盟1 则将工件易安排到m 2 加工其余的工件的安 排到尬上加工 ( 5 ) 若l ( 尬) + 譬 ! 坠2 s + 巫1 ( ) 若p j 垃监2 s + l 盟将乃安排在尬上，其余的工件安排到m 2 上 ( 税) 若p 3 垃老蜂铲分两种情况 1 0 ( i i l ) 若三等当t + 8 r s ( r + 譬) ，则将g j 安排在上，其余的安排在 尬上。 ( i t 2 ) 半 t + s r s ( r + 譬) 则将g j 安排到m 上，其余的安排到尬 上。 定理1 算法m h 对于q 2 ，r j s u m c m i 。的竞争比至少为丽s + 1 证明显然有p t 丐箐 ( 1 ) ( i ) 若t r 时，则h = p t 此时已为最优 ( i i ) 若r r ，此 时有c m h = m i n l ( m 1 ) + 易，t - i - s r - ( l 。( m i ) + p j ) j 1 ，若l ( m ) + b 墨t + s r - ( l 。( m i ) 4 - p j ) ，贝4 日= l ( m 1 ) + 弓此时 堕co缝拱掰2坐pt 2 ) r 2 s - f1 一专箐一t + s r 一如+ 一 若r t 4 - s r - ( l 。( m 1 ) - f p i ) t + 二s r - ：( l ( m ：i ) + p $ ) ： ! ! ! 1 2 型 型! c o p tc o p t i 。4 - 8 r8 + 2 2 s - 1 - 1 ( 2 ) 若2 r 鬓 坐 c o p t 豆s + 互l 丽 若算法执行步( 5 ) ，则l ( m 2 + 导 鼎，弓 划2 s d - 1 ， 设算法按( 5 ) ( i ) 将以安排到炳上，其余的安排到尬上若l ( 蝎) sl ( 尬) c m h = l ( m 1 ) 划2 s + l ，此时有 h 、! 群、s + 1 p t2 等2 2 s + 1 若此时有l ( m 1 ) l ( m j ) ，即b 三等生，则有 器亨t+sr-p苄t+sr- 葬2 s + l 丽s + 1 卷亨 苄 葬丽 若算法按( 5 ) ( 乱) 则b 鲣掣，可以证明此算法的竞争比也至少为孙8 + + 1 ， n n - r 件j j 要么排在舰上，要么排在m 2 上 ( 一) 若把工件如排在排在m 上，则此时l ( 尬) 弓，三( ) 三等丑 撕) p 譬器掣 l ( ) 墨t + s r - p 。 l ( m 2 ) 。要使目标值尽可能的大，则应把工件j 排在排在地上， 其余的工件全部安排到m 2 上则此时c 1 ：堡芝生 ( 二) 若把工件易排在排在尬上，则此时 州) r + 参r + 器 丽t + s r 2 s s l z s + l l s+ l l ( 蜮) t + 8 r - 8 ( r + 争 此时的目标值q = m i n l ( m ：) ，l ( 嘣) ) ( i i l ) 半t + s r s p + 孚) ，则学丽t + s r r + 譬算法把工件力 排在排在上，其余的工件安排到舰上此时c 1 岛，从而c k 片：q ： m i n l ( 叫) ，l ( 瞒) ) 若l ( 叫) l ( 嗡) ，从而胃= 三( 必) 业2 s + 1 则有 c m h 、丽t + s r 、8 + 1 瓦匾s + l 互鬲。 1 2 若l ( 叫) t + s r s ( r + 导) 此时有半 丽s + l r + 导并且c 2 = ( 叫) = r + s r s ( r + 孕) 雩丑，则称只为大工件用瑞。来表示第一个到达的最大的工件， 用只一尬来表示把加工时间为只的工件分给屿来加工分别用c a ( zm ) 和 c o p ( zm ) 来分别表示算法a 解某实例( 以m ) 的目标值和该问题在离线状态下 的最优值，其中c a l ( z m ) = m a x m i n l ( m 1 ) ，l ( 尬) ) 其中l ( 尬) ，l ( ) 分别表示 算法a 解实例( zm ) 完工时机器尬，尬的负载c o p ( 以m ) = m a x m i n l ( 尬) ，l ( 尬) 】) 分别表示实例( zm ) 在离线下完工的两机器的负载在不引起混淆的情况下， 简记为伊t ，c o p t 三算法a 1 ( 1 ) 若r 坐，把所有的工件均放在上 ( 2 ) 若r 呈【1 5 盟，进行以下算法。 ( 2 1 ) 若r 盟掣，则可以把r 虚拟为一个小工件 ( 2 1 1 ) 若0 塑掣，用l s 算法安排所有工件，停机 1 4 ( 2 1 2 ) 若塑5 盟 t + r ，将础。一，其余的工件安排到舰上 ( 2 1 3 ) 坚5 盟只 型 ，设当前的工件为p ( 2 1 3 1 ) 停机准则( 1 ) ：若p 能安排给两台中任一处理器，使其加工完p 后 的负载位于f 鼍掣，! 5 立1 j 之间，则把p 安排到此处理器，以后的工件安排给另 一处理器，停机 停机准则( 2 ) ：如果p 在础a x 之前到，且如果把其安排到某台机器上加工， 使其加工完p 后的负载位于【掣一p m 。，掣一p m 。】之间，则把p 和安 排给此台机器加工所有除础。外的剩余工件安排到另一台机器上加工，停 机 ( 2 1 3 2 ) 如果p 堡盟5 或p = 瑞。则把p 一尬上，若p 是不同于碟。的 大工件，则把p 一尬如果上已有两个大工件，则把所有的剩余的工件安 排到尬上停机 ( 2 1 3 3 ) 如果p 不是最后工件，返回( 1 ) ，反之停机 ( 2 2 ) 如果0 尸m 。 r ! 幽5 ( 2 2 1 ) 若0 尸m 。皿5 皿时，执行( 2 1 1 ) ( 2 2 2 ) 掣sp m 。 ! 掣， ( 2 2 2 1 ) 执行( 2 1 3 1 ) ( 2 2 2 2 ) 如果p 雩丑，则把p 一尬上，若p 是大工件，则把p 一尬如果 尬上已有两个大工件，则把所有的剩余的工件安排到上停机 ( 2 2 3 3 ) 执行( 2 1 3 3 ) ( 2 3 ) 如果必5 r p m a x 掣， ( 2 3 1 ) 执行( 2 1 3 1 ) ( 2 3 2 ) 如果p 坚5 丝或p = 础。则把p 一上，若p 是不同于赡的大 工件，则把p 一尬如果舰上已有一个大工件，则把所有的剩余的工件安排 到尬上停机 ( 2 3 3 ) 如果p 不是最后工件，返回( 1 ) ，反之停机 四：算法竞争比的证明 1 5 引理l 如果以停机准则( 1 ) ，( 2 ) 停机，则一定有竞争比c a 两1 i 4 证明：无论以停机准则( 1 ) ，( 2 ) 停机，都有c 4 1 型又因为c o ms 盟 所以有丽c q 扣4 定理1 算法a 1 对任意的实例都有丽c ax 5 4 证明：显然对任意的实例都有st t + r ( 1 ) 当t r 时，既t + rsr + r ，孚sr 若按算法把所有的工件都安排到 上，则此时l ( m 1 ) = r l ( ) = t r 从而为算法为最优 当型毛掣r r 因此c a - = r 丽c a , 毒等i 4丽孚章i ( 2 ) 设r ! 【型5 时 若r 里挚，此时可把r 虚拟为一个小工件 ( 2 1 1 ) 0 l ( ) ，则有 l ( 炳) 一l ( ) p m 。竖掣， l ( 尬) + l ( 如) = t + r 可得，c z = 己( 尬) 塑产则有 竺等5 2i 4 c o p t 一1 f 2i 若l ( 饥) l ( ) 时，贝0 有 工( 尬) 一i ( i o p m 。譬掣， 三( 尬) + 三( ) = r + r 从而- = i ( u o 掣因此 筹之掣5 专4 ( 2 1 2 ) 若錾粤p m 。 t + n 根据算法，若鼍导sp m 。 卫 有l ( ) = p m a x ，l ( 蛆) = t + r 一尸m a x 可以计算c 唧= l ( ) l ( m ) c 4 1 4 两5 坐2 盟p m 。 鼍盟，若尬上还有别的大工件则有l ( m 2 ) 2 鼍垃+ 掣又因为 碟。一舰，所以有两台机器的总加工时间之和大于t + r 与总加工时间为t + r 矛盾因此在磁。到来之前，上至多有两个大工件。以下为这种情形的讨 论。 ( i ) 在瑶。到来之前，尬上恰有两个大工件，分别设r ，p b 由前面的分析 可知，l ( m 2 ) = 只+ b 韭5 盟，l ( m 1 ) = t + r 一( r + r ) 绁 苎【三而剩余工 件的总加工时间三( 州) = t + r 一( + r ) 呈( 专盟 ! 坚 三( 瞒) t + r 一( r + 岛+ r ) 塑从而c o p = l ( 噬) c 山则此时该算法 是最好的 ( i i ) 设在瑶a x 到来之前，上少于两个大工件由停机准则( 2 ) ，在础。到 来时，( m 1 ) 型专咀一p m 。，且l ( ) 型毛掣，由于尬仅加工了小工件和p m 。， 】7 为避免停机准则( 1 ) ，尬不能再加工小工件，否则m 的负载将大于坐一p m 。， 满足停机准则( 2 ) 此外尬上又都只加工大工件，而大工件的加工时间的加工 时间介于( 孚，! 坦) 之间所以 如至少应加工两个大工件因为若 如上只 加工一个大工件，则尬的负载将小于! 譬立，不能使机器加工完所有的工件。 ( 2 2 ) 如果0 只一 r 呈【三 ( 2 2 1 ) 的正确性的证明同上面的( 2 1 1 ) ( 2 2 2 1 ) 的正确性的证明由引理1 可证 ( 2 2 2 2 ) 的正确性的证明与( 2 1 3 ) 相似，只需要把r 当成碟。即可 ( 2 3 1 ) 的正确性的证明有引理i 可证明。 ( 2 3 2 ) 的证明与( 2 , 1 3 ) 相似，只需要把r 当成一个大工件即可 这样我们就证明了在任何情况下算法的竞争比至少为i 4 因为在没有准备 时间时其最优算法的竞争比为 这样我们也可以说明算法a - 是最优的算法 1 8 2 3 已知总加工时间和最大加工时间的同类机排序问题 本节主要研究了已知复合信息带有机器准备时间的同类机排序问题设预 先知道所有工件的加工时间总和( s u m ) 和最大工件的加工时间尸。其目标为 极大化最小机器的完工时间h e 证明了算法凰是求解p 2 1 s u m c m ，。的最优算 法，且其竞争比为；h e 还对p 2 i p m 。i c k t 。问题提出了竞争比为；的最优的p l s 算法l 乱证明了算法s m 是模型p 2 1 s u m ，只一i g 曲的最优的半在线算法且其 竞争比为i 4 对于q 2 l s u m ，p m 。i ，n 的模型，t a n 1 9 】给出了此问题的竞争比为 警鬟的半在线算法本节对于模q 2 ，r j s u m ，r 。l 恤进行了研究并且证明了其 竞争比为仍为丽2 s + 2 二问题的描述 设工件集，= ，如，厶) 包含几个相互独立的工件，其中工件五的加工 时间为只工件按其下标的顺序依次到达，需要不中断的在两台机器尬，尬上 加工机器m j 的速度为s t ，不失一般性，可设s 。= 1 ，l 絮等，则称只为大工件用碟。来表示第一个到达的最大的工件， 用只一坞来表示把加工时间为只的工件分给坞来加工分别用c “( zm ) 和 c 唧( zm ) 来分别表示算法a 解某实例( zm ) 的目标值和该问题在离线状态下 的最优值，其中c 4 ( 正m ) = m a x m i n l ( m t ) ，l ( ) 】) 其中l ( m ) ，l ( m 2 ) 分别表示 算法a 解实例( zm ) 完工时机器舰，尬的负载c o p t ( 以m ) = m i n l ( 尬) ，l 7 ( ) ) 分别表示实例( zm ) 在离线下完工时两机器的负载在不引起混淆的情况下， 简记为c a ，g 咿 三算法a ( 1 ) 若r2 等警，把所有的工件均放在m 2 上 ( 2 ) 若r ! 搿， ( 2 1 ) 若r 冯三导，则可以把r 虚拟为一个小工件 1 9 ( 2 1 1 ) 若0 p m 。坚3 s + 盟2 ，用l s 算法安排所有工件，停机 ( 2 1 2 ) 若! 韭3 s + 生2 1 p m 。 t + n 将碟a x a 如，其余的工件安排到尬上 ( 2 1 3 ) 1 3 竖s + 盟2 p m a x 必3 s + 2 设当前的工件为p ( 2 1 3 1 ) 停机准则( 1 ) ：若p 能安排给两台中任一处理器，使其加工完p 后的 负载位于 弓：警，! 群 之间，则把安排到此处理器，以后的工件安排给另一处 理器，停机 ( 2 1 3 2 ) 停机准则( 2 ) ：如果p 在础。之前到，且如果把其安排到尬上加 工，使其加工完p 后的负载位于 鬟等一p m 。，等导一p m 。】之间，则把p 和尸m 。 安排给舰加工所有除础。外的剩余工件安排到m 2 上加工，停机如果p 在f 2 。之前到，且如果把其安排到尬上加工，使其加工完p 后的负载位于 【等等一争，警等一平】之间，则把