（运筹学与控制论专业论文）带有运输的单机平行分批在线排序问题.pdf

郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者：习彳j 2 0 0 6 年4 月 摘要 所谓排序，就是在一定的约束条件下分配时间资源去完成一些任务，使一 个或多个目标达到最优。近年来，在线排序和分批排序是两个发展比较迅速的 排序模型。在线排序是指工件信息在其到达之前是一无所知的，并且一旦工件 被安排后就不允许再改变。平行分批排序是指机器可以同时加工多个工件，每 批的加工时间是这批工件中所有工件加工时间的最大者。一旦批开始加工就不 能被中断，直到该批被加工完毕。 本文中，我们研究了一种在线排序模型：带有运输的单机平行分批在线排序 问题。在这里，我们有一台批处理机和充分多的车辆。有n 个工件 ，如，厶，每 个工件都分别有一个到达时间r ，加工时间巧和运输时间。工件的这些信息 在其到达之后我们才能获得。在此问题中，每个工件需要在机器上加工，并且工 件一旦完工就由车辆将其运送到目的地。我们的目标函数是最小化所有工件被 运到目的地所花费的时间用g r n h n m 等人 4 提出的三参数表示法，我们的问题 可以表示为：l f o n 一打n e ，q ，啦，且f 巩。，其中d 竹，。= m a x b f 功= g + 略，l jsn ) 本文的主要结果如下： ( 1 ) 给出了排序模型1j o n j j n e ，o ，q ，b = 。j d 。的一个竞争比不超过2 的在 线算法。 ( 2 ) 给出了排序模型1 l o n - j 伽e ，_ ，一p p r e c ，b = 。i d 。一个竞争比为 ( 怕+ 1 ) 2 的在线算法。该在线算法是最好可能的。 ( 3 ) 给出了排序模型l i o n ，j 伽e ，r 7 ，q ，b n l d k 。的一个竞争比不超过3 的在 线算法。 ( 4 ) 给出了排序模型l i o n j f n e ，q ，p j = p 1 日 州d 。一个竞争比为( 、，百十1 ) 2 的在线算法。该在线算法是最好可能的。 ( 5 ) 给出了排序模型l f o n 一咖e ，q ，q 。功= p ，p r e c ，b n f d 。一个竞争比不超过 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 ns o m et a s k st ot i m er e s o u r c e su n d e rs o m ec o n 8 t r 出n t s ，s u c ht h a t o n e o 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 r e c e n t l y o n l i n es c h e d u l i n ga n dp a r a l l e l b a t c hs c h e d u l i n ga r et w of l o u r i s h i n gs c h e d u l i n gm o d e l s o n l i n es c h e d u l i n gm e a n st h a ta l l j o bi n f o r m a t i o n sa r eu n k n o w nb e f o r et h e i rr e l e a s et i m e s ，a n do n c eaj o bi 8s c h e d u l e di t c a n n o tb ec h a n g e d p a r a l l e lb a t c hs c h e d u l i n gm e a n st h a tam a c l l i n ec a np r o c e s 8s e v e r a l j o b ss i m u l t a n e o u s l y8 sab a t c h ，a n dt h ep r o c e s s i n gt i m eo ft h eb a t c hi se q u 出t ot h e1 0 n g e s t p r o c e s 8 i n gt i m eo ft h ej o b sa s s i g n e dt oi t o n c eab a t c hi ss t a r t e d ，i tc a n n o tb es t o p p e d u n t i li t sc o m p l e t i o n i no u rp a p e r ，w ec o n s i d e ra no n l i n e8 c h e d u l i n gm o d e i ：o n l i n es c h e d u l i n gw i t hd e l i 、吧r y t i m eo nas i n g l eb a t c hm a c h i n e h e r e ，1 w eh a v eab a t c hn l a c h i n ea n ds u m c i e n tv e h i c l e s t h e r ea r en j o b sl ，l ，如， e a c hj o bh a sar e l e a s et i m e0 ，ap r o c e s s i n gt i m e 功，a n d a ( 1 e l i v e r yt i m e t h e s ei n f o r m a t i o n sa r ek n o w na b o u taj o bt m t i li ta r r i v e s i nt h i s p r o b l e m ，e a c hj o bn e e d st ob ep r o c e s s e do nt h em a c h i n e ，a n do n c et h ej o bi sc o n l p l e t e d 、 帕 d e l i v e ri tt ot h ed e s t i n a t i o nb yav e h i c l e 0 l l ro b j e c t i v ei st om i i l i n l i z et l l et i m eb yw h i c h a uj o b sh a v eb e e nd e l i v e r e d u s i n gt h e3 一f i e l dn o t a t i o no fg r a h a me ta 1 4 】，o l l rp r o b l e i n i sd e n o t e da sl i o n j n e ，吩，劬，b i d k w h e r ed = m 孤 功l 功= q + 劬，1 j n t h em a i nr e s u l t so ft h i sp a p e ra r ea sf o l l o w s ( 1 ) f o rt h es c l l e d u l i n gm o d e l1 1 0 n j 胁e ，q ，吣，b = 。l d m 船，w eg i v ea no n 一1 i n ea l g o - r i t l l mw i t hc o h l p e t i t i v er a t i on o tg r e a t e rt h a n2 ( 2 ) f o rt h es c l l e d u l i n gm o d e llj o n 一加e ，巧，劬，功= p ，e c ，b = 。i d ，憎g i v ea n o n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i on o tg r e a t e rt h a n ( 5 + 1 ) 2 ，a n ( 1i ti sab e s t p o s s i b l eo i 卜l i n ea l g o r i t h m ( 3 ) f b rt h es c h e d u l i n gh l o d e l1 i o n j j n c ，0 ，毋，b 儿i d m 。z ，、v eg i v ea no 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 、他r a t i on o tg r e a t e rt h a n3 ( 4 ) f b rt h es c h e d l l l i n gi n o d e l1 io j l m 】e ，q ，q j ，功= n b 礼i d m w eg i v ea no n 一1 i n e a l g o r i t h n lw i t l lc o i n p e t i t i v er a t i on o tg r e a t e rt h a n ( 、5 + 1 ) 2 ，a n di t i sab e s tp o s s i b l e 2 o n 1 i n ea l g o r i t h n ( 5 ) f o rt h es c h e d u l i n gm o d e l l i o 皿一j j n e ，q ，p j = p ，刀e c ，b o ，a 都是优化问题p 的一个 ( 1 + s ) 一因子的近似算法，那么算法a 称为p 的一个近似方案。 1 2在线排序和分批排序 本文主要涉及到现代排序中的在线排序和分批排序。下面我们将对这两个 模型作简单介绍： 6 在经典排序中，一般假设一个实例的所有信息，包括工件的个数，到达时 间，加工时间等在开始排序前都是事先知道的这种情形我们称为是离线的。 然而在现实生活中许多情况并非如此，决策者需要在所有信息到来之前就必须 进行决策这种情形我们称为是在线( o n 一j n e ) 或者是半在线( s e m io n 一正n e ) 的。 在在线排序中，工件信息是逐个释放的，决策者在决定当前工件的加工时对其 后的到达工件是一无所知的，并且一旦决定工件安排后就不允许改变。 根据工件的到达方式，在线排序分为两种： ( 1 ) 列表( 。”e r 池) 在线排序：工件是排列成一个表逐个出现的。一个工件 只有当表中排在其前面的工件都安排后才知道这个工件的相关信息。 ( 2 ) 时间( 删e r i ，n e ) 在线排序；工件随着时间进行安排，在任何时刻只知道 当前已到达工件的信息。 事实上，在时间列表在线排序中，又有两种分类：第一种是工件的信息， 如加工时间，在工件到达时就可知道；第二种就是工件的信息在其加工完时才 能被“告知”。而在本文中我们主要考虑第一种时间在线排序。 由于在线排序问题( 除个别目标函数外) 通常不存在最优算法，因此，我们 往往考虑它们的近似算法。通常我们用在线排序算法的竞争比来衡量它的优 劣，即把在线算法的结果与对相同工件运用离线排序算法得到结果进行比较。 我们定义在线算法4 的竞争比r 一是排序问题所有实例的比值舅竺的上确界， 其中c 矗和g 。分别由算法a 得到的目标函数值和相应的离线排序的最优值。 然而，由于对未来工件信息的未知，我们很难找到一个在线算法达到最优。因 此，r 。的值往往大于1 。另一方面，对于一个在线问题，我们可以设计不同 的在线算法来区分它们的“好坏”。我们的目标是设计竞争比尽可能小的在线 算法。 在经典排序中，我们还假设任何机器任何时刻最多只能加工一个工件，而实 际生活中有的“机器”可以同时加工多个“工件”。例如，一个烤箱可同时烘烤多个 面包。最典型的是发生在大规模集成电路的生产中，为了保证成品合格，检验阶 段要把集成电路放在烘箱中试验它们的耐温性能。一个烘箱可以同时检测多个 集成电路，而且在检测过程中不可以移走任何集成电路。这种机器可以同时加 7 工多个工件的排序问题称为分批加工机器排序( s c e d u “唧a c 觚n 9m n c 觚n e ) 。 分批排序问题与经典排序问题的不同在于若干个工件可以在一批中加工， 工件加工过程中不允许中断，也不允许移走正在加工的工件。在分批排序中， 如何确定批是问题的关键，一旦批确定后，就可将批视为一个工件来寻找其最 优算法或近似算法。根据每批的加工时间的定义不同，它又可分为“并行工件 同时被加工的排序”( p o r o “e f 蚰c m 叼p r 0 6 f e m s ) 和“串行工件同时被加工的排 序”( s e 州lb n t c 溉gp r o m e m s ) 。前者每批的加工时间是这批工件中所有工件加 工时间的最大者；后者每批的加工时间是这批工件中所有工件加工时间之和。 本文我们所考虑的模型是前者。 1 3排序的记号 1 9 7 9 年，g r o h o m ，l n e r 等人【4 】提出用三参数来表示一个排序问题。在这 里，我们采用ni 卢h 来表示，其中a 域表示机器状况，口域表示工件状况， 7 域表示目标函数。下面我们分别作一些说明： ( 1 ) 口域： 。= 1 单台机器 n p 相同的平行机 a = q 一致的平行机 n = r 无关的平行机 ( 2 ) p 域： 口= n 工件的到达时间 卢= 玑工件的运输时间 口= 出工件的工期 = “肼= p ”工件有相同工时 p = p r e c 工件间有序约束 = o n j j n e _ j s 工件是列表在线 口= o n 一咖e ，n工件是时间在线 r ( 3 ) 7 域： 首先，我们介绍一些符号： g 工件如的完工时间 岛工件以的延迟时间，这里，与= q 一奶 功工件以被运到目的地的时间，这里，d j = g 十 乃工件以的延误时间 巧工件五的误工记数 现在，我们介绍一些目标函数： ，y = c k 。最大完工时间，此处，c k 。= m a x q i lsj n ) 7 = l 。最大延迟，此处，l = m 觚 岛l l j 兰礼) 1 = d r 一工件被运到目的地的最大时间，此处，d 。= m a x d j l l j sn ) 7 = g 完工时间和 7 = ”f g 加权完工时间和 ，y = 乃误工时间和 7 = 叼巧加权误工时间和 7 = 阢误工工件数 7 = 屿u ，加权误工工件数 1 4相关结果及本文主要结果 本节我们主要介绍本文研究的排序模型以及现有文献中有关此类模型的 相关结果，最后列出本文的主要结果。 设有一台批处理机和充分多的车辆，有n 个工件，每个工件需要在机器上 加工，一旦完工就用车辆将其运送到目的地。每个工件 都分别有一个到达 时间? ，加工时间纺，和运输时间o 。工件的信息在其到达之前是一无所知 的，而一旦工件到达，其所有信息也就知道了。我们的目标函数是最小化所有 工件被运到目的地所花费的时间。我们的排序模型用上一节提到的三参数法可 表示为：1 1 0 n j 抽e ，q ，b l d 。 9 对于目标函数为最小化所有工件被运到目的地所花费时间的排序问题，现 有文献已有研究。在1 9 9 3 年，三n 训e r 【5 】等人证明了模型l l o ，j d m 。是p 一 困难的，而在工件允许中断的情形下是多项式时间可解的更早时期，在工件 同时到达情形下，人们利用l d 丁算法( 即每次总是优先考虑已到达工件中运 输时间最长的工件) 解决了此问题。在工件到达时间不同的情形时，1 9 7 9 年， i s e 等人6 1 证明了l d t 算法是一个2 一近似算法。在在线情形下，2 0 0 0 年， j ah o o g 鲫e 帆等人【7 证明了模型1 l o n 一妇e ，q ，i d 。所有在线算法的下界为 ( 怕+ 1 ) 2 ，并给出了一个与此下界相吻合的在线算法。上述结果考虑的都是 非批处理机的情形，下面我们将对批处理机情形加以讨论。 如果我们将上述模型中加以限制，比如q ，= q ，v 1sj 茎扎则上述模 型就可转化为批加工在线排序模型：1 l o 丑一j j n e ，r ，b 1 。对于此模型已有大 量文献进行过研究在离线情形下，当所有工件的到达时间相同时， b r “c 自e r ( 1 9 9 8 ) 8 1 和l e e ，u 。s 州( 1 9 9 9 ) 9 】提到了由b n r 地o f d i 发现的f b l p 丁最优算法( 即 每次总是优先考虑已到达工件中加工时间最长工件进行装批) ，此算法在分批 排序中有着重要的作用；当所有工件的到达时间不同，批容量无界( b = 。) 时，l e e ，矿z s 删( 1 9 9 9 ) 9 给出了一个动态规划算法，而批容量有界( b n ) 时， b r c 女e r ( 1 9 9 8 ) 8 和l 沈，y 札( 2 0 0 0 ) 1 0 】证明了此问题是j d 一困难的。在在线情 形下，d 帆9 ( 2 0 0 3 ) 1 1 和z h n n 9 ( 2 0 0 1 ) 1 2 】对平行分批加工在线排序问题进行了 研究。他们独立地证明了此模型所有在线算法的下界为( 怕+ 1 ) 2 ，并且，在 批容量无界( b = ) 时，找到了与此下界吻合的最好可能的在线算法；在批容 量有界( b ) 时，z n 札9 ( 2 0 0 1 ) 1 2 】给出了两个竞争比不超过2 的在线算法， 而这些算法都是基于f b l _ p t 算法的思想。随后，p 0 。，。，y “( 2 0 0 5 ) | 1 3 1 证明了基 于f b l p 丁算法思想的在线算法的竞争比都不超过2 ，并且在b = 2 时，他们 给出了一个竞争比为7 4 的在线算法。 我们在增加了工件的运输时间之后，对此模型进行了研究。在一般情形下 我们可以获得两个竞争比分别为2 ( b = 。) 和3 ( b n ) 的在线算法；在特殊情 形( 比如功= p ) 下，得到了最好可能的在线算法。 下面我们就给出本文的主要结果。 1 n ( 1 ) 对于排序模型1 f o n j j n e ，q ，叻，b = 。i d 。，给出一个竞争比不超过2 的 在线算法。 ( 2 ) 对于排序模型1 0 力一j j n e ，q ，西= p ，p r e c ，b = o 。i d 。，给出一个竞争比 为( 怕+ 1 ) 2 的在线算法。该在线算法是最好可能的。 ( 3 ) 对于排序模型1 1 0 n j j n e ，q ，劬，b 礼d 。，给出一个竞争比不超过3 的在 线算法。 ( 4 ) 对于排序模型1 1 0 刀一妇e ，q ，册= p ，b n i 给出一个竞争比为( 怕+ 1 ) 2 的在线算法。该在线算法是最好可能。 ( 5 ) 对于排序模型l i o n j j n e ，o ，功= np r e c ，b 训d 。，给出一个竞争比不 超过2 的在线算法。 第二章带有运输的单机平行分批在线排序问题 本章我们考虑的排序模型是1l o n 一j n e ，q ，b l d k 。首先，我们引用z h n 礼9 ( 2 0 0 1 ) 1 2 】中给出的此问题的所有在线算法的下界，然后，在第一节我们给出批 无界情形下的在线算法及证明，在第二节我们给出批有界情形下的在线算法及 证明。 在本文中，我们用以表示工件j ，用q ，功，劬分别表示工件出的到达 时间，加工时间以及运输时间，用一和丌分别表示在线算法产生的排序和对 应的离线情形下的一个最优排序。若用彤( 盯) ，g ( 和d j ( 一) 分别表示工件。乃 在排序a 中的开工时间，完工时间以及工件被运到目的地所花费的时间，则 功( = 0 ( a ) + 毋。对于一个排序实例l ，我们记d 。( 口) 和d k 。( ”) 分别为在 线算法中工件的完工时间与运输时间之和的最大值和离线情形下最优排序中 工件的完工时间与运输时间之和的最大值。在线算法的竞争比r 可以定义为 r = s u p d 。( 盯) d 。( 7 r ) ) v l 在线算法的下界 我们考虑排序问题1 f o n 一】j 力e ，巧，劬，b 1 d 。的特殊情形1 0 n j j n e ，勺，b 1 c 。，那 么后者的在线算法的下界必然是前者在线算法的下界。对于后者z o n g ( 2 0 0 1 ) 旧 给出了一个所有在线算法的下界。我们引用如下： 引理1 ( z n 他g ( 2 0 0 1 ) 1 2 】) ：对于排序问题1j 0 n j j 玎e ，勺，口l 。，不存在在线 算法使得其竞争比小于l + n ，其中o = ( 帕一1 ) 2 。 口 通过上面引理1 ( z n n 9 ( 2 0 叭) 1 2 ) 中证明，对于批容量无界和批容量有界 两种情形( 即使p ，= p ) ，上述下界都是适用的，这在后面的证明中我们将反复 提到。 52 1批容量无界情形 首先我们考虑所有工件同时到达的模型：l 慨，劬，b = 。j d 在此模型 中，我们可以假设工件集r = ，厶) 满足性质： 1 2 p 1 p 2 ， 倘若工件集r 中存在工件 和如使得p ls 功且哦缈，我们可以认为工 件 被工件 “吸收”，也就是说，工件 可以被忽略。事实上，由于批容量无 界，我们可以发现工件被“吸收”前后目标函数的最优值并未发生改变。因此， 我们可以递归地调用上述操作并最终得到：如果工件以和易满足a q j 。 根据上述假设，我们可以发现所有工件是按照卯r 规则排列的，即， p 。 p 2 ，类似于b r c e r ( 1 9 9 8 ) 【8 】中对排序模型1 i l l 给出 的动态规划方法，我们将给出此排序问题的一个动态规划算法。 动态规划算法a 令r ( k )是工件序列 ，以 所有s j p 了1 批排序中全部工件被运到 目的地花费的时间的最小值。 ”( )表示由前女个工件组成的所有的最优的s p t 一批排序的集合。 g ( k )表示排序集”( 女) 中所有排序中最小的最大完工时间，即， g ( 尼) 2 勰) n z ( ”) ：d m z ( ”) = r ( 记 r ( 七) = j ：r ( 后) = m a x r 0 ) ，g 0 ) + p 女十q j + 1 ， 则 c ( k ) 2 罢絮) c 0 ) + m ) j r ( ) 初值：，r ( o ) = 0 ，c ( o ) 一o ，月( o ) = o 3 递归公式：v 七= 1 ，n r ( 七) = 。，卿p ，m 缸 r ( j ) ，a u ) + p k + q j 十1 ) 、0 9 s k 一1 “。 最优值：兄( 礼) 对于排序问题l i p ，b = o 。i d 。，上述动态规划算法a 给出了一个运行时 间界为o ( n 3 ) 的多项式时间算法 下面，我们考虑在线排序模型； l i o n j j n e ，o ，o ，b = o 。f d 。在此模型中， 批的容量b 可以充分大，也就是，在任何时刻已到达的所有工件可以放在一 批中加工。令u ( 表示时刻t 所有未加工的已到达的工件集合。我们首先给出 问题的一个在线算法。 算法日产 s t 印o ：令ko 。 s t e p1 ：若机器在时刻t 空闲且u ( t ) = o ，转s t e p4 ；否则，对工件集u ( t ) 应 用上述的动态算法a ，并且计算兄( 1 u ( t ) j ) 和e ( 叭) j ) 。令s = m 瓢协r ( j u ( t ) ) ) 。 s t e l ，2 ：在时间区间hs ) 内，如果有新工件 到达，比如在时刻7 ，则令 矿0 7 ) = c ，0 ) u 。重置= 7 ，返回s e p1 。 s t e p3 ：在时刻s ，连续加工由动态算法a 作用于u ( s ) 产生的所有的批。 令= s + c ( i u ( s ) i ) 。返回s z e p1 。 s t e p4 ：若仍有工件到来，令f 为接着到来工件的到达时间，返回& 印l ； 否则，算法在时刻t 终止。 算法注释：在算法日产中，在s 时刻，一旦我们决定加工由动态算法a 产 生的批后，我们需要不间断地将它们加工完毕。若我们将时刻s 产生的批看成 一个“块”，那么由算法h 产产生的排序将是由诸多“块”组成。 1 4 定理2 ：对于排序问题l o n 勘e ，r j ，彩，b = 。i d 。，在线算法卵的竞争比 不会大于2 。 证明：我们设丑和d 2 分别表示最后一个被运到目的地的工件和机器加工 此工件时包含此工件的“块”。设( 若存在) 是在线算法田。中吼之前加工 的“块”。设d + 和毋的开始加工时刻分别为r 和t 。我们考虑下面两种情形； 情形l ：若d + 不存在，由算法研。，我们有扣_ r ( 1 u ( ) j ) 且 d 。( 口) = t + r ( 1 u ( ) i ) = 2 r ( i u ( t ) 1 ) ， 又 d 。( 丌) r ( i u ( t ) 1 ) 因此，我们有 型 2 日。( 丌) 一 情形2 ：若d + 和d 。之间有空闲时间，我们设d f 中工件的最小到达时间为 卜由算法可知t + r 冬t ，根据r 的取值，我们有以下两种子情形： 情形2 1 ；若+ 吼，则分别重置七= ，n k 和s 。令u ( 7 ) = u ( t ) u 以) 。 重置扛7 。 s t e p3 ：在时刻s ，将u ( s ) 中所有工件作为一批进行加工。令扛s + p k 。返 回s f e p1 。 s t e p4 ：若仍有工件到来，令t 为接着到来工件的到达时间，返回e pl ； 否则，算法在时刻t 终止。 1 6 给定一个实例，我们假设毋。总共产生了m 批。我们将这些批按完工时间 不减的顺序进行排列令工件五；) 是第i 批中由算法的s 印l 选取的工件 ，r 和) 分另h 表示工件矗) 的到达时间和运输时间，s ( i ) 表示第i 批的开工时 间我们可以看到，由算法月譬。生成的第i 批或者在时刻( 1 + q ) r ( ；) + n p + n 开始 加工，或者在第i l 批完工时刻( 。( ) + p ) 开始加工。如果在( 1 + d h ) + 叩+ n 吼) 时刻开始加工，我们称之为“规则”批；否则，我们称之为“推迟”批。下面 我们将证明由算法月尹生成的所有批都是规则的 引理3 ：由在线算法月罗产生的所有批都是“规则”批 证明：根据算法月罗，我们知道第一批是一个“规则”批。现假设第i 批是 一个“规则”批，而第i 十1 批是一个“推迟”批。由算法可知，第i + l 批的所 有工件皆在时刻s ( 之后到达因此，我们有 又因为第i + 1 批是一个“推迟”批，我们有 s ( 1 ) 2s ( t ) 十p = ( 1 + ( 】= ) r ( ：) + ( 1 + n ) p + n g ( ，) ( 1 + q ) r “十1 ) + q p + q g “+ 1 ) ( 1 + q ) f ( 1 + q ) r ( ，) + q p 十( 1 9 f ；) j + c i p + q 口( 胖1 ) = ( 2 + o ) r ( 。) + ( 1 + q ) p + q + 。叮( 件】) 。 由上式我们得到a 蚴 r ( 。) 十+ n + 。) ，这就产生了矛盾。故假设不成 立，则第i + 1 批必然是“规则”批。由归纳假设，引理成立。 口 定理4 ：对于排序模型1 o n n n e ，q ，仍= p ，b = 旧。，在线算法爿的 竞争比不会大于1 + n 。 证明：我们考虑一个工件序列l 。设工件 是在线算法爿p 产生的排序一 中第一个达到d 。( a ) 的工件，批且是工件以所在的批。设”是离线情形时的 一个最优排序。由引理3 可知，批b l 是规则批，即，s ( f ) = ( 1 + 。) ”( f ) 十。p + 。蚴。 1 7 因此，我们有 d m 。( 口) = s ( 1 ) + p + q ( z ) = ( 1 + q ) r “) + o p + o 口( f ) + p + 叮( 1 ) = ( 1 + 口) ( r ( f ) + p + q ( 1 ) ) ， 又因为 d m 毗( 7 r ) r ( f ) + p + q ( f ) ， 因此 定理证明完毕 罢喇曼1 + 。 d 。( 7 r ) 一 口 由引理1 和定理4 可知，蟛。是排序模型1 i o n 一e ，吩，劬，聊= p ，b = 。i 。 的一个最好可能的在线算法。 在上面的讨论中，我们的限制条件为肼= p ，事实上，我们在工件间再加 上序约束之后，仍然可以找到最好可能的在线算法。 在工件有序约束的情形下，若一个算法产生的批序列为b s = b ，b k ) ， 这些批的开工时间为s 丁= f s ”，s 竹j ，则我们有如下性质： ( 1 ) 对每一个批瓯，& m a x n ：。，i 鼠 ，地 1 ) ，n ) ； ( 2 ) vl z m l ，叉+ l2 曼+ p ； ( 3 ) 任意选取两个工件以和以，若。五_ 且 毋，乃玩，则。 g 。 在这里，我们引用y “n n ( 2 0 0 5 ) 1 4 等人提出的在线贪婪算法，发现它同时 也是模型1j o n j 抽e ，r ，q ，功= n p r b = 。l d 的一个最好可能的在线算法。 算法g a ： s 蛔) l ：令= o 。 s 印2 ：在时刻a p + 坳，将那些已到达的且无前任的或前任已加工完毕的 1 8 工件形成第七+ 1 批加工( 在这里，我们允许批中无任何工件) 。 m 印3 ：令七= 后+ 1 ，转回s 卸2 类似y 札。礼等人【1 4 】的证明，我们有 定理5 ：对于排序模型1 i o n 一曲e ，o ，功= p ，矿e c ，b = o o l d 。，上述g a 算 法的竞争比不会超过1 + n 。 证明：给定一个排序实例l ，我们设丌= ( b s t + ) 是实例工的一个最优 排序，其中b p = 日，磷) ，s t + = 研，碟) ；我们设一= ( b s ，s 丁) 是实例上在算法g a 下的排序，其中b s = bh 鼠 ，盯= s 1 1 ，叉) ， 则我们有& = ( q + z 一1 ) p ，v 1 z n 。任意的工件如，若如域，则 现( ”) = + p + 劬；若以玩，则功( 口) = 岛+ p + 劬= ( a + ) p + 。我们令 岛= ( n 一1 ) p ，贝4s = 8 一】+ p = ( q 十i 一1 ) p ， v1 is 礼 首先，我们有下面的两个论断： 论断1 ：任取工件易，功( 一) b ( ”) + p 。 若存在工件。厶，使得功( o ) d j ( ”) + p ，我们取占为实例l 中第一个满足 这样条件的工件，并设乃彤且易岛。 若。可，马( 7 r ) 印+ 2 p + 彤，又因为功( = ( q + 汩+ ，于是， d ( 一) 岛一- 或者存在 邑一， 使得 _ s l ，我们有功( 7 r ) 三o + p + s 一1 + p + = ( q + 口一 2 巾+ p + = ( a + 一1 ) p + 田= s + ，则b ( 盯) = ，s + p + 毋 b ( 7 r ) + p ，与假 设矛盾。 。隋形2 ：若存在 b 川，使得 _ 如。根据如是第一个满足假设的 工件可知：d 。( 一) q ( ”) + p ，于是，我们有g ( 仃) g ( ”) + p 。又因为， 1 9 屿2g ( o ) + p + 劬且q ( 7 r ) a ( 7 r ) + p ，所以， 功( 口) = q ( 口) + p + q ( ”) + 2 p + 劬 g ( 丌) + p + 如= d ( 丌) + p ，与假设矛盾 论断2 ：任取工件占，b ( 叫( 1 + a ) b ( 丌) 若b ( ”) ( 1 十n ) p ，根据论断1 ，我们有 粼 哿南外nd i ( 7 r ) 、d i ( 丌) 1 。d ，( 7 r ) 2 1 。“ 若马( ”) ( 1 + 。) p ，我们有乃研，q 叩，且以无前任，故山b ，。 因此， q ( 叫= ( 1 + o ) p 十。又因为功( 丌) p + 啦 裂 业业 1 + 。 b ( 7 r ) 、p + 吼 2 ”一 设j f 是最后一个被运到目的地的工件，则d 。( a ) 一d j 曼( 1 + a ) d j ( 丌) 。又 三i m 。( 丌) d l ( 丌) ，因此，我们有 剖粼d 。( 7 r ) d f ( 7 r ) 一 定理证明完毕。n 引理1 和定理5 表明算法g a 是排序问题1 j 彻一“n b q ，。，乃：p ，e c ，b 。 。1 d 一一个最好可能的在线算法。 以上我们考虑了批容量无界的模型，下面我们将讨论批容量有界的情形。 2 2批容量有界情形 对批容量有界的情形，首先我们考虑工件同时到达的模型：1 b ，盼，b n i d m n 。对于此模型， b r 乱c 七c r ( 1 9 9 8 ) 等人 8 证明了它是p 一困难的。 下面我们考虑排序问题1 旧一j 抽e ，q ，劬，b 训。的在线算法。首先我们给 出b n r o f 出提出的f b l p 丁算法。 2 0 算法f b l 尸t s t e p1 ：将工件按加工时间不增的顺序排列，即p l p 2 m 。 s t e p2 ：从第i b + 1 个工件开始，至第( i + 1 ) b 个工件形成一批，其中 江o ，f 礼卅，m 表示小于z + l 的最大整数 s t e p3 ：按s t e p2 中形成批的顺序依次进行加工。 对于排序模型1 1 0 n j j ne ，n ，b l 。，根据上述f b l p 丁算法，人们已经 讨论了一系列以此算法思想为基础的在线算法。随后，尸0 0 礼等人【1 3 将这些 算法定义为f b 工p 丁一6 s e 算法，并证明了这些算法的竞争比不超过2 。下面 我们给出l e e ，比s 叫( 1 9 9 3 ) 9 】中提到的g r l p t 算法，并证明此算法对排序问 题1 f o n f j n e ，r ，劬，b n l 正 m 。是一个竞争比为3 的在线算法。在这里，我们仍用 u ( t ) 表示t 时刻所有已到的但仍未加工的工件的集合 算法g r l p t ： s t e po ：令t = o 。 s t e pl ：若u ( ) = o ，转s 卸2 ；否则，在时刻t ，从u ( t ) 中选取= m i n b ，l 矿( ) l 个最长加工时间的工件形成批进行加工，令t = + p ，其中 p = m 哟u ( ) 协) 。重置u ( ) 。转回s 印l ； s t e p2 ：等待新的工件到来，若仍有新工件到来，令为新工件的第一个到 达时间，转e p1 ；否则，算法终止。 根据p 0 0 n 等人 1 3 】的证明，g r l p t 算法是一个f b 工p t 一蚰s e 在线算法， 且它的竞争比不超过2 。于是，我们有 引理6 ：( 尸d o n ，y u ) 1 3 】对于排序模型1 伽一j 抽e ，o ，b n i g 。， g r l p 丁1 算法 是它的一个竞争比不超过2 的在线算法。 口 根据引理6 ，我们易得到下面定理： 定理7 ：对于排序问题1 l o n 一血n e ，? ，b 旧，上述的g r l p r 算法是一 2 1 个竞争比不超过3 的在线算法。 证明：我们用盯表示排序问题1 i o n j j n e q ，毋，b 叫历一在g r l p t 算法下 的排序，”，表示对应的离线情形下的一个最优排序。用丌。表示上述在线问题 中忽略运输时间后所对应的离线情形下的一个最优排序。记最后一个被运 到目的地的工件为五，其加工时间为缅由引理6 可知， c m 。p ) 墨2 c k 。( 丌2 ) 又因为 c k 。( 7 r 2 ) 茎l 二k 。( 7 r ，) 曼d m 。( 7 r 1 ) ， q f k 。( ”1 ) 所以，我们有 d 。( 口) ( k 。( 口) + 哦 2 c k 。( 7 r 2 ) + 锄 曼3 d ( 7 r 1 ) 定理证明完毕。 口 上面我们讨论了批容量有界情形下一般模型的在线算法，得到了一个竞争 比为3 的在线算法。若我们对工件的加工时间加以限制，比如p f = p ，即所有 工件加工时间相同，我们将给出一个最好可能的在线算法。首先我们考虑工件 到达时间一样时，类似常见的f b l p t 算法，我们给出一个多项式时间算法， 简记为f b l d t ( f u f fb a c l n r 9 e 毹d e 托u e r 丁i l e ) 。 算法，b l d t s t e p1 ：将工件按运输时间不增的顺序排列，即q ，2q 2 。 s t e p2 ：从第i b + 1 个工件开始，至第( i + 1 ) b 个工件形成一批，其中i o ，n b ，m 表示小于z + 1 最大整数。 s t 印3 ：按s t e p2 中形成批的顺序依次进行加工。 定理8 ：对于排序模型1 峙= p ，b 圳d 。，上述f b 三d t 算法是一个最 优算法 证明：类似于算法f b 上p 丁的证明，我们采取常用的二交换方法。设r = ，厶) 是一个工件集合假设”是r 的一个最优排序，并设丌由七批组 成，记为日，吼若存在工件 玩和工件以岛满足：啦 且 1 z ，则我们交换以和五的位置，记新产生的排序为丌7 。设批玩在 排序”中的开工时间为t ，我们有 d i ( 丌) = t + p + 吼；d j ( 丌) = + 白一。+ 1 ) p + q j 另一方面，在排序”7 中，我们有 功( 丌) = t 十p + 劬；n ( 7 r ) = + ( 一z + 1 ) p + 吼 i ) t ( 丌7 ) d j ( 丌) 口。( 丌) ，d ，( 7 r ) d ，( 7 r ) d 。( 丌) 注意到，对任意的 r ，以 ，仇( ”) 并未改变。因此，d 。( ”) sd ( ”) 。 重复上述操作一直到最优排序中不存在这样的工件以和以。定理得证。 口 下面我们将讨论在线排序模型l i o n j j n e ，r ，骱= p ，b n l 口。在此模型 中，不失一般性，我们假设工件的第一个到达时间为o 。给定一个工件集合， 我们任意选取一个具有最长运输时间的工件，把