（运筹学与控制论专业论文）具有同时性约束的平行机排序问题.pdf

摘要 排序理论是组合最优化学科中一个蓬勃发展的研究方向。平行机排序是其 中一个重要组成部分。在经典的平行机排序文献中，人们往往研究工件间的序 约束。这种序约束是用一个有向图d 描述的先后顺序关系，即一个工件必须 在它的先行工件完工后才能开始加工。本论文研究工件间的另一种相互关系一 一同时性关系，即一个工件必须与享有同一资源的其他工件同时加工。这种同 时性约束用一个无向图g 来描述。例如对城市间的通道进行检疫消毒时，图 g 的顶点表示城市，边表示城市间的通道；每条边都有一个检疫任务，即一个 工件。若干个平行作业的医疗队用m 台平行机表示。为对疫情的传播进行严 格封锁，同一城市引出的通道必须由相应的医疗队同时进行防疫处理。这就是 说，关联于图g 的一个顶点的边工件必须同时加工。又如在对一个通讯网络进 行检测时，从一个节点( 交换台站) 发出检测信号，在其引出的所有线路中， 检测人员必须同时进行操作。在其它系统中，当一些任务要共享一些资源( 信 息资源或物资资源) 时，都有这种同时性约束。这样一来，我们得到有同时性 约束的平行机排序问题如下：给定”t 台平行机及一个无向图g ，其中g 的边 代表工件( 称为“边工件”) ；若一个边工件c = t t ”安排在时刻t 开始加工，则 关联于“( 或”) 的全部未加工的边工件必须也在时刻开始加工。至于目标函 数，仍与通常的平行机排序一样，如最大完工时间g 一或完工时间和g 等 等。按照传统的三参数分类记号，此问题记为p m l g s m t l ，其中s m 丁为 同时性( s i m “n e 。匆) 的简写，g 表示工件间邻接关系的图，_ 厂为正则的目 标函数，如c k 。及g 等等。这将称为“一般模型”。在这个模型中，同一个 时刻可以有多于一个顶点关联的边工件同时被加工( 只要机器数足够多) 。但 是，有些实际问题提出更苛刻的要求：任何时刻只有一个顶点关联的边工件可 以被同时加工，也就是被处理的顶点呈一个序列形式，所以我们称之为“序列 模型”。 无论一般模型或序列模型，同时性约束的特点是：工件的安排受到机器数 m 及图g 的顶点度的双重限制，所以此类问题的一般形式是困难的。本论文 将从算法的观点研究此类问题，包括三个方面：计算复杂性，多项式时间算法 及近似算法。具体的说，本论文的主要结果如下： 1 p 一完全性证明。对序列模型及一般模型，证明p m 慨= 1 ，g s m t l c 。 及尸m 协= 1 ：g s f r i q 的判定形式是p 一完全问题。 2 对l 功= 1 ，g s m 丁i 。给出( 2 一击) 一近似算法。 3 对特殊图g 给出p m b = l ，g s 丁l c 。( 或q ) 的多项式时间算 法，如g 为树、单圈图、完全偶图、完全k 部图、平面格子图等。 关键词：平行机排序；同时性约束；最大完工时间；p 一完全；近似算 法；多项式时间算法 a b s t r a c t s c h e d u l i n gi 8a 舳u r i 8 h i n gd i r e c t i o no fc o m b i n 如o r i a lo p t i m i z a t 油p a r a l l e lm a c h i n e s c h e d u l ei 8a ni m p o r t a n tc o m p o n e n to fi ti n1 i t e r a t u r e 8o fc l a 船i c a lp a r a l l e lm a c h i n e s c l l e d u l i n 岛p e 叩1 eo f t e n8 t u d yt h ep r e c e d e n c ec o n s t r a i n ta m o n gj o b s t h i 8p r e c e d e n c e c o n 8 t r a i n ti 8d e s c r i b e db yad 培r a p hd ，t h a ti st os a 弘w ec 蛐o t8 c h e d u l eaj o bu n t i l a l li t 8p r 耐e c e 8 b o r 8a r e8 c h e d u l e d i nt h bp a p e r ，w ec o n s i d e ra n o t h e rr e l a 乞i o na m o n g j o b 8 一s i i m 山a n e i t yc o n 8 t r a i n t i tm e a n st h “t h ej o b ss h a r i n gc o m m o nr e 8 0 u r c e 8m u 8 t 8 t a r tp r o c e 8 s i n ga tt h e8 a m et i m e t h er e l a t i o nc a nb ed e 8 c r i b e db rag r a p hg f b r e x a m p l e ，w h e nw eq u 缸a n t i ea n dd i s i n f e c tt h er o a d sb e t 、代e nc i t i 镐，t h ev e r t i c e 8o fg d e n o t ec i t i c e sa n dt h ee d g e 吕d e n er o a d 8 e v e r ye d g eh a 8aq u 缸a n t i i l et a s k 一一aj o b s e v e r m m e d i c a ig r o u p s 盯er e p r e 8 e n t e db ymp a r 出l e lm h i n s f 0 rw em u s tb l o c kt h es p r e 8 do f e p i d e m i c8 t r i c t l 弘t h er o a d sl e a m n gf r o n lac o m m o nc i t ym u s tb ep r e v e n t e db ym e d i c a l g r o u p 8s i m u l t a n e o u s l 矿 t h a ti st os a y ，t h ee d g ej o b si n c i d e n tw i t hav e r t e xi ngn l u s t 8 t a r tp r o c 髓8 i n g8 i i m l l t a n e o u s l y f o ra n o t h e re x a 瑚p l e ，w h e nw ee x a m i n eac o m t m 】n i c a t i o n n e t w o r k ，w es e n ds i n g a lf r o man o d ea n dt e 8 t i n gm u s tb ec a r r i e do u ts i m u l t a n e o u s l yo na u 1 i n e sl e a d i n gf r o mt h i sn o d et h e r ei st h e8 i m t l l t a i l e i t yc o n s t r a i n ti no t h e rs y s t e m 8w h e n s o m et a s k s8 h a r eac o m m o nr e s o u r c et h e n ，eg e tap a r a l l e lm a c h i n es 曲e d u l ep r o b l e m w i t hs i i m l t a n e i t yc o n s t r 出1 1 ta sf o u o w 8 ：g i v e nm p a r a l l e lm a c h m e 8a n dag r a p hg ，t h e e d g e so fgr e p r e s e n tj o b s ；i fa ne d g ej o be = u vs t a r t sa tt i m et ，t h e na ut h eu n 8 c h e d u l e d e d g ej o b si n c i d e n tw i t hu ( 0 rv ) n l u s ts t a r ta tt i i n et t h eo b j e c t i v ef u n c t i o ni st h es a m ea s u s u a l ，s u c l la 吕m a k e s p a n ( k 口zo r 0a n ds oo n a c c o r d i n gt ot h ct r a d i l ：i o n a it h r e e 一矗p l d c l a s 8 i 矗c a t i o i l ，t l l l sp i o b l e l ui 8d e i l o t e db y 。f g s a ，t 1 ，w h e r es m ti st h ea b b r e v i a t i o n o fs i m u l t a n e i t ya n dg r a p hgr e p r e s e n t st h ei n c i d e n c er e l a t i o n sa m o n gj o b s ，a _ i l d ，i 8a r e g u l a r 胁c t i o n ，8 u c ha sq 。8 。o r q t h i si sc a l l e d“g e n e r a lm o d e l ” i nt h i sm o d e l ， j t i sa l l o w e dt os c h e d u l ee d g ej o b si n c i d e n tw i t hm o r et h a l lo n ev e r t e x 乱池es a m et i n l e ( i f t h e r ea r ee n o u g hm a c h l n e 8 ) b u t 主np r a c t l c a l 由t u a t l o nt h e r em a yb em o r er i g o r o u sr e q u s t ： a ta n yt i m et h es c h e d u l e de d g ej o b 8h l u s t b ei n c i d e n tw i t ho n l yo n ev e r t e x t h a ti 8t os a m 1 1 l w es e l e c tv e r t e xi nas e r i e s ，s ow ec a ui t “s e r i e sm o ( k l ” r e g a r d l e s so f“g e n e r a lm o d d ” o r “8 e r i e 8m o d e l ”，此ef e a 土u r eo fs i m u l t a n e i t v c o n s t r a i n ti st h a tt h ea r r a n g e m e n to fj o b si sc 0 曲n e db yt h en u n l b e ro fm a c h i n 8 n la n d t h ev e r 七e xd e g r e eo fg r a p hg s ot h eg e n e r a lf o r mo ft h i 8p r o b k mi sh a r d i nt h i sp a p e r ， w e8 t 1 1 d yt h i sp r o b l e mf r o mt h ea l g o r i t h m i cp o i n to fv i e w ，w h i c hi n c l u d e st h r e ea s d e c t s ： c o m p l e x i t y ，p 0 1 y n o m i a la l g o r i t l l i na n da p p r 0 碰m a t i o na k o r i t h m s p e c m c a l l mw ep r e s e n t t h em a i nr e 8 u l t sa sf o l l o w 8 ： 1 t h ep r o o fo fn p h 盯d n e s s 1 1 0 “g e n e r a l 瑚o d e l “ a n d“s e r i e 8m o d e l ”w e p r o v et h a tp m i 功= 1 ，g s m r i g m 础a i l d 尸m 妨= 1 ，g s m 丁l qa r en p h a r d 2 w bg i v ea ( 2 一击) 一a p p r o ) d m a t i o na l g o r i t h mf o r l p j = 1 ，g s 彳丁l ( ：_ m 。 3 ，w h e gi sat r e e ，u n i c y l i cg r 印h ，c o m p l e t eg r a p h ，c o m p l e t eb i p 舡t i t eg r 印h ，c o m _ p l e t ek _ p a r t i t eg r a p h ，o rp l a n e 擎i dg r a p h ，t h e r ei sap o l y n o m i a la l g o r i t h mf o r 只。| p f = l ，g s f 7 1 f ( 。a j l d ，m f 聊= l ，g s 7 1 f ( 0 k e yw b r d s ：p a r a u e lm a c h i n es c h e d u l i n g ；8 i 皿【u l t a n e i t yc o n s t r a i n t tn l a k e s p a n ；n p c o m p l e t e n e 8 s ；a p p r o ) c i m a t i o na 培o r i t h m ；p 0 1 y n o m i a l 出g o r i t h m 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者：j 爿啉 2 0 0 6 年4 月2 6 日 第一章概述 1 1引言 排序论又称为时间表理论，其作为运筹学的一个分支，作为一门应用科 学，有着深刻的实际背景和广阔的应用前景。1 9 5 4 年，j o 概s m 完成了论文 “d p i m z t u o 一n d r e e s c w ep r 。d u c i o ns c e d “z e st 口 s e “p “m e s 竹d u d e d ”， 人们普遍认为这是第一篇关于排序问题研究的论文。排序问题产生的背景主要 是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从 普通的生产部门的计划安排、人员调度、学校课程表的制定，到宇宙飞船的复 杂庞大的飞行计划，都要用到排序的理论和算法。 排序问题是一类重要的组合优化问题，它是利用一些处理机、机器或资 源，最优地完成一批给定的任务或作业。在执行这些任务或作业时需要满足某 些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对 加工时间的影响等。最优地完成指的是使目标函数达到最小，而且目标函数通 常是对加工时间的长短、处理机的利用率的描述。 如果数学分为理论数学和应用数学，那么排序论可以分为排序的理论部分 和应用部分。排序的理论部分又可分为经典排序( r j f n m fs c 7 m f t z f i r 哪) 和现代排 序( 盯z o d e r ns c e d “托n 9 ) 。曰r c 七e ，1 和他“s t 毛e “( 了o l p 把z z yr e s u f so ，s c e d f z n g p r 。讹m s ”中使用c f n c “和e 耐e n d e d 两个词来区别经典和非经典两种排序问 题。他们也用m wc f 。s so ，s c k d “9p r 曲f s ( 新型排序) 来表示非经典的排序 问题新型排序相对经典排序而言，其特点是突破经典排序的基本假设。根据 1 9 9 3 年e 工l n 训f e r ，k l e 扎s t r n ，ah gr i 礼忆d d 剪n n 礼和d 口s m o 掣s 等的观 点，经典排序有4 个基本假设。 ( 1 ) 资源的类型。机器是加工工件所需要的一种资源。经典排序假设，一台 机器在任何时刻最多只能加工一个工件；同时还假设，一个工件在任何时刻至 多在一台机器上加工。 ( 2 ) 确定性。经典排序假设决定排序问题的一个实例的所有输入参数都是 事先知道的和完全确定的。 1 ( 3 ) 可运算性。经典排序是在可以运算，可以计算的程度上研究排序问题， 而不去顾及诸如如何确定工件的交货期，如何购置机器和配备设备等技术上可 能发生的问题。 ( 4 ) 单目标和正则性。经典排序假定排序的目的是使衡量排法好坏的一个一 维目标函数的函数值为最小。而且这个目标函数是工件完工时间的非降函数。 这就是所谓正则目标。 唐国春、张峰等编著了现代排序论，书中介绍了新型排序论的十个 研究方向。 对一个排序问题来说，找到一个有效的算法，得到一个最优解是十分必要 的。口0 6 n m ( 1 9 6 4 ) 和e d m o n 如( 1 9 6 5 ) 建议，一个好的有效的算法应该是一个多 项式时间算法。也就是说，存在一个整数k ，使得算法在o ( n “) 时间内完成。 对所有有多项式时间算法的问题，我们称它为j p 问题。对于那些没能找出多 项式时间算法的问题，我们转而研究它的，v f ) 一困难性；一旦证明了一个问题 是p 一困难的，我们就可以设计近似算法去逼近最优解。 平行机排序问题是排序问题的一个重要组成部分。我们知道，机器可以分为 两大类：通用平行( p n r “f e f ) 机和专用串联( d e d c o 把d ) 机。对于不允许中断加工的 情况来讲，一个工件在m 台平行机上的加工是只需要在这m 台机器中的任何一 台机器上加工一次。平行机又可分为3 类：具有相同加工速度的同型( 埘m i c 叫) 机，具有不同的加工速度但此速度不依赖工件的同类( “n i ，o r m ) 机和随加工的 工件不同加工速度也不同的非同类型( “n r “m d ) 机。在本论文中我们考虑的是 同型机。同型机的排序问题在已有的文献中得到了广泛而深入的研究。一般的 同型机排序问题的模型是这样的：给定一个工件集j = p ，m ，m ) ，每个工 件都有一个加工时间，它们必须在m 台同型机上加工，我们用它们的加工时间 来区分工件，工件和机器都在。时刻到达，不允许抢先。目标函数是最小化时 间表长。这个p 一完备问题 1 ，被记作刚( k 。，在实际中应用很广泛 2 。 在经典的平行机排序文献中，关于工件的约束，如到达时间、交货期、截 止时间等都是对单个工件而言的；至于工件之间的约束关系，人们只研究先后 顺序关系，即序约束( p r e c e d e n c ec o n s c r a i n t s ) 。具体的说，给定一个无圈有向图 d 描述的偏序关系，其中g 的每一个顶点对应于一个工件，工件间的先后顺序 限制用d 的有向弧表示。所谓序约束就是：每一个工件必须在其先行工件都 完工之后才能开始加工。这种序约束体现了时间上的纵向关系一先后顺序。 本论文提出研究工件之间的另一种相互关系，即时间上的横向关系一同时性 约束。在一些运作系统中，某些工件共享着一个信息的或物质的资源，它们必 须同时开始加工。例如，若干通道连接着同一个传染源，若干条线路从同一个 交换台引出，或者若干台处理机在等候着同一个信息指令，如此等等，那么相 应的操作任务便应该同时启动。就本来的意义上说，平行机排序就有两方面的 特点；既有时间的纵向关系一工件的顺序性( 序列性) ，也有时间的横向关系 一机器的并行性( 同时性) 。因此，本文的宗旨是研究平行机排序中的这种横 向的、并行的同时性约束。 1 2问题的提出 首先我们来看几个实际例子。我们知道，一直以来，大范围的传染性疾病 都是困扰各个国家的一个难题。像前年的s j 4 r s 和现在的禽流感，国家采取了 一系列措施才控制住疫情。由于传染性疾病的特殊性，尽快的检查以便掌握信 息是至关重要的，并且在检查时不能留后患，因为我们只有先切断疫情传播的 通道才能集中力量消灭它，所谓后患是指如果我们只对某个城市的一部分通道 进行检查，即使当时已经把城市中的疫情消灭掉了，也不能保证疫情不会从剩 余的未检查的通道传入，导致更大面积的感染和更严重的人员伤亡。因此说在 医疗组够用的前提下，我们要求当选中某些城市时，它们发出的道路必须同时 开始检查和消毒。我们称这个要求为同时性约束( s z m u 舶n e 坷c o n s 打删州) 。问题 是如何安排通道的检疫顺序，在满足同时性约束之下，使得最后完工时间( 或 完工时间和) 为最小。 在一个通讯网络中，节点表示交换台站，边表示通讯线路。现要对所有线 路进行检测。检测时从选定的节点发出一个信号，检测人员便在从这个节点引 出的所有线路上同时进行接收试验，确定线路的质量。假定有”t 个检测人员， 则从这个节点引出的边数不能超过m ，才能进行并行操作。问题是如何安排 所有线路的检测时间，在同时性约束下，使得最后完工时间为最小。 在疏通一个管道系统时，首先选定一个交叉点进行加压，同时疏通由它引 出的所有管道；然后再选定另一个交叉点，重复这样的操作。在地下坑道的搜 救活动中也有类似情形。 综合以上实际应用例子，可以得到有同时性约束的平行机排序问题：给定 m 台平行机及一个无向图g ，其中g 的边代表工件( 称为“边工件”) ；若一个 边工件e = u ”安排在时刻开始加工，则关联于”( 或”) 的全部未加工的边工件 也必须从时刻开始加工。这称为同时性约束。问题是求所有边工件安排在”。 台平行机上的加工方式，在同时性约束下，使得最大加工时间c 。或完工时间 和g 为最小。按照传统的三参数分类记号，此问题记为焉g s m 7 i c k 。或 4 q ，其中s m 丁为同时性( s i t f 一e z ) 的缩写，这将被称为“一般模型”。注 意在此模型中，同一个时刻可以有多于一个顶点关联的边工件同时被加工。但 是，在某些实际问题中，可能要求任何时刻只有一个顶点关联的边工件可以被 同时加工，这祥一来，被处理的顶点形成一个序列形式，所以我们称这种特殊 情形为“序列模型”，并记为p m l g s m 丁( s e r l e s ) 1 c m n 。或q 。 下面是这个问题的三参数法描述及相关说明：p m f g s m t f ， g ：一个连通无向图( 允许为多重图) ，f ( g ) 是工件集； 肼：工件的加工时间； m ：平行机数目m 三d ( g ) ，d ( g ) 为图g 的最小度； s m r ；同时性约束； ，：目标函数，包括最大完工时间c k 。和完工时间和g 等。 事实上，虽然我们定义的工件是边，但我们的排序过程就是一个选点的过 程，根据选点的要求不同，在下面的章节里我们主要讨论了两种排序模型： 序列模型：这是一个比较特殊的模型。在同时性约束以外，还要求任两个 顶点的关联边在加工时不重叠，即任何一个时刻只允许至多有一个顶点的未加 工工件加工，我们主要研究g 为简单图的情形。 一般模型：我们总是假设问题有解，即不会出现医疗组实在太少根本无从 下手的情形。在这个模型中，可以在满足同时性约束的情况下，同时检查多个 顶点关联的边工件。 1 3预备知识 首先我们把图论的相关概念简要介绍一下。 一个图由一些点以及连接它们当中某些点对的边所组成，我们用g = ( y ( g ) ， e ( g ) ，妒。) 这个三元组来表示一个图，其中y ( g ) 是g 的顶点集，e ( g ) 是g 的 边集，抛表示的是g 中点之间的关联关系。我们说一个顶点”的度是指g 中 ”所关联的边数，记作如( ”) 。我们记g 一”为由y ( g ) ”) 导出的子图，我们说 顶点子集k y ( g ) 是g 的点覆盖是指对任e e ( g ) ，e 至少有一个端点在 中。最小覆盖指的就是点数最少的点覆盖。图g 中顶点的最大度记为( g ) ，顶 点的最小度记为6 ( g ) 。本文有一个假设就是m 6 ( g ) ，否则在满足同时性约 束的条件下，没有可以加工的工件，也即问题无解，所以我们只讨论”。d ( g ) 的情形。在文中我们除了对一般图进行研究外，还对一系列的特殊图类给出了 多项式时间算法。 其次我们把计算复杂性的相关概念简要介绍一下。 尸问题：我们称具有多项式时间算法的问题为尸问题。也就是说，存在 一个参数，使得算法在o ( 舻) 时间内完成。 v ，) 问题：我们说判定问题a 是p 问题，如果_ 的任一个肯定实例， 都存在一个简明的判据，使之可以在多项式时间检验。 多项式时间归结：设p 。与p 。是两个判定问题，如果对任意给定的p ，的 实例，。，我们都能在多项式时间内构造p 。的实例如，使得 是p ，的“是” 实例当且仅当如是p ：的一个“是”实例，则我们称p ，能多项式时间内归结 为p 2 。 p 7 一d 问题：如果所有其他的j 问题都能多项式归结到以，则称问 题以为p 一 n r d 问题。若以p ，则称a 为p 一完全的。 强p 一 n 州问题：如果一个问题在一元输入下是p 一 n 砌的，则我们 称它为强p 一 n 砌问题。 对于一个排序问题来说，一般主要从三个方面进行研究： ( 1 ) 寻找多项式时间算法； 6 ( 2 ) 证明排序问题是p f d 或强，一胁4 ； ( 3 ) 对于p 一 o 州问题，一方面考虑特殊情形下的多项式可解性，另一方 面寻找一个近似算法或者一个拟多项式时间算法。 女一因子近似算法：设p 是一个具有非负权的排序问题，1 。如果p 的一个多项式时间算法a ，对p 的每个实例，都有a ( ，) 曼d p t ( ，) ，则我们 称多项式时间算法a 是排序问题p 的一个一因子近似算法。 算法a 的最差性能比：最差性能比是判定算法好坏的一个通用标准。一 个 一因子近似算法有性能比女，我们把使得a ( ，) d p 丁( ，) 成立的最小的女 叫做a 的最差性能比。 1 4本论文的主要结果 本论文主要从以下几个方面研究此类问题： 1 p 一完全性证明。对序列模型及一般模型，我们分别用点覆盖问题和 3 一划分问题作归结，证明了p m 协= 1 ，g s 丁i 。及尸m 切= 1 ，g s m t i q 的判定形式是p 完全的。 2 近似算法：对p m 蹄= l ，g s m 丁i g 。给出一个2 一近似和( 2 一去) 一近似 算法。 3 多项式时间算法：对序列模型我们给出了直径不超过5 的树的多项式时 间算法；在一般模型中，对特殊图g 给出p m 切= 1 ，g s m t i g ( 或g ) 的多项式时间算法，其中g 为树、单圈图时时间界为o ( n 2 叼n ) ，当g 为完全 偶图、完全 部图、平面格子图时时间界为d ( n ) 。 第二章具有同时性约束的平行机排序的序列模型 2 1p 一完全性证明 本节我们给出序列模型的两个p 一 的点覆盖问题来归结的。 点覆盖问题：给定图g 和正整数 ? 完全性证明，都是用已知是，一完全 问是否存在g 的一个点覆盖使得 引理1 ：排序问题p m l 乃= 1 ，g s m 丁( e s ) 1 。的判定形式是p 一完全 的。 证明：显然该判定问题属于p 类。 给定点覆盖问题的一个实例图g 和正整数k ，我们构造排序问题的一个 实例如下：e ( g ) 的n 条边对应于n 个具有单位工时的工件 ，也，。厶。令 y = k m = ( g ) ，排序问题的判定问题是：是否存在一个排序n ，使得 g 。s ，? 首先，如果点覆盖问题有解，即存在一个整数女 1 ，由序列模型的要求知，是唯一的；若 i 鼠 = 1 ，则任取一个端点即可) 。显然。，。，。就是g 的一个k 点覆盖 满足 ! ，。 上述归结明显是多项式时间的，因此排序问题p m 慨= 1 ，g s m t ，( s e 州e s ) i c k 。 的判定问题是p 一完全的。 口 引理2 ：排序问题焉i p = 1 ，g s m r ( s e s ) l ，的判定形式是p 一完 全的，其中b 表示在_ ，i + 1 1 时间段内加工的工件集，可看作第i 批，g 最就 表示第f 批的完工时间。 8 证明：显然该判定问题属于j 尸类。 给定点覆盖问题的一个实例图g 和正整数k ，我们构造排序问题的一个 实例如下：e ( g ) 的n 条边对应于n 个具有单位工时的工件以，如，厶，令 y = ；k ( + 1 ) ，m = ( g ) ，排序问题的判定问题是：是否存在一个排序n ，使 得，茎y ? 首先，如果点覆盖问题有解，即存在一个整数 ，使得图g 有一个 女点覆盖，则在排序问题中依次加工它们关联的剩余边。由同时性约束，每个 顶点对应的剩余工件集的加工时间为1 ，即每批的加工时间都为1 ，因此有 。= ( 女+ 1 ) ；( + 1 ) = y ，排序问题有解。反之，若排序问题有解使 得c 直= ；( k + 1 ) y = ；( + 1 ) ，则有女，f 。由排序问题中的同时性约 束和序列性，将从。时刻开始每批的边工件关联的唯一顶点取出即为g 的一 个女覆盖，从而点覆盖问题有解。 很明显上面的归结是多项式的，因此排序闯题的判定问题是p 一完全的。 9 口 2 2直径不超过5 的树的情形 我们已经证明了当g 是一般图时，问题p m 慨= 1 ，g s f 丁( s e s ) l g m 。的 判定形式是p 一完全的，我们转而考虑g 为特殊图的情况，树是比较简单 的图，那么当g 为树时，有没有好算法呢? 我们用d 来表示树的直径，假定 m 2 ( g ) ，下面就是d 5 的树的情形： d = 1 时，t = 虬，c k 。( 丁) = p ( e ) ； d = 2 时，t = s t n r ，c k ( 丁) = m n z p ( e ) l e e ( t ) ，； d = 3 时，丁为双星，用e 表示两个中心点之间的边。e 与e ”分别表示两 个中心点关联的悬挂边中的最长边，则 d = 4 时，r 有一个中心点o 。考虑那些有且仅有一条非悬挂边e 的顶点 ”，设”关联的悬挂边中最长的为e 7 。若p ( e 7 ) p ( e ) ，则 g ，。( t ) = ( 。( r u ) + p ( e ) 我们称这样的顶点组成的集合为“先选集”，记为，记加工k 中顶点的关联 边的总时间为，则c t m 。( r ) = 。( 7 1 ) + 岛。这样一来，我们只需考虑 p ( e 7 ) p ( e ) 的情形：中心点。的邻点要么是悬挂点，要么是有且仅有一条非悬 挂边的顶点，我们将中心点关联的边从大到小排列： e 1 ，e 2 ，其中e = d a i ， 相应地它们关联的悬挂边中的最长边记为e 。7 ，e 。，e 。7 ，( 若不存在岛7 ，则令 p ( 靠) - o ) 。若e ，是悬挂边，则 。( t ) = p ( e ，) + p ( e ；，) t = 1 否则 ( 。( r ) = i n i n p ( e 1 ) + p ( 岛) ，p ( e 1 ) + c ；。蚪( t a 1 ) ) 在t 一以t 中我们考虑e 。，若e 。是悬挂边，则 ? 一( t a 1 ) = p ( e 2 ) + p ( e 。) ， = 2 否则 z 舳。( t a 1 ) = m i n p ( e 2 ) + p ( e ，) ，p ( e 2 ) + c ；。叮( 丁一a l a 2 ) ) 事实上我们是用下图来记录中间产生的数据的： u ：c 掣) 1 q 一 三兰印b 、a 3 诅i e 。一d ：g 。( t ) l 若a 在t 中是悬挂点，则 ( 0 一( 丁) = l l l i n 。( 丁) l ，。( 丁) 。( t ) 。) 若。所有的邻点都不是悬挂点，则 。z ( r ) = m i n a z ( 丁) 1 ，。( 7 ) 。，c ( t ) ，p ( e 。) ) 其中 一( t 1 ) ，= p ( e ；) + p ( e ；，) 所以，对于d = 4 的树，我们可以按以下算法找到最优解： 算法： s 印1 ：从丁中找出“先选集”，计算c t o ，t ：= 丁一，其中及岛的定 义如前所述； 砒p2 ：将t 中中心点。关联的边按加工时间从大到小排列：。，。， 。； 觑p3 ：若这些边中有悬挂边，取最小的i 使得屯是悬挂边，则 n z ( 了) = m i n a 。( 丁) l ，。( 7 _ ) 2 ，。( 7 1 ) 。) + 否则 k 。z ( 丁) 2m i n g m 。z ( t ) l ，。( 丁) 2 ，。( 丁) ，p ( 龟) + t = 1 其中。( 丁) j = 查p ( e t ) + 皇p ( e t ) 。 2 1 以上的每一步都可以在o ( n f 叩n ) 时间内完成，因此我们可以在o ( n f 叼n ) 时 间内找到直径为4 的树的最优解。 d = 5 时，丁有两个中心点，设为o 。和o 。，我们仍先从丁中找出“先选 集”，计算g ，。( 丁) = g 。( 丁一) + 岛。然后在t k 选最长边e ( 它 只可能是中心点的关联边) ，有下面两种情形： 1 若e 的两个端点是树的两个中心点，e o 。o 。，则不论是加工o t 的所 有关联边得到的了1 一o ，或加工o 。的所有关联边得到的t d 2 都是直径不超过 4 的分枝树，因此可在多项式时间内求出 ( k 。( 丁一k ) = p ( e ) + “n ( 。( t 0 1 ) ，( k 。( 丁一0 2 ) ) ； 2 若e 只关联一个中心点，e = o ；a ，c 毛。( t 一) = p ( e ) + m n ( 。( 丁一 q ) ，c k 。( 丁一a ) ) ，其中丁一q 是直径为4 的树，g 。( t o 。) 可在多项式时间 内求出；t a 仍是一个直径不超过5 的树，仍可分情况讨论，但中心点的度 变小了，由于两个中心点的度和不超过n ，所以至多经过o ( n ) 次分情况一定 出现情形1 。 由上面的分析我们可以看出，情形2 至多需要d ( n ) 次时间可化为情形1 ， 而情形1 用d = 4 的树的算法可得到最优解，用时o ( n f 叩r 。) ，因此我们可以在 o ( n 。z 。g n ) 时间内得到d = 5 的树的最优解。 第三章具有同时性约束的平行机排序的一般模型 3 1p 一完全性证明 3 一划分问题：对给定的3 f 个正整数口1 ，n 2 ，及正整数b ，其中等 罢，且基嘶= b ，问是否存在l ，2 ，3 t 的划分( s - ，禺，s t ) 使得i s i = 3 且 ，蠹却( 江1 ，2 ，。) 7 引理3 ：排序问题p m | g s ，丁f 。的判定问题是p 一完全的。 证明：当消除同时性约束时，判定问题退化为一个已知的p 一完全问题 。，也即是说，该判定问题是。的一个推广，因此是p 一完全 的。 口 引理4 ；排序问题尸m l g s 丁l q 的判定问题是p 一完全的。 证明：显然该判定问题属于尸类。 用已知是强p 完全的3 一划分问题作归结。对给定的3 t 个正整数n 。，n 。， 及正整数b ，其中等 y 。因此说满足门槛值的排序一定满足s p 丁 规则，也即前个时间段被f b 个长度为1 的工件占满了，由同时性约束，每 个时间段上的工件只能且一定关联y 中的3 个顶点，分别把每个时间段的下 标集合记为s 。，& ，显然这就是3 一划分问题的一个解。 因为3 划分问题是强p 一完全的，所以该判定问题是尸一完全的。 口 实际上，两个城市之间有可能有不止一条通道，这就需要我们考虑多重图 的情形t 引理5 ：当g 为多重偶图时，排序问题p m 肼= l ，g s m t | c k 。的判定形 式是p 一完全的。 证明：显然该判定问题属于p 类。 用已知是强p 一完全的3 一划分问题作归结。对给定的3 个正整数n 。， n 3 c 及正整数b ，其中学 导，塞= b 。构造排序问题的一个实例： m = b ，l = ，约束图g 包含3 h 1 个顶点，分为两部分 孔孙，z 3 。) ， y ) 。 顶点间的连边规则是：q 到连条边( ，= 1 ，2 ，3 ) ，其中巧的度为q 。 如下图所示： z l 观 z 3 这里，图g 的顶点数为3 t + 1 ，边数为月，故町在拟多项式时间内完成排 序实例的构造。下面只要证明 论断：3 一划分的实例有解当且仅当判定问题的实例有解。 事实上，若3 一划分问题有解 s - ，昆，s ) 使得i & i = 3 且，。黾q = 威 1 ，2 ，0 ，则将 b 最 的3 个顶点关联的b 个工件放在第i 时段加工， 1 ，2 ，) ，这样就得到了排序问题实例的解且。= 扣l 。 反之，若排序实例有解( c 。st ) ，则由于的度为b ，所以在前t 一1 个时段不可能选中g 的全部关联边来加工，又根据。t 和工件总数为日 的限制，我们知道每个时段必须没有机器空闲，对每一个顶点，其关联的 n ，条边工件必须同时加工，即必须安排在同一个时段，为简单起见，我们说顶 点z j 被安排在一个时段加工，占用n j 个台机器。由条件鲁 。， 导可知，每 个时段至多安排三个顶点：但若安排两个顶点，必有机器空闲。因此，每个时 段均安排三个顶点且没有机器空闲。则我们就可以令s = 驯被安排在时段 i 上) ，则l & l = 3 且= b ，这就是孓划分闻题的一个解。 j 最 综上，当允许g 为多重图时，排序问题p m 慨= 1 ，g s m t i c k 。的判定问 题是p 一完全的。 口 下面是本节中的两个主要的p 一完全证明。 引理6 ：问题p m i b = l ，g s m 丁l ( k 。的判定形式是p 完全的。 证明：此判定形式显然属于p 类( 满足条件的可行排序”作为简短的 判据) ，下面将强p 一完全的3 一划分