（基础数学专业论文）关于分批排序问题的研究.pdf

摘要 分批排序是近年来发展非常迅速的现代排序模型，有很强的应用背景分批是 将工件集分割成若干个子集，每一工件子集为一批每批的工件放在一起加工同 批： 件的完工时间均等于该批中最后工件的完工时间目标是将工件分成若干批且 排出各批的加工顺序，使目标值最优分批排序模型按分批方式的不同分两大类：平 行分批排序模型与继列分批排序模型在平行分批排序模型中，机器在每一时刻可 同时加工多个工件；在继列分批排序模型中，机器在每一时刻最多加工一个工件，工 件是按照一个接一个串联的方式形成一批的 多重指标排序作为一种多目标决策，在解决经济、管理、工程、军事等领域出 现的复杂问题中起着越来越重要的作用例如，在一个工厂的生产过程中，生产决 策者不但想要使工件的总完工时间最小以减少生产费用，还要尽量使误工工件的个 数最少，以更好地满足顾客的要求多重指标排序的最优性规则是：求解具有重 指标问题的最优解就是在对应的前七一1 重指标问题最优解集合中寻找第七单指 标问题的最优解近年来，多重指标的排序问题并不多见，李忠义等人在文献中给 出了当第一指标是o ，嘶q ，死。及时若干问题的算法和复杂性分析 准时排序是一种经典的排序问题，已有很多研究结果该模型的特点是工件不 论是提前完工或推迟完工都产生不准时费用 本文的内容分三大部分：第一部分提出了三种新型分批排序模型：( 1 ) 具有主次 指标的单机分批排序问题( 第二章) ；( 2 ) 具有三重指标的单机平行分批排序问题( 第 三章) ；( 3 ) 单机准时分批排序问题( 第四章) 对于这些问题的研究在文献中几乎没有 见到，而这些模型具有很强的应用背景和理论研究意义本文对这些新型排序模型 给出了若干研究结果第二部分对一些现有单机分批排序问题最优解的结构性质进 行了系统研究( 第五章) 对于分批排序结构性质的研究在文献中也没见到第三部 分研究了工件在限选机器上加工的若干平行机分批排序问题( 第六章) 在第二章中，本文研究了具有主次指标的单机分批排序问题，其主要结果如下： 证明了带有到达时间、主指标为最大完工时间的两个问题是强n p - 困难的：第一个 是批容量有限制、次指标为总存储费用的平行分批排序问题；第二个是批容量无限 制、次指标为最大延迟的继列分批排序问题给出了三个批容量无限制问题的多项 式时间算法：第一个是带有到达时间、主指标为最大完工时间、次指标为占用机器 总时间的继列分批排序问题；第二个是主指标为最大延迟、次指标为最大完工时间 的平行分批排序问题；第三个是主指标为最大延迟、次指标为误工总数的平行分批 问题此外，给出了主指标为最大延迟、次指标为关于g 的任意正规函数、批容量 无限制的平行分批模型的拟多项式时间算法 在第三章中，对于具有三重指标的单机平行分批排序问题，主要给出了两种批 容量无限制平行分批模型的0 m 2 ) 时间算法：第一个问题是带有到达时间、三个指 标依次为最大完工时间、占用机器的总时间、总存贮费用；第二个问题的三个指标 依次为最大延迟、最大完工时间、关于工件完= i ：时间的任意正规函数 在第四章中，对于若干批容量无限制的继列分批和平行分批准时排序问题，给 出了当每批恰有6 个工件且工件有相同交工期时的0 ( nl o g 礼) 时间算法 第五章主要研究批容量无限制的继列分批和平行分批问题最优特殊分批的存 在性条件，目标函数分别为：加权完工时间之和、总完工时间、完工时间平方之和及 最大延迟这里，特殊分批主要指仅分一批和恰分n 批 第六章主要讨论当工件的加工长度均为1 、每个工件以只能在限选机器( 允许 加工的机器) m ，上加工时的平行机分批排序问题，其中m f 是机器集台的某个子 集已知分批排序问题pls - b 8 t c l l ；p j = 1 ；朋，lc k 。可归结为非分批问题pl 胁= 1 ；m ，lg _ a x p i n e d o ( 1 9 9 5 ) 给出了当子集族 m ，) 是嵌套集族时的1l f j ( 1 e a s t f l e ) 【i b k j o bi i r s t ) 算法这里给出了子集族 m ， 为一般情形的多项式时间算法作 为子集族 川，) 为嵌套情形的推广本文研究了子集族 m ，) 是凸的情形并给出 了有效算法 关键词：排序；分批排序；准时排序：多重指标；动态规划；限选机器 儿 a b s t r a c t b a t c hs c h e d u u n gi so n eo fs i g n 逾c a n tm o d e r ns c h e d u l i n gm o d e l st 1 1 a ta d v a n c e s r a p i d l yj nr e c e n t ”a r s i ti sm o t i v a 钯db yi m p o r t a n t 印p l i c a t i o n s b a c h i n gm e a n s t h a ts e t so fj o b sw h i 出a r ep r o c e s s e do nt h es a m em a c h i n em u s tb ef o u p e di n t o b a t c h e s t h ef i n i s h i 工1 9t i m eo fa | lt h ej o b si nab a t ( hi sd e 丘n e dt ob et h e 矗n i s h i n gt i m eo ft h e1 a 8 tj o bi nt h eb a t c h t h eg o a lo fb a t c hs c h e d u u n gi st op a r t i t i o nj o b si d 七ob a t c h e s8 n dsc ：h e d u l et h eb a t c h e 8s u c ht h a tt h ed b j e c t i v ef 1 1 n c t i o ni s o p t i m i z e d b a t c h - 8 c h e d u l i n gm o d e l 8g oi n t ot w oc a t e 9 0 r i e sb yt h ew a yo fb a t c h - i n g ：p a r a h e l - b a t c hs c h e d u l i n ga n ds e r i a l 一b a t c h8 c l l e d u l i n g f 0 rt h ep a r a l l e l - b a t c h ( p b a c h ) s c h e d u l i n gm o d e l ，t h em a e h i n ec a nh a n d l em o r et h a no n e5 0 ba tat i m e ， w h i l ef o rt h es e r i a l - b a t c h ( 争b a t c h ) s c h e d u l i n gm o d e l ，i tc a nh a n d l e 矾m o s to n ej o b a tt h es 锄em o m e n ts ot h a 七七h ej o b si nab a t c hi n u s tb ep r o c e 8 s e do n eb yo n ei a s e r i a io r d e r h j e r a r c h i c a lc r i t e r i 8s c h e d u l i n 昏8 saw 黾yo fm u l t i _ o b j e c t i v ed e c i s i o n _ m a 玉d n e p l a y sa ni m p o r t a n tr o l ei ns o l v i n gc o m p l i c a t e dp r o b l e m sa 血8 i n gf r o me c o n o m i c s ， a d m i n i s t r a t i o n ，e n g i i l e e r i n & e t c f b re x 锄p l e ，af a c t o r ya d i l l i n i s t h a t o rn e e d st o 甜r a n g et h ej o b st ob ep r o c e 帑e ds u c ht h a tt h et o t mc o m p l e t i o nt i m ei sm i n i m i z e d 盆r s t l yt or e d u c et h ep m c e s s i n gc o s t ，a n dt h et 盯d yj d b 8a r el i m i t e dt oal o w e s tl e v e l s e c o n d l yt os a t i s 如t h ec l i e n t s t h eo p t i i n 址t yp r i n c i p l eo fs c k 蛆u l i n gp r o b l e m sw i t h h i e r a 出i c a lc r i t e r i ai s ：f b ras c h e d u l i n gp r o b l e mw i t h 七c r j t e r i a ，t o6 工l di t so p t i m a l s o l u t i o ni st of i dt h eo p t i m ms o l u t i o no ft h ep r o b l e mw i t h 七t hc r i t e r i o n8 m o n gt h e s e to fo p t i m 出s o l u t i o n so ft h ep m b l 锄w i t ht h ee a r l i e r 七一1c r i t e r i a v e r yf e w r e s e a r c h e 8o nh i e r 跗c h i c a lc r i t e r i as c h e d u i i n gp r o b l e ma r er e p o r t e di ni i t e r a t u r e sa t p r e s e n t l e ep r e s e n t e ds o m ea l g o r i t h m sa n dc o m p l e x i t ya n a l y s i sf 撕s o m ep r o b l e m s i n t h i s a s p e c t ，哇t h t h e l i 蹴喇t e f i o f g ，叻g ，死“粕d 幻，r e s p e c t i v e l p j u s t i n t i m e ( j i t ) s c h e d u l i n gi 8ac l a s s i c 蛆s c l l e d u l i n gm o d e l ，f o rw h i c hm u c h r e s e a r c hw o r kh a sb e e nd o n ea n ds i g n i 矗c a n tp r o g r e s s e sh a v e b e e nm a d es of a r t h e m o d e l i sc h a r a c t e r i z e db yar i g o r o u sr u l et h a ta l lj o b sm u s tb ec o p l e t e de x a c t l y o nt h e i ra s s i g n e dd u e 出 e s ，o t h e r w i s ep e n a l t ym u s tb ee x e c u t e d ，b o t hf o re a r l i n e 8 s l u a n dt a r d i n e s s t h i 8p a p e rm a i n l y m c l u d e st h r e ep a r t s i nt h el i r s tp a r t ，t h r e en e wb a t c h - s c h e d u l i n gm o d e l sa r ep r e s e n t e d ：( 1 ) s i n g l eb 8 t c hm a c h i n es c h e d u l i n gm o d e lw i t h t w dh i e r a r c h i c a lc r i t e r i a ( c h a p t e r2 ) ；( 2 ) s i n g kp a r 出k l - b a t c hm a c h i n e8 c h e d u l i n g m o d e lw i t ht h r e e1 1 i e r a r c h i c a lc r i t e r i a ( c h a p t e r3 ) ；( 3 ) s i n g l em a c h i n ej u s t i h t i m e b a t c l ls c h e d u l i n gm o d e l ( c h b p t e r4 ) 7 i h e s ei n o d e l sh a ei m p o r t a n ta p p l 【i c a t i o n sa n d a r eo ft h e o r e t i c a ls i g n i 丘c a c e h 0 虺v e r ，s t u d i e so nt l e s ep r o b l e n l sh a es c a r c e l y b e e ns e e ni nl i t e r a t u r e s t h i sp a p e rd e v e l o p s 吕0 m er e 8 u l t sf o rt h en e wm o d e l s i n 七h es e c o n dp a r t ，t h es t n l c t l l r a lp r o p e r t i e so ft h eo p t i m 8 ls o l u t i o n so ft h ek n o w n s i n g l em a c h i n eb 8 t c hs c h e d u l i n gp r o b l e m sa r ed i s c u s s e ds y s t e m a t i c a u y c h a p t e r5 ) s t u d i e 8o nt l l i sp r o b l e mh a v en o tb e e ns e e ny e ti nl i t e r a t u r e s i nt h et h i r dp a r t ， s o m ep r o b l e m sf o rp a r a l l e lm a c h i n eb a t c hs c h e d u l i n gw i t hd i 髓r e n tj o be l i g i b i l i t y r e s t r i c t i o na r es t u d i e d ( c h a p t e r6 ) i nc h a p t e r2 ，t h ef o u o 科n gr e s u l t sa r ed e v e l o p e d ( 1 ) t w op r o b l e m sw i t hr e l e a s e d a t e sa n df i r s tc r i t e r i o no fm a l c e s p a n 盯ep r o 、硝t ob es t r o n 9 1 yn p - h a d d t h e 矗r s t i 8t h eb o u n d e dp a r 8 l l e lb a t c hs c h e d u l i n gp r o b k mw i t ht h es e c o n dc r i t e r i o no ft o t a l 8 t o c b n gc o s t t h es e c o n di st h e u n b o u n d e d8 e r i 越b a t c hs c h e d u l i n gp r o b l e m 、啦t ht h e s e c o n dc r i t e r i o no fm a 甜m u ml a t e n e s s ( 2 ) p o l y n o m 试t i m ea 王g o r i t h h l sa r ep r e s e n t e d f o rt h r e eu n b o u n d e dp r o b l e 塔t h ef l r s ti st h es e r i 8 1b a t c hs c h e d u l i n gp r o b l e mw i t h r e l e a s ed a t e sa n dt w oh i e r a r c h i c a lc r i t e r i ao fm a k e s p a na n dm a c h i n eo c c u p a t i o n t i m er e 8 p e c t i v e l y t h es e c o n di st h ep 村a i l e lb a t c hs c l l e d u l i n gp r o b l e 阻w i t ht w o h i e r a r c l l i c a lc r i t e r i ao fm 8 证舢ml a t e n e s s8 n dm a k e s p a nr e 8 p e c t i v e l y t h el a s to n e i st h 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 ht w oh i e r a r c h i c a lc r i t e r i ao fm 8 x i m u m l a t e n e s sa n dt h en u m b e ro ft a r d yj o b 8r e s p e c t i v e l y ( 3 ) ap s e u d o p o l y n o m i 以t i m e a l g o r i t h mi sp r e s e n t e df o rt h eu n b o u n d e dp a r a l l e lb a t c hs c h e d u u n gp 蚰b l e mw i t h t h ef i r s ta n d8 e c o n dc r i t e r i ao fm a x i m 啪1 a t e n e 韶a i l dt h ea r b i t r a r yr e g u l a rf u n c t i o n o fg i nc h a p t e r3 t0 ( n 2 ) t i m ea 1 9 0 r i t h m sa 托p r o p 0 8 e df o rt w op a r a l l e lu n b o u n d e d b a t c hp r o b l e m s t h ef i r s ti st h ep m b l e mw i t hr e k a s ed a t e sa n dt h ef i r s t ，s e c o n d a n dt h i r dc r i t e r i ao fm i n i m i z e dma ：k e s p a n ，m a c h i n eo c c u p a t i o n i m ea i 工l ds t o c k i n g c o s t ；七h es e c o n di st h ep m b l e mw i t ht h ef i r s t ，s e c o n da n dt h i r dc r i t e r i ao fm a x i m u m l a t e n e s s ，m a k e s p a na n da na r b i t r a r yr e g u l a rf t l n c t i o no fg w i nc h a p t e r4 ，0 l o gn ) t i m ea l g o r i t h m sa r ep u tf o r t hf o rt h eu n b o u n d e ds e r i a l b a t c ha n dp a r a l l e lb a t c hj u s b i n t i m es c h e d u l j n gp r o b l e i n si nw h j c he a 曲b a t c hh a s e x a c t l y6j o b 8a n da l lj o b 8h a v eac o m m o nd u ed a t e ， c h a p t e r5d i 8 c u s s e st h ec o n d 王t i o n so fe 虹s t i n go p t i m a lb a t c hs e q l n c ew i 七ho n l y o n eb a t c ha n de x a c t l ynb a t c h e sf o ru n b o l l 工l d e db a t c hp r o b l e m s 讯t hc r i t e r i o no t o t a l 、v e i g h t e dc o m p l e t i o nt i m e ，t o t a lc o m p l e t i o nt i m e ，t o t a ls q u a r e dc o m p l e t i o n t i m eo ri n a x i n m ml a t e i l e s s c h a p t e r6s t u d i e st h 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 mw i t hu n i t 一1 e n g t h j o b si nw h i c he a c hj o b 乃i so n l y 出l o w e dt ob ep m c e s s e do as p e c i 丘e ds u b s e t m o fm a c h i n e s f 0 rt h ep r o b l e m 尸l 岛= 1 ；m f b x ，w h i c hi s e q u i v a l e n tt o p l l o b l e mps _ b a t c h ；岛= 1 ；j ic k a x ，a nl f j ( 1 e a s t 丑e x i b l ej o bf i r s t ) a l g o r i t h m w a se s t a b l i s h e db yp i n e d o ( 1 9 9 5 ) ，w h e r et h es u b s e t i i yf m i sn e s t e d i n a d d i t i o n ，p o l y n o m i a la l g o r i t h m sa r es u g g e s t e df o rt h ep r o b j e mw i t hg e n e r a ls u b s e t f a m i l y m 】) a sag e n e r a l i z a t i o no ft h ep r o b l e mf o rn e s t e d 眦i 堍t h ep r o b i e m f o rc o n v e xs u b s e tf a m i l y m j ) i ss t u d i e da n da ne 历c i e n t “g o r i t h mf o rs o l v i n gi ti s d r e s e n t e d k e yw o r d s ： s c l l e d u l i n g ， b a t c hs c h e d u l i n g ，j t l s t - i n - t i m es c h e d u l i n g ， h i e r 剐? c h i c a lc r i t e r i a ， d y n a m i cp r q g r 踟m i n g ， m a c h i n ee l i g i b i l i t y c o n s t r a i n t v 郑重声明 本人的学位论文是在导师指导下独立撰写完成的，学位论文没有剽 窃、抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由 此产生的一切法律责任和法律后果：特此声明。 学位论文黼签名x 才；备 。6 年岁月；o 日 第一章绪论 1排序问题 排序( 8 c h e d u l i n g ) 问题产生的背景主要是机器制造，后来被广泛应用于农业、制 造业、运输业、管理、计算机科学等领域排序理论的研究是从二十世纪五十年代 初期开始的由于研究排序问题的方法涉及组合最优化的各个分支，如线性规划与 整数规划、动态规划、最大流理论、匹配理论、计算复杂性理论等，自从它创立以来 得到了运筹学、信息管理、计算机科学等学科领域的普遍重视，特别是新兴排序的 丰硕成果，使排序论已成为研究活跃、前景诱人的学科领域之一 1 1 机器排序模型 在排序论中，工件是被加工的对象，是要执行的任务；机器是提供加工的对象， 是完成任务所需要的资源；安排时间表是在一定约束条件下对工件和机器按时间进 行分配和安排次序，使某一个或某一些指标达到最大或最小排序是安排时间表的 简称这样就可以把形形色色的实际问题纳入一种简明的模型之中 设有n 个工件，记为 ，以，厶；有m 台机器，记为舰，尬，不同 的问题由不同的加工规则和目标函数来描述为此我们常常用到如下的基本参数： 阳( 或p j ) ( p r o c e s 8 i i l gt i m e ) 表示工件五在机器且盈上的加工时间( 简称工 时) ，当p 巧= 胁时，说明工件以的加工时间与选择的机器无关或所研究的问题是 单机排序问题 q ( r e l e a s ed a t e ) 表示工件易的准备( 到达) 时间，也就是工件以可以进行 加工的最早时刻 而( d u ed a t e ) 表示工件也的交工期( 应交工时间) 如果一个工件在它的交 工期之前完成，我们称之为按期完工工件( o n - t i m ej o b ) ：否则，我们称之为误工工 件( t a r d yj o b ) 对误工工件有时需要付出一定的罚值 嘶( w e i 曲t ) 表示工件毋的权重体现工件出在整个系统中相对其他因素 的熏要性 g ( c o m p l e t i o nt i m e ) 表示工件 的完工时间 1 岛= g 一面( 1 a t e n e s s ) 表示工件以的延迟 弓= m a x o ，q 由) ( t a r d i n e s s ) 表示工件以的误时 局= m a x o ，如g ) ( e 砌i i l e s s ) 表示工件如提前完工的时间 = 呈 霎喜由( u n i tp e n a l t y ) 表示工件以的单位误时惩罚，也叫 做误工计数 关于作业时间安排，有几点不言而喻的约定： ( 1 ) 一个工件一旦开始加工，则一赢加工到完毕( 除非有允许中断的声明) ； ( 2 ) 每个工件必须在它的到达( 准备) 时间之后才能加工； ( 3 ) 除非当前没有工件到达( 没有准备好) ，机器不能空闲 1 2 排序问题的分类 目前文献普遍采用三参数分类法，即( a 7 ) 一分类法，来给排序问题命名 因为一个排序问题主要由三方面的特征来确定：机器的状况( 口) 、工件的状况( p ) 及 目标函数( 7 ) “) 机器状况：表示机器的类型和加工规则，例如： o = l ( s i n g l em a c h i n e ) 表示一台机器，是各种机器状况中特殊的情形( 单机 情形) = r ，( i d e n t i c a lm a c l l i n e si np a r a l l e l ) 表示m 台速度相同的平行机器( 简 称恒同机1 o = q m ( m a c h i n e 8i np 盯姐e lw i t hd i 乳r e n ts p e e d s ) 表示m 台一致的平行 机器( 简称一致机) 若机器惦的速度为咄，工件以的加工时间为鳓，则工件如在 机器尬上加工时的实际加工时间为= 功 ；如果所有机器的速废都相同，此 时即为晶。的情形 = ( u n r e l a t e dm a c h i n e si np a r a l l e l ) 表示m 台无关的平行机器( 简称无 关机) 此类机器随加工工件的不同而加工速度也不同若机器蚴的速度为吡，则 工件如只在机器尬上加工时的实际加工时间为= 功此情形是q 。的推 广 口一( f l o ws h o p ) 表示m 台机器的流水作业每个工件以特定的相同机器 2 次序在这些机器上加工 q = o 。( o p e ns h o p ) 表示m 台机器的自由作业每个工件在机器上加工的 次序不事先假定 a = 厶( j o bs h o p ) 表示m 台机器的异序作业每个工件以各自特定的机器 次序进行加工 ( i i ) 工件状况：表示工件的限制条件( 如果不写任何内容则表示无艘制) ，例如 p = 0 表示工件乃的准备时间不相同工件乃的加工不能在之前开始 卢= 石表示工件有截止期限 口= 矾表示工件有交工期 p = = 1 ”表示工件的工时为单位时间 j 8 = p r e c 表示工件的加工过程有一个先后次序的要求，后面的工件必须在 它前面的工件全部加工完成后才能开始加工 口= p m 饥表示工件允许中断抢先 p = m 表示工件易在平行机加工中允许加工的机器集合m ，是机器集 的子集 p = 6 0 c h 表示工件是分批进行加工的分批排序模型按分批方式的不同分 两大类：继列分批与平行分批 在继列分批模型( s _ b a t c l l ) 中，机器在每一时刻只能加工一个工件，工件是按照 一个接一个串联的方式形成一批的，同批的工件完工时间为该批最后卫件的完工 时间，批的加工时间定义为该批中所有工件的加工时间之和；在平彳亍分批模型( p - b a t c h ) 中，机器在每一时刻可同时加工多个工件，同批的工件完工时间相同，批的 加工时间定义为该批中所有工件加工时间最长者 本文讨论分批排序模型的若干结果，此问题的研究是现代排序论的童要课题 ( i i i ) 目标函数：表示优化的指标，例如： - 1 = j q 表示各工件加权完工时间之和 7 = q 弓表示各工件加权误时之和 ，y = 四表示各工件完工时间平方之和 3 ，y = 表示误工工件数 7 = c k a x 表示各工件的最终完工时间 7 = 三。表示各工件的最大延迟 7 = l 如1 表示各工件的加权绝对误差之和最小化该指标是使工件完工 的提前值与延迟值加权之和尽量小 7 = l 上，i 。表示各工件的最大绝对误差 7 = ( 他1 1 ) 表示多重指标的排序目标是在第一个指标1 1 为最优的条件下， 使第二个指标他为最优 2 计算复杂性 在为组合最优化问题提供计算方案时，同时要对此算法进行计算复杂性分析， 以说明算法的效率及历研究问题的难易程度计算复杂性理论中一个很重要的部分 是区别出“容易”问题( 即存在多项式时间算法的问题) 与“困难”问题( 即所谓n p h a r d 问题) 问题与实例 在计算复杂性理论中，主要研究判定问题( d e c i s i o np r o b i e m ) 所谓判定问题， 是指含一组参数的问句，要求回答“是”或“否”当问题中的参数给定时，便称为一 个实例( i n s t a n c e ) 一个实例的大小( 输入长度) 称为规模( s i z e ) 算法的时间界 一个算法的运算次数是指其中使用的基本算术运算( 加、减、乘、除、比较) 的 次数 定义1 1一个算法的时间界是指对输入长度为1 引的实例而害，在最坏情 况的运算次数的上界州 定义1 2 若一个算法 l 的时间界为，( n ) = o ( 扩) ，其中礼为实例的规模，k 为确定的正整数，则a l 称为多项式时间算法( p o l y n o m i 越t i i n em g o r i t l l m ) 多项式时间算法也称为好算法或有效算法，它是相对于二元代码箍言的 4 定义1 3 一元代码的多项式时间算法称为拟多项式时间算法( p s e 们o - p o l y n o m i a l ) p 问题与n p 问题 定义1 4 若一个问题存在多项式时间算法，则称之为p 问题 定义1 5 个判定问题a 称为n p 问题，是指对此问题的任一个y e s 一实例， 都存在一个判据c ( ，) 及一个验证算法，使得检验g ( ，) 可在多项式时间内完成 命题1 1p 问题类n p 问题类 多项式时间变换 问题a 可在多项式时间内变换为问题川，是指存在一个多项式p ，对任给问 题a 的个实例j ，可以在p ( 1 巾的时间内构造出闽题的实例，使得，是a 的y e s 实例锌，是a 的”s 实例，简记为ao ( a 7 n p 完全问题 定义1 6 若判定问题a 满足如下两个条件，则称为n f l 完全问题：( j ) a 是 n p 问题；( i l ) 所有n p 问题均可多项式地变换为a 要证明一个问题a 是n p 完全的就只需要做这样两件事： ( i ) a 属于n p 类； ( i i ) 找一个已知的n p 一完全问题b ，证明b 可多项式地变换为a 定义1 7 如果一个最优化问题的判定形式是n p 一完全问题，则称该问题为 n p - 困难( n p h a r d ) 问题 对一个问题a 及一个多项式p ，它的限制问题也是由a 中这样的实例组 成：z 中出现的最大整数俐m 6 e r ( z ) 茎p ( ) 定义1 8 对于一个n p - 完全问题，若存在一个多项式p ，使得其限制问题a 。 也是n p 一完全的，则称为强n p - 完全的( s t r o l l g l yn p c o m p l e t e ) 要证明某排序问题是n p 困难的，只需证明它的判定形式是n p 完全的常用 的已知n p _ 完全的问题是2 划分问题和3 - 划分问题 2 划分问题 5 给定正整数n 1 ，口。，是否存在子集sc = ( 1 ，2 ，礼 ，使 啦= 吼? 埏s t s 命题1 2 【3 9 】2 划分问题是n r 完全的 3 - 划分问题 给定正整数n 1 ，n 鼢，6 ，其中；6 q ；6 且翟1 啦一曲，是否存 在 1 ，2 ，3 礼) 的划分( s 。，晶) ，使得 岛i = 3 且啦= b ( j = 1 棚) ? 马 命题1 3 【3 9 13 - 划分问题是强n p 一完全的 3分批排序问题 分批排序问题是经典排序问题的推广，有很强的应用背景，主要产生于大规模 的生产流水作业线例如，半导体生产流水线分为四个主要阶段，其中最后阶段是 把半导体产品放在一个一个“烤箱”中，每个“烤箱”又放在“炉子”里烤，如果经 的住这样的烤就称为合格产品，否则为不合格此问题可描述如下：有n 个工件要 在一台机器上分批加工，每批至多可同时加工6 个工件( 6 称为批容量) ，每批作 为一个工件加工，问题是怎样分批且排序，使目标函数最优 本文讨论的分批排序问题可叙述如下：给定加工机器及n 个工件 ，如， ， 每个工件的加工是无问断的工件以的加工时间为肼且满足以下特征： ( 1 ) 将工件集分割成若干个子集，每一工件子集为一批 ( 2 ) 工件按批加工。即每批的工件放在一起加工 ( 3 ) 同批的所有工件的完工时间均相同，等于该批中最后工件的完工时间 ( 4 ) 当每批形成时，都有相同的安装时间，记为s ( 5 ) 每批最多可加工b 个工件，b 称为批容量当b n 时，称此模型为容量 有限制模型，模型三参数表示中的p 部分加入6 礼；若口部分没有加入6 n ， 此模型即为容量无限制模型，此时6 n ( 6 ) 目标是寻求可行的分批排序，即将工件分成若干批且排出各批的加工顺 序同时又使目标函数，最小按三参数表示法，此模型记为i b a 曲l ， 6 对于分批排序问题的解，工件的排列顺序往往是有规律的为了讨论方便，这 里先给出三个定义 定义1 9对于问题1 | b a c hi ，一个分批排序8 = ( b t ，b 2 ，匠) 称为 s p t 一型的，如果当正毋，乃岛且。 时，总有鼽胁 如果已知某单机分批排序问题存在s p t 一型的最优解，则若将工件按s p tf s h o r t e s tp r o c e s s i n gt i m el i r s t ) 序排列，即p l p 2 肌，那么一定存在最优 解召= ( b l ，岛，鼠) 使得每一批具有如下形式： 玩= 五：“sj ) ，其中“和 均为正整数 因此我们在讨论该问题时，总可以假定扎个工件是按照顺序p 1 p 2s s m 排 列的 定义1 1 0 对于问题1ib 8 c hi ，一个分批排序8 = ( b i ，疡，鼠) 称为 e d n 型的，如果当正疡，五玩且z 可时，总有d t d j 如果已知某单机分批排序问题存在e d d - 型的最优解，则若将工件按e d d f e 盯l i e s t d u ed a t ef i r s t ) 序排列，即工件按照交工期的非降序排列，那么一定存在最优解8 = ( 口l ，b 2 ，鼠) 使得每一批具有如下形式： b = 如：u j ”) ，其中乜和 均为正整数 因此我们在讨论该问题时，总可以假定n 个工件是按照顺序d 1 茎d 2 矍 列的 定义1 1 l 对于问题l | b 8 e 吐；qi ，一个分批排序b = ( b 1 ，岛， e r d 氆! 的，如果当j ：i f k ，如岛且z 0 ，戎们可令p ：= s + p j ( 1sj 茎礼) 此时有= 0 在继列分批模型( s - b 8 吐) 中，机器在每一时刻只能加工一个工件，工件是按 照一个接一个串联的方式形成一批的，批b 的加工时间定义为 岛= 功 山日 3 1 平行分批排序 平行分批排序模型是近年来文献中出现的最重要的现代排序模型之一其基本 模型是李忠义等在文【56 】中首先提出的如果研究的模型是容量有限制情形，即每 批工件数不超过常数6 ( 6 称为批容量) ，由三参数表示法，此模型记为 l p 6 a 曲；6 礼l ， 容量有限制的平行分批排序模型具有很好的应用背景例如f 5 6 】所述的实际问题来 源于所谓b u m j n 的半导体元件检验过程：将一批集成电路元件( 工件b 放入限制容 量的烘烤炉中加温，用以检验它们的抗热能力将选择好的一批元件放入特制炉中 加温赢到所有元件熔化各元件的熔化时间( 工件的加工时间) 可能各不相同当某 一元件先熔化之后，还要在炉中等待直到所有元件熔化，因此，这一批元件在炉中 的时间就是该批元件在炉中熔化的时间，即批的加工时间为该批所有工件加工时间 的最长者 显然，当批容量b = 1 时，平行分批排序模型就变成了经典的单机排序模型，机 器在每时刻最多加工一个工件由此可以看出，有容量限制的平行分批排序模型 研究起来不会比相应的传统非分批排序模型容易 对容量无限制情形，b m d ( e r 在l l l 】中综述了若干结果由三参数表示法，该模 型记为1p b a c j li ，容量无限制模型的应用背景也很强例如，在f 6 6 中，当炉 子的容量不比总元件个数少时，即可看作无容量限制的情形 有关平行分批排序的基本结果可在书b r u c l ( e rf 9 1 和网站f 12 1 中查蓟b r u c k e r 在文 1 1 】中给出如下结果：问题1p b a 6 曲lc l 。是多项式可解的，算法的时间界 8 为d ( n ) ；问题ljp b 8 吐；6 几ic r m 。是多项式可解的，时间界为0 ( n 1 0 9 凡) ；问 题1p 6 a t 曲il 。是多项式可解的，算法的时间界为d ( n l o g 礼) ；问题 1 p _ b 8 0 c j li q g 是多项式可解的，算法的时间界为o ( 几l o g n