（运筹学与控制论专业论文）限位排序和单机工件运输排序的若干结果.pdf

郑重声明 本人的学位论文是在导师指导下独立完成的，学位论文没有剽窃、抄袭等违反学术道 德的侵权行为，否则，本人愿意承担由此产生的一切法律责任和法律后果，特此郑重声明 学位论文作者( 签名) ：陈友军 2 0 0 5 年0 4 月2 5 日 似髻 摘要 在本文中，我们研究了两种排序模型：( 1 ) 工件具有位置约束的限位排序问题( 2 ) 工件 先加工后运送到顾客的单机排序问题 ( 1 ) 工件具有位置约束的限位排序问题 在限位排序中1 ，6 1 ，我们有n 个工件j 1 ，如，厶和m 个工件族五，磊， m 且 五n 乃= o ( i ) ，它们是工件集 以，j 2 ，厶) 的一个划分每个工件j j 有一个加工时 间p ，权 ，到达时间q 和一个工期出，每个族氕有一个位置允许集 1 ，2 ，n ) ，= 1 ，2 ，一，m 对于i j 来说，& 与昂可以相交在文献中，这个问题被记为i l p r i f ，其中 ，= c 矗一g ，q 弓，q ，q 这个问题( i i p r i f ) 最早由林诒勋和原晋江提出，我们知道1 1 q 岛可以按照s m i t h 。s 规则获得最优解，1 i l l 。a x 可以按照e d d 规则获得最优解，1 1 i w j 叻和1 1 i w 3 t j 都是n p 困难的但是i i p r i 功g 的复杂性仍是未知的我们通过考虑此间题的特殊情形，给出了 一些多项式可解的例子，接着考虑了个关于平行机排序问题 ( 2 ) 工件先分批加工后运送到顾客的单机排序问题 在一般的单机排序和工件运输问题模型中，我们有n 个工件以，也，- ， ，它们先分批 后在一台机器上n z _ ，然后被一个有容量限制的汽车运送给两个顾客每个工件 有一个 加工时间p j 和个尺寸s ，在这里s j 代表工件如被装到汽车中所要占的空间大小仅仅 有一辆汽车去运送所有的工件，它有一个容量限制z 目标是寻找一个工件加工和运输的 排序，使得所有工件被加工完毕并运送给顾客的时间达到最小本文考虑的是在2 t 1 t 3 限制下的问题根据l e e 和c h e n 1 5 l 的记号，这个问题被记为1 一d ，k = 2 m 。1 ，c = ：，2 t 1 t 3 i c 。，这里“1 一d ，k = 2 ”表示工件首先在一台机器上加工，然后被运送给两个 顾客；“v = 1 ，c = z ”表示仅仅有一辆汽车去运送所有的工件，并且汽车的容量为# 工件加工和运输的排序问题已经成为在近十几年里最重要的被广泛研究的课题之 一a h m a d i1 7 等人研究了两台机器( 一台单机和一台随后的分批加工机器) 的f l o w s h o p 排 序问题，目标是最小化最大完工时间与完工时间总和i t e r r m a n n 和l e e 【l4 ，y u a nf 19 ，c h e n 【9 1y a n g 1 8 和c h e n g 【1 1 lg 笋人考虑了带有工期相关指标的分批排序问题l e e 和c h e n 1 5 1 根据运输时间和汽车容量，而不管运送费用，考虑了另一种工件加工和运输的最小化最大 完工时间问题c h a n g 和l e e 1 0 】又发展了这个问题，他们考虑每个工件在汽车占据不同 的空间他们证明了这个问题1 一d ，k = 2 ”= 1 ，c = z l a 。a x 是强n p 困难的，同时提供了 一个启发式算法，它的最劣性能比为2 在2 n t z 限制下，我们提供了一个最劣性能比为 强的改进算法 关键词：限位排序；横贯拟阵；独立系统；启发式算法；最劣性能比 a b s t r a c t i nt h i sp a p e r ，w ec o n s i d e rt w om o d e r ns c h e d u l i n gm o d e l s ：( 1 ) s c h e d u l i n gw i t hj o bp o s i t i o n r e s t r i c t i o n ( i i p r i f ) ( 2 ) t h es i n g l em a c h i n es c h e d u l i n gw 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 ( 1 一d ，k = 2 i v = 1 ，c = z ，2 五码l g k 一) ( 1 )s c h e d u l i n gw i t hj o bp o s i t i o nr e s t r i c t i o n ( 1 i p r l ，) i nt h em a c h i n ep o s i t i o nr e s t r i c t i o np r o b l e m ，w eh a v enj o b sj l ，如， a n dmf a m i l i e so f j o b s 五，五，五。，w h i c hp a r t i t i o n t h e j o bs e t ，j 2 ， w i t h 五n 乃= o ( i j ) e a c h j o b g j h a sap r o c e s s i n gt i m ep j ，aw e i g h tw j ar e l e a s ed a t e75a n dad u ed a t ed j e a c h 氏h a sa p o s i t i o na d m i s s i b l es e t & 1 ，2 ，n ，k = l ，2 ，m & a n d 与m a y i n t e r s e c t f r o me a c ho t h e r ( i j ) t h e nl p = s l ，s m ) i sas u b s e tf a m i l yo fp o s i t i o n s i nt h el i t e r a t u r e ，t h i sp r o b l e m i sd e n o t e db yl l p n l f t h es c h e d u l i n gp r o b l e m1 l p 咒l ，w a sf i r s tp r o p o s e db yl i ny i x u na n dy u a nj i n j i a n g w e k n o w t h a t l l i w j qc a l 2 b es o l v e d i n p o l y n o m i a l t i m eb ys m i t h sr u l e ：p r o c e s s t h e j o b s i n o r d e r o fn o n i n c r e a s i n gr a t i o s 署l t l lc a 2 2b es o l v e di np o l y n o m i a lt i m ei ne d d r u l e 1 1 l w j u j a n d l l i e q t ja r e b o t h n p - h a r db u t t h ec o m p l e x i t y o f t h e p r o b l e m i p r l e w j o i ss t i l lo p e n i nt h i sa r t i c l e ，w ec o n s i d e rs o m ep o l y n o m i a l l ys o l v a b l ec a s e so b t a i n e db yr e s t r i c t i n gp j = 1 t h e n w ef u r t h e rc o n s i d e rap r o b l e mo nu n r e l a t e dp a r a l l e lp r o c e s s o r s ( 2 ) t h es i n g l em a c h i n es c h e d u l i n gw 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 ( 1 一d ，k = 2 i v = 1 ，e = # ，2 五t a l c k 。) 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 h v e r yt om i n i m i z em a k e s p a ne 8 2 2 , b 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 ob ef i r s tb a t c h e da n dt h e np r o c e s s e db ya s 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 ot w oc u s t o m e r s e a c hl o bj ih a sap r o c e s s i n gt i m e p ja n da s 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 ni t i sl o 甜e di nt h e v 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 sac a p a c i t yz t h a ti s ，t h e t o t a lp h y s i c a ls p a c eo fj 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 dz t h ep r o b l e mi st of i n da s 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 df o r d e l i v e r i n gf i t f i s h e dj o b st ot w o c u s t o m e r ss 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 ob 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 r s i sm i n i m i z e db yu s i n gt h en o t a t i o no fl e ea n dc h e n 【1 5 ) ，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 m w 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 ni sd e n o t e db y1 _ d ，k = 2 l ”= 1 ，c = 2 ，2 t 1 t a l c , 。， w h e r e “1 _ d ，= ri su s e dt or e p r e s e n tp 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 d0 1 2as i n g l e m a c h i n e ，a n dt h e nd e l i v e r e dt ot w oc u s t o m e r s ；a n d “ = 1 ，c = z m e a n st h a to n l yav e h i c l ei 8 e m p l o y e dt od e l i v e ra l lj o b s ，w h i c hh a sac a p a c i t y2 2 t h em a c h i n es c h e d u h 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 ti 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 td e c a d ea h m a d ie t a 1 7 】h a v ec o n s i d e r e dat w o - m a c h i n ef l o w s h o p ( as i n g l em a c h i n ea n das 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 h 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 gt h em a k e s p a na n dt h et o t a l c o m p l e t i o nt i m e h e r r m a n na n dl e e 1 4 1 ，y u m l 【1 9 】，c h e n 【9 1 ，y a n g 【l s a n dc h e n ge ta 1 【1 1 】 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 hd 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 【1 5 】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 fp 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 t t 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 uw 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 db yc h a n ga n dl e e 【1 0 b yc o n s i d e r i n gt h es i t u a t i o nw h e r ee a c h j o bm i g h to c c u p yad i f f e r e n ta m m m to fp h y s i c a ls p a c ei nav e h i c l e t 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 bi si n d e p e n d e n to i li 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 d a n dt h e np r o v i d e dah e u r i s t i co fw o r s t - e a s ep e r f o r m a n c er a t i oo f2 i nt h i sp a p e r ，w ea s s u m et h a t2 t , 乃，w h e r en ( 正) i st h et r a n s p o r t a t i o nt i m ef o rab a t c h t h a tc o n t a i n so n l yj o b st h a tr e q u i r ed e l i v e r yt oa r e al ( a r e a2 ) ，t 3i st h et r a n s p o r t a t i o nt i n l ef o r ab a t c ht h a tc o n t a i n sj o b st h a tr e q u i r ed e l i v e r yt oa r e a1a n da r e a2 u d e rt h i sr e s t r i c t i o n t h e p r o b l e mi sd e n o t e db y1 _ d ，k = 2 i v = 1 ，c = z ，2 t , t 3 1 c m “w eg i v ea na l g o r i t h mw i t h w o l ：s t * e a s ep e r f o r m a n c er a t i o 可2 7 k e yw o r d s ：p o s i t i o nr e s t r i c t i o ns c h e d u l i n g ；b a t c h i n g ；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 e r a t i o 3 第一章排序问题概述 1 1排序问题介绍 所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排加上次序， 使一个或多个指标达到最优。它作为运筹学的一个分支，作为- - f 虚用科学，有着深刻的实 际背景和广阔的应用前景随着机器制造业的迅速发展人们也越来越意识到排序问题研 究的重要性1 9 5 4 年，j o h n e o a 完成了论文“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 s w 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 i r 和k m t s t 在“c o m p l e x i t yr e s u l t s o fs c h e d u l i n gp r o b l e m s ”( 见h t t p ：t w w w m a t h e m a t i k1 1 1 1 h i l 如m 以d e r e s e a r c h o r c l a s s ) 也 使用c l a s s i c m 和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 一困难( b i n a r yn p h a r d ) 或者一元n p 困难( u n a r yn p h a r d ) 3 对那些n p 一困难问题，寻找一个近似算法或者一个拟多项式时间算法 对个排序问题来说，找到一个比较有效的算法得到一个最优解是十分必要的尽管 当工件的个数n 比较小的时候，我们可“枚举所有n 1 种可艏的排序方式但是，当n 比较 大吨枚举几乎是不可能的甚至对一个最简单的最小化完工时间和的单机排序问题，当 n = 2 0 时，就有2 0 112 4x1 0 馆种排序方式即使使用目前最快的计算机，也需要几个世纪 5 的时间才能枚举完因此，枚举不是一个好的算法 什么是一个好的算法呢? c o b h a m 【1 9 6 4 】和e d m o n d s 1 9 6 5 】建议，一个好的有效的算法 应该是一个多项式时间算法也就是说，存在一个整数k ，使得算法在d ( 舻) 时间内完成 例如，对上述的最小化完工时间和的单机排序问题，s m i t h 算法在o ( n l o g n ) 时间内能够解 决，计算机只需要几秒钟就能完成因此，对一个排序问题来说，如果能找到一个多项式时 间的算法，这是最为理想的对所有的有一个多项式时间算法的问题类，我们记为p 不幸的是，对大多数的排序问题来说，我们不知道是否存在一个多项式时间的算法然 而，我们知道有这样一类问题一旦其中的一个问题能够在多项式时间内解决，那么所有 其它的问题都可以在多项式时间内解决，这就是一类n p 困难问题因此，这些问题是最 难找到一个多项式时问算法的但是我们可以设计一个算法去近似逼近最优解，这就是近 似算法的思想 设s 是一个具有非负权的排序问题，k 1 ，如果s 的一个多项式时间算法a ，对s 的 每一个实例j 都有a ( i ) k o p t ( j ) ，则我们称多项式时间算法a 是排序问题s 的一个k 因子近似算法我们也说算法a 有性能比k 使得a ( i ) k o p t ( i ) 成立的最小的k ，就称 为a 的最劣情形性能比 1 2排序论记号 根据1 9 7 9 年g r a h a m 等人【1 4 】提出的排序问题的三参数表示法，我们使用n 1 来表 示一个排序问题在这里，o z 表示机器的数量、类型和环境；口表示工件的特征和约束；1 表 示要优化的目标 ( 1 ) a 域： 1 所有工件在一台机器上加工 1 ，d ，k = 2 所有工件在一台机器上加工，然后被运送给两个顾客 晶。m 台同速的平行机 q 。m 台恒速的平行机 岛，m 台变速的平行机 e m ”l 台机器且流水作业 厶m 台机器且异序作业 0 。m 台机器且自由作业 ( 2 ) 卢域： 以， n 个需要加工的工件 五，矗m 个族，它们是工件以，厶的一个划分 对j = 1 ，n 和i = 1 ，m 6 p j 工件如的加工时间 p i j 工件出的第i 个工序的加工时间 & 族五的位置允许集 由工件如的工期 町工件由的尺寸，也就是工件如在运输中所占汽车空间的大小 ”= 1 只有一辆汽车运送所有的工件 c 一= 汽车的容量限制为z ，也就是说在一次运输中，汽车中所装的工件的尺寸总和不 能超过= w 工件 的权 q 工件如的准备时问 p r e c 优先约束，一般地，我们使用 _ 由，则v j = 1 现在，我们开始介绍一些规则的优化指标 c k a x 最大完工时间，在这里c k 。= m q l l j n ) 工m “最大延迟，在这里k m x = m “ ，i i j n ) q 完工时间和 吩g 加权的完工时间和 乃误工时间和 嘶乃加权的误工时间和 误工工件数 q 加权的误工工件数 7 第二章关于限位排序问题的一些结果 2 1引言 排序理论有广泛的应用在一些应用情形，受资源条件限制，每一个工件可能仅允许在 一些指定位置加工这就有新的模型一限位排序的产生，它是经典排序问题的一般化 在单机限位问题中，我们有n 个工件j l ，如， 和m 个工件族 ，冗，矗，这m 个 工件族是工件集 ，如， 的一个划分，五n 乃= 0 “j ) 每个工件出有一个加 工时间功，权q ，到达时间q 和工期d j 每个族氕有一个位置允许集& 1 ，2 ，n ， k = 1 ，2 ，m 最和与可以相交( i j ) 那么【p = s l ， 是位置的子集族 工件的一个排序= ( ”( 1 ) ，n ( 2 ) ，”( n ) ) 是可行的如果厶f 1 1 氕意味着i 假定1 五睁l c f c 。m = n 通过把& 拷贝m 份构造一个新的子集族矿，即矿= n - s l ，n 。，n 。s 如果给矿的元素下标重新标号，那么我们得到下面的一 令o = s l ，s 2 ， 是e = e l ，e 。) = 1 ，2 ，n ) 的一个子集族，其中e 代表位置 集，是工件以( 1 k 茎n ) 的位置允许集一个子集，= q 。，e j 。，e j 。) 是部分横贯如果 存在“1 ，i 2 ，i t ) 1 ，2 ，耐使得e j k s i 。，k = 1 ，2 ，t 如果t = n ，那么j 是口的一个 横贯 如果我们选择，= el 每个是a 的一个部分横贯 ，那么( e ，) 构成一个拟阵，称 为，横贯拟阵f 3 ，4 1 可以看出一个可行的排序”是一个横贯事实上，如果”= ( ”( 1 ) ，”( 2 ) ，”( n ) ) 是可行 的，那么位置k 属于允许集兔，其中i k = 口( ) ，k = 1 ，2 ，n 因此，i = l ，2 ，。n ，是 o = & ，岛，最。) 的一个横贯相反地，如果是a 的一个横贯且k & ，那么通过令 ”( ) = i k ( k = 1 ，2 ，n ) ，得到7 r 是一个可行的排序因此，我们可用一个横贯，来代替一个 可行的排序 我们把上述的限位排序问题表示为i p r f ，其中，是一个正则的目标函数 在本章中，我们首先考虑当，= c k o ，w i t 3 ，屿， o 的情形接着， 我们考虑另一个问题r i p r i c j ，其中r 表示m 个无关的_ 甲行机排序术语和记号和2 ， 6 】中的是一样的 8 2 2一些多项式可解的例子 我们首先考虑排序问题i l p r i c , 。一 引理2 1 【1 ，4 1 偶图最大匹配算法可在o ( n 2 ) 时间内完成 定理2 1 问题1 j p 月l g 一是多项式可解的 证明令p = 1 ( j 9 p j 那么对一个排序i 来诡 g = j 只 如果i 是口的堋贯 io 。，否则 判断j 是否( 9 - 的一个横贯可以在o ( n 2 ) 时间内通过偶图匹配算法解决因此结果得证口 引理2 2 1 ，q 偶图最大权匹配算法的时问界是o ( 护) 接着，我们来看1 p r i g ，其中q 是工件乃的完工时间注意到一个排序”的目标 函数 q ( i ) = 伽一i + 1 ) p 。( ；) 因此，如果工件出排在第i 个位置( ”( i ) = j ) ，那么，我们定义费用锄= m i + 1 ) p j 这 就有下面的结果 定理2 2 排序问题1 p r leq 是多项式可解的 证明我们把上面的问题转化为下面的分配问题令 = ：，一+ ”功罢嚣，5 岛i o 。， 古则， 一 i 1 ， 如果5 2 件j j 排在位置i 峋一1o ，否则 那么排序问题等价于 r a i n c 4 j z 玎 l 兰t n1 s j g n s t ex i j = 1 0 = 1 ，2 ，n ) 1 曼，兰“ x i j = 1 0 = 1 ，2 ，n ) l t ” x i j o ，1 ) 我们知道分配问题通过偶图的最大权匹配算法可以在o ( n a ) 时间内解尧口 9 类似地，我们现在考虑问题l lp j = 1 ，p r l ”，q 令 那么这个排序问题等价于 i ， 如果i 岛 否则， 如果工件j j 排在位置i 否则 r a i n q l 矗( 砷 问题是找一个排列”使得加权误工工件数 ，( ”) = 。( 砷( k ) 1 蔓k “ 达到最小，其中t j 。( ”o 是工件矗( 蚺的权 在组合最优化理论中独立系统扮演着重要的角色其中一个原因就是广泛的实际问题 可以用独立系统中的最大权独立集问题( 简记为m w i ) 来系统地表述拟阵是一种特殊的 独立系统，它具有的特征是贪婪算法对于对应的有任意权函数的m w i 问题总是有效的 令e 是一个有限集，2 8 是e 的子集族，它满足 1 0 町 k 仉 ricl【，l【 = 1 1 叼 ( i ) i0 ，； f i i ) ，j ，辛， 那么旧，厂) 是一个独立系统，的所有元素称为独立集，2 8 ，的所有元素称为相关 集 一个独立系统( e ，) 称为一个拟阵，如果 ( i i i ) 对于，和i ，f 1 ，1 ，必有一个元素e j v 使得，+ e ， 最大权独立集( m w i ) 问题可以叙述如下：在独立系统( e ，) 中，对每一个e e ，给 定一个权”( e ) 0 ，找一个j ，使得( j ) = 。，”( e ) 达到最大【3 ，4 ，5 】 现在，令e = l ，2 ，n ) 是工件的下标集为简化记号，我们可以假定r l r 2 sh 且q + 1 兰d j 定义位置集t = a 1 ，i 2 ，t 。) 如下： ( a ) i l = r 1 + 1 ； ( b ) i k = r r t a x i k 一1 ，n + 1 ( k 2 ) 易证下面的引理 引理2 3 必存在一个最优解使每一个工件乃满足c j t 0 f ) 口 对所考虑的排序，我们可以假定完工时间集为丁且i t ，i 2 ，i 。称为丁的n 个时间间 隔 由于p j = 1 ，令最。= u ir ，+ 1 i k d j n u ike 岛l ( i k t ) 是允许排在第k 个时 问间隔的工件集，我们得到矿= 最。li k 丁) 令i = j l ，j 2 ，j t ，表示按时完工工件集根据引理2 3 ，j j 。的完工时间是i k t 意昧 着j k ( k = 1 ，2 ，t ) 因此，是a + 的一个部分横贯相反地，一+ 的任意一个部分横贯 对应一个按时完工工件集最小化w ( 风j ) 等价于最大化”( n 所以，我们的问题可以转 化为由矿定义的横贯拟阵旧，一中的最大权独立集问题 以我们看来，这就是拟阵中的m w ，问题解决m w l 问题的一种途径就是下面的贪 婪算法【3 ，4 】： 1 。，：= 0 2 。如果e ：= 0 ，则停止 3 0 找一个e 的有最大权的元素e ，令e ：= e e 4 。如果，+ e ，那么：= i + e 返回步骤2 。 定理2 3 问题lr j ，珊= 1 ，p rl 可以用贪婪算法在o ( n 3 ) 时间内解决 证明上述问题已转化为拟阵中的最大权独立集问题，所以算法运行正确 在步骤4 。中，我们需要判断是否+ e f 它可以用偶图最大匹配算法在d ( n 2 ) 时间 内解决上述算法至多需要0 ( n ) 步就结束因此，总的时间界是o ( n 3 ) 口 2 3 一个平行机问题 在本节中，我们考虑问题rp r g 假定有m 个无关平行机m ，慨，尬。和n 个工件以，j 2 ， 如在机器舰上的加 工时间是砘f 现在，我们有m n 个位置可供工件选择我们从每台机器的最后一个工件计数位置，因 此，第k 个位置意味着倒数第k 个位置令( i 、k ) 代表机器尬的第k 个位置和从前一样， 每个工件j j 有一个位置允许集，被表示为岛= ( i ，k ) i 以可以在位置( i ，k ) 上加工) 为了 解决这个排序问题，我们构造一个偶图g = ( u u ；e ) 如下：令v = 口l ，v 2 ，) 对应于n 个工件，令u = 啦k1 兰i m ，l k n ) 对应于m n 个位置，吩和u n 相邻当且仅当 ( i ，k ) 岛边( v i ，u l k ) 的权定义为k p i j ，即工件以排在位置( i ，k ) 对目标函数q 的贡 献图g 的一个匹配是完美的如果它能覆盖y 的所有顶点易证排序问题rp ri 岛 等价于图g 的最小权完美匹配问题，而最小权完美匹配问题可以转化为线性规划中的分配 问题，也即是： 其中 x l k j = 1 ( j = 1 ，2 ，n ) x l k j 1 “= 1 2 ，m ，k = 1 1 2 ，n ) 1eje “ 。埘 o ，1 ) c t q = 竺，p 罢盖，a 女) z 砌= ： 薯盖_ 件以排在位置。，) 于是我们有下面的结果 定理2 2 4 ：问题r p r q 是多项式可解的 幻 z 蜓 m n 鬟 n m n 薹 s 证明我们已把所要考虑的问题转化为上面的分配问题而分配问题可用偶图的最大 权匹配算法在o ( m 札3 ) 时间内解决口 1 3 第三章单机工件运输排序问题1 一d ，k = 2 旧= 1 ，c 一2 ，2 五乃i ( k 一 3 1引言 单机排序和工件运输最小化最大完工时问的问题可描述如下：有n 个工件j ，厶， 它们首先在一台机器上加工，然后被一辆有容量限制的汽车运送给两个顾誊每个必须运 送到顾客的工件出有一个加工时间m 和个尺寸q ，这里勺代表工件如装在汽车中所 占空间的大小仅仅有一辆汽车去运送所有的工件，它有一个容量限制：也就是说，在一 次运输中汽车中装的工件的尺寸的总和不能超过z 在一次运输中的所有工件被称为一个 批令丑( t 。) 是仅包含需要运送到顾客1 ( 顾客2 ) 的批的运输时间，令乃是需要运送到顾 客1 和顾客2 的批的运输时间假定t 3 t 2 孔 设p = 整l p j 是所有工件的加工时间的总和在一个排序一中，我们定义以下一些记 号： q ( 一)工件j j 的完工时间，也就是它到达顾客的时间 k ( c r ) 在排序a 中批的数目 对每个k = 1 ，k ( 口) ， b k ( a )在排序a 中的第k 个批并且先运输的批有更小的下标 p k ( o ) = j ，e b 。( 。) 珊，它表示在批b k ( o - ) 中的所有的工件的加工时间的总和 j k ( a )汽车运送批b k ( a ) 时离开机器的时间 p r ( o - ) 批b k ( a ) 的准备时间，也就是批b ( 中的工件在机器上最后一个完工的工件 的完工时间注意到在任意一个可行排序中6 k ( a ) m ( a ) 在不引起混淆的情况下，我们分别简化b k ( a ) ，r ( a ) ，靠( a ) ，风( d ) 与q ( n ) 为b k ，p k ， 6 k ，p k sc i 问题是寻找一个工件加工和运输的排序使得所有工件被2 n z 并运送给顾客所需要的 时间最小为了便于分析，在排序一中的最大完工时间，被记为c a x ( a ) ，它被定义为汽车 运送最后一个拙到顾客并返回机器的时间在不引起混淆的情况下，我们简化g 一( 一) 为 g n “ 根据g r a h a me ta 1 1 4 与l e e 和c h e n 1 6 】中的记号，在本章中，单机排序和工件运输最 小化最大完工时i e i e 题被记为1 一d ，k = 2 = 1 ，c = z ，2 丑兰t z l c m 这里“1 。d ，k ：2 ， 表示工件首先在一台机器上加工，然后被一辆汽车运送给两个顾客；“”= 1 ，c = z ”表示仅 仅由一辆汽车去运送所有的工件，并且它的容量为z 带有运输考虑的机器排序问题已经成为近十几年来排序论中最重要的，被广泛讨论的 1 4 课题之一a h m a d i 等人【8 1 已经考虑了最小化最大完工时间和最小化完工时间和的两台机 器的流水作业问题( 一台单机与一台随后的批加工机器) h e r r m a n n 和l e e 【1 6 ，y u a n 2 0 ， c h e n 【1 0 】，y a n g 【1 9 和c h e n g 等人 1 2 】已经考虑了与工期相关的指标的几个批排序问题 l e e 和c h e n 1 6 考虑了另一种工件加工和运输的最小化最大完工时间的排序问题，他们只 考虑运输的时间和汽车的容量，而不考虑运输的费用c h a n g 和l e e 【1 1 】又推广了这个问 题，他们考虑工件在汽车中占据不同的空间他们假设工件的加工时间和它们的尺寸是独 立的，证明了这个问题1 一d ，= 2 l ”= l ，c = 纠c k 。是强n p - 困难的同时，他们也提供 了个启发式算法，它的最劣性能比为2 在本章中，在2 乃2 毋限制下，我们给出了一个 最劣性能比为琶的算法 3 2启发式算法 既然工件是以批的形式运输的，每个运输批可等价地认为是一个单独的工件( 称为一个 批工件) ，它需要先在机器上加工然后用汽车运送到顾客对应于一个批工件的加工时间等 于分到此批中所有工件的加工时间之和注意到g k a x ( a ) 被定义为汽车运送最后一个批到 顾客并返回机器的时问在这种意义下，汽车被定义为运送工件的”机器”因此，如果工件 已分成运输批，那么这个问题等价于一个经典的两台机器流水作业问题( 被记为见| | g 。) ： 机器看作机器1 ，汽车看作机器2 ，每个运送到顾客1 ( 2 ，1a n d2 ) 的批在机器2 上可分别看 作具有加工时间n ( 乃，码) 的工件 j o h n s o n ( 1 9 m ) 提出了一个规则，称为j o h n s o n 规则，对问题n | | c 。最小化完工时间 下面考虑问题f 2 l e 令p l ，和是工件乃分别在机器1 和机器2 上的加工时间应用 j o h n s o n 规则得到的最优序可以描述如下：p l y ! p 2 j 的工件按p u 非降的顺序排列；p l j p 卸 的工件，按p 非增的顺序排列 既然1 一d ，k = 1 l = 1 ，c = z ，t = lj c t m 。是强p 一困难的，问题1 一d ，k = 2j 口= 1 ，c = z ，2 乃码j c k 。也是强n p - 困难的下面的具有最劣分析的启发式算法是由【1 0 】给 出的 启发式算法h ： 第1 步：对工件分组：到达顾客1 的工件分成一组，表示为g 1 ，到达顾客2 的工件分成 一组，表示为g 2 每组按照f f d 算法把工件分成批( 后面要解释) 每组的批按照在f f d 算法中的形成顺序进行标号 第2 步：如果g l 和g z 各自的最后一批可以合并成一个可行( 工件尺寸之和不超过= ) ， 就合并它们把合并批中的工件从g l 和g t 中去掉，它们单独形成一批，记为g 3 设获得 的总批数为b h 1 5 第3 步：应用j o h n s o n 规则确定批的顺序根据所得的顺序重新对批进行标号，得到批 b 1 ，_ 9 2 ，8 h “ 第4 步：从批b l 开始，依次把批b t 的工件安排到机器上加工，= 1 ，2 ，b “每个批 里面的工件按任意顺序加工 第5 步：当汽车可用时，把已经完工但没有运输的批装入汽车运送给顾客如果此时有 多个批已经被加工完毕，则先装下标最小的批 令c ”为从启发式算法口中获得的完工时间注意到g 3 中至多有一个批，即i g 3 l 1 如果i g