（运筹学与控制论专业论文）具有相容约束条件的单机平行分批排序问题.pdf

郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽 窃、抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此 产生的一切法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) 多半智 二零零五年四月 摘要 平行分批排序问题是排序问题的重要组成部分。本论文主要考虑的是在工 件具有相容性约束条件下工件如何分批排序而使问题的目标函数达到最小。 这里的目标函数主要是最大完工时间，也略微考虑了完工时间和的情形，而 且完工时间和在这里分批的完工时间和与工件的完工时间和两种情形。工件 的相容性约束的二元关系可以通过一个图来描述，也就是说，我们把工件集 看作是图的顶点集合，而图的边集合是通过工件间的关系来体现：如果两个 工件有相容关系，则就在这两个顶点工件闯连条边这样在相容约束条件下 的分批问题就转化为图的团问题当我们把图限制为不同的特殊图类时，就 对应了不同情况下的排序问题。具体说来，给定n 个工件 ，如，厶，这些 工件间有的工件是可以在一个批中同时加工，而有的则不能在同一个批中加 工。我们把这些工件分别对应与图g 中不同的顶点，如果工件是相容的，则 对应于图g 中对应的顶点闯就可以连边，否则就不连边。通过这一转换，我 们就把工件的相容性约束通过图论中具体的团问题来刻画，从而使解决相容 性约束条件下的排序同题显得更加具体直观。既然相容性约束条件可以用图 类刻画，不同的约束条件对应于不同的图类，那我们就把考虑的模型记为 1 b b a t c h ；g ， 其中，图g 就是代表我们所讨论的工件相容性条件，用一个简单图来表示； 而，是指排序问题的正则目标函数。本论文主要就以下方面的问题进行了研 究： 1 目标函数是最大完工时间情形，即 1 旧一b a t c h ；g l c m a x 在这一部分，当图g 是一般图时，我们给出了排序问题是n p 一困难问题 的证明；并且当把图限定为一些特殊图的情况下，我们试图找出排序问题的 好的算法具体说来，当图g 是一般二部图、完全二部图、完全m 部图、直 径不超过4 的树以及分裂图时，本论文分别给出了排序问题的多项式时间的 算法。具体结论如下： ( 1 ) 排序问题l i p b a t c h ；g l c m a x 的判定闻题是n p - 完全的。 ( 2 ) 当把图g 限定为一般二部图g = ( 墨y ；e ) ，x = p l ，) ，y = q 。一，) 时，其中p i ，( 对所有的 ，j ) 也表示相应工件的加工时间，则对问 题l i p b a t c h ；b i p a r t i t e i c m 。本论文给出了多项式算法，使得在o ( n 3 ) 时间内给 出问题的最优排序。 ( 3 ) 给定完全二部图g = ( x ，y ；e ) ，其中x = p ，p m ，y = q 一，) ，而 缸，毋也分别代表相应的工件的加工时问。不失一般性，我们假定m 茎n 这 种情况下本论文给出了时间界为o ( n l o g n ) 的多项式算法，使得在该时间内给 出排序问题l p b a t c h ；c o m p l e t eb i p a r t i t e l c m 。的最优排序 ( 4 ) 作为完全二部图的推广，我们考虑完全m 部图的情形。给定完全m 部图 g = ( x 一，；e ) ，其中l x i l = m ，曼啦= n 。不妨假定n 1 n 2 n 。 此时，本论文同样给出了时间界为o ( n l o g n ) 的多项式算法，在该时间内，算 法给出排序问题l p b a t c h ；c o m p l e t em p a r t i t e g k 。的最优排序。 ( 5 ) 树明显是一个特殊的二部图，因而我们希望存在比情形( 2 ) 更为有效 的算法这是显而易见的，因为在图树上运行匈牙利算法会有更为简单的计 算。对于直径不超过4 的树而言，本论文另外有一个直观的算法该算法在 线性时间o ( n ) 内给出问题l i p b a t c h ；t r e ew i t hd 4 l 。的最优排序。 ( 6 ) 给定分裂图g = 似e ) ，其中v = s u q ，而s = 扎，p 。) 是一个独立 集，0 = 口h 一，吼) 则是一个团需要说明的是，p l 和也同时分别表示为 工件的加工时间，而且我们不妨假定，p 。p 2 p 。，q 1 啦吼。 此时，本论文给出了一个多项式算法，使得该算法至多在0 ( 舻) 时间内给出 问题l i p h a t c h ；s p l i t9 r a p h l 。的最优排序。 2 目标函数是批的完工时间和情形，即 1 旧一b a t c h ；g i g ( 鼠) 在这一部分本论文讨论了目标函数为批的完工时间和情形，其中g ( 最) 2 表示批的完工时间和。这种情形下论文给出了两个基本结果。 ( 7 ) 排序问题1 i v b a t c h ，功= 1 ；g i r , c ( b ) 的判定问题是n p 一完全的 ( 8 ) 排序问题1 i v b a t c h ，辨= 1 ；b i p a r t i t e l e c ( b i ) 存在o ( n 2 ) 算法。 关键词：分批排序；最大完工时间；工件相容性；近似算法；完工时间和 3 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 h es i n g l em a c h i n ep a r a l l e lb a t c hp r o b l e mw i t hj o be o m p a t i b i l i t yc o n s t r a i n t s g i v e nuj o b s ，j 2 ，厶a n das i n g l em a c h i n et h a tc a l lp r o c e s sa b a t c ho f j o b sa tt h es s a n et i m e t h ej o b sa r ep r o c e s s e di nb a t c h e si fa n do n l yi ft h e s ej o b s s a t i s f yt h er e l a t i o no fc o m p a t i b i l i t y h o w e v e re a c ho ft h o s et h a tc a n n o tb ec o m p a t i b l e h a st os c h e d u l ei nas i n g l eb a t c hr e s p e c t i v e l y n o ww ec o n s t r u c tan e wg r a p hg a sf o l l o w s ： c o n s i d e r t h e j o b s 以，j 2 ， a s t h e v e r t i c e so f t h e g r a p h g ；a n d j o i n t h e j 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 nb 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 t t 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 tb eac h q u ei ng r a p hg t h e r e f o r ew ec a n s t u d yt h i ss c h e d u l i n gp r o b l e mt h r o u g hag r a p hg w h i c hm a y b eae a s i e rw a yt os o l v e t h ep r o b l e m b e f o r ew es t a r tt os t u d yt h es c h e d u l i n gp r o b l e m ，i ti sn e c e s s a r yt od e f i n e t h em o d e lo ft h i sp r o b l e ma n ds o m en o t a t i o n s w ec a l lt h i sm o d e lt h es i n g l em a c h i n e p 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 s ，a n dw e d e n o t e i tb y 1l p b a t c h ；g i ， w h e r e ，i sar e g u l a ro b j e c t i v ef u n c t i o n h e r e i n ，t h i sp a p e rm m n l yc o n s i d e rt h i ss c h e d u l i n gp r o b l e mw i t hm a k e s p a na si t so h - j e c t i v ef u n c t i o n ，a n dw ea l s ot a l kal i t t l ea b o u tt h et o t a lc o m p l e t i o nt i m ea si t so b j e c t i v e f u n c t i o nt h e r e f o r et h i sp a p e rr e p r e s e n t si t sm a i nc o n c l u s i o n sa sf o l l o w s ： w h e nt h eg r a p hgi sag e n e r a lg r a p h w ec a np r o v et h es c h e d u f i n gp r o b l e ml i p b a t c h ；g i c m i sn p h a r db yr e d u c t i o nf r o mt h ec l i q u ec o v e rp r o b l e m ( 1 ) t h ed e c i s i o nv e r s i o no ft h ep r o b l e m1f p b a t c h ；gj ( 麓。i sn p - c o m p l e t e s i n c et h es c h e d u l i n gp r o b l e mll p b a t c h ；g | c k “i sn p h a r d ，w ef i r s tc o n s i d e rg r a p h s w i t hs p e c i a ls t r u c t u r e ( 2 ) w h e nt h eg r a p hi sl i m i t e dt ob eag e n e r a lb i p a r t i t eg r a p hg = ( x ，y ；e ) ，x = p l ，一，p m ) ，y = 口l ，- 一，) ，w h e r e p i ，q j f o ra l l i ，j a r e a l s or e p r e s e n t i n g t h e p r o c e s s i n g t i m eo ft h ec o r r e s p o n d i n gj o b s t h e nw eh a v eap o l y n o m i a la l g o r i t t n n ，w h i c hs o v l e st h e 4 s c h e d u l i n gp r o b l e ml i p b a t c h ；b i p a r t i t e l c 。w i t ht h er u n n i n gt i m e0 ( 护) ( 3 ) g i v e nt h ec o m p l e t eb i p a r t i t eg r a p hg = ( x ，y ；e ) ，w h e r ex = p l ，p m ) ，y = 口l ，一，g n ) ，p i ，毋a l s od e n o t et h ep r o c e s s i n gt i m eo ft h ec o r r e s p o n d i n gj o b sr e s p e c t i v e l y w i t h o u tl o s so fg e n e r a l i t y , w es u p p o s et h a tm u t h e nw eh a v eam o r ee f f e c t i v e a l g o r i t h m ，w h i c hs o l v e st h ep r o b l e m1 恼一b a t c h ；c o m p l e t eb i p a r t i t el c m “c o r r e c t l yw i t h r u n n i n gt i m eo ( n l o g n ) ( 4 ) a sag e n e r a l i z a t i o no ft h ec o m p l e t eb i p a r t i t eg r a p h ，w ec o n s i d e rt h ec o m p l e t e m - p a r t i t eg r a p h g i v e nt h ec o m p l e t em - p a r t i t eg r a p hg = ( x i ，；e ) ，w h e r e j 五j = 啦，垩1 啦；s u p p o s et h a t 珊站2 。a n dt h e nt h i sp a p e rg _ i v e sa p o l y n o m i a la l g o r i t h m ，w h i c hs o l v e st h ep r o b l e m1l p b a t c h ；c o m p l e t em p a r t i t ei c m “ i no ( n l o g n ) t i m e ( 5 ) s u p p o s et h a tt h eg r a p hg i sat r e ew i t hd i a m e t e rn on l o r et h a n4 l e tdb et h e d i a m e t e ro ft r e et t h e nt h i sp a p e rh a sap o l y n o m i a la l g o r i t h mw i t ht h er u n n i n gt i m e o ( ) ，w h i c hs o l v e st h ep r o b l e m1 泌一b a t c h ；t r e ew i t hd 4 f c 二。c o r r e c t l y ( 6 ) s u p p o s e t h e g r a p h g = ( s u q ，e ) b eas p l i tg r a p h ，w h e r e s = p l ，- - ，风) i sa n i n d e p e n d e n ts e t ，q = q i ，- - - ，吼) i sac l i q u e ，a n dp i ，g ji sa l s ot h ep r o c e s s i n gt i m eo ft h e c o r r e s p o n d i n gj o b sr e s p e c t i v e l y t h e nt h i sp a p e rg i v e sap o l y n o m i a la l g o r i t h m ，w h i c h s o l v e st h ep r o b l e ml i p b a t c h ；s p r i tg r a p h l g 。i no ( n 2 ) t i m e w h e nt h i sp a p e rc o n s i d e rt h et o t a lc o m p l e t i o nt i m eo fb a t c h e sa st h eo h j e c t i v er u n e - t i o n ，w eh a v et h ef o l l o w i n gc o n c l u s i o n s ( 7 ) t h ed e c i s i o n v e r s i o no ft h ep r o b l e mli p b a t c h ，p = l ；g ie c ( b | f ) i sn p - c o m p l e t e ( 8 ) t h ep r o b l e ml i p b a t c h ，岛= 1 ；b i p a r t i t e i e ( b ) h a sap o l y n o m i a la l g o r i t h m w i t ht h er u n n i n gt i m e0 ( n 2 ) k e yw o r d s ：b a t c h i n g ；m a k e s p a n ；c o m p a t a b i l i t y ；a p p r o x i m a t i o na l g o r i t h m ；t h e t o t a lc o m p l e t i o nt i m e 5 第一章概论 1 1排序论学科的发展概况 排序是一类重要的组合最优化问题，它广泛地应用于管理科学、计算机 科学和工程技术等很多领域，也是运筹学研究的一个非常活跃的分支排序 论又称为时间表理论，其作为运筹学的分支，作为一门应用学科，有着深刻 的实际背景和广阔的应用背景题为美国国防部与数学科学研究的报告 认为，2 0 世纪9 0 年代以至整个2 1 世纪数学发展的重点，将从连续的对象 转向离散的对象，并且组合最优化将会有很大的发展，因为“在这个领域内 存在着大量急需解决而又极端困难的问题，其中包括如何对各个部件进行分 隔，布线和布局的问题”。这“分隔，布线和布局”就与排序有关。排序的英 文单词是s c h e d u l i n g ，在自动化学科中又称为调度( 英汉自动化词汇疏松 桂等编，科学出版社，1 9 8 5 年4 月第一版第4 8 0 页) 。s c h e d u l i n g 既有“分配 ( a l l o c a t i o n ) ”的作用，是把被加工的对象“工件”分配给提供加工的对象“机 器”以便进行加工；又有“排序”的功能，有被加工的对象“工件”的次序和 提供加工的对象“机器”的次序等两类次序的安排；还有“调度”的效果， 是在于把“机器”和“工件”按时间进行调度。工件”何时就绪，何时安 装，何时开始加工，何时中断加工( p r e e m p t ) ，何时更换“工件”，何时再继续 加工原“工件”，直到何时结束加工；“机器”何时就绪，何时进行加工，何 时空闲( i d l e ) ，何时更换“机器”等等。这些都是按时间进行“分配”、“排 序”和“调度”。单纯的分配问题，单纯的次序安排问题是s e q u e n c i n g 问题 从词义和词性上来分析，把s e q u e n c e ( 次序) 动名词s e q u e n c i n g 可以译成“安排 次序“，即“排序”；而把s c h e d u l e ( 时间表) 的动名词s c h e d u l i n g 可以译成“安 排时间表”。因而，从最优化的角度来讲，安排时间表( s c h e d u l i n g ) 是为完成 若干项任务( 如加工若干个“工件”) ，而把所需要用到的人、财、物等资源 ( 如加工“工件”所需要的“机器”) 按时间进行最优分配、最优排序和最优调 度。s e q u e n c i n g 是一种特殊的s c h e d u l i n g ，是只要确定“工件”的次序就完全 6 确定加工的时间表( s c h e d u l e ) 问题。现在把s e q u e n c i n g 和s c h e d u l i n g 都称为“排 序”，是尊重使用的习惯和方便。我们应该把“排序”理解为具有两种涵义： 狭义的涵义是s e q u e n c i n g ，是安排次序；广义的涵义是s c h e d u l i n g ，是安排时 间表。我们应该视不同的情况理解为不同的涵义在英文文献中有时也使用 p r o c e s s o r ( 处理机) 而不使用m a c h i n e ( 机器) ；使用t a s k ( 任务) 丽不使用j o b ( 工件 ) ，不过明显的趋势是越来越多的文献中使用“机器”和“工件”这两个术 语。排序论中的“机器”和“工件”已经不是机器制造业中的“车床”和“车 床加工的螺丝”，已经从“车床”和“螺丝”等具体事务中抽象出来。“机器 ”和“工件”是一个运作系统的数学模型中的两种元素。“机器”可以是数 控机床、计算机c p u ( 中央处理器) 、医生、机场跑道等， “工件”可以是零 件、计算机终端、病人、降落的飞机等。例如，计算机科学并行计算机的出 现，促进排序论中对多台平行机( p a r a l l e lm a c h i n e ) 的深入研究；反过来，排序 论中的平行机可以应用到具体的计算机科学平行计算机中去，平行机排序的 成果在一定程度上推动并行计算机的发展。 因此，在排序论中，工件是被加工的对象，是要完成的任务；机器是提供 加工的对象，是完成任务的作业资源；安排时间表是在一定的约束条件下对 工件和机器按时将进行分配和安排次序，使某一个或某一些目标达到最优； 排序是安排时间表的简称。 普遍认为1 9 5 4 年j o h n s o n 发表在n a v a lr e s e a r c hl o g i s i t c s 上的论文“o p - t i r n 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 千多 篇，其中包括排序论的专著和教材4 0 余种。这些排序的论文和书籍中绝大 部分是在过去十年中发表的排序论的长足发展，特别是新型排序的成果丰 硕，使排序论已经成为发展最迅速、研究最活跃、成果最丰硕、前景最诱人 的学科领域之一。 早在2 0 世纪6 0 年代中国科学院越民义先生就注意到排序问题的重要性 和在理论上的难度。1 9 6 0 年，他编写国内第一本排序理论讲义。7 0 年代初 他和韩继业一起研究同顺序流水作业( 同序作业) 排序问题他们发表在中 7 国科学上的著名论文开创了中国研究排序论的先河。在他们两位的倡导和 带动下，国内的排序研究有了较大的开展最近越民义先生出版专著 ( 组合 优化导论，精心撰写许多著名的多项式时间可解的排序问题。1 9 9 8 年陈礴 等的论文是迄今为止对排序研究最为完整的综述，介绍5 7 4 篇论文的成果 唐恒永和赵传立教授合著的排序引论已由科学出版社出版。唐国春教授 等著的现代排序论介绍现代排序的十个研究方向，也已出版。 在新型排序的研究发展中，特别值得一提的是分批排序的发展。分批排 序与经典排序的不同在于机器环境的不同，经典排序是假设任何机器在任何 时刻最多只能加工一个工件，但分批排序则不是这样，它可以同时加工若干 个工件。这其实也是对实际生活中提炼的模型，例如在一个烘箱或烤箱中可 以同时烘烤多个面包比较典型的是发生在大规模集成电路的生产中。大规 模集成电路的生产过程可以分为四个阶段：芯片制作、芯片测试、装配和成 品检验为了保证成品合格，检验阶段要把集成电路放在烘箱中试验集成电 路能否能够在一定的温度下经受一定时间的烘烤。一个烘箱可以同时烘烤多 个集成电路一批集成电路的烘烤时间为其中所需时间最长的集成电路的烘 烤时间，并且在烘烤过程中不能移走任何集成电路。由于烘烤时间比检验过 程的其它步骤需要的时间要长的多，所以有效地安排烘烤的次序具有重要意 义。这类机器可以同时加工多个工件的排序问题就是分批排序问题，严格的 讲是平行分批排序问题，以区别序列分批排序问题但是本论文主要涉及平 行分批而没有涉及序列分批，故这里就不对序列分批作具体的介绍。平行分 批排序问题最早出现在半导体生产过程中，后来在许多其它的生产中都得到 应用，因而具有广泛的应用价值和现实意义 具体来讲，设有n 个工件五一1 ，2 ，n ) 要在一台或多台批处理机器 上加工，其就绪时间、加工时间、交货期等的定义与经典排序情况下是相同 的( 符号也是相同，分别为n ，p i ，也等) 。这些工件可以分成若干个批，记为 b t ，b z ，鼠，每一批中可以包含多个工件，可以在机器上同时加工。此时， 如对批鼠，相应有批的就绪时间( 记为r ) ) 和批的加工时间( 记为p ( b ) ) ， 它们分别是这批中所含工件的就绪时间和加工时间的最大者；而同一批中的 8 工件有相同的完工时间。如何对工件进行分批，如何安排各批的次序，是一 定的目标函数值最优，就是平行分批排序问题要解决的问题。 平行分批排序问题可以按照机器容量的大小分为两类：第一类是机器容 量有限的情况；第二类是机器容量无限的情况一般而言，我们默认机器的 容量是有限的，同时可以看到，当机器容量为1 时，平行分批排序问题就是 经典排序问题。因此，我们可以说平行分批排序问题是经典排序问题的推广。 1 2问题的提出 这个问题的模型是原晋江教授在一次讨论班上提出的。我们首先从一个 具体的问题入手，设若一家化工厂生产化学产品，而不同的化学产品，有的 可以置入同一个反应炉中生产，或存放在同一个库房，或可以用同一车辆运 输；而有的化学产品则不能同时生产、存放或运输前一情形称为这些产品 是相容的，后一种情形称为是不相容的，这意味着化学产品之间存在着相容 性约束。这些化学产品的生产、存放或运输必须满足相容性约束条件，否则 就会产生严重的事故或危险。如何在有相容性约束条件下安排这些化学产品 的生产、存放或运输，可以视作是一个分批排序优化问题。原晋江教授指出， 把上面的问题推广开去，就可以发现这个问题在实际生活中具有广阔的应用 价值和广泛的现实意义 我们把上面模型中的化学产品用更一般的术语工件代替，其生产、存放或 运输的工具则用机器表示，这样就把上面的具体问题一般化了。详细的讲， 设有1 1 个工件 ，以， ，其中有的工件之间具有相容性，可以放在同一个 批中加工，面有的工件彼此闾并不具有相容性，它们不能在同一批加工，只 能在不同的批中加工。因而就有这样一个问题：在工件具有相容约束的条件 下，如何对这些工件进行分批，如何对这些批排序，在机器上加工从而使得 这样的分批排序的目标函数值最小? 本论文主要考虑了两个目标函数：最大 完工时间与完工时间和情形 给定一个单处理机，该处理机能够同时加工一批工件，而且这些工件是 9 有相容约束条件的。单处理机把这些工件按照工件的相容性分批加工，从而 这些批就构成了这些工件集的一个划分。首先需要说明两个概念；其一就是 批的加工时间，比如说批b 的加工时间，就是这一批工件中所有工件的最大 的加工时间，用公式表示就是t 岛= m a x p j ：也b ) ，其中班表示工件易的 加工时间，j = 1 ，n ；其二就是最大完工时间，最大完工时间就是最后一 个工件的完工时间在平行分批排序中，也就是最后一批的批的完工时间。 其次，我们在进入正文之前，需要对相容性约束条件做一个具体的刻画。 下面就考虑如何把工件的相容约束关系通过一个图来刻画。首先把工件 集五，五，厶对应于图g 的具有n 个顶点的顶点集；其次来考虑图的顶点 的相邻关系，任两个顶点之间有边相连当且仅当对应的两个工件满足相容约 束条件。显而易见，安排在同一批加工的工件对应在图中就是图g 中的一个 团。这样我们就通过考察图结构来考察工件间的相容约束关系，从而使排序 问题变得简洁直观。 我们不妨称这样的模型为具有相容约束的单机平行分批排序问题。如果 用排序问题的三参数表示，则可以表示为t 1 b b a t c h ；g l f 其中，g 表示工件的相容性约束条件，而，就是问题的目标函数本论文主 要考虑目标函数是最大完工时间情况下排序问题的计算复杂性，证明了这种 情况下排序问题是n p 困难的；并在相容约束条件限定为一般二部图、完全 二部图、完全m 部图、直径不超过4 的树以及分裂图时，给出排序问题的多 项式算法；同时，在考虑目标函数是完工时间和时，本论文对批的完工时间 和情形进行了讨论，得到了一些基本结果 1 0 第二章目标函数为最大完工时间的一些结果 2 1预备知识 在本节我们给出以下几个定义和一个引理t 定义1 我们说判定问题a 是n p 类的，如果存在多项式p ( n ) 和算法”， 使以下论断成立：符号串。是a 的问题为是的实例，当且仅当存在符号串 c ( x ) ( i c ( 圳i p ( 。) 1 ) ，若给”提供一个输入z ，c ( z ) ，则至多p ( x ) 之后，丌给出 答案“是” 定义2 设a ，和a 2 都是判定问题，我们说a 。多项式归结到a 2 ( 记作 a 。“a 。) ，是指对a 。的任意的实例 ，我们可以在多项式时间内构造出 a 。的实例厶，使得，1 有解当且仅当1 2 有解。 定义3 如果所有其他的n p 问题都能多项式归结到a ，且判定问题ae n p ， 则称问题a 为n p - 完全的 如果一个判定问题是n p - 完全的，其相应的最优化问题就称为是n p 一困 难的。 团分解问题 给定图g = e ) 和正整数k l v i ，则问图g 的顶点能否被划分为k k 个不交的子集合k ，k ，磙，使得图g 吲( 1 isk ) 是图g 的一个完全子 图? 引理1 团分解问题是n p 一完全的【4 2 2n p 完全性证明 对于目标函数为最大完工时间的有相容约束的分批排序问题，首先解决 的任务就是问题的计算复杂性如何。既然本文把该排序模型的相容约束性用 一个图的团来表示，则考虑排序模型的计算复杂性时，我们就自然而然地想 起团分解问题由引理1 知道，团分解问题是n p - 完全的。因此，当g 是一 个一般图时，我们考虑的排序问题1 协一b a t c h ；g i 瓯。的计算复杂性证明可以 用此作归结 命题1 问题1 i p b a t c h ，p j = 1 ；g i 。的判定问题是n p 完全的。 证明t 显而易见，该排序问题的判定问题属于n p 类。 用团的分解问题作归结，由引理1 知道，团分解问题是n p ，完全问题。给定 团分解问题的一个实例g = e ) 及正整数k ，我们构造问题1 陋一b a t c h ，胁= 1 ；g i 。的判定问题的一个实例如下：l y ( g ) i 的n 个顶点分别对应n 个具有 单位工时的工件 ，以，j n ，并令门槛值为y = k 。这样一来，排序问题的 判定问题就是；是否存在一个平行分批排序”，使得瓯。以给定的门槛值为 上界，即。y ? 首先如果团分解问题有解，即存在一个整数k k ，使得图g 的顶点集 v ( g ) 被划分为k 个不交的子集合，k ，而且每个子集的导出子图g m l ， 1 墨i ，是图g 的完全子图，则在排序问题中我们将团k 视作一个批，即 有个批鼠，口2 ，鼠，而且批序列”= ( b 。，b 一，巩) 是一个可行排序。很 明显，有c k 。= y 成立，因此排序问题有解。 反之，假定该排序问题的实例有解，即有一个可行排序”，使得。sy ； k 。不妨设”= ( b ，b 。，鼠) ，则我们有。= 女y = k 。将。看作对应 于批鼠中工件的顶点集，g i ；】是图g 的完全子图，则划分，v 毫，v 文 就是团分解问题的一个解因而命题得证。口 2 3一般二部图的情形 既然问题l i p b a t c h ；q 。是n p 困难的，下一步的研究就是或者给出问 题的近似算法或者把相容性约束限定为具有特殊结构的图时，给出排序问题 的多项式算法。本论文在第二方面做出了尝试，给出了一些结果。 当限定图g 为一个一般二部图时，我们可以给出问题1 i p b a t c h ；6 p a t i t e i 。 的一个多项式时间的算法这个算法的基本思想就是：既然二部图中的一个 团至多包含两个顶点，而且恰好可以看作匹配的两个顶点，而这两个顶点也 1 2 就是两个相容的工件，他们可以放在同一个批中加工。因此排序问题的批序 列就是图g 中的匹配顶点工件和一些独立点工件。 给定二部图g = ( x ，y ；e ) ，其中x = p - ，p m ) ，y = q - ，) ，同时 鼽，如对所有的i ，j 也表示相应工件的加工时间，则在一般二部图条件下的 排序问题l l p b a t c h ；b i p a r t i t e l c 。有如下的多项式时间算法： 算法1 1 赋权：对任意的边慨，q j ) e ( g ) ，令= m i n p ，q j ) ； 2 对赋权图g 执行最大加权匹配算法( h u n g a r i a nm e t h o d 3 j ) ，贝h 得到一个 最优匹配m ； 3 最优匹配m + 中的每一对配对顶点工件安排在同一批中加工；其余未匹 配的工件y ( g ) w ( m + ) 分别单独成批加工。 命题2 算法1 可在o ( n s ) 时间内给出问题1 i p b a t c h ；b i p a t i t e l c m 。的最优 排序。 证明：显而易见，该算法第二步中匈牙利方法的执行确定了整个算法的 时间界，而其他的步骤都不超过这个时间界。 如果图g 中的某两个顶点能被一个匹配边饱和，这说明对应于排序问题 中这两个工件是相容的，因而这两个工件可以在同一批中加工；反之亦是， 而那些未能被图g 的某个匹配m 饱和的顶点工件只能分别在一个单独的批 中加工。对二部图的任一个匹配m 所表示的分批排序方案，我们有t 。=鼽+ q i + m a x p i ，啦) 讵v ( g ) y ( m )i c y ( e ) 妒( m ) ( i d ) e m mn = a + 毋一嘣n 协，如) 社l j = l ( i ，j ) e m mn = 鼽+ 劬一a ( m ) t = t i = t 因此，使。达到最小就等价于使c ( m ) 最大。而在算法1 中第二步刚好保 证c ( m ) 达到最大值c ( m + ) 。所以，该算法得到一个最优排序口 为了更好的理解这个算法，我f j 来看一个例子给定二部图g = ( x ，一e ) 1 3 以及相容性约束如下图示，其中x = p l p z ，p a ，p 4 ) ，y = q t ，q 2 ，q 3 ，q 4 ，而且工 件的加工时间分别为：p l = 3 ，p 2 = 6 ，p 3 = 4 ，1 0 4 = 2 ；q l = 8 ，q 2 = 7 ，啦= 2 ，q 4 = 5 。 则对该排序问题算法的实施如下： 1 对图中的各边赋权如下：c l ，q 。) = 3 ，c ( p - ，q 2 ) = 3 ， c 慨，q 1 ) = 6 ，c ( p 2 ，q 2 ) = 6 ，c ( p 2 ，q 3 ) = 2 ，c ( p a ，啦) = 4 ， c ( p 3 ，9 4 ) = 4 ，c 慨，9 1 ) = 2 ，c 慨，) = 2 ，c 慨，q 4 ) = 2 ； 2 对赋权后的图执行匈牙利算法，得到的最大加权匹配m 4 3 由最大匹配m 得到最优分批如下：b 。= p ，q 1 ) ， b 3 = p 3 ，口4 ) ，鼠= 锄，q 3 。 2 4完全二部图的情形 c ( p 1 ，q 4 ) = 3 ， c 慨，q 3 ) = 2 ， = p i 窖1 ，见g ? ，p 3 q 4 ，风啦) ； 岛= n ，啦) ， 完全二部图是特殊的= 部图，我们在这里考虑这种情形，只是因为当图 g 是一个完全二部图时，我们有比算法1 更为有效的算法。先来看下面的命 题； 命题3 若两个序列满足 p 1 p 2 ，2 肌，口l 日2 芝 1 4 则我们有如下结论： m a x p ，岱) m a x p i ，g 丌( 。) ) i = 1i = 1 其中n 是 1 ，2 ，” 的任意一个排列。 证明 设7 r 是 1 ，2 ，n ) 的一个排列，满足条件p ；岛和( ，) q , k j ) ， 则我们断言 事实上 m a x a ，o ) ) + m a x p ，q - ( 0 ) m a x 鼽，o ) ) + m a x p i ，蚰u ) ) m a x p i ，q n u ) + m a x p j ，g 。“) ) = o ) + ( ；) ，若鼽茎( j ) ，功q - ( 0 口丌o ) + 功，若骱( ；) s p i p l 如o ) a + p j ， 若骱( ：) p i ，针( j ) a 1 t i a x 鼽，妇( ：) + m a x p ，钉) 设“7 是 1 ，2 ，n ) 的另外个排列，满足”咏) = ”( j ) ，n 协) = ”( t ) 和“ ) = ”( ) ，其中k i ，j 。则我们有 nn m & x 协，( i ) ) m a x p i ，口丌( t ) ) i 尘l i = 1 如果还存在其他的( ，j ) ，使得p l2 功和一g ) 口。，o ) ，我们可以继续做相同 的交换，直到没有为止，此时即得结论。口 有了上面的命题做保证，我们就可以给出完全二部图条件下的平行分批 排序闯题的算法。 给定完全二部图g = ( x ，y ；e ) ，其中x = p ，m ) ，y = g l q ，) ，而 且p l ，劬也分别代表相应工件的加工时间。不失一般性，我们假定msn 算法2 1 封目芋( s o r t i n g ) p 1 p 2 p m ， q l 口2 兰，； 2 工件p l 和g ( 江1 ，m ) 安排在同一批中加工，而其余每个工件劬 1 r f m j n ) 单独成批加工 命题4算法2 在0 l o g n ) 时间内给出问题l l p 一如e ( m x p f e t e 坼t t t e i g 。 的最优排序。 证明t 由于算法第一步要求对两个长度至多为n 的序列按l p t 排定顺序， 因此我们就得到了算法的运行时间界。 若增加n m 个具有零加工时间的新顶点到顶点集x ，而且每个新顶点 都与顶点工件集y 中的所有顶点都连一条边，于是就得到一个新的完全二部 图由命题3 知，算法给出问题最优的排序，命题得证。口 2 5完全i t i 部图的情形 作为完全二部图的推广，我们考虑完全m 部图的情形。 给定完全m 部图g = ( x v 一，；e ) ，其中l 墨l = m ，銎l 啦= n 。不妨假 定n ，砌n 。并设玛= 纠，凼，壤) ，其中戎同时表示工件的加 工时间。 算法3 1 排序p p 2 p 妒瑚，j = 1 ，2 ，一，m ； 2 具有相同下标的工件安排在同一个批中加工，其他的工件则分别单独 成批。 命题5算法3 在o ( n l o g n ) 时间内给出问题1 恼一b a t c h ；c o m p l e t em p a r t i t e 。的最优排序。 要证明命题5 的正确性，我只需证明下面命题的正确性事实上，我们 仅需通过增加珏，一啦个具有零加工时间的新顶点到工件集五，江2 ，m ， 而且弼中的任一个新工件都与其他的墨中的所有工件连边，包括其中加入 恐中的新工件。这样就得到一个新的完全m 部图而且每一部分都有n 。个顶 点此时命题5 就转化为下面命题6 的情形，而且，这种转换不会影响算法 和命题的正确性。 1 6 命题6假设 p # 毋p g o = 1 ，2 ，m ) ，则 m a x 西”，p ；2 ，妒) m 一 端妒龆) j = l j = l 其中每个几0 = l ，m ) 都是( 1 ，2 ，n 的任一个排列。 证明用归纳法证明，对m 作归纳。 当m = 2 时，由命题3 知，此命题正确 当m = 一1 时，假定命题正确，则我们考虑m = 女时的情形，即考虑完 全部图的情况。由归纳假设知，当m = 一l 时，我们有 姜m a x p ；”，谬叫