（运筹学与控制论专业论文）可中断平行机排序问题研究.pdf

摘要 摘要 本文主要研究可中断平行机( 半) 在线排序问题的近似算法设计及其竞争比 分析对多个不同机器环境和目标函数下的可中断( 半) 在线问题以及两个新排序 模型，本文讨论了这些问题的下界，设计了相应的近似算法并给出了它们的竞 争比全文共分为七章，第一章首先介绍了与排序问题相关的一些概念以及预 备知识，并总结了近些年在半在线领域研究中取得的成果 第二章研究可中断的机器覆盖问题( p ( q ) 1 n a p t g 咖) 对m 台同类机的离 线情形，文中证明了能在o ( m n ) 时间内找到最优解随后研究了在线机器覆 盖问题的下界，给出了一个求解这类问题下界的一般公式并由此得出了闯 题q m l p m p t l c i m m 和p m i 删i c 0 。的下界分别为m 和銎l1 i 最后，文章还研 究了两台同类机的在线算法并分别给出了在不允许机器空闲与允许机器空情况 下的最优在线算法 第三章研究已知工件加工时间位于某一区问的可中断半在线 排序问题文中分别给出了问题p 3 1 p m p t ，g r o u p 、q 2 1 p m p t ，g r o u p 和q 2 l p m p t ，g r o u p g 咖的最优可中断参数界算法 第四章研究了两台同类机上已知工件按非增序到达和已 知最大工件长度这两个可中断半在线排序问题文中分别给出 t q 2 1 p m p t ，d e c r i a n i n 、q 2 t p m p t ，m o 茹l c l 一和q 2 1 肼p t ，m a x i c 。的最优可中断 算法 第五章研究带不确定信息的可中断半在线排序问题文章分别给出 了p m l p m p t ，d i s t 卿i g 。、q 2 1 p m p t ，d i s t 卿f g 。和q 2 l p m p t ，d i x tm a x i c m 。的 最优可中断算法 第六章研究带机器费用的平行机可中断( 半) 在线排序问题在该问题中，一 开始没有任何机器可用，当一个工件到达后，算法必须作出选择是购买新机器 加工该工件还是将其放在已购买的机器上加工目标函数是极小化m a k e s p a n 和所 有机器的购买费用之和文中首先给出了一个竞争比为( 2 、，佰+ 2 ) s 1 3 7 9 8 的 在线可中断算法，而该问题的下界为4 3 此外，还研究了已知工件按非增序到 达的半在线情形，给出了竞争比为4 3 的最优算法，该算法无需工件被中断，因 此也是不可中断问题的最优算法 第七章研究带服务等级约束的平行机在线排序问题该问题对每个工件和机 摘要 器都赋予一个服务等级，工件只能在服务等级不高于自己的机器上加工文中 首先给出了两台机器上的最优在线算法对m 台机器带有两个服务等级的在线排 序问题，证明了该问题的下界至少为2 ，随后证明了贪婪算法求解该问题的紧界 为4 1 m 并给出了一个竞争比为1 2 土 近2 5 2 2 的改进算法 关键词：排序问题，可中断，半在线，近似算法，竞争比- 一一 a b s t r a c t a b s t r a c t t h i st h e s i sm a i n l yc o n c e i t sd e s i g na n da n a l y s i so fa p p r o x i m a t i o na l g o r i t h m sf o r p r e e m p t i v e ( s e m i ) o n h n ep a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m s f o re a c hp r o b l e m c o n s i d e r e di nt h i st h e s i s b o t hl o w e rb o u n da n do n l i n ea p p r o x i m a t i o na l g o r i t h mf i r e p r o v i d e & t h e t h e s i si s s p l i t u p i n t os e v e n c h a p t e r s w e f i r s t i n t r o d u c es o m e p r e l i m i n a r y c o u c e ，t sr e l a t e d t o s c b e d u f i n g p r o b l e m sa n d t h e ns u m m a r i z e t h e r e s u l t s o f s e m i - o n l i n e s c h e d u l i n gi nc h a p t e c1 i nc h a p t e r2 ，w ei n v e s t i g a t ep r e e m p t i v em a c h i n ec o v e r i n gp r o b l e m - w ef i m t s h o w t h e o f f - l i n e v e r s i o n c a r l b es o l v e d i n o ( m n ) t i m e f o r g e n e r a l m - u n i f o r m - m a c h l n e c a s e f b rt h eo n l i n ev e r s i o n w ep r e s e n tag e n e r a lf o r m u l at oo b r a i nt h el o w e rb o u n d o ft h ep r o b l e mo nmu n i f o r mm a c h i n e sa n dm i l ss h o wt h a tt h el o w e rb o x m d so f q m l 删l c + m a n d p , n l o m p t l c 赢a r e m a n d ：1 1 i ，r e s p e c t i v e l y l a s t l y w e f o c u s o n t h e o n l i n e a l g o r i l h r a s f o r v x o - u n i f o r m - m a c h i n e c a s e w e f i r s t p r e s e n t o p t i m a l o n - l i n e a l g o r i t h m f o r t h e o s s e t h a t t h e i d l e t i m e i s n o t a l l o w e d t o b e i n u - o d u c e d w e f u r t h e r p r e s e n t e da l lo p t i m a lo n l i n ea l g o r i t h mw h e nt h ei d l et i m ei sa l l o w e d i nc h a p t e r3 ，w ec o n s i d e rp r e e m p t i v es e m i - o n l i n es c h e d u l i n gp r o b l e m sw h e r ea l l j o b sh a v et h e i r p r o c e $ i n gt i m e si na ni n t e r v a l 。w ep r e s e n t r e s p e d i v e l yo p t i m a ls 删一 o n l i n ea l g o r i t h m sf o rt h ep r o b l e m sp 3 如m 刃，g r 圳g 。q 2 1 p m t ，9 _ r o u p l g ma n d 0 2 b ”倒，删l ( n kc = i l a p t e r4 w es t u o yt w o p r e e m p t i v es e n t i - o n l i n es c h e d u l i n gp r o b l e m s i nt h e f i r s ts e m i o n l i n ep r o b l e m , i ti sa s s u m e dt h a ta l lj o b sa r r i v e so n eb yo n ew i t hn o d _ - i n c r e a s i n gj o bs i z e s ，w ep r e s e n ta no p t i m a la l g o r i t h mf o rq 2 1 p m p t ，出c r i g m m 1 n t h es d ：o a ds e m i - o n l i n ep r o b l e m , i t i sa s s u m e d t h a t t h es i z e o f t h e l a r g e s t j o b i s k n o w n i na d v a n c e w ep r e s e n to p t i m a la l g o r i t h m sf o rm cp r o b l e m sq 2 l p m p t t ”m z i ( ? m ha n d 口2 i p f 卵 m i ( k i n r e s p e c t i v e l y i nc h a p t e r5 ，w ei n v e s t i g a t ep r e e m p t i v es 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 l m a c h i n e sw i t hi n e x a c tp e r 曲li n f o r m a t i o n w ep r e s e n tr e s p e c t i v e l yo p t i m a la l o e - r i t h m sf o rt h ep r o b l e m s ，mj p ，妒，c 托鲥o ( ? 二腑，0 2 j 牟，职，班时。印拉；螂a n d q 2 l 矿n 彤，d s tm n l ( k “ i n 西a p t e r6 ，w ec o n s i d e rp r e e m p t i v e ( s e m i - ) o n l i n ep a r a l l e ls c h e d u l i n gw i t hl n a - 一一 a b s t r a c t c h i n ec o s t i nt h i sp r o b l e m , n om a c h i n e sa l ei n i t i a l l yp r o v i d e d , a n dw h e naj o bi s r e v e a l e dt h ea l g o r i t h mh a st h eo p t i o nt op u r c h a s en e wm a c h i n e s t h eo b j e c t i v ei st o m i n i m i z et h es u mo ft h em a k e s p a na n dc o s to fm a c h i n e s w ep r e s e n ta no n l i n ea l g o - r i t h m w i t h a c o m p e t i t i v er a t i o o f ( 2 6 + 2 ) 5 1 3 7 9 8 w h i l e t h e l o w e r b o u n d i s4 3 。 f o rt h es e m i - o n l i n ep r o b l e mw i t hd e c r e a s i n gs i z e s ，w ed e s i g na no p t i m a la l g o r i t h m w i t hac o m p e t i t i v er a t i oo f 4 3 , w h i c hd o e sn o ti n 仃o d l l c ea n yp r e e m p t i o n a n dh e n c ei s a l s oa no p t i m a la l g o r i t h mf o rt h en o n - p r e e m p t i v es e m i - o n l i n ep r o b l e m 。 i nc h a p t e r7 ，w ed e a lw i t ho n l i n ep a r a l l e ls c h e d u l i n gu n d e rag r a d eo fs e r v i c e ( g o s ) p r o v i s i o n , w h e r ee a c hj o ba n dm a c h i n ea t el a b e l l e dw i t ht h eg o sl e v e l s ，a n d e a c hj o bc a n h ep r o c e s s e db yap a r t i c u l a rm a c h i n eo n l yw h e nt h eg o sl e v e lo ft h ej o b i s1 1 0l e s st h a nt h a to ft h em a c h i n e w ef i r s tp r o p o s ea no p t i m a lo 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 o5 1 3o nt w oi d e n t i c a lm a c h i n e s t h c nw ec o n s i d e rt h eo n l i n ep r o b l e m o nmi d e n t i c a lm a c h i n o sw i t ht w og o sl e v e l s w es h o wt h a tt h el o w e rb o u n do ft h e p r o b l e mi sa tl e a s t2a n dt h eg r e e d ya l g o r i t h mh a sat i g h tb o u n do f4 1 m f i n a l l y , w ed e s i g na ni m p r o v e da l g o r i t h mw i t hac o m p e t i t i v er a t i oo f 丝攀2 5 2 2 k e y w o r d s ： s c h e d u l i n g ，p r e e m p t i o n ，a p p r o x i m a t i o na l g o r i t h m ，s e m i - o n l i n e ，c o m - p e t i t i v er a t i o 一i v 第一章绪论 1 1 排序问题 第一章绪论 排序( s c h e d u l i n g ) 理论是研究如何在满足一定要求下，对需完成的任务进行 合理安排使得到的结果在某种意义下达到最优，它有着重要的理论意义和广泛 的应用背景排序理论与理论计算机科学和离散数学结合紧密，并广泛应用到生 产计划调度、信息处理、物流管理、服务行业等领域，这些新兴领域的蓬勃发 展不仅使经典问题的研究不断深入，而且还涌现了许多有实际背景的新问题 自上世纪5 0 年代人们开始研究排序问题至今，已有大量的排序文献发表在国内 外的重要期刊上，可以说，排序研究已成为目前组合优化领域最活跃的分支之 根据排序研究的最初背景，我们通常把需要完成的任务称为工件g o b ) ， 把完成任务需要的资源称为机器( m a c h i n e ) ，我们希望找到一个可行的排 序( s c h e d u l e ) ，使得某个给定的目标函数达到最小( 大) 这里的可行一般是指 在同一时刻，一台机器至多加工一个工件，一个工件也只能在一台机器上加 工，并且该排序满足问题特定的约束要求描述一个排序问题可用所谓的“三 参数表示法”( t h r e e - f i e l d 把p 把s 饥t a l i o n ) 8 伊一【2 6 1 ，其中n ，p ，y 分别代表特定 的机器环境、工件特征和最优准则它们是排序问题的三个组成部分 机器环境用来描述机器的数量、不同机器之间的关系等与机器有关的性 质常见的机器系统包括单台机( s i n g l em a c h i n e ) 、平行机( p a r a l l e lm a c h i n e s ) 、流 水作q p ( f l o ws h o p ) 、有序作q p ( j o bs h o p ) 和自由作盟k ( o p e ns h o p ) 等在本文中， 我们着重讨论平行机排序问题，即机器数至少为2 ，每个工件只需经过某 台机器加工一次即可完成根据机器的性能，可以把平行机分为三类：同 型( i d e n t i c a l ) 平行机：系统中所有机器的功能，效率完全一样：同类( u n i f o r m ) 平行机：系统中机器有各自不同的加工速度，但任意工件在不同机器上 的加工时间有相同的比例关系；不同类( u n r e l a t e d ) 平行机：系统中机器各不 相同，工件在不同机器上的加工时间比不全相同在三参数表示法中， 它们分别用p ，q ，脓示本文中主要考虑同型机和同类机两种机器对 一般的m 台同类机，设舰的速度为，i = 1 ，2 ，m 不失一般性，不妨 设8 l 现s 若只考虑2 台机器同类机，我们假设1 = s ls5 2 = 乳若考 第一章绪论 虑m 台同型机，则假设所有机器速度为1 ，即s 1 = 8 2 _ = 8 r n , = 1 工件特征一般可用工件的加工时间( 也称为工件长度) ，工件的释放时间， 工件相互之间的依赖关系，工件加工时是否可中断等来刻划根据排序者对工 件信息的了解程度，又可将排序问题分为离线、在线和半在线等如果排序者 在排序开始前已知工件的全部信息，例如工件数，每个工件的加工时间等，则 称该问题是离线( o f l i n e ) 的反之，如果工件的信息是随着排序过程个个地依 次释放的具体地说，只有在位于某个工件前的全部工件均被安排完毕后，排 序者才能知道该工件的有关信息，而且工件一旦被安排就不能改变这样的排 序问题称为在线( o n l i n e ) 的而半在线( s e m i o n l i n e ) 是指排序者掌握的信息位于在 线和离线之间，我们将在后面的小节中详细讨论 所谓最优准则，通俗地讲，也就是以什么为目标函数根据可行排序和工 件的加工时问，我们可以算出某排序下工件m 的完工时间。和机器舰的完工时 间厶称g 。= m a x o 为排序的最大完工时间( m a k e s p a n ) 称c k 。= m 遗厶为 最小机器负载它们是本文中主要讨论的两个目标函数，前者为极小化目标， 后者为极大化目标( 该问题也叫机器覆盖( m a c h i n ec o v e r i n g ) f 司题) 文献中常见” 的其他目标函数还有( 赋权) 总完工时间、最大延误时间、最大误工时间、最小 误工个数等有关排序问题的综述，可参看文献【8 ；6 6 1 1 2 近似算法和竞争比分析 所谓排序问题的算法( a l g o r i t h m ) 是指一个预先制定的执行程序，对这个排序 问题的任何一个具体的例子( 简称为实例。i n s t a n c e ) ，按照这个程序操作后都可 以得到一个可行的排序解离线问题的算法称为离线算法，相应地，解在线问 题的算法称为在线算法例如l p t ( l a r g e s tp r o c e s s i n gt n n e ) 算法【2 5 】和l s ( l i s t s c h e d u l i n g ) 算法c 2 4 】分别是经典平行机排序问题的离线和在线算法由于在离 线问题中，排序者在排序前知道工件的全部信息，因此l p t 算法先把所有工件 按加工时间的非增序排成一列，然后依次将它们安排在能使其最早完工的机器 上加工而在在线问题中，在排序进行过程中后续工件信息是未知的，因此不 可能将工件按加工时间大小排列，l s 算法在极小化c - 。时将工件按原来的顺 序安排在能使其最早完工的机器上加工，而在极大化c _ i 。时则将工件按原来的 顺序安排在能使其最早开工的机器上加工将实例通过某种规则编码后输入计 算机所占用的字节数称为该实例的输入长度对每一个可能的输入长度，算法 解此输入长度的最坏可能实例所需的基本运算次数( 如加法、乘法、比较等) 称 一2 一 第一章绪论 为该算法的时间复杂性( 函数) 如果存在一个多项式函数p ( n ) ，使得算法的时 间复杂性为o ( p ( n ) ) ，那么称该算法为多项式时间算法，否则称为指数时间算 法伪多项式时间算法是一类特殊的指数时问算法，它的时间复杂性是关于实 例输入长度扎和实例中最大数的二元多项式函数由此出发，可以导出计算复 杂性理论的一系列重要概念和结论【2 3 1 本文中讨论的排序问题都是已被证明 为p h a r d 的，除非尸= n p ，否贝不存在求这些问题最优解的多项式时间算 法因此我们把研究的重点转向寻找能在较短时问( 多项式时间) 内得到接近于 最优解的算法，称之为近似算法( a p p r o x i m a t i o na l g o r i t h m ) 衡重近似算法的优劣 可从两个方面来看，一是算法的时间复杂性，二是它得到的解值与最优解值的 接近程度 设a 是求解一个极小化问题的一个近似算法称 , o a = i n f p l l c - u ( 1 ) p c ( j ) ，v j ) 为算法a 的最坏情况界( w o r s t - c a s er a t i o ) ( 对于离线情形) 或竞争比( c o m p e t i t i v e r a t i o ) ( 对于在线和半在线情形) ，这里c a ( ，) 和矿( j ) 分别表示算法a 解实例j 所得 的目标函数值和相应问题离线情形的最优目标值，在不引起混淆时分别简记 作一和c 同样地，对极大化排序问题，称 p h = i n f p l l e ( z ) sp 矿( ，) ，v x 为算法a 的最坏情况界( w o r s t - c a s er a t i o ) ( 对于离线情形) 或竞争比( c o m p e t i t i v e 住t i o c 对于在线和半在线情形) 称在线问题( 极小化目标或极大化目标) 的竞争比下界( 简称为下界，l o w e r b o u n d ) 为c 。若不存在该问题竞争比小于c 的在线算法为了得到下界，一般可以 通过给出一系列实例使得任何在线算法都不能很好地求解所有实例来得到若 算法a 的竞争比等于该问题的下界，则称a 为最优( o p t i m a l ) 算法这是从竞争比 意义上来说，个p 一玩r d 在线问题可能得到的最好结果 近年来，组合优化问题的研究又增加了随机算法这一新的工具所谓随机算 法( r a n d o m i z e d a l g o r i o _ m ) 是指在算法执行过程中可以作出随机选择的一类算法 前面定义的算法我们称为确定性算法( d e t e r m i n i s t i ca l g o r i t h m ) 对极小化排序问 一3 一 第一章绪论 题，称 以= i n f 伽l i e ( c a ( i ) ) p c * ( n w ) 为随机算法a 的竞争比，这里e ( c a ( 聊表示算法a 解实例j 所得的期望目标函数 值同样地，对极大化排序问题，称 m = i n f 如1 i c 搴( ，) sp e ( ( d ) ，v 为随机算法的竞争比排序问题的随机下界可利用y a o 氏定理得到【7 9 】有关随 机算法可参考m o t w a n i 年f l r a g h a v e n 的专著 6 3 1 排序问题的随机下界不会小于确 定性的下界，而最好的随机算法的竞争比则不会大于任何确定性算法的竞争比 因此。如果存在一个确定性算法，它的竞争比与该问题的随机下界相等，在这种情 况下。我们可以说研究该问题的随机算法是没有意思的相对确定性算法而言，随 机算法在排序中的应用虽逐渐增多，但还远未成熟今后若不特别说明，文中所 指的算法均为确定性算法 1 3 可中断排序 在第一节中提到，工件特征包括加工过程中是否可中断所谓工件加工时不 可中断( n o n - p r e e m p i t v e ) 是指工件一旦分绘了菜台机器，就必须一直在该机器上加 工直到结束但是，在很多实际系统中，例如许多操作系统的调度器，就是利用 可中断来平衡每个任务的等待时间，从而提高系统的响应时间因此，允许工件 可中断的调度策略具有重要的实际意义另一方面，若在可中断的前提下，还允许 并行，即同一个工件的不同部分可以并行的分配给不同的机器处理，则会导致平 凡解( 每台机器的负载一样大) 所以，我们主要考虑不可并行的情形，即同一个工 件的不同部分必须是不可重叠的分配到机器上加工的具体地，工件加工可中 断( p r e e m p t i v e ) 是指每个工件可以被分成几个部分放在不同的机器上加工，但必 须保证不重叠，即在同一个时刻不能在不同机器上加工同一工件如果机器必须 从零时刻开始不问断的工作直到分给它的所有工件全部完工了才能停止，我们 称这种情况为机器不允许空闲但是，我们有时候并不要求机器自始至终都是工 作的，因此，有时候将会出现这种情况。就是某一时间机器暂时不工作，且该机器 在以后还会加工其它工件，我们称这段空余的时间为空闲时间( i d l et i m e ) 如果允 许这样的空闲时间，我们称这种情况为机器允许空闲事实上，在同类机可中断 排序的某些情况下，机器允许空闲的确可以改进算法的竞争比【3 5 ；5 3 ；3 6 由于 一4 一 第一章绪论 空闲时间的存在，前面提到的第二个目标函数g 。并不能简单地认为是负载最 小的机器负载，在这里它表示从零时刻开始所有机器一起工作的连续时间 在本文中，我们将可中断简记为p m p t ，并将其写在三参数表示法的第二域 中接下来介绍一下现有的可中断离线和在线的主要结果 1 离线情形 对排序问题p m l p m p t l 。的离线模型，m c n a u g h t o n 6 2 给出了最优排序。 中断次数不超过m 1 次。面对q m l p m r * l a 。的离线模型，h o r w a t h 等【4 6 】以 及g o n z a l e z ，s a n n i 2 7 分别给出了求解最优解的算法只是后者的算法更有 效，其中断次数不超过2 ( m 1 ) 次然而对第二个目标函数c r m i 。一直未有文献讨 论，本文第二章对q , n l p r ，| p t l g - m i 。的离线模型给出了求解最优解的算法以上算法 都在线性时间内解决，也就是说这些离线闯题都是多项式时闻可解的 2 在线情形 对p m l r , m p t l g 。的在线排序问题，c h e r t ，h e 痢w b e g i n g e r 给出了竞争 比为芒南的算法并证明了它为最优【9 】对q m l p m p t l g 。的在线排序问题。 e b e n l e n d r 和s g a l l 1 5 给出了竞争比为4 的确定型算法和竞争比为e 2 7 1 8 的随机 算法，而该问题的随机下界至少为2 1 2 2 1 最近，e b e n l e n d r 等【1 4 】给出了该问题的确 定性算法，竞争比仍然为e 2 7 1 8 ，并证明该问题的下界在2 0 5 4 与e 之间在这之 前，e p s t e i n ：芷某种特殊条件下给出了一个最优算法 1 6 l 。文中假设机器的速度比 是不减的。就是说，等者，2 i m 一1 ，算法的竞争比为z 可寰b ，其 中= 銎，s ( 銎，& 一1 ) 可见m 台同类机的在线情形解决起来相当困难， 相比之下，2 台机器情况却容易得到最优算法对q 2 l p m p t l 。，w e n 和d u 7 7 】 和e p s t c i n 等 2 1 】独立给出了竞争比为吉壬糟的算法并证明所给算法是最优的而 对q 2 1 p m p t l c k j n 也一直未有文献给出算法，本文第二章对该问题做了详细的讨 论。分别给出了机器不允许空闲时间和允许空闲时间的最优算法 1 4 半在线排序 从上节的讨论中可以看到，在线和离线分属两个极端情形对离线问题，已 知的工件信息非常充分，排序者可以对数据进行整序、运算、比较等操作以得到 性能较好的算法而对在线问题，排序者对后续工件的信息一无所知，甚至不知 道在其后有没有工件，而且工件一旦被安排就不能改变在实际问题中，出现这 两种情况的机会并不多，大量存在着的问题是排序者一方面不可能知道工件的所 一5 一 第一章绪论 有信息，另一方面可能掌握着比经典在线模型更多的信息或有着更大的排序自由 度，因而使问题变得比离线相对“困难”一些，但比在线相对“容易”一些，即可 能得到比在线算法性能更好的算法我们把不完全满足在线排序问题的两条基 本假设，难度介于在线和离线之间的模型称为半在线模型当然这种提法只是为 了与经典在线问题加以区别，从排序者在排序前未掌握该实例的全部信息且一 旦安排好就不允许改变这一点来看，它们仍然是“在线”的，因此我们仍用竞 争比分析来研究半在线问题 在实际需要的大力推动和理论工作者的不懈努力下，自1 9 9 6 年半在线概念 提出后的l o 年中，各种不同的模型不断涌现，初步形成了排序研究的一个新的分 支我们将在资料所及范围内。对已有的各模型和结果作一简单的介绍 已知工件总加工时间半在线模型( s u m ) 该模型由l 翻l e 托r 等【5 4 】首先提出，它假设所有工件的总加工时间已知此 后研究该问题的文献有【3 0 ；l ；l o 等 已知实例的最优解( o p t ) 该模型由a z a r 和e p s t e i n 2 最早提出，它假设实例的最优解值( 当然不是最 有解本身) 可在零时刻( 此时工件尚未到达) 为排序者所知另有文献【5 】称之 为b i n - s t r e t c h i n g f 司题 已知工件最大加工时间半在线模型( m a x ) 该模型假设所有工件中加工时间最长的工件的加工时间已知，相关研究文 献有【4 3 ；3 0 ；7 0 ；6 0 ；6 1 已知工件加工时间非增半在线模型( d e e r ) 该模型由a z a r 和e p s t e i n 2 最早提出，它假设工件按加工时间的非增序到 达，研究该问题的文献还有【1 9 ；6 8 已知工件加工时间位于某一区间内半在线模型( g r o u p ) 该模型l e t h e 和z h a n g 4 3 首先提出。它假设所有工件的加工时间位于有限区 间眵，例，其中p o 和r l 是已知常数研究文献还有【2 9 ；3 0 ；3 2 o r d i n a l 半在线模型( o r d i n a l ) o r d i n a l 半在线模型是l i u ，s i d n e y 和v a nv l i e t 首先提出的 5 9 1 在该模型 中，我们只知道某工件的加工时间在由所有工件的加工时间重排组成的有 序集中的位置，而不知道其确切大小，且所有工件的安排必须在零时刻作 一6 一 第一章绪论 出并不能改变此后t a n 和h e 对该模型的研究做了大