（运筹学与控制论专业论文）几类特殊的分批排序问题.pdf

摘要 平行分批排序和在线排序是两个发展比较迅速的排序模型平行分批排序 是指机器可以同时加工多个工件，每批包含的工件同时开工同时完工，批的加 工时间是这批工件中加工时间的最大者在线排序是指工件信息在其到达之前 是一无所知的，并且一旦工件被安排后就不允许再改变 本文主要考虑了几类特殊的分批排序问题。首先研究了工件具有相容约束 的带有运输的单机平行分批排序问题。在这里，我们有一台批处理机和充分多的 车辆有n 个同工时的工件 ，如，厶，每个工件的加工时间为p ，运输时间为劬 这些工件间有的工件可以在同一批中加工，而有的则不能在同一个批中加工一 批完工后并行地运输这里的目标函数是工件最后运达顾客的时间我们把这 些工件分别对应于一个图g 中不同的顶点，如果工件是相容的，则图g 中对应 的顶点间就可以连边，否则就不连边通过这一转换，我们就把工件的相容性约 束通过图论中具体的团来刻画，从而使解决相容性约束条件下的排序问题显得 更加直观于是我们所考虑的模型可记为l i p - b a t c h ；p j = p ，q j ；g i d 。，其中，图g 就是代表我们所讨论的工件相容约束性，d 。= m a x d j l 功= g + 劬，1 ，n 由张群发的硕士学位论文【8 】可知1 p - b a t c h ；p j = p ；g l g 一是n p 一困难的，从而 我们的问题亦是n p - 困难的相容约束图限定为某些特殊图类时，本文给出了 多项式时间算法主要结论如下： ( 1 ) 相容约束图g 限定为分裂图时，文中给出了问题l l p - b a t c h ；p j = p ，q j ；g l d 一 的时间界为d ( 住z ) 的最优算法 ( 2 ) 相容约束图g 限定为完全二部图时，文中给出了问题1 p - b a t c h ；p j = p ，劬；g i d m 。的时间界为o ( nl o g n ) 的最优算法 ( 3 ) 相容约束图g 限定为完全m 都图时，文中给出了问题l p - b a t e h ；p j = p q j ；a l d 。的时间界为o ( n l o g n ) 的最优算法 ( 4 ) 相容约束图g 限定为直径不超过4 的树时，文中给出了问题1 p - b a t c h ；p j = p ，劬；g l d r 。的时间界为0 ( n l o g n ) 的最优算法。 其次，本文对带有禁用区间的目标为最小化最大完工时间的单机平行分批 排序问题进行了研究在经典排序中，所有机器都是假设在整个加工过程中一 直可用。然而，这个假设往往太过理想，在实际生产过程中，情形可能并非如 此。由于对机器的预防性维修或机器突然出现故障都会导致机器在某一段时 间内不能使用，有时候我们也把机器不能使用的这一段时间叫做机器的禁用区 间我们假设机器的禁用区间是在工件就绪前已经确定的工件就只能在剩下 的时间内加工文中考虑两种禁用情形：若一个批在禁用区间之前未能完工而 它在机器重新可用后可以接续加工，这种情形称为可继续的，用记号r - a 来表 示；若该批不可接续而只能重启，即从头开始加工，我们称为不可继续的，用 记号n r - a 表示，这是借文献【1 0 】的用法本文对离线情形，要么给出了多项式 时间算法，要么给出了近似算法；对一般在线情形，给出了其竞争比的下界可 任意大的证明，并对特殊情形给出了最好可能的算法 本文最后对带有强制工件的单机在线分批排序问题进行了讨论这里所 有工件都是在线的，但是，其中有一些特殊工件，它们要求单独成批，其它 工件不能与其共批，并且一旦到达就要对其立即加工，我们称其为强制工件 ( m a s t e rj o b ) ，其它工件称为自由工件假设强制工件间不冲突该模型可记为 l l m a s t e r j o b ；p - b a t c h ，6 ；o n 一h e ，r j l g 。文中考虑了和强制工件相冲突的批可中断 ( p m t n ) 与需要重启( r e s t a r t ) 两种情形，主要结果如下： ( 5 ) 给出了问题l m a s t e r j o b ( r e s t a r t ) ；p - b a t c h ，b = o o ；o n 1 i n e , q i g 。的竞争比下 界及最好可能算法 ( 6 ) 给出了问题1 m a s t e r j o b ( r e s t a r t ) ；p - b a t c h ，b n ；o n l i n e , 吩1 。的竞争比下 界及最好可能算法 关键词：单机；平行分批；在线；相容性；竞争比；禁用区间；强制工件 a b s t r a c t r e c e n t l y , p a r a l l e lb a t c hs c h e d u l i n ga n do n l i n es 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 p a r a l l e lb a t c hs c h e d u l i n gm e a n $ t h a tam a c h i n ec a np r o c e s ss e v e r a lj o b ss i m u l t a n e o u s l ya sab a t c h ，a n da l lj o b si nab a t c hs t a r ta n dc o m p l e t ea tt h es a m et i m e t h e p r o c e s s i n gt i m eo fab a t c hi se q u a lt ot h el o n g e s tp r o c e s s i n gt i m eo ft h ej o b sa s s i g n e dt o i 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 du n t i li t sc o m p l e t i o n o n l i n es c h e d u l i n g m e a n st h a ta l lj o b 8i n f o r m a t i o na 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 s s c h e d u l e di tc a n n o tb ec h a n g e d i nt h i sp a p e r ，w em a i n l yc o n s i d e rs o m es p e c i a lm o d e l so nb a t c hs c h e d u l i n g f i r s to f a l l ，w ei n v e s t i g a t et h es i n g l em a c h i n ep a r a l l e lb a t c hs c h e d u l i n gp r o b l e mw i t hj o bc o m p a t - i b i l i t yc o n s t r a i n t sa n dd e l i v e r yt i m e h e r e ，w eh a v eab a t c h i n gm a c h i n ea n ds u f f i c i e n t l y m a n yv e h i c l e s t h e r ea r enj o b s 以，如，厶，e a c ho fw h i c hh a st h es a m ep r o c e s s i n gt i m e pa n dad e l i v e r yt i m e 毋t h ej o b sc a l lb ep r o c e s s e di nab a t c hi fa n do n l yi ft h e ys a t i s f y t h er e l a t i o no fc o m p a t i b i l i t y ab a t c hc a nb ed e l i v e r e dt ot h ed e s t i n a t i o nb yav e h i c l ea 8 s o o na si ti sc o m p l e t e d o u ro b j e c t i v ei st om i n i m i z et h et i m eb yw h i c ha l lj o b sh a v eb e e n d e l i v e r e d n o ww ec o n s t r u c tag r a p hga sf o l l o w s ：c o n s i d e rt h ej o b s ，j 2 ，厶a st h e v e r t i c e so fg r a p hg ；a n dj o i nt h ej o b s ( v e r t i c e s ) 五a n dj ji ft h e ya r ec o m p a t i b l ea n dc a n b ep r o c e s s e di no n eb a t c h i ti se a s yt os e et h a tt h ej o b ss c h e d u l e di nt h es a m eb a t c hm u s t b eac l i q u ei ng r a p hg w ed e n o t et h i sm o d e lb y 1 p - b a t c h ；p l = p ，毋；g i d ，m z ，w h e r ed 。= m a x 功i 岛= c + 叻，1 曼j 礼 n o mz h a n gq u n f a 8d i s s e r t a t i o n s ，w ek n o w1i p - b a t c h ；办= p ；g i a mi 8n p - h a r d ，s o t h ep r o b l e mw ec o n s i d e ri sa l s on p h a r d f o rs o m es p e c i a lg r a p h s ，w eg i v ep o l y n o m i a l a l g o r i t h m s t h em a i nc o n c l u s i o n sa r ea sf o l l o w s ： ( 1 ) w h e nt h eg r a p hg i sl i m i t e dt oas p l i tg r a p h ，w eg i v ea no p t i m a la l g o r i t h mw i t h t h er u n n i n gt i m ed ( n 2 ) ( 2 ) w h e nt h eg r a p hgi sl i m i t e dt oac o m p l e t eb i p a r t i t eg r a p h ，w eg i v ea no p t i m a l a l g o r i t h mw i t hr u n n i n gt i m ed ml o gn ) i i i ( 3 ) w h e nt h eg r a p hg i sl i m i t e dt oac o m p l e t em p a r t i t eg r a p h ，w eg i v ea l lo p t i m a l a l g o r i t h mw i t hr u n n i n gt i m eo ( nl o gn ) ( 4 ) w h e nt h eg r a p hg i sl i m i t e dt oat r e ew i t hd i a m e t e rn om o r et h a n4 ，w eg i v ea n o p t i m a la l g o r i t h mw i t hr u n n i n gt i m eo ( nl o gn ) t h e n ，w ec o n s i d e rt h es i n g l em a c h i n ep a r a l l e lb a t c hs c h e d u l i n gw i t ha na v a i l a b i l i t y c o n s t r a i n t m o s tl i t e r a t u r ei ns c h e d u l i n ga s s u m e st h a tm a c h i n e sa r ea v a i l a b l ea ta l lt i m e s h o w e v e rt h i sa v a i l a b i l i t ya s s u m p t i o nm a yn o tb et r e ei np r a c t i c e f o re x a m p l e ，am a c h i n e m a yn o tb ea v a i l a b l ei nt h es c h e d u l i n gp e r i o dd u et op r e v e n t i v em a i n t e n a n c eo ras u d d e n b r e a k d o w n w ea s s u m et h a tt h eu n a v a i l a b l et i m ei sk n o w ni na d v a n c e t w oc a s e sa r e c o n s i d e r e d ：o n ei sc a l l e dr e s u m a b l e ( r - a ) p r o v i d e dt h a ti fab a t c hc a n n o tb ef i n i s h e d b e f o r et h eu n a v a i l a b l ep e r i o do fam a c h i n e ，t h e ni tc a nc o n t i n u ea f t e rt h em a c h i n eb e c o m e s a v a i l a b l ea g a i n t h eo t h e ri sc a l l e dn o n r e s u m a b l e ( n r - a ) i ft h eb a t c hh a st or e s t a r tr a t h e r t h a nc o n t i n u e i ti sf o l l o w i n gt h en o t a t i o no ff 1 0 i nt h eo f f - l i n ec a s e ，w eg i v ee i t h e ra p o l y n o m i a la l g o r i t h mo r a na p p r o x i m a t i o na l g o r i t h m i nt h eo n - l i n ec a f l e ，w eg i v eap r o o f t h a tt h el o w e rb o u n do fc o m p e t i t i v er a t i oc a ub ea r b i t r a r i l yl a r g ea n da l s og i v ea no p t i m a l o n - l i n ea l g o r i t h mi nas p e c i a lc a s e f i n a l l y , w ed i s c u s sa l lo n l i n em o d e l ：o n - l i n es c h e d u l i n gw i t hm a s t e rj o b so nas i n g l e b a t c h i n gm a c h i n e h e r e ，a l lj o b sa r eo n - l i n e t h e r ea r es o m es p e c i a lj o b s ，o fw h i c he a c hh a s t os c h e d u l ei na s i n g l eb a t c hr e s p e c t i v e l ya n dm u s tb ep r o c e s s e do n c ei tc o m e s w ec a l lt h e m m a s t e r j o b s ，o t h e r s f r e e j o b s d e n o t e t h i s m o d e l b y l l m a s t e r j o k p - b a t c h ，b ；o n - n n e , 勺l g w ec o n s i d e rt w oc a s e s ：t h eb a t c hm e e t i n gw i t ham a s t e rj o bc a nc o n t i n u ea n dm u s tr e s t a r t t h em a i nc o n c l u s i o n sa r e 鞠f o l l o w s ： ( 5 ) f o rt h em o d e ll i m a s t e r j o b ( r e s t a r t ) ；p - b a t c h ，b = o o ；o n - l i n e ，q l g m ，w eg i v ea b e s tp o s s i b l eo 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 o2 ( 6 ) f o rt h em o d e ll l m a s t e r j o b ( r e s t a r t ) ；p - b a t c h ，b 0 ，a 都是优化问题p 的一个 ( 1 + s ) 一因子的近似算法，那么算法a 称为尹的一个近似方案 1 2在线排序和分批排序 本文主要涉及到现代排序中的在线排序和分批排序下面我们将对这两个 模型作简单介绍： 在经典排序中，一般假设一个实例的所有信息，包括工件的个数，到达时 间、加工时间等在开始排序前都是事先知道的。这种情形我们称为是离线的 然而在现实生活中许多情况并非如此，决策者需要在所有信息到来之前就必须 进行决策这种情形我们称为是在线( 0 1 1 i e ) 或者是半在线( s e m io n ，l i e ) 的 在在线排序中，工件信息是逐个释放的，决策者在决定当前工件的加工时对其 后的到达工件是一无所知的，并且一旦决定工件安排后就不允许改变 根据工件的到达方式，在线排序分为两种： ( 1 ) 按序( o v e r 船0 在线排序：工件是排列成一个表逐个出现的。一个工件 只有当表中排在其前面的工件都安排后才知道这个工件的相关信息 ( 2 ) 按时( o v e rt i m e ) 在线排序：工件随着时间进行安排，在任何时刻只知道 当前已到达工件的信息。 3 事实上，在按时在线排序中，又有两种分类：第一种是工件的信息，如加 工时间，在工件到达时就可知道；第二种就是工件的信息在其加工完时才能被 “告知”而在本文中我们主要考虑第一种按时在线排序 由于在线排序问题( 除个别目标函数外) 通常不存在最优算法，因此，我 们往往考虑它们的近似算法通常我们用在线排序算法的竞争比来衡量它的优 劣，即把在线算法的结果与对相同工件运用离线排序算法得到结果进行比较 我们定义在线算法a 的竞争比r a 是排序问题所有实例的比值暑苎的上确界， 其中c k 和分别由算法a 得到的目标函数值和相应的离线排序的最优值 然而，由于对未来工件信息的未知，我们很难找到一个在线算法达到最优因 此，r a 的值往往大于1 另一方面，对于一个在线问题，我们可以设计不同 的在线算法来区分它们的。好坏”我们的目标是设计竞争比尽可能小的在线 算法 在经典排序中，我们还假设任何机器任何时刻最多只能加工一个工件，而 实际生活中有的“机器”可以同时加工多个“工件”例如，一个烤箱可同时烘烤多 个面包最典型的是发生在大规模集成电路的生产中，为了保证成品合格，检验 阶段要把集成电路放在烘箱中试验它们的耐温性能一个烘箱可以同时检测多 个集成电路，而且在检测过程中不可以移走任何集成电路这种机器可以同时加 工多个工件的排序问题称为分批加工机器排序( s c h e d u l i n gab a t c h i n gm a c h i n e ) 分批排序问题与经典排序问题的不同在于若干个工件可以在一批中加工， 工件加工过程中不允许中断，也不允许移走正在加工的工件在分批排序中， 如何确定批是问题的关键，一旦批确定后，就可将批视为一个工件来寻找其最 优算法或近似算法根据每批的加工时间的定义不同，它又可分为“并行工件 同时被加工的排序”( p a r a l l e lh a t c h i n gp r o b l e m s ) 和“串行工件同时被加工的排 序”( s e r i a lb a t c h i n gp r o b l e m s ) 前者每批的加工时间是这批工件中所有工件加 工时间的最大者；后者每批的加工时间是这批工件中所有工件加工时间之和 本文我们所考虑的模型是前者 4 1 3排序的记号 1 9 7 9 年，g r a h a m 等人f 6 】提出用三参数来表示一个排序问题。在这里，我 们采用qi 卢i ，y 来表示，其中n 域表示机器状况，卢域表示工件状况，7 域表 示将要极小化的目标函数采用这种记法，我们研究的排序模型可以表示为： l i p - b a t c h ；乃= p ，彩；g i d ，。，l l r - a ；p - b a t c h ，6 ；0 1 3 一l i n e ，q i 瓯“， 1 n r - a ；p - b a t c h ，6 ；o n l i n e , r j i g m ，l m a s t e r j o b ；p - b a t c h ，6 - o n - l i n e , 吩i g m 下面我们对常用的和在上述模型中出现的符号作出说明： ( 1 ) 口域； a = 1 单台机器 n = p 相同的平行机 o t = q 一致的平行机 o t = r 无关的平行机 ( 2 ) 域： 卢= 吩工件的到达时间 芦= 毋工件的运输时间 p = 也工件的工期 = “办= p ”工件有相同工时 卢= p r e c 工件间有序约束 卢= n r - a 工件在禁用区间后不可继续 声= m a s t e r j o b 含有强制性工件 卢= g 工件间具有相容约束条件 卢= o n l i n e - l i s t 工件是按序在线 卢= 0 1 3 1 一l i n e , r j 工件是按时在线 ( 3 ) ，y 域： 首先，我们介绍一些符号： q 工件乃的完工时间 易工件易的延迟时间，这里，l j = 劬一也 5 功工件如被运到目的地的时间，这里，功= 0 + 彩 乃工件乃的延误时间 码工件乃的误工记数 现在，我们介绍一些目标函数： 7 = a 。最大完工时间，此处，g 。= m a x 0 1 1 j 礼) 7 = l 。最大延迟，此处，工，= m a x l j l l j n ) ，y = d ，一工件最后运达顾客的时间，此处，口一= m a x t d j l l j 扎， 其中功= 岛+ 彩 7 = e 0 完工时间和 7 = e w j 0 加权完工时间和 7 = e t j 误工时间和 1 = e w i t s 加权误工时间和 ，y = u s 误工工件数 ，y = w s u s 加权误工工件数 1 4相关结果及本文主要结果 本节我们主要介绍本文研究的排序模型以及现有文献中有关此类模型的 相关结果，最后列出本文的主要结果 对于排序模型l i o n 一h e , r s ；p - b a t c h ，6 | g 。，已有大量文献进行过研究在离线 情形下，当所有工件的到达时间相同时，b r u c k e r ( 1 9 9 8 ) 1 1 】和l e e ，u z s o y ( 1 9 9 9 ) 1 2 】 提到了由b a r t h o l d i 发现的f b l p t 最优算法( 即每次总是优先考虑已到达工件 中加工时间最长工件进行装批) ，此算法在分批排序中有着重要的作用；当所 有工件的到达时间不同，批容量无界( b = 0 0 ) 时，l e e ，u z s o y ( 1 9 9 9 ) 1 2 给出了一 个动态规划算法，而批容量有界( b n ) 时，b r u c k e r ( 1 9 9 s ) 1 1 】和l i u ，y u ( 2 0 0 0 ) 1 3 】 证明了此问题是n p 一困难的在在线情形下，d e n g ( 2 0 0 3 ) 1 5 】和z h a n g ( 2 0 0 1 ) 1 4 1 对平行分批加工在线排序问题进行了研究他们独立地证明了此模型所有在线 算法的下界为( 、，百+ 1 ) 2 ，并且，在批容量无界( b = o o ) 时，找到了与此下界吻 6 合的最好可能的在线算法；在批容量有界( b 秭( 件1 ) 且虬，( ) 口t ，扎 k 运用基本不等式( 2 ) ( 其中的。替换为醵可知： m a x i p + m a x ( q - ( i ) ，0 ( i ) ) ，0 + d p + m a x ( q - ( i + 1 ) ，k ，“+ 1 ) ) ) = m a x i p + ，i p + & ，( i + 1 ) p + 岱，( i + 1 ) p + & ) 2 伽z 细+ q a ，咖+ k ，( i + 1 ) p + 吼，( i + 1 ) p + k ) = m a 卫 i p + m a x ( q - ( i ) ，k 唯+ 1 ) ) ，( i + d p + m a x ( q - ( i + 1 ) ，姊( i ) ) 也就是消除逆序后，可使( 3 ) 右端下降如序列t q 霄( ) 与 k ，( 订) 仍有逆序，可 继续此法直至没有逆序为止，即使得，r 变为丌，从而( 3 ) 得证 我们进一步证明 兰答 i p + m a x ( q i ，玩) ) l m ：；a ! x 。 i p + 仇凹( ( ) ，k ( 日) ) ( 4 ) 令( ) = m a x ( q ，r ( i ) ，k ( i ) ) ，则上式可改写为 1 m 坐a x 。 i p + a i 迟搭 咖+ 。”( 1 ) ) ， 1 3 其中a 。n 2 运用基本不等式( 2 ) ，对相邻两项进行2 交换，即可导 出此不等式，从而( 4 ) 得证 将( 3 ) 与( 4 ) 结合起来，即得到不等式( 1 ) 证毕 口 有了上面命题作保证，我们就可以给出完全二部图条件下的平行分批排序 问题的算法 给定完全二部图g = ( x ，y ；e ) ，其中x = 譬l ，g m ，y = 6 l ，k ，而且 q i 、幻也分别代表相应工件的运输时间不失一般性，我们假定m n 算法c b g s t e p1 ：对工件重新标号使得q l 啦2 ，b l 6 2 b n s t e p2 ：将工件m 和瞳0 = 1 ，2 ，m ) 安排在同一批，而其余每个工件h a m - b a t c h ；p j = p ，口j ；t r e ew i t h d 4 d l 一的最优分批 1 7 第三章带有禁用区间的单机平行分批排序问题 3 1预备知识 经典排序中，所有机器都是假设在整个加工过程中一直可用然而，这个 假设往往太过理想，在实际生产过程中，情形可能并非如此由于对机器的预 防性维修或机器突然出现故障都会导致机器在某一段时间内不能使用，有时候 我们也把机器不能使用的这一段时间叫做机器的禁用区间，记为【厶同我们假 设机器的禁用区间是在工件就绪前已经确定的工件就只能在剩下的时间区间 内加工 工r 文中将考虑两种禁用情形，可继续的( r e s u m b l e ) 和不可继续的( n o n r e s u m b l e ) 如果一批在禁用区间之前未能完工而它在机器重新可用后可以接续加工，这种 情形称为可继续的，记为r - a ；如果该批不可接续而只能重启，即从头开始加 工，我们称为不可继续的，记为l l - a 对于机器带有禁用区间的单机离线排序问题l l n r - a l c 一，l e e 1 0 】给出了n p - 困难性的证明，证明l p t ( t h el o n g e s tp r o c e s s i n gt i m ef i r s t ) 算法的最坏性能比为 ； h e ，j i ，和c h e n g 2 0 则给出了一个完全多项式时间近似方案 对于在线算法，我们用竞争比来衡量一个在线算法的优良程度设c 日( 工) ， c ( l ) 分别表示对任意输入的工件序列l ，在线算法日得到的最大完工时间和 离线情形下得到的最优值我们定义算法日的竞争比r 日如下： r h = s u p c 月( l ) c ( l ) ) f 山 也就是说竞争比是对所有工件序列l ，c 日( l ) 与c ( l ) 比值的上确界。竞争比 越小，说明算法越好在不引起混淆的情况下，我们把c ( 三) 和c + ( 工) 简记为 c 日和口。 1 8 对于单机平行分批在线排序问题：l i o n l i n e , r j ；p - b a t c h ，6 g 一，g z h a n g 【1 4 】 等人进行了研究，证明了此模型所有在线算法的下界为l + a ，其中a = ( 怕一1 ) 2 ， 并且在批容量无界时，给出了与此下界吻合的最好可能的在线算法卵；在批 容量有界( b p k ，则重置k = h 及戗，马令u ( t ) = u ( t ) u ，重置t = f s t e p3 ；在时刻点毛把u ( 8 ) 中所有工件做为一整批开始加工著直到时刻 s + m ，有新工件到来，则令t = s + 鲰；否则，等待直至一新工件到来，令t 为此 工件的到达时间，返回s t e p1 算法日b 1 9 用u ( t ) 来表示时刻t 可以安排的工件集 s t e po ：令t = 0 ，u ( o ) = j , i r s 2 o ) s t e p1 ：对工件集u ( t ) 应用f b 工p t 得到m ( t ) 个批如果m ( t ) = 0 ，也就是 说，这一时刻无可排工件，则执行s t e p3 假如m ( t ) 1 ，记p ( t ) 和r ( t ) 分别 是最长批中最大工件的加工时间和到达时间如果t ( 1 + n ) r ( t ) + 叩( t ) ，那么 在t 时刻开始加工最长批并且重置t 为该批的完工时间，返回s t e p1 否则执 行s t e p2 s t e p2 。如果m ( t ) = 1 ，重置t 为( 1 + o ) r ( t ) + a p ( t ) 和下一工件到达时间 的最小值；否则，在t 时刻开始加工最短批并且重置t 为该批完成时间，返回 s t e p1 s t e p3t 如果仍有工件到来，重置t 为下一个工件的到达时间，返回s t e p 1 ；否则，算法在时刻t 终止 3 2离线情形 机器的禁用区间，我们记为陋，捌用记号_ r - a 表示可继续情形，用i - a 表 示不可继续情形 命题1 问题1j r - a ；p - b a t c h ，b = o o i c k 。是多项式时间可解的 事实上，所有工件放在一批中即可若该批在时刻l 之前加工不完，时刻 r 之后接续加工 命题2 问题l l r - a ；p - b a t c h ，b 叫g 。是多项式时间可解的 事实上，f b l p t 算法即是最优的若某批在时刻二之前加工不完，时刻 r 之后接续加工该批，然后加工其它批 命题3 问题l i n t - a ；p - b a t c h ，b = i g 一是多项式时间可廨的 事实上，所有工件放在一批中即可若该批加工时间大于，则把其放在 时刻r 开始加工 命题4 问题1 n r - a ；p - b a t c h ，b n l g 。是n p h a r d 的 证明：我们有如下两个论断： 论断1 对任意实例，存在这样的最优解，其分批方式是f b l p t 的 对任意实例，首先对所有工件按加工时间重新标号，使得p 。p 2 取，的任一最优解，可以用二交换法得到具有如下性质的最优批：各批 工件标号连续然后按批的加工时间不减的顺序将邻批中长工件依次调到长批 中，将长批补成满批依次类推，最终得到的批显然是f b l p t 的而目标值 不增，故仍是最优的 论断2 问题( d ：i n r - a ；p - b a t c h ，b n l g 一与问题( i i ) ：l l 弘a l q 一是等价 的 对( d 的任意实例j ，首先对工件按f b l p t 进行分批，得到m 个批 b l ，一，b m 各批最长工件记为 ，知构造( ，) 的实例，包含m 个工件：以，知取同一个门槛值若j 有可行解的话，显然，有一目标 值相等的可行解反之，对( ，) 的任意实例 ，工件为： ，厶构造( ，) 的实例 ，包含概个工件，其中p 1 1 9 2 一p b = m ；p 一一p 2 6 = 2 】 弛；p ( 。一l 一一m = 鼽，同一个门槛值若j 有可行解的话，由论断1 可 知，有一目标值相等的可行解 而我们已经知道，问题l l n r - a l g 。是n p h a r d 的( 二划分问题作归结 ( l e e i o ) ) ，当有多个禁用区间的话，该问题就变成强p h a r d 的( 三划分问题 作归结) 综上命题得证 口 下面我们将给出问题i m r - a ；p - b a t c h ，b 礼f g 。的一个近似算法 算法m l p t ： s t e p1 ；对工件按f b l p t 进行分批 s t e p2 ：对得到的批按l p t 重新标号 s t e p3 ：对批按照从小到大的标号分配给机器加工 定理对于排序问题 1i n r - a ；p - b a t c h ，b 训g n “， m l p t 是一个4 孓近似算法 证明： 对( i ) 的任意实例j ，记其最优值及算法目标值为c ，c 舭胛按照上命题 论断2 中提到的方法来构造( i i ) 的实例，的最优值及算法l p t 的目标值 记为a ，白刀由于l p t 对问题l l 肚a f a 是紧4 3 一近似的( l e e 1 0 ) ，有 a 。丹a 。4 3 由上命题证明过程中论断1 、论断2 可知俨= a + ，c u l p t = c 刀从而c 肌刀肥4 3 故m 工p t 是问题l i r a - a ；p - b a t c h ，b n i g 。的一个 4 1 3 近似算法，且紧的 口 类似于y h e 2 0 l ，我们可以给出问题l i n t - a ；p - b a t c h ，b 1 ，第一个工件 于 零时刻到达，加工时间p ，= 1 对任意算法a ， c a s e l ：若算法a 在s 一1 时刻之前未开始加工 ，则不再来工件，此时 c s ，而c + = 1 ，故c a c + 2s c a s e 2 ：若算法a 在t 时刻( 0st 8 1 ) 开始加工工件 ，则第二个工件 j 2 在t + e ( 8 1 ) 时刻到来，其中p 2 = s t e ，不再来工件显然， c m s + s t e 一( s t 一1 ) = m s + 1 一g 但是在t + 时刻 与也并成一批加工，可得最优值即c kt + e + 0 一t e ) = s 从而c a c 半= m + 孚芝m 当s ，m 比较大时，可知命题成立 口 下面我们考虑一种特殊情形 3 1 1 事先知道在时刻r 之后会有工件来到，即r n a a x r 我们考虑排序问题：1 i t - a ；p - b a t c h ，6 ；o n l i n e , r j ，r m n x r i 。的特殊情形 l i p - b a t c h ，6 ；o n - l i n e ，吩l g ， 那么后者的算法的竞争比下界必是前者在线算法的竞争比下界 我们引用如下： 引理2 ( z h a n g ( 2 0 0 1 ) 1 4 ) 对于排序问题 l i p - b a t c h ，6 ；o n 一h e , q i g m ， 不存在在线算法使得其竞争比小于1 + n ，其中a = ( 怕一1 ) 2 口 通过上面引理可知，对于批容量无界和批容量有界两种情形，上述下界都 是通用的 2 3 3 1 1 1 批容量无界情形，即 1 i t - a ；p - b a t c h ，b = o o ；o n l i n e , q ，r i g m 算法尬日产： s t e po ：把禁用区间收缩为一点工，修改时间轴 s t e p1 ：执行算法卵 算法注释：在算法晒研。中，由于我们所考虑的是可继续( r a ) 情形，所以 收缩禁用区间为一点是可行的，对于禁用区间内到达的工件，均看作工时刻来 的，这将给证明带来方便 定理3 对于排序问题 1 i r - a ；p - b a t c h ，b = o o ；0 1 2 一l i n e , 巧，r m “r i ( ；。“， 在线算法m 1 h f 的竞争比不超过1 + a 证明：对任意实例厶用a 和g 分别表示算法研。在修改时间轴下的目 标值和最优值，用c 和c 分别表示算法尬研。产生的目标值和最优值，禁用 区间长度记为上我们有 c = 四+ a l ；c = c 1 + a l 对于a 和g ，由z h a n g 1 4 】可知，c , c ；1 + q ，从而 叫矿= 翰+ 三) ( g + a l ) g 曰1 + m 口 由引理2 和定理3 可知，算法坼研。是最好可能的 3 1 1 2 批容量有界情形，即 il l , p - b a t c h ，b n ；o n 一i n e , 吩，r m 口r i ( k a 】【 算法尬日日： s t e po ：把禁用区间【厶捌收缩为一点l ，修改时间轴。 s t e pl ：执行算法日丑。 2 4 定理4 对于排序问题 1 i t - a ；p - b a t c h ，b 1 ，第一工件 于零 时刻到达，加工时间p x = 1 对任意算法a ， c a s e l 。若算法a 在s 一1 时刻之前未加工 ，则不再来工件，此时c s 两c = 1 ，故c a c & c a s e 2 ：若算法a 在t 时刻( 0 t 8 1 ) 开始加工工件 ，则第二个 工件如在t + ( ss 一1 ) 时刻到来，其中b = s t 一，不再来工件显然， c a m s + s t 一但是，在t + 时刻 与如并成一批加工，可得最优值即 c = t + e + ( 8 一t 一0 = 3 从而c a c + 型妇 土：= m + 1 一半m 当s ，m 比较大时，可知命题成立 口 3 4带有强制工件的单机在线分批排序问题 这里所有工件都是在线的，但是其中有一些特殊工件，它们要求单独成 批，其它工件不能与其共批，并且一旦到达就要对其立即加工，我们称其为强 制工件( m a s t e rj o b ) ，其它工件称为自由工件假设强制工件间不冲突该模型 可记为 1 i m a s t e r j o b ；p - b a t c h ，6 ；o n 一豇n e ，巧i g 我们考虑仅和强制工件相冲突的批可中断( p m t n ) 与需要重启( r e s t a r t ) 两种情 形一批允许重启是指，我们可以打断当前正在加工的批，已经加工的部分全 部作废，批中工件被释放出来，各自成为独立的未加工工件，它们可以与其它 已经到达的未加工的工件重新组合成一批，再被加工 4 1 可中断( p m t n ) 情形 定理6 对于排序问题 1 i m a s t e r j o b ( p m t n ) ；p - b a t c h ，6 ；o n - l i n e , 巧