（运筹学与控制论专业论文）关于两种现代排序模型的一些结果.pdfVIP

摘要 所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排 加工次序，使一个或多个目标达到最优它可以分为经典排序和现代排序相 对于经典排序而言，现代排序是非经典的、新型的排序近几十年来，有关现 代排序的研究有了很大的发展，新的排序模型也不断涌现常见的现代排序模 型有可控排序、成组分批排序、在线排序、同时加工排序、资源受限排序、多 目标排序和带有运输考虑的排序等等在本文中，我们研究了两种现代排序模 型：( 1 ) 相同的族安装时间的最小化最大延迟的单机成组分批排序问题( 2 ) 工件的加工时间和它们的尺寸成正比的最小化最大完工时间的单机排序和工 件运输问题 ( 1 ) 相同的族安装时间的最小化最大延迟的单机成组分批排序问题 在带有族安装时间的单机成组分批的排序问题中( 见 2 ，1 1 1 ) ，我们有n 个 工件 ，如，厶和f 个工件族氕，元，厅，它们是工件 ，无，厶的一个 划分每个工件五有一个加工时间功和一个工期d j ，每个族乃有一个安装 时间8 ，同一族里面的工件可以分批加工并且族乃的每个批要有一个安装时 间sr 目标是最小化最大延迟，在文献中，这个问题被记为l l s ，| 工这个问 题( 1 i s ，i 工。) 最早由b r u n o 和d o w n e y 2 】开始研究他们证明了这个问题在一 般意义下是n p 一困难的对这个问题，最好的算法是由g h o s h 和g u p t a 6 】提 出来的一个动态规划算法它的时间界是o ( f 2 n 7 ) ，这里n = 击。，。，i 乃1 + 1 在2 0 0 3 年，c h e n g ，n g 和y u a n 【9 】证明了这个问题是强n p 困难的这解决了 1 9 7 8 年由b r u n o 和d o w n e y 提出的一个长期的未解问题但是，当所有的族安 装时间都相同时，这个问题可以被记为1 l s ，= s l l 。，它的复杂性仍然是未知 的我们通过对 9 证明的发展，证明了这个问题仍然是强n p 一困难的 ( 2 ) 工件的加工时间和它们的尺寸成正比的最小化最大完工时间的单机排 序和工件运输问题 在一般的单机排序和工件运输问题模型中，我们有n 个工件 ，如， ， 它们首先在一台机器上加工，然后被一个有容量限制的汽车运送给一个顾客 每个工件以有一个加工时间p 3 和一个尺寸岛，在这里s j 代表工件以被装到 汽车中所要占的空间大小仅仅有一辆汽车去运送所有的工件，它有一个容量 限制。目标是寻找一个工件加工和运输的排序，使得所有工件被加工完毕并 运送给顾客的时间达到最小根据l e e 和c h e r tf 2 0 j 的记号，这个问题被记为 1 一d ，= 1 i ”= l ，c z i c , 。这里“1 一d ，k = 1 ”表示工件首先在一台机器上 加工，然后被运送给一个顾客；“”= 1 ，c = z ”表示仅仅有一辆汽车去运送所 有的工件，并且汽车的容量为z 有关工件加工和运输的排序问题已经成为在近十几年里最重要的、被广泛 研究的课题之一 a h m a d i1 1 3 】等人研究了两台机器( 一台单机和一台随后的 分批加工机器) 的流水作业排序问题，目标是最小化最大完工时间和完工时间 和h e r r m a n n 和l e e 1 9 】，y u a n 【2 4 ，c h e n 1 5 】，y a n g 【2 3 1 和c h e n g 1 7 等人考虑了 与工期相关的指标的分批排序问题l e e 和c h e n 2 0 根据运输时间和汽车容 量，而不考虑运送的费用，提出了另一种工件加工和运输的最小化最大完工时 间问题c h a n g 和l e e 1 6 】又发展了这个问题，他们考虑每个工件在汽车中占 据不同的空间他们证明了这个问题1 一d ，k = lj ”= 1 ，c = z l c 。是强n p 一困 难的，同时也提供了一个启发式算法，它的最差执行比为：，并且这个界是紧 的 但是，他们所考虑的工件的加工时间和它们的尺寸是独立的而在实际生 产中，与小的尺寸的工件相比，具有大的尺寸的工件往往需要更多的加工时 间因此，我们考虑了一种特殊的情形，即工件的加工时间和它们的尺寸戍正 比在这种限制下，问题被记为1 一d ，k = l p = 1 ，c = 。，p j _ “q f 。我们证 明了当工件的加工时间和它们的尺寸成正比时，这个问题仍然是强n p 困难 的并且c h a n g 和l e e 提出的启发式算法对我们研究的问题有更好的执行比嚣 我们也提供了一种新的启发式算法，它的最差执行比是2 ，并且这个界是最好 的 关键词t 排序；分批；工期；最大延迟；多工序工件；启发式算法；最差执 行比；渐进的p t a s a b s t r a c t s c h e d u l i n gi st oa s s i g nj o b sp r o c e s s e do nm a c h i n e su n d e rs o m ec o n s t r a i n t s ，s u c ht h a t o n e - o rn l 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 i tc a l lb ed i v i d e di n t oc l a s s i c a ls c h e d u l i n ga n d m o d e r ns c h e d u l i n g c o m p a r e dw i t ht h ec l a s s i c a ls c h e d u l i n g ，t h em o d e ms c h e d u l i n gi sn o n 。 c l a s s i c a la n dn e w - t y p e t h e r eh a v eb e e nm o r et h a nt e nm o d e r ns c h e d u l i n gm o d e l sw h i c h a r ew i d e l yd i s c u s s e do v e rt h el a s tt w e n t yy e a r s ，s u c ha st h es c h e d u l i n gw i t hc o n t r o l l a b l e p r o c e s s i n gt i m e ，t h eb a t c h i n gs c h e d u l i n g ，m u l t i - c r i t e r i as c h e d u l i n g ，t h es c h e d u l i n gw i t h t r a n s p o r t a t i o nc o n s t r a i n t sa n ds oo n i nt h i sp a p e r ，w ec o n s i d e rt w om o d e ms c h e d u l i n g m o d e l s ：( 1 ) t h es i n g l em a c h i n eb a t c h i n gp r o b l e mw i t hi d e n t i c a lf a m i l ys e t u p t i m e st o m i n i m i z em a x i m u ml a t e n e s s ( 1 3 ，= s l l 。“) ( 2 ) t h es i n g l em a c h i n es c h e d u l i n ga n dj o b d e l i v e r yt om i n i m i z em a k e s p a nw i t ht h ep r o c e s s i n gt i m eo f j o b sb e i n gp r o p o r t i o n a lt ot h e i r s i z e s ( 1 d ，k = 1 卜= 1 ，c = z ，功= u s j l c m 。) ( 1 ) t h es i n g l em a c h i n eb a t c h i n gp r o b l e mw i t hi d e n t i c a lf a m i l ys e t u pt i m e st om i n i m i z em a x i m u ml a t e n e s s ( 1 l s f = s l m h ) i nt h es i n g l em a c h i n e ，f a m i l yj o b s ，b a t c hs c h e d u l i n gp r o b l e m ( s e e 2 ，l l 】) ，w eh a v e nj o b sj l ，也，厶a n dff a m i l i e so fj o b s ，五，厅，w h i c hp a r t i t i o nt h ej o bs e t t j l fj 2 lj 0 e a c h3 0 bj ih a sap r o c e s s i n gt i m ep ia n dad u ed a t ed i ，a n de a c hf a m i l y 乃h a sa na s s o c i a t e ds e t u pt i m es f t h ej o b si naf a m i l ya r ep r o c e s s e di nb a t c h e sa n de a c h b a t c ho ff a m i l yf fw i l li n c u ras e t u pt i m es 1 t h eo b j e c t i v ei st om i n i m i z et h em a x i m u m l a t e n e s s i nt h el i t e r a t u r e ，t h i sp r o b l e mi sd e n o t e db yl s f l m 雠 t h es c h e d u l i n gp r o b l e ml s l m hw a sf i r s tr e s e a r c h e db yb r u n oa n dd o w n e y 2 】2 i n1 9 7 8 t h eb i n a r yn p h a r d n e s sp r o o ff o rt h ep r o b l e ml l s f l l m “w a sg i v e nb yb r u n o a n dd o w n e y1 2 jt h eb e s ta l g o r i t h mf o rt h ep r o b l e ml l s f l l m “i sad y n a m i cp r o g r a m r u i n ga l g o r i t h mg i v e nb yg h o s ha n dg u p t a 【6 】w i t hat i m eb o u n do ( f 2 n f ) ，w h e r e n = 吾l ，fi 乃i + 1 ，t h es t r o n g l yn p h a r d n e s so ft h ep r o b l e m1 1 8 ，i 工。w a sp r o v e d b yc h e n g ，n ga n dy u a n 9 】i n2 0 0 3 t h i sa n s w e r sal o n g - s t a n d i n go p e np r o b l e mp o s e db y b r u n oa n dd o w n e y 【2 i n1 9 7 8 w h e nt h eg e t u pt i m e so f 赳lf a m i h e sa r ei d e n t i c a l ，w h e t h e r t h ep r o b l e ml l s ，= s l l m a xi ss t r o n g l yn p - h a r d i ss t i l la no p e np r o b l e m b yad e v e l o p m e n t o ft h ep r o o fi n ( 9 ，w es h o wi nt h i sp a p e rt h a tt h es c h e d u l i n gp r o b l e m1 1 s s = s l l m 8 xi ss t i l l s t r o n g l yn p - h a r d ( 2 ) t h es i n g l em a c h i n es c h e d u l i n ga n dj o bd e h v e r yt om i n i m i z em a k e s p a nw i t ht h e p r o c e s s i n gt i m eo fj o b sb e i n gp r o p o r t i o n a lt ot h e i rs i z e s ( 1 d ，k = l i = 1 ，c = z l 岛= u s j l g 。) t h es i n g l em a c h i n es c h e d u l i n ga n dj o bd e l i v e r yp r o b l e mt om i n i m i z em a k e s p a nc a 2 1b e d e s c r i b e da sf o l l o w s t h e r ea r enj o b sj 1 ， t of i r s tb ep r o c e s s e di nam a n u f a c t u r i n g s y s t e mb yas i n g l em a c h i n ea n dt h e nt ob ed e l i v e r e dt oas i n g l ec u s t o m e r e a c hj o b 以h a s ap r o c e s s i n gt i m ep ja n das i z es j ，w h e r es jr e p r e s e n t st h ep h y s i c a ls p a c e 如o c c u p i e sw h e n i ti sl o a d e di nt h ev e h i c l e o n l yo n ev e h i c l ei se m p l o y e dt od e l i v e ra l lt h ej o b s ，w h i c hh a sa c a p a c i t yz t h a ti s ，t h et o t a lp h y s i c a ls p a c eo f j o b sl o a d e di n t ot h ev e h i c l ed o e sn o te x c e e d z t h ep r o b l e mi st of i n das c h e d u l ef o rp r o c e s s i n gj o b si nt h em a n u f a c t u r i n gs y s t e ma n d f o rd e l i v e r i n gf i n i s h e dj o b st oas i n g l ec u s t o m e rs u c ht h a tt h et i m er e q u i r e df o ra l lj o b st o b ep r o c e s s e da n dd e l i v e r e dt ot h ec o s t u m e ri sm i n i m i z e d b yu s i n gt h en o t i o no fl e ea n d c h e n 【2 0 ，t h es i n g l em a c h i n es c h e d u l i n gp r o b l e mw i t hj o bd e l i v e r yt om i n i m i z em a k e s p a n i sd e n o t e d b y l _ d ，k = 1 1 v = 1 ，e = z f “，w h e r e “1 _ d ，k = 1 ”i su s e d t or e p r e s e n t p r o b l e m si nw h i c hj o b sa r ef i r s tp r o c e s s e do i las i n g l em a c h i n e ，a n dt h e nd e l i v e r e dt oa s i n g l ec u s t o m e r ；a n d 知= 1 c = 名”m e a n st h a to n l yav e h i c l ei se m p l o y e dt od e l i v e ra l l j o b s ，w h i c hh a sac a p a c i t yz t h em a c h i n es c h e d u l i n gp r o b l e mw i t hd e l i v e r yc o o r d i n a t i o nh a sb e e no n eo ft h em o s t i m p o r t a n ta n dw i d e l yd i s c u s s e dt o p i c si nm a n u f a c t u r i n gr e s e a r c ho v e rt h el a s tt e ny e a r s a h m a d ie ta 1 1 3 h a v ec o n s i d e r e dat w o - m a c h i n ef l c w s h o p ( as i n g l em a c h i n ea n da s u b s e q u e n tb a t c hp r o c e s s o r ) s c h e d u l i n gp r o b l e mw i t ht w op e r f o r m a n c em e a s u r e si n c l u d i n g m a k e s p a na n ds u mo fc o m p l e t i o nt i m e s h e r r m a n na n dl e e 【1 9 ，y u a n 2 4 】，c h e n 1 5 】， y a n g 【2 3 a n dc h e n ge ta 1 1 7 h a v ec o n s i d e r e ds e v e r a lb a t c hs c h e d u l i n gp r o b l e mw i t h d u ed a t e sr e l a t e dm e a s u r e s l e ea n dc h e n 2 0 h a v ec o n s i d e r e da n o t h e rc o o r d i n a t i o no f p r o d u c t i o ns c h e d u l i n ga n dt r a n s p o r t a t i o n ( s u b j e c tt od e l i v e r yt i m ea n dv e h i c l ec a p a c i t y ) t om i n i m i z em a k e s p a nw i t h o u tc o n s i d e r i n gd e l i v e r yc o s t t h i sp r o b l e mh a sb e e ne x t e n d e d b yc h a n ga n dl e e 16 1b yc o n s i d e r i n gt h es i t u a t i o n w h e r ee a c hj o bm i g h to c c u p yad i f f e r e n t a m o u n to fp h y s i c a ls p a c ei nav e h i c l et h e ya s s u m e dt h a tt h ep r o c e s s i n gt i m eo faj o b i s i n d e p e n d e n to ni t ss i z e ，a n dp r o v e dt h a tt h i sp r o b l e mi ss t r o n g l yn p h a r da n dt h e n p r o v i d e dah e u r i s t i co fw o r s t - c a 8 ep e r f o r m a n c e r a t i oo fi ，a n dt h i sb o u n di st i g h t b u ti nt h em a n u f a c t u r i n gs y s t e m ，t h ej o bw i t hb i g g e rs i z em i g h tn e e dm o r ep r o c e s s i n g t i m et h a na n o t h e rj o bw i t hs m a l l e rs i z ew h e nt h e ya r ep r o c e s s e do nas i n g l em a c h i n e ，i n t h i sp a p e r ，w ea s s u m et h a tt h ep r o c e s s i n gt i m e so fj o b sa r ep r o p o r t i o n a lt ot h e i rs i z e s ， i e ，功= u s j ，w h e r eu d e n o t e st h ep r o c e s s i n gt i m en e e d e df o rau n i ts i z e u n d e r t h i sr e s t r i c t i o n ，t h ep r o b l e mi sd e n o t e db y1 _ d ，女= l i ”= 1 ，c = 五p j = u s j t v m b b y s e t t i n g “= 0 ，w ec a no b s e r v et h a tt h es t r o n g l yn p h a r db i n - p a c k i n gp r o b l e m ( g a r e y a n d j o h n s o n ，【3 1 ) i sas u b p r o b l e mo ft h ep r o b l e mu n d e rc o n s i d e r a t i o n h e n c e ，t h ep r o b l e m 1 + d ，女= l p = 1 ，c = 2 ，鳓：u s a c m “i ss t i l ls t r o n g l yn p - h a r d f o rt h i sp r o b l e m ， w ef i r s ts h o wt h a tc h a n g - l e e sh e u r i s t i ch a sab e t t e rp e r f o r m a n c er a t i oo f 嚣，a n dt h e n w ea l s op r o v i d e8n e wh e u r i s t i cw h i c hh a st h ew o r s t - c a s ep e r f o r m a n c er a t i oo fi ，a n dt h i s b o u n di 8b e s t k e yw o r d s ：s c h e d u l i n g ；b a t c h i n g ；d u e - d a t e s ；m a x i m u ml a t e n e s s ；m u l t i o p e r a t i o n j o b s ；h e u r i s t i c ；w o r s t c a s ep e r f o r m a n c er a t i o ；a s y m p t o t i cp t a s 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者 年月日 第一章引言 1 1排序的介绍 所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排 加工次序，使一个或多个指标达到最优它作为运筹学的一个分支，作为一门 应用科学，有着深刻的实际背景和广阔的应用前景随着机器制造业的迅速发 展，人们也越来越意识到排序问题研究的重要性1 9 5 4 年，j o h n s o n 完成了论 文“o p t i m a lt w o - a n dt h r e e - s t a g ep r o d u c t i o ns c h e d u l e sw i t hs e t u pt i m e si n c l u d e d ”，人们 普遍认为这是第一篇关于排序问题研究的论文在随后的五十年里，有关排序 问题的研究有了迅速的发展，已经发表的排序文献有近三千篇，排序专著和教 材近五十种现在，排序不仅被用在机器制造业当中，更被广泛应用在许多非 制造业的领域例如，对门诊病人到医疗诊所看病的问题，我们可以把病人当 成要加工的工件，把医生当成机器，这就转化成了一个机器排序问题 在唐国春，张峰等人2 0 0 3 年的现代排序论一书中，他们把排序分为 经典排序( c l a s s i c a ls c h e d u l i n g ) 和现代排序( m o d e r ns c h e d u l i n g ) 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 s ”f 见h t t p ：w w w m a t h e m a t i k u n i o s n a b r u e c k d e r e s e a r c h o r c l a s s ) 也使用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 so fs c h e d u l i n gp r o b l e m s ( 新 型排序) 来表示非经典的排序问题因此，现代排序就是非经典的，新型的排 序现代排序或新型排序是相对于经典排序而言的，其特征是突破了经典排序 的许多基本假设在最近的二十年间，现代排序模型不断涌现，已经达到了十 多种比较常见的现代排序模型有可控排序、成组分批排序、在线排序、带有 运输考虑的排序，准时排序和窗时排序，不同时加工排序、资源受限排序、随 机排序、模糊排序、多目标排序等等排序论的长足发展，特别是现代排序的 丰硕成果，已经使排序论成为发展最迅速，研究最活跃，成果最丰硕，前景最 诱人的学科领域之一 对一个排序问题来说，一般主要从三个方面进行研究： 1 寻找一个多项式时间算法 2 证明排序问题在一般意义下是n p 一困难的或者是强n p 困难的 3 对那些n p 一困难的问题，寻找一个近似算法或者一个拟多项式时间算 法 对一个排序问题来说，找到一个比较有效的算法得到一个最优解是十分必 要的尽管当工件的个数礼比较小的时候，我们可以枚举所有n ! 种可能的排 序方式但是，当n 比较大时，枚举几乎是不可能的甚至对一个最简单的最 小化完工时间和的单机排序问题，当n = 2 0 时，就有2 0 1 = 2 4 1 0 ”种排序方 式即使使用目前最快的计算机，也需要几年的时间才能枚举完因此，枚举 不是一个好的算法 什么是一个好的算法呢? c o b h a m 1 9 6 4 】和e d m o n d s 1 9 6 5 】建议，一个好的 有效的算法应该是一个多项式时间算法也就是说，存在一个整数k ，使得算 法在o ( n ) 时间内完成例如，对上述的最小化完工时间和的单机排序问题， s m i t h 算法在o ( n l o g n ) 时间内能够解决，计算机只需要几秒钟就能完成因此， 对一个排序问题来说，如果能找到一个多项式时间的算法，这是最为理想的 对所有的有一个多项式时间算法的问题类，我们记为p 不幸的是，对大多数的排序问题来说，我们不知道是否存在一个多项式时 间的算法然而，我们知道有这样一类问题一旦其中的一个问题能够在多项 式时间内解决，那么所有其它的问题都可以在多项式时间内解决因此，这些 问题是最难找到一个多项式时间算法的我们很有必要去讨论一个问题有多 难，也就是证明它是否是n p 一困难的现在，我们将介绍一些相关的概念 一个判定问题是一个二元组p = ( x ，y ) ，在这里x 能在多项式时间内判定， 并且y x x 中的元素被称为p 的实例；y 中的元素被称为p 的是实例， x y 中的元素被称为p 的否一实例一个判定问题p = ( x ，y ) ，如果存在一个 多项式p 和一个证据的集合c ( x ) 使得，对每个。x ，g ( z ) 的大小( s i z e ) 至多 是p ( s i z e ( x ) ) ，并且对每个”y ，g ( f ) 实际是一个证明y y 的证据，我们就说 p = ( x ，l ，) 属于n p 尽管大多数人都猜测p n p ，但是长期以来一直没有得 2 到解决，这已经成为目前最为重要的未解问题之一 假设p 1 和尼是两个判定问题如果对任意给定的p l 的实例 ，我们能在 多项式时间内构造p 2 的实例1 2 ，使得 是p 1 的一个是一实例当且仅当厶是p 2 的一个是一实例，则我们称p 1 能多项式时间内转化为p 2 ，假如p l 能多项式时 间内转化为p 2 ，那么岛至少不会比p l 更容易因此，如果恳有一个多项式时 间算法，则r 一定也有一个多项式时间算法 一个判定问题p = ，y ) n p ，如果所有其它的在n p 类中的问题都可 以在多项式时间内转化为p ，则我们称p 是n p 完全的如果一个问题p = ( x ，y ) n p 在二元输入时是n p 一完全的，则我们称p 在一般的意义下是n p 一 完全的；相应的，如果一个问题p = ( x ，y ) n p 在一元输入时是n p 一完全的， 则我们称p 是强n p 一完全的 对一个最优化问题p ( 包括排序问题) 来说，如果它的判定问题是n p 一完全 的，那么我们称p 是n p 一困难的类似地，我们也有在一般的意义下是n p 一困 难的和强n p 困难的定义对这些n p 困难的问题，找到一个多项式时间的算 法获得一个最优解是非常难的但是，如果我们降低一些要求，找个一个拟多 项式时间算法来输出一个最优解，或者设计一个多项式时间的算法得到一个接 近于最优解的近似解，这都是有可能的寻找一个比较有效的近似算法和拟多 项式时间算法，已经成为当前排序论研究最活跃，最主要的一个方向下面， 我们将介绍一些有关排序问题拟多项式时间算法和近似算法的定义 设p 是一个具有非负权的排序问题，且每个实例，的元素都是整数设 其中最大的整数为l a r g e s t ( i ) 如果p 的一个算法a 的运行时间有界于s i z e ( i ) 和 l a x g e s t ( i ) 的一个多项式，则我们称算法a 是p 的一个拟多项式时间算法并 且我们已经知道，对一个强n p 一困难的问题p ，不可能有一个拟多项式时间算 法 设p 是一个具有非负权的排序问题，k 1 如果p 的一个多项式时间 算法a ，对p 的每一个实例j 都有a ( i ) k o p t ( i ) ，则我们称多项式时间算法 a 是排序问题p 的一个k 一因子近似算法我们也说算法a 有执行比k 使得 a ( i ) k o p t ( i ) 成立的最小的k ，就称为a 的最差执行比 3 设p 是一个具有非负权的排序问题如果p 的一个多项式时间算法a ，存 在一个常数c 对p 的每一个实例j 都有a ( i ) k o p t ( i ) + c ，则我们称多项式时 间算法a 是排序问题p 的一个渐进的因子近似算法，我们也说算法a 有渐 进的执行比k 设p 是一个具有非负权的排序问题如果p 的一个多项式时间算法a 任 意输入p 的一个实例j 和一个e 0 ，使得对每一个固定的e ，a 都是p 的一个 ( 1 + e ) 因子的近似算法，那么，我们称算法a 是p 的一个近似方案 p 的一个渐进的近似方案是一个算法对( a ，a ) 在这里，是一个多项式时 间算法，如果输入一个数e 0 ，将输出一个常数c c 并且如果a 任意输入p 的一 个实例，和一个e 0 ，它将输出j 的一个可行解且满足a ( i ，e ) ( 1 + e ) o p t ( 1 ) + c 。 对每个固定的e ，a 的运行时间有界于s i z e ( i ) 的一个多项式我们也把多项式时 间的近似方案缩写为p t a s 1 2排序的记号 根据1 9 7 9 年g r a h a m 等人【18 】提出的排序问题的三参数表示法，我们使用 a 例7 来表示一个排序问题在这里，a 表示机器的数量，类型和环境；卢表 示工件的特征和约束；7 表示要优化的目标 ( 1 ) a 域： 1 所有工件在一台机器上加工 1 ，d ，k = 1所有工件在一台机器上加工，然后被运送给一个顾客。 f mm 台机器且流水作业 ( 2 ) 卢域t ，厶n 个需要加工的工件 五，厅f 个族，他们是工件 ，厶的一个划分 对j = 1 ，n 和，= 1 ，f 功工件以的加工时间 a ，工件以的第i 个工序的加工时间 4 s ，族乃的安装时间 d j 工件 的工期 s ，工件以的尺寸，也就是工件以在运输中所占汽车空间的大小 ”= 1 只有一辆汽车运送所有的工件 c = ：汽车的容量限制为也就是说在一次运输中，汽车中所装的工件的 尺寸总和不能超过z p j = u 工件五的加工时间p j 和它的尺寸s j 成正比 奶工件以的权 ( 3 ) 7 域t 首先，我们需要介绍一些概念 q 工件五的完工时间 岛工件以的延迟时间，这里，岛= g d j 弓工件以的延误时间，这里，弓= m “ 岛，o ) 工件以的误工记数如果g 由，则= o ；如果q 略，则= 1 现在，我们开始介绍一些规则的优化指标 。最大完工时间，在这里。= m a x ( c j l lsj 1 k 。最大延迟，在这里l 。= m a x l j l l j n ) e g 完工时间和 屿q 加权的完工时间和 乃误工时间和。 屿弓加权的误工时间和 玛误工工件数 嘶加权的误工工件数 5 第二章单机成组分批排序问题1 s f = s l l 。 2 1相关介绍 在单机成组分批排序问题中( 见 2 ，1 1 ) ，我们有n 个工件 ，也， 和f 个工件族五，兀， f ，这里的 ，焉，斥是工件 ，如，厶 的一个划分 每个工件有一个加工时间功和一个工期d j ，并且每个族乃有一个安装时间s f 同一个族的工件可以成批加工，并且族乃的每个批在加工之前要有一个安装 时间即在文献中，这个问题被记为1 s a v ，这里y 是要最小化的目标函数 对问题1 蚓嘶g ，g h o s h 【5 】提出了了一个动态规划算法，算法的复杂性是 o ( n ，) 当f 是个固定的常数时，这是一个多项式时间算法但是，当f 是一个 任意的数时，p o r t s 和k o v a l y o v 【1 2 指出了1 1 8 ，l q 和1 s ，l 屿0 的复杂性都 是未知的对问题l 8 f i q ，g u p t a 7 ，w i l l i a m s 和w i r t h 【8 | 1a h n 和h y u n 【1 】都提 出了一些启发式算法r o t e 和w o e g i n g e r 【2 6 1 证明了当同一族中的所有工件有 相同的工期时，问题1 i s ，i 能在o ( n 2 ) 的时间内解决对这个问题1 i s ，i ， c r a u w e l s 等人 27 】也提供了一个分枝定界算法 最小化最大延迟的单机成组分批排序问题1 蚓三。首先在1 9 7 8 年由b r u n o 和d o w n e y 2 开始研究，他们证明了这个问题在一般意义下是n p 一困难的对这 个问题，最好的算法是g h o s h 和g u p t a 6 】提出的一个界为o ( f z n ，) 的动态规划 算法，这里n = 毒l d j ，则( ”) = 1 因此，一个工件乃是误工的当且仅当= 1 我们也定 义工件占的延迟岛( n ) = q ( ”) 一略，l j n 在这篇文章中，我们考虑的目标 是寻找一个排序”使得最大延迟工。8 x ( ”) = m a x t g 。如( ”) 达到最小我们称这 个问题为单机多工序工件成组分批加工组装的最小化最大延迟排序问题根据 4 】我们把这个问题记为 1 1 8 ，a s s e m b l y l m ， 这里“a s s e m b l y l 表示当一个工件的所有工序都被机器加工完可以组装时，这个 工件才算完工相应的可行性问题，记为1 i s ，a s s e m b l y i = 0 ，并问是否存在一 个可行排序”，使得所有的工件都被按时完工在【4 中，问题1l s ，a s s e m b l y l 。 和1 蚓l 。的等价性被建立 通过对f 9 证明的发展，我们证明了可行性问题1 i s ，= s ，a s s e m b l y i u j = 0 是强n p - 困难的相应的，排序问题l s s = s ，a s s e m b l y l l 。和小，：s f 三。都 是强n p 一困难的 7 2 2n p 困难性证明 正如 4 】所表达的，我们有 引理2 1 如果问题1 1 8 ，= 8 ，a s s e m b l y le = 0 是可行的，那么有一个可行 的排序”，使得每个族里的工序在”中按工期从小到大的顺序( e d d 序) 进行加 工也就是说，对族乃( 1 ，f ) 中的任意两个工序( ， t ) 和( ，j ) ，在排序” 中( f ，i ) 在( ，j ) 之前加工，当且仅当d t 略 我们需要下面强n p 一完全的3 一划分闻题【3 进行我们的归结 3 _ 划分问题设有3 t 个正整数a l ，a ”，a 3 t ，1 a i b 一1 ，且饕l a 产t b ， 问是否存在一个划分把a t 分成t 组且每组3 个元素，使得每组3 个元素的和恰 等于b ? 下面的引理2 2 将用在我们的证明中，在 9 中定理2 3 的证明过程保证了 它的正确性 引理2 2 设o l ，0 2 ，啦和b 是t + 1 个正整数使得o l + a 2 + + 啦= t b 且 ( t + 1 ) ；= o l k + l ：，k a k 墨水+ 1 ) 蜀= _ b + 盛：，k b ，对每个r ，1 r 墨t 都成立 男5 么0 1 = 血2 = = a t = b 定理2 3 可行性问