（技术经济及管理专业论文）资源受限条件下N元行偶顺序优化的理论与方法研究.pdf

华北电力大学硕士学位论文 摘要 资源限制项目排序问题是项目管理的核心内容。现有的解析法和启发式算法在 解决该类问题时存在明显缺陷，如计算量大、难以达到最优、缺少普适性等。为了 设计出能克服上述缺陷的新算法，先在假设资源无限时做“理想网络计划”，再根 据实际资源限制把“理想网络计划”中的平行工序调整为顺序工序，从而使项目排 序问题分解为多个平行工序顺序优化的子问题，减小了工作的难度。本文研究其中 一类子问题将l 个平行工序中的2 n 个调整为n 对顺序工序。利用c p m 网络自 身的特点和机动时间规律，在考虑前、后继工序约束条件下，设计出带松弛量的n 元行偶顺序优化算法，并分析算法的时间复杂性。该子问题的解决为资源限制项目 排序问题的彻底解决奠定了基础。 关键词：运筹学，项目管理，进度控制，机动时间 a b s t r a c t r e s o u r c er e s t r i c t e dp r o j e c ts c h e d u l i n gp r o b l e mi sai m p o r p a n tp r o b l e mi n p r o j e c tm a n a g e m e n t t h e r ea r eo b v i o u sd e f e c t sw h e nu s i n ga n a l y t i ca l g o r i t h ma n d h e u r i s t i ca l g o r i t h mt or e s o l v et h ep r o b l e m ，s u c ha sn e e dh e a v yc a l c u l a t i o n ，d i f f i c u l tt og e t o p t i m i z a t i o n ，c o u l d n tb ea p p l i e dw i d e l y , a n ds oo n f o rd e s i g n i n gn e wa l g o r i t h mw i t h o u t t h e s ed e f e c t s ，m a k e s “p e r f e c tn e t w o r kp l a n n i n g i nc a s eo fr e s o u r c el i m i t l e s sf i r s t l y , a n dt h e n a r r a y sp a r a l l e la c t i v i t i e si n p e r f e c tn e t w o r kp l a n n i n g t oo r d i n a la c t i v i t i e sb a s eo na c t u a l r e s o u r c er e s t r i c t e d ，t h e r e b yd e c o m p o s e sp r o j e c ts c h e d u l i n gp r o b l e mt om a n ys u b - p r o b l e m sf o r r e d u c i n gd i f f i c u l t y t h i sp a p e rr e s e a r c h e so n eo fs u b p r o b l e m s - - a r r a y s2 na c t i v i t i e sf r o ml p a r a l l e l a c t i v i t i e st ono r d i n a la c t i v i t i e s w h e na c c o r d i n gr e s t r i c t i o no fp r e c e d i n ga n d s u c c e e d i n ga c t i v i t i e s ，d e s i g n so p t i m i z a t i o na l g o r i t h mo fnd i m e n s i o n sr o w m a t ew i t h r e l a x a t i o nq u a n t i t yb yu t i l i z i n gr u l e so fc p mn e t w o r ka n dc h a r a c t e r i s t i c so ff l o a t ，a n d a n a l y z e st h et i m ec o m p l e x i t yo ft h ea l g o r i t h m t h er e v o l u a t i o no ft h es u b p r o b l e mc o u l d e s t a b l i s hb a s ef o rr e v o l v i n gr s o u r c er e s t r i c t e dp r o j e c ts c h e d u l i n gp r o b l e mc o m p l e t e l y s uz h i - x i o n g ( t e c h n o l o g ye c o n o m ya n dm a n a g e m e n t ) d i r e c t e db yp r o f q ij i a n - x u n k e y w o r d s ：o p e r a t i o n a lr e s e a r c h ，p r o j e c tm a n a g e m e n t ，s c h e d u l i n gc o n t r o l ，f l o a t 华北电力大学硕士学位论文 摘要 资源限制项目排序问题是项目管理的核心内容。现有的解析法和启发式算法在 解决该类问题时存在明显缺陷，如计算量大、难以达到最优、缺少普适性等。为了 设计出能克服上述缺陷的新算法，先在假设资源无限时做“理想网络计划”，再根 据实际资源限制把“理想网络计划”中的平行工序调整为顺序工序，从而使项目排 序问题分解为多个平行工序顺序优化的子问题，减小了工作的难度。本文研究其中 一类子问题将l 个平行工序中的2 n 个调整为n 对顺序工序。利用c p m 网络自 身的特点和机动时间规律，在考虑前、后继工序约束条件下，设计出带松弛量的n 元行偶顺序优化算法，并分析算法的时间复杂性。该子问题的解决为资源限制项目 排序问题的彻底解决奠定了基础。 关键词：运筹学，项目管理，进度控制，机动时间 a b s t r a c t r e s o u r c er e s t r i c t e dp r o j e c ts c h e d u l i n gp r o b l e mi sai m p o r p a n tp r o b l e mi n p r o j e c tm a n a g e m e n t t h e r ea r eo b v i o u sd e f e c t sw h e nu s i n ga n a l y t i ca l g o r i t h ma n d h e u r i s t i ca l g o r i t h mt or e s o l v et h ep r o b l e m ，s u c ha sn e e dh e a v yc a l c u l a t i o n ，d i f f i c u l tt og e t o p t i m i z a t i o n ，c o u l d n tb ea p p l i e dw i d e l y , a n ds oo n f o rd e s i g n i n gn e wa l g o r i t h mw i t h o u t t h e s ed e f e c t s ，m a k e s “p e r f e c tn e t w o r kp l a n n i n g i nc a s eo fr e s o u r c el i m i t l e s sf i r s t l y , a n dt h e n a r r a y sp a r a l l e la c t i v i t i e si n p e r f e c tn e t w o r kp l a n n i n g t oo r d i n a la c t i v i t i e sb a s eo na c t u a l r e s o u r c er e s t r i c t e d ，t h e r e b yd e c o m p o s e sp r o j e c ts c h e d u l i n gp r o b l e mt om a n ys u b - p r o b l e m sf o r r e d u c i n gd i f f i c u l t y t h i sp a p e rr e s e a r c h e so n eo fs u b p r o b l e m s - - a r r a y s2 na c t i v i t i e sf r o ml p a r a l l e l a c t i v i t i e st ono r d i n a la c t i v i t i e s w h e na c c o r d i n gr e s t r i c t i o no fp r e c e d i n ga n d s u c c e e d i n ga c t i v i t i e s ，d e s i g n so p t i m i z a t i o na l g o r i t h mo fnd i m e n s i o n sr o w m a t ew i t h r e l a x a t i o nq u a n t i t yb yu t i l i z i n gr u l e so fc p mn e t w o r ka n dc h a r a c t e r i s t i c so ff l o a t ，a n d a n a l y z e st h et i m ec o m p l e x i t yo ft h ea l g o r i t h m t h er e v o l u a t i o no ft h es u b p r o b l e mc o u l d e s t a b l i s hb a s ef o rr e v o l v i n gr s o u r c er e s t r i c t e dp r o j e c ts c h e d u l i n gp r o b l e mc o m p l e t e l y s uz h i - x i o n g ( t e c h n o l o g ye c o n o m ya n dm a n a g e m e n t ) d i r e c t e db yp r o f q ij i a n - x u n k e y w o r d s ：o p e r a t i o n a lr e s e a r c h ，p r o j e c tm a n a g e m e n t ，s c h e d u l i n gc o n t r o l ，f l o a t 声明尸明 本人郑重声明：此处所提交的硕士学位论文资源受限条件下n 元行偶顺序优化的 理论与方法研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研 究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 学位论文作者签名：茏盎蕉篷 日 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：益主左( 童 日期：2 生殳星；( ：f 口 导师签名： 华北电力大学硕士学位论文 1 1 选题背景及其意义 第一章引言 随着生产力提高和科技发展，生产规模在全球范围内都有不断扩大的趋势。规 模扩大不可避免的会导致更多的资源消耗和资金投入。当前全球资源短缺问题日益 突出，生产部门若一味的采用增加资源消耗来扩大生产的做法，不管从近期发展还 是从长远发展来看都是不可行的。我国在过去长时间内的经济增长主要依靠的就是 增加固定资产投资和资源消耗来实现的，若继续这样的经济增长方式对我国的可持 续发展十分不利，可能导致各类恶性循环的产生，最终造成难以预料的后果。中央 领导层充分认识到了这一问题的严重性，并对其给予高度重视。中共十七大报告中 明确提出节约资源、降低能耗、推动可持续发展的要求。可见，在当前环境下，各 行各业实施节能措施势在必行。 当前，项目的理念已经深入到各行各业，任何社会活动都可归结为项目，在此 环境下项目管理也变得炙手可热。由于节约资源的措施贯穿于项目的整个进度中， 为了更好地实现资源节约，保障可持续发展，有必要从项目进度管理入手。项目进 度管理是项目管理中最重要的“三大目标之一刀，它不但根据进度目标的要求编制 计划，而且在实施的过程中调整、修改计划。在资源普遍存在短缺和当前提倡节能 的情况下，提供给各项目的资源( 如劳动力、资金、机器设备、材料等) 都是有限 度的，因此需要对项目中的各项任务进行排序。由于将多个独立的任务顺序化后不 可避免的会导致项目总工期比原计划推迟，这样必然会增大成本费用，特别是大规 模的项目，总工期推迟一点就会造成费用迅速提高，极易产生超支，可见，如何合 理的安排任务顺序，使项目总工期所受影响最小是必须要深入考虑的问题。该问题 可归结为资源受限条件下项目排序问题( r c p s p ) 。在资源短缺问题日益突出和节能 要求日益增大的条件下，资源限制项目排序问题已经成为项目进度管理的核心问题 d 3 l ，若能将其解决无疑有很大的理论价值和现实意义。 资源限制项目排序问题从理论上说是一种组合优化问题，具有排列组合的一般 特点，随着考虑对象数量的增长，问题的可行方案数量急剧增加，增长级数往往是 指数级的，因此，求解该类问题的计算量往往也成指数级增长【4 5 】。很多时候，若要 求得最优解，再高速的计算机也难以在可接受的时间内完成。这也成为该类问题到 现在为止一直未能有效解决的最大障碍。 鉴于此，本文选择从简入手，将资源限制项目排序问题进行细化，分解成若干 相对简单的子问题，若将各子问题解决了，原问题的解决就变得容易了。本文主要 华北电力大学硕士学位论文 研究这些子问题中的一类，具体可描述为在工程项目的某环节中，用m 单位资源( 人 力、设备等) 完成n 项相互独立的工作，假设每单位资源都可完成这n 项工作中的 任意一项，且m n ，2 m n ，要求用每单位资源完成其中一项或两项工作，并且 使总工期推迟最少。该问题在实际中广泛存在，如有7 项工作，只有4 台设备可用， 应用最多的是选择其中三台，每台做两项工作，剩余的一台做一项工作为合理方案， 但是具体如何选择才能得到理想方案中的最优方案，即对总工期影响最小，依然是 当前未解决的问题。该类问题虽然是资源限制项目排序的子问题，但求解的复杂程 度却依然很高。例如，用n 台设备完成2 n 项工作，每台设备完成两项，可行方案 有a 是= ( 2 n ) ! n ! 个，假设n = 1 5 ，那么a ：2 0 3 x 1 0 ，即使计算机每秒排百亿次 ( 一年约3 1 5 x 1 0 7 秒) ，得到最终答案也需6 4 4 年以上。如何设计出多项式算法求解 这类很复杂问题的最优解成为本文研究的核心之一。 同时，由于将独立的工作调整为有严格先后顺序的工作虽然是一局部的变化， 但造成的影响却是全局性的，理应从全局的角度来考虑，可是这样不仅会增加分析 的难度，而且也会使一些无需考虑的对象列入分析的范围。如果能够发现局部与全 局之间的联系，用局部的变化反应全局所受的影响，进而通过局部寻优实现全局寻 优，这样分析起来无疑大为简便并不失准确性。如何通过局部寻优实现全局寻优也 成为本文研究的核心之一。 本文将项目进度用相应的c p m 网络计划图表示，图中箭线表示工序( 工作) ， 深入研究工序的机动时间及其特性，在此基础上设计出多项式的算法求解带松弛量 的n 元行偶顺序优化问题，得出最优方案，进而为资源限制项目排序问题的最终解 决提供理论基础和依据。特别是本文运用“通过局部寻优实现全局寻优”的思路和 方法，为更多的因为分析和求解起来难度很大，进而导致研究进展缓慢的问题提供 一定的指导和启示。因此，本文的研究不但具有巨大的实用价值，更有重大的理论 意义。 1 2 国内外研究动态 资源限制项目排序问题作为组合优化问题的一类，目前国内外常用线性规划 法、0 1 规划法、分支定界法、隐枚举法等试图求得其最优解。这些方法通常只适 用于小规模的项目排序问题( 对于5 0 项工作以下的项目，可得到较为满意的处理) 【6 1 ，当遇到大规模的项目排序问题时，运用这些方法虽然从理论上能得到最优解， 但计算量都相当大，其求解时间甚至是无法接受的，很多时候还存在增加无谓的计 算量的情况。如用数学规划等方法在解决排序优化问题时，参加排序和不参加排序 的工作都被考虑在内，这样，即使一个很简单的排序问题，其线性规划模型也包含 了众多的自变量和约束条件，增加了计算复杂度 7 1 0 】。 2 华北电力大学硕士学位论文 另一方面，经典的组合优化问题通常只是考虑排序对象本身。但是，从系统论 的角度来看，每个工序都受到其前继工序的制约，也会影响其后继工序，所以，工 序与其前、后继工序之间的关系会直接影响到排序结果。如在工序排序时，把一个 机动时间为2 0 天的工序与机动时间为零的关键工序同等看待，显然是不合理的。 因此，排序时应当考虑到工序的前后制约关系，这就使得项目排序问题变得难上加 难。五十年代后期，关键路线法( 简称c p m t q 3 】) 网络计划技术产生后，各项目 进度可用相应的工序网络图来表示，工序的前、后继关系能够通过其最早时间参数 和最迟时间参数科学地表达出来，尤其是工序机动时间可以科学地计算出来l l 州， 能综合反映一个工序与其前、后继工序之间的关系，为研究考虑前、后继关系的排 序问题奠定了基础。 由于项目管理实践的迫切需要，再加之求解资源限制项目排序问题最优解的复 杂性，国内外的众多专家学者在c p m 网络计划时间参数的基础上，对于每类项目 排序问题的优化都提出了多种启发式方法【1 8 】，如“机动时间少的先干，机动时间多 的后干”、“先开始的先干”等等。日本的加滕昭吉先生提出的“k s 法1 1 9 引j 给出 了在资源约束下将平行工序调整为顺序工序的优化三原则：一是工期长的工序先 干、工期短的工序后干；二是机动时间少的工序先干，特别是关键工序要先干；三 是可以先开始的工作先干。上述三条原则，并不完全正确，有时结论正好相反。文 献 2 0 ，2 1 1 从理论和实例上说明了“k s ”法的不科学性。文献【2 2 】研究了有资源约束 的各种启发式方法，结合网络本身的结构特征分析了启发式方法的有效性：文献 2 3 】 已经提到网络排序技术在项目排序中可能的应用，但缺少对该应用的详细描述；文 献 1 9 】在研究项目排序中的机器排序时采用了析取图法，但它仅适用于小型网络； 文献 2 4 3 0 采用的启发式方法运算极其复杂；文献【1 8 1 介绍了资源有限的网络计划 问题的启发式优化方法的发展与特点，对两种启发式方法“并列法 和“序列 法”分别做了介绍，并比较分析了三十余种启发式准则，虽然这类方法简单易行， 但无法保证得到最优解。因为启发式方法的着眼点不是求取数学意义上的最优解， 而是为了在一定程度上满足实际需要，所以所求得的解与最优解的偏离程度是不可 预知的。在处理同一问题时，使用不同的启发式方法得到的结果是不同的。并且， 解决具有不同网络特征( 网络结构、工序工期、资源限量与种类、工序的资源需求 量等) 的优化问题，同种启发式方法产生的结果也是不同的，有时差别会很大，因 此无法保证解的最优性和方法的普遍适用性i l 引。 早在六十年代，中国科学院越民义先生就意识到排序优化问题的重要性和解决 的艰巨性，并指出，“排序问题是规划数学和计算机科学没有能力解决的国际性难 题”。该问题之所以半个世纪以来都未能彻底解决，主要是由于难度大，且没有适 合解决该问题的数学工具，同时也与人们“一步到位一的研究思路有关。人们总是 想寻求到某一种方法一蹴而就地解决这个世纪难题。但是，经过半个世纪的探索， 3 华北电力大学硕士学位论文 实际证明这个思路是不可取的。鉴于此，人们试图把该问题分解为多个较为简单的 子问题 3 1 , 3 2 】，每个子问题都比较容易解决，当所有的子问题解决以后，该问题就可 以自然而然地解决了。主要思路如下： 首先，假定所需资源无限，构建一个“理想网络计划”，即只按工艺流程的 要求排列工序的先后顺序。在这种情况下，必定会出现很多独立的平行工序。在理 想情况下制定的计划称为理想计划。 然后，回到现实生活中来，按照实际的资源限制情况调整“理想网络计划 ， 把其中某些独立的平行工序调整为先后进行的顺序工序，根据不同的情况将问题进 行分解。这样，可通过研究分解出的各类子问题的最优化理论和方法彻底解决该问 题。平行工序调整为顺序工序的子问题如下： 1 把n 个独立平行工序a ，a ，a 调整为一条顺序工序链a _ a _ 一a 的理论与方法。 2 把n 个独立平行工序a ，a ，a 调整为两条顺序工序链a a _ 一a ， a + l - a + 2 - _ 气，n = r h + 1 1 2 的理论与方法。 3 设n = 1 1 1 + 1 1 2 + + n n ，把n 个平行工序a ，a ，a 调整为n 条顺序工序链， a _ a _ 一a ，a + 1 + a + 2 _ _ 八，a 2 + l _ 人+ 2 _ 一，一。+ l 一- l + 2 _ - ，n = n l + 1 1 2 + + n n 的理论与方法等等。 当1 1 l = r h = = n n = 2 时，就是将2 n 个平行工序调整为n 对顺序工序的问题， 该问题是最简单的情况，也是用的最多、最重要的情况。本文就把该子问题作为研 究的重点。虽然这是个子问题，但该问题的可行方案有秣= ( 2 n ) ! n ! 个，随着n 的 增大，方案数也会呈指数形式急剧增长。目前国内外任何数学方法也不能完全地解 决该问题，因此对该问题也需要从n = l ，2 ，3 ，4 ，开始，由简而繁的去解决。文献 【2 0 ，2 l 】已就n = l 的情况进行了研究，文献 3 3 ，3 4 1 就n = 2 的情况进行了研究，文献 【1 1 ，3 5 ，3 6 】就n = 3 的情况进行了研究，并得到了最优化结果，但是目前对n 为任意 自然数的情况仍尚未解决。 平行工序调整为顺序工序如上所述有多个子问题，每个子问题相对于排序总问 题而言都更单纯，更典型，因而解决起来难度也会更小，尤其是，这些子问题之间 都有着一定的共通性，都是研究把平行工序调整为顺序工序的问题，因而有一定共 同的理论基础，当某个子问题解决后，对其它的子问题都会有很大的借鉴作用。尽 管这些子问题相对难度较小，但现代数学已有的方法依然不能将其彻底解决。科学 院越民义先生早在二十年前就指出，彻底解决该问题需要有新的数学工具和数学理 论。文献 3 3 3 6 1 在解决这个问题的过程中，在这方面作了很好的尝试，这些文献通 过研究c p m 网络计划自身的特点，研究了工序之间的各种依存关系，研究了机动 时间的分布规律以及机动时间与路长的关系，解决了n = l 、n = 2 、n = 3 时的特 殊问题。由于平行工序顺序优化各子问题之间的共通性，这些方法和理论为继续研 4 华北电力大学硕士学位论文 究平行工序调整为顺序工序的其它子问题，提供了新的借鉴和启发。 1 3 本文的主要研究内容及方法 本文利用c p m 网络中机动时间特性建立平行工序顺序化后对总工期影响的量 化模型，进一步改进、完善现有的理论和方法，解决n 为任意自然数时，如何将2 n 个平行工序排成n 对顺序工序能使总工期受影响最小的普遍问题，找到既具有解析 法的最优性又具有启发式方法的简便性的多项式方法。同时，将问题进一步拓宽， 解决从l 个平行工序中选出2 n 个排成n 对顺序工序的最优方案，使得总工期受影 响最小的这类资源限制项目排序问题。 5 华北电力大学硕士学位论文 2 1 时间参数 第二章时间参数和基本概念 2 1 1 节点时间参数及其计算方法 c p m 网络计划中的节点时间参数有节点的最早开始时间和最迟结束时间。比 如，对于节点( i ) 而言，它的最早开始时间记为e s ；，最迟结束时间记为l f i 设p ( j ) 和s ( j ) 分别表示c p m 网络中节点( j ) 的紧前节点和紧后节点，1 ；i 表示工 序( i ，j ) 的工期，节点时间参数的计算方法如下： 1 ) 按下式从左往右计算： ie s l = 0 e s j2 m a x l f e s i4 t i j ，j - 2 ，3 ，n ( 2 - 1 ) 2 ) 再按下式从右向左计算： l l f f n ；：= 纳e s o l f k ，j = n - l p 2 ，l ( 2 - 2 ) i l f j = 黜) l f k k ， l ，n - 2 ，l “吃夕 0 3 ) 从左向右检验，若节点( j ) 是虚入节点( 该节点的紧前工序都是虚工序) ，按 下式进行修正： l f j2 m 删a x j f 、l f i ，j = 2 ，3 ，n ( 2 3 ) 4 ) 再从右向左检验，g ：t s 点( j ) 是虚出节点( 该节点的紧后工序都是虚工序) ， 按下式进行修正： e s j 。k s m i ( n j ) e s k ) ，j = n - l , n - 2 , - , l ( 2 - 4 ) 2 1 2 工序时间参数及其计算方法 c p m 网络计划中的工序时间参数有工序的最早开始时间、最早结束时间、最迟 开始时间和最迟结束时间。比如，对于工序( i ，j ) 而言，它的最早开始时间记为e ， 6 华北电力大学硕士学位论文 最早结束时间记为e ，最迟开始时间记为l s i i ，最迟结束时间记为l ，工序的时 间参数和节点的时间参数密切相关，它们的计算公式如下： e s = e s , e 民= e + 1 i j l = l f j l = l f 一1 ；j ( 2 5 ) 本文为了描述简便，将工序( i ，j ) 用单字母表示，如工序a ，因此它的时间参数 可以表示为最早开始时间e s a 、最早结束时间e f a 、最迟开始时间l s a 和最迟结束时 间l f a 。 2 2 基本概念 本论文所包笛的基本檄忿如卜： ( 1 ) 平行工序 c p m 网络中不在同一条路线上的工序称为平行工序。 ( 2 ) 序偶与序偶亏值 平行工序a 、b 调整为a _ b 顺序后，称为一个序偶，记为( a b ) 或i 含 。总工 期因此而延长的时间称为序偶的亏值，记为【a b 】或i 斟。 ( 3 ) n 元行偶及其亏值 把2 n 个平行工序a ，a ，八，b ，b ，b n 调整为n 个序偶( 含】， 盒】，【瓮】后， 记为( 会盒：盒】；总工期因此而推迟的时间称为该行偶的亏 ( 4 ) 规范行偶 若e f s e f ，且e k e f ，称行偶 含盒i 瓮】为规范行偶。 ( 5 ) 行偶规范化与同族行偶 通过a ，a ，a 之间的位置互换和b ，b 2 ，氐之间的位置互换，使得任意行偶 【会盒：衾】变为规范行偶 会盒：瓮】，叫做行偶的规范化，规范化后相同的行偶称 7 偶、卜 行 氐氐 元 一 n a b 为队惮 称 为 体 记 总 ， 其 值 华北电力大学硕士学位论文 为同族行偶。 ( 6 ) 工序的重心 工序的最早开始时间与最迟结束时间的和称为工序的重心，记为c a ，即 c a = e s a + l f a ( 2 6 ) ( 7 ) 标准行偶 若c c q ，称行偶【盒盒：衾】为标准行偶。 ( 8 ) 行偶标准化与同类行偶 在任意行偶【含盒：衾 中，通过调换部分a 与b i 的位置，使该行偶成为标准行 偶【含盒：衾 ，叫做把 含盒：盒】标准化为( 会盒：衾) 。标准化后相同的行偶称为 同类行偶。 ( 9 ) 标准规范行偶 若一个行偶既是规范行偶，也是标准行偶，则该行偶称为标准规范行偶。 ( 1 0 ) 序偶前i 序和后工序 。 序偶( ab ) 中，称a 为序偶前工序，b 为序偶后工序。 ( 1 1 ) 行偶上行工序和下行工序 行偶 含盒i 衾】中，称a ，a ，氐为行偶上行工序，b l ，b ，b n 为行偶下行工 序。 ( 1 2 ) 含有单个最大亏值序偶的行偶四分图 记行偶中最大亏值序偶为( a ，b i ) ，则行偶四分图如图2 - 1 所示。 ( i i )( i ) a b ( 1 1 1 )( 1 v ) 图2 1 行偶四分图 ( 1 3 ) 含有m ( m 2 ) 个最大亏值序偶的行偶六分图 记行偶中最大亏值序偶为( a ，b 。) ，( a ：，b i ：) ，( a m ，b i 。) ，1 5 le f i 簿：汁m a x 料卧一，踟 协2 ) 两平行工序调整为顺序工序时，中心小者在先，则序偶亏值最小，顺序最佳。 即若c a c b ，则 若c b c ，则 a - b b _ a 1 0 华北电力大学硕士学位论文 3 2 新定理 3 2 1 规范行偶定理 规范行偶的亏值小于等于同族行偶的亏值，即 睑排譬刽 ( 3 3 ) 鲶婷黢簧】 且( 篱剖的最大亏值序偶为( 删) ，根据行偶亏值定理 簿婷黢珈州l 规范叫辫裂矧。 。l s w l s b f ，【群，群】= e f f l s b f ，【群，b 1 = e f f - l s q , ， f 群，耳】 群，b 1 根据行偶亏值定理 【州群群n 1 ，f 州a ，群群1 i b 噬群b 7 球j 一【喇b 7 群球j 簿外降掰矧 不规范叫嚣搿剖。 e f t , e f ，【群，耳】= e f f l s b f ，【a ，群】e f ，一l s b f ， f 群，群】【群】 根据行偶亏值定理 i 州a ，群群1 州a ，群n 1 -i ( 1i l b 膨群b 7 球r 【b 膨耳b ，b l ：j 华北电力大学硕士学位论文 瞄外黢锚矧 ( 3 ) 若将群与工序畔毯，b f - l 中任意工序b 7 ( i i i 一1 ) 互换，得基本的不 规范行叫辫描矧。 l s 耳l s w ，【群，群1 = e f f - l s w ，【群，b 1 = e f f - l s 吖， 【a ，群】【a ，b ，】 根据行偶亏值定理 州群群n 1 e f ，l ，群】= e f f l s b f ，【k 群1 = e f ，一l s 吖， 群，群】【a ，群】 根据行偶亏值定理 黢锱矧瞄掰矧l b 倒群b 7 或r 【b 。鹾b ，耳kj 瞄球麟掰矧 ( 5 ) i 序群与群的相对位置不动，同行间其它工序相互移动，也形成一类基 本不规范行偶，该行偶包括序偶( 群，群) ，所以该行偶亏值不小于 a ，群1 ，即不小于 黢针 因为此五类基本不规范行偶代表了其它所有的不规范行偶，具有普遍性，所以 簿外簿刽 该定理成立。 证毕。 3 22 标准行俚定理 标准行偶的亏值小于等于其同类行偶的亏值，即 1 2 华北电力大学硕士学位论文 牌甜睑刽 ( 3 - 4 ) 证明：c t ) 已知行偶( 含盒：衾】，标准化后，若 盒盒i 盒】= i 盒i 盒】，由 定义可知，c 日i c 。根据重心定理得 【b ，a 】【a ，b 】 所以 f 盒盒i 瓮】= f 芡盒瓮1 f 盒衾：衾】 譬甜盼刽 ( 2 ) 同理可证其它情况下定理也成立。 证毕。 3 2 3 含右堕个景大亏值序偶的行俚可优化调罄的半l i 审章理 3 2 3 1 定理描述及证明 设规范行偶中亏值最大的序偶为( a ，b ) ，且唯一。在行偶四分图中，若( i ) 中 存在a ，使得l s l s 马，或( i i i ) 中存在b i ，使得e f b j l s b i ； ( 2 ) b je ( i i i ) ，且e f b j l s b l ； ( 2 ) b je ( i i i ) ，f ! e f b j e f 。 调整方法： 将a 移至( i v ) ，b j 移至( i ) 。， 模型3 图3 3 1 4 华北电力大学硕士学位论文 该模型对应的行偶四分图如图3 - 4 所示。 模型成立的条件： ( 1 ) a ( i ) ，l ql s l s b i ； ( 2 ) b je ( i v ) ，r e f b j e f 。 调整方法： 将a 移至( ) ，b j 移至( i i ) 图3 4 模型4 该模型对应的行偶四分图如图3 5 所示。 模型成立的条件： ( 1 ) b je ( 1 i i ) ，_ re f b e f ； ( 2 ) a ( i ) ，i ql s l s 马。 调整方法： 将b j 移至( i i ) ，a 移至( i i i ) 。 图3 5 模型5 该模型对应的行偶四分图如图3 - 6 所示。 1 5 华北电力大学硕士学位论文 模型成立的条件： ( 1 ) b je ( i i i ) ，i le f b j e f ； ( 2 ) ae ( i i ) ，_ g l s l s 日i 调整方法： 将b j 移至( 1 ) ，4 移g ( x v ) 。 图3 8 模型8 该模型对应的行偶四分图如图3 - 9 所示。 模型成立的条件： ( 1 ) b j ( i v ) ，g e f b j e f ； ( 2 ) ae ( i ) ，且l s l s 岛。 调整方法： 将b j 移至( i ) ，a 龆( 1 l i ) 。 图3 - 9 模型9 该模型对应的行偶四分图如图3 1 0 所示。 1 7 华北电力大学硕士学位论文 模型成立的条件： ( 1 ) ae ( i i ) ，且l s l s b i ； ( 2 ) b je ( i v ) ，j | e f b j e f 。 调整方法： 将a 移至( i i i ) ，b j 移至( i i ) 图3 1 0 模型1 0 该模型对应的行偶四分图如图3 - 1 l 所示。 模型成立的条件： ( 1 ) a ( i i ) ，且l s e f 。 调整方法： 将a 移至( i i i ) ，b j 移至( i ) 。 图3 1 l 因为行偶为规范行偶，( a ，b i ) 为最大亏值序偶，所以e f “ e f e f + i ， l s 轧l s b i l sb i ，或 ( 2 ) b je ( i i i ) ，且e f b l s 马，且( i i i ) 中不存在b j ，使得e f b e f ，并且c c b i ，则该行偶 为最优行偶，即行偶亏值最小。 推论3 2 记规范行偶的最大亏值序偶为( a ，b i ) ，在行偶四分图中，若将( i ) 中任一工序 移至( i v ) ，行偶下行的任一工序移至行偶上行，或将( i i i ) 中任一工序移至( 1 1 ) ，行 偶上行的任一工序移至行偶下行，都不能够使行偶亏值减小，且c s c 吗，则该行 偶为最佳行偶，即行偶亏值最小。 3 2 4 差量定理 设对行偶进行一次调整后，生成n 个新序偶，其序偶上差量和下差量分别是m ；， n i ( i = l ，2 ，n ) ， ( 1 ) 若所有m ； n ；，则调整成功； ( 2 ) 若存在某个m ；n ；，则该不调整不能进行。 证明：设行偶的最大亏值序偶为( a ，b 1 ) ，由亏值定义得 【a ，b 】= e f 一l s b l 经过一步调整后，生成的新序偶记为( 群，q ) ，由序偶亏值的定义得 【碍，b ； = e f j q l s b ： 所以 【群，b j 卜【a ，b i 】2 ( e f g - l s b , ? 一( e f 一l s 马) ( 3 5 ) = ( e k e f ) 一l s b ；- l s q ) 根据序偶上差量和下差量的定义，得 1 9 华北电力大学硕士学位论文 m i = e f a ；一e f a n i = l s g l s 马 将公式( 3 - 5 ) 代入公式( 3 - 6 ) 得 【群，b 争【a ，b i = m 。- n i ( 3 6 ) ( 3 7 ) 由公式( 3 - 7 ) 得 ( i ) 若m i n i ，则 【群，q 卜【a ，b i 】 o 。 即 【群，q 】 e f ，l s k l s 日i ； ( 2 ) ( i ) 中e f 大于等于e f 吖的工序中，其l s 均小于等于l s b l ； ( 3 ) ( i ) 中e f 小于e 的工序中，存在a ，使得l s l s 马，且e f k e f b ； ( 4 ) 记e f p e f t , l s b l ，( i v ) 中存在b j ，使得l s 马 l s a ，l s a , ，g le f b j l s b i ； ( 2 ) ( i v ) 中l s 小于等于l s 硝的工序中，其e f 均大于等于e f ； ( 3 ) ( i v ) 中l s 大于l s n 的工序中，存在b j ，使得e f b j e f ； ( 4 ) 若用气表示k ，即l s i - - - m a x l s a , i i n ，l m n ，且记l s b p l s l s b p + ，i p n ，则m p + l 5 ( 5 ) b n 为行偶下行工序中b p + i 后面( 包括b ，+ 1 ) 第一个e f 小于e f 的工序， 且r l m 。 调整步骤： 将气移至( i v ) ，b n 移至( i i ) ，将新行偶规范化。 模型4 1 6 该模型对应的行偶四分图如图4 1 6 所示。 图4 1 6 模型成立的条件： l s 硝l s 日l ，( 1 1 1 ) 9 b 存在b j ，使得l s b j l s 硝，e f b j e f 调整步骤： 将k 移至( i i i ) ，b j 中e f 最小的工序移至( i i ) ，将新行偶规范化。 2 4 华北电力大学硕士学位论文 模型4 1 7 该模型对应的行偶四分图如图3 1 7 所示。 ( i i )( 1 ) ( 1 1 1 )( i v ) 图4 1 7 模型成立的条件： ( 1 ) l s q , l s b l ，e f t , ( 1 l i ) q al s 大于