（应用数学专业论文）具有资源约束的物流工程调度.pdf

ab s t r a c t ab s t r a c t t h e re a r e e x t e n s i v e a p p l i c a t i o n s t o p r o j e c t s c h e d u l 吨 p r o b l e m i n t h e r e a l i t y , i n c l u d i n g t h e b u i l d i n g i n d u s t ry , t h e d e v e l o p m e n t a n d p r o d u c t i o n o f n e w p r o d u c t s , t h e m e d i u m a n d l o n g p e r i o d i n v e s t m e n t i n t h e c a p i t a l m a r k e t , s e r v i c e s y s t e m s , t h e s o ft w a re p a c k a g e e t c . r e c e n t l y p r o j e c t s c h e d u l i n g p ro b l e m h a s a l r e a d y b e e n a p p l i e d s u c c e s s f u l l y t o t h e j i t o f t h e m a n u f a c t u r i n g i n d u s t ry a n d m o d e m l o g i s t i c s c o n t ro l . b e c a u s e o f i t s i mp o r t a n t t h e o re t i c a l a n d p r a c t i c a l m e a n i n g , p r o j e c t s c h e d u l i n g p rob l e m h a s b e i n g d r a w n n u me ro u s s c h o l a r s a t h o m e a n d a b r o a d . t e m p o r a l p ro j e c t s c h e d u l 吨 h a s b e e n re s e a r c h e d m o s t l y i n t h e e a r l i e r p e r i 喊 h o w e v e r i t w i ll h a v e m o re r e a l i s t i c m e a n i n g w i t h re s o u r c e c o n s t r a i n t , a n d b e a l s o s o l v e d w i t h m o re d i ff i c u l t y . t h i s p a p e r in t r o d u c e s l o g i s t i c s a n d p r o b l e m i n b r ie f f ir s t , a n d p r e s e n t s t h e t h e o ry f o r t e m p o r a l p ro j e c t s c h e d u l i n g ; th e n e x p o u n d s p ro j e c t s c h e d u l in g p r o b l e m w i t h r e s o u r c e c o n s t r a in t a n d g i v e s t h e s o l u t i o n - b r a n d r a n d - b o u n d a l g o r i t h m ( b a b ) . k e y w o r d s : l o g i s t i c s p ro j e c t s c h e d u l i n g t i m e c o n s t r a i n t re s o u r ce bab 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的 规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电 子版 本; 学校有权保存学位论文的印 刷本和电 子版，并采用影印、 缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国 家有 关部门 或者机构送交论文的复印件和电 子版; 在不以 赢利为目 的的 前 提下，学校可 以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 沁 才 称 、 -w n b 年 ! ) 月 才 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内 部_ 5 年 谈最长5 年， 一 可少于7 年) ( v , t 10 年 ， 可 少 于 10 甲 ( 最长 2 0年厂可少于2 0 年 南开大学学位论文原创性声明 本人郑重声明: 所呈交的 学位论文， 是本人在导师指导下， 进行 研究工 作所取得的成果。 除文中已经注明 引用的内容外， 本学 位论 文 的研究成果不包含任何他人创作的、 己 公开发表或者没有公开 发表的 作品的内容。 对本论文所涉及的研究工作做出贡献的 其他个人和集 体， 均己在文中以明确方式标明。 本学 位论文原创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 : 初 才 k b a 年 i f月可 日 第一章预备知识 第一章预备知识 第一节现代物流概述 1 . 1 . 1 物流概念的产生和发展 物流学术界对物流概念的产生和发展有两种观点。 第一种观点认为，物流概念是因为经济原因而产生的，即起源于人们对协 调经济活 动中 物流及 其相关活 动的 追求。 1 9 1 5 年， 阿 奇。 萧 ( a r c h s h a w ) 在 市 场流通中 的若千问题 一书中明 确地将企业的 流通活动分为创造需求的活动和 物流活动，指出:“ 创造需求与实物供给的各种活动之间的关系说明 ( 这些 活动之间) 存在平衡 性和相互依 赖性两个原则” ， “ 物流( t h e p h y s ic a l d i s t r ib u t i o n o f g o o d s)是与创造需求不同的一个问题流通活动中的重大失误都是因为 创造需求与物流 之间缺 乏协调造成的” 。 文中 提到的 “ 平衡性” 、 “ 相互依赖 性” 、 “ 协调”等正是物流理论与实践的基础。 第二种观点 认为， 物流概念是 因为军事原因 产生的 。 其次， 在英语中， “ 物 流” 一词 “ l o g i s t i c s ”的原意为“ 后勤” ，这是 在第二次世界大战中，军队在 运 输武器、粮食等给养时使用的一个名词。因此，物流最初是从军方后勤理念引 申 过来的。 在第二次 世界大 战期间，美国军事部门 运用它 所研发的 “ 后勤管理” ( l o g i s t i c s m a n a g e m e n t ) 方法对 军需物资的 采购、 运 输、 仓储、 分发进行统筹 安排和全面管理，取得显著效果。战后 “ 后勤管理”被引入经济部门，应用于 流通领域和生产经营管理全过程中所有的与物品获取、运送、仓储、分配有关 的 活 动。 后 来人 们 把“ l o g is t ic s ” 一词 专用 于 物资 的 流 通中， 把 “ l o g is tic s d i s t r i b u t i o n ”译成 “ 货物配送ff. 第二次世界大战期间积累的大量军事后勤保障理论、经验，形成和丰富了 “ 运筹学” 的理论和 方法，战后 被很多国 家运用到了民 用领域， 促进了2 0 世纪 六七 十年 代世界经济的 发展，也促 使现代 “ 物流” 理论的 形成与发展。 近2 0 年来， 在技术 进步 的推动下， 流通、 消费 等领域得到 广泛 应用， 经济 全球化的进程逐渐加 快。 在当前 的经济形式和市 场竞争环境下， 现代物流 作为 一种先进的组织方式和管理技术、其重要性得到突出体现，有效的物流管理被 广泛地认为是企业在除了降 低物资 消耗， 提高劳动生 产率以 外的又一个可以 增 加利润的方式。此外，物流管理的范畴也很广，不但涉及各行各业，而且针对 第一章预备知识 具体的问题，其决策的目标与影响因素又不尽相同。 近几十年来，随着运输成本上升，生产效率饱和、库存理念的变革、产业 组织一体化、计算机与信息技术的广泛应用，物流的内涵和外延在不断扩大， 物流领域获得了实质性拓展。 1 . 1 . 2 物流的定义 企业对物流的需求不是与生俱来的，只有当企业足够壮大、业务日 趋复杂 时，才会对现代的物流提出要求。物流的概念也经过了一个比较漫长的发展过 程，下面介绍几个比较典型的物流概念. 2 0 0 2 年1 月， 美国 物流管理协 会推出的 最新的“ 物流” 定义是: “ 物流是供 应链运作的一部分，是以满足客户需求为目的，对货物、服务和相关信息在产 出地和消费地之间实现高效且经济的正向和反向的流动和储存所进行的计划、 执行和控制的过程。 ” 1 9 9 7 年， 日 本物流系统协会对 物流的定 义为: “ 物流是对原材 料、 半 成品和 成品的有 效率流动 进行规划、实施和管 理， 它同时协调供应、生产 和销售各部 门的个别利益，最终达到满足顾客的需求。 ” 在我国 “ 物流”一词是 2 0 世纪 7 0 年代末从日本引进的。至今，物流概念 引入我国已有2 0 余年的历史。和其他国家的情况相似，我国理论界和企业界对 物流的认识 也经历了 从混沌到有序、 从 狭义到 广义的过程。 这个变化过 程可以 从以下定义中看出: 1 9 9 7 年我国国 家技术监督局 将物流定义 为: “ 以 最小的总费用， 按 用户要求， 将物资资料 ( 包括原材料、 半成品、 产成品、 商品等) 从供给地向 需要地转移 地过程。主要包括运输、储存、包装、装卸、配送、流通加工、信息处理等活 动。 ” 2 0 0 1 年我国 颁布的 物流术语 国 家标准对 物流的定义为: “ 物流是 物品从 供应地向接收地的实体流动过程。根据实际需要，将运输、储存、搬运、包装、 流通加工、配送、信息处理等基本功能实施有机结合。 ” 3 物流优化简介 3 . 1 物流优化的基本思路 现代物 流管理系统处于多 变的环 境中， 物流优化是围 绕物流 管理的目 标进 第一章预备知识 行的，涉 及物流管理的各 个方面，可为 物流战略、计 划和运作提 供合理 性方案， 因此，物流优化对实现物流管理目 标具 有重大的 意义和作用。对于大多数的企 业来说，物流系统优化的目标在支持企业经营战略决策前提下，降低其运营总 成本，这种成本的节约必然转化为企业投资回报率的提高。 在进行物流优化时，应通过一系列的步骤，帮助决策者选择并实施物流优 化方案。 在进行物流优化时，分析优 化的对象并建立反映该 对象内 在本质的抽 象模型是其中的一个重要步骤。这是因为，通过建立模型，我们可以分析物流 系统的 构成及其输入与输出 之间的关系，按照一定的方 法选 择合理的物流系统 构建方案，从而为管理者进行合理决策提供依据。 3 . 2 物流优化中的算法与计算的复杂性 算法是能被机械地执行的动作 ( 或称规则、指令)的有穷集合，一个动作 的 一次 执行称为一步。能 够用算法来求解的函数或问 题称为可计算函数或可计 算问题。算法有五大特征: ( 1 ) 输入。 一个算法有零 个或多 个输入量， 这些输入 量是 算法所要求的 初始信息，它们取自某一特定的集合。 ( 2 ) 确定性。 算 法的 每一步骤都 必须有确定的 含义， 动作不能有 二义性。 ( 3 ) 有限 性。 一 个算 法对任一 合法输入都必须在执行 有限 步后终止。 ( 4 )输出。 一个算法有一个或多 个输出 信息， 它们常是同输入信息有特 定联系的量. ( 5 ) 可执行性。指算法中的所有动作必须是相当基本的，也就是说，每 一步至少在原理上能由人在有限的时间内用笔和纸来完成。 计算机技术的发展， 促进了问 题的数值解法、 模拟技术和信息处理技术的 发展。 计算机准确和全面地识别和执行一系列的指令，而这些指令是用于求解 严格确定的可计算问题的。 考察一个规模为n 的输入，对不同的输入，算法的行为可能不同，把其中 的 最坏行为， 定义为该 算法关于 规模n 的复杂性。 故算法 或问 题的复杂性一般是 问题规模n 的函数。 设f ( n g ( n ) 是定义 在正整 数上的正实值函数，如果存 在正 常数c 0 ，使得 当n 足够大时， 有f ( n ) 5 c g ( n ) ， 则记f ( n ) = o ( g ( n ) ) .在分析问 题复 杂性时，可以 求出 算法的复杂性函数f ( n ) ，也 可以 方 便地用复 杂性函数的阶o ( g ( n ) ) o 第一章预备知识 数， 则称该算法为多 项式时间算 法。 复杂性高于多 项式的 算法称为指数算法。 当输入规模不断增大时，任意一个多项式算法终将变得比任何指数算法更 有效。有少 数最 坏情况下复杂度为指数函数的 算法， 但在实践中 证明是有效的 算法，如线性规划中的单纯形算法，它的算法复杂性为指数时间，可是实践表 明其 运行时间 相当 快， 原因就在于这个算法的 平均形态良 好。因 此，在具体选 择算法时，应根据算法的时间和空间复杂度，结合具体因素 ( 如问题大小、机 器容量、 平均性态等) ， 选择使 用更 好的算法。 定义 1 . 1 . 2 如果 一个问 题有解 它的多 项式时间 d t m ( 确定 性图 灵机) 程 序，则 称该 问题属于p ( p o l y n o m i a l ) 类。 p类问 题表示多项式 算法所能 解决的 判断问题类。如果一个问题有解它的多项式时间n t m ( 非确定性图灵机) 程序， 则 称该问 题属于n p ( n o n - d e t e r m i n i s t i c p o l y n o m i a l ) 类问 题. n p 类问 题是指在多 项式时间内检测的问题类，至今尚未找到多项式时间算法。 定 义1 .1 3 n p - c o m p le t e ( n p 一 完 全) 问 题 为n p 类 中 难 度 最 大 的 问 题， 具 有以下性质: ( 1 ) 任何一 个n p - c o m p le t e 问题都不能 用任何已 知的多项式算法求解: ( 2 ) 若任何一 个n p - c o m p l e t e 问题 有多 项式算 法， 则所有n p - c o m p l e t e 问 题都有多项式算法 定义 1 . 1 . 4 对于有些问题，也许能够证明所有 n p问题都可在多项式时间 内变换成该问题， 但不能证明它至少与任何n p问题有同样难度， 则这类问题被 称为n p - h a r d ( n p 难)问 题。 n p - c o m p l e t e问题一定是 n p - h a r d问题，但 n p - h a r d问题不一定是 n p - c o m p l e t e 问 题. 对于一个新的 组合优化问题，当 找不到解它的有 效算法时， 可以把注意 力转向 设法证明 它是n p - h a r d 问 题。 这样就 避免了 浪费 经历去找有效 算法，而采取另外可供选择的途径。 第二节工程项目 与工程调 度的概念 定义1 . 2 . 1 项目 是指同一 性质的 投资或同一 部门一系列不相关的 投资， 或 在不同 部门 的投资;项目 是在一定时间内为了 达到 特定目 标而调集到一起的资 源组合，是为了获得特定的成果而开展的一系列活动;项 目是在一定组织机构 内，在限定的资源条件下，在计划的时间里，满足一定的性能，要求，质量， 第一章预备知识 数量而完成的一次性任务。 定 义1 .2 .2 工程项目 是由 相互 联系 ， 相互制约的研 究， 技术，生 产， 管理 活动所组成.这些活动具有优先关系。工程项 目中每项活动也称为一项任务， 完成需要时间 与资源。工程项目 是唯一保证 或努力完成又可以 划分为 个别子任 务或活动，而且每项活动均需要时间和稀缺资源才可以完成。( 6 ) 定义1 . 2 3 工程调度是指需要时间 和资 源保障其任务或活 动实施的系统， 同时有一个期望实现的目标，( 例如: 工期最短， 资源消耗最少， 净现值最大等) 此外，在活动 执行期间还需要考虑它 们之间的优 先关系。工程调 度的基本方 式 是求所有活动的开 始时间， 使得已 给的资 源和 优先约束满足，而且使目 标函 数 达到最优。 由 于工 程项目 的 概念可以 非常广泛 地解释，因而工 程调 度在众多 领域中出 现。包括建筑工程，新产品的开发和引进，服务系统或软件包，制造和服务业 的长期规划，能源规划等等。最近，工程调度已成功地运用于生产与工序管理， 例如，制造业的按订单生产和加工工业的批量生产。 第二章时间约束的工程调度 第二章时间约束的工程调度 资源约束工程调度问题是在时间约束工程调度问题的基础上发展起来的， 因此， 先对后者做一些相关介绍。 首先， 介绍由实际中 技术约束得到的活动之 间的 最小、 最大时差; 其次， 介 绍怎 样把a o n网 络运用到工 程调 度中去: 最后， 给出求解时间约束工程调度问题的方法。 第一节最小、最大时差 假设一项工程由n ? 1 个实活动组成，每个活动在执行时无中断 ( 即活动一 旦开 始， 在完 成之前不能中 途停止) ， 另 外引 入两个虚活动0 和n + 1 ， 分别表 示 工 程 的 开 始 和 结 束 。 况 表 示 活 动 i 的 开 始 时间( 规定 s , = o ) , 则 凡: 表 示 工 程的 最 早 完 成时 间 ; p ， 表示 活动 i 的 执 行时 间 ( p o = p . = 0 ) ， 对 每 个 实 活 动i t p i e z z o . 两个不同活动之间的关系可以通过以下几种时差来表示: s s ( s t a rt - t o - s t a rt ) 时差， s c ( s ta r t - t o- c o m p l e t i o n ) 时差， c s ( c o m p l e t i o n - t o - s ta rt ) 时差和c c ( c o m p l e t i o n 一 c o m p l e t i o n )时差。四 种时差之间 可以 相互转 化。 本文 采用的是s s ( s t a r t - t o - s t a rt ) 时差。 两 个 不 同 活 动 i 和1 的 开 始 时 间 的 最 小 时 差 记 为 d . e z , ， 满 足 凡一 s , _ d . ( 2 .1 .1 ) 也 就 是 说 ， 活 动i 最 早 可以 在 活 动 i 开 始 后d 尸时 开 始 。 类 似 地 ， 记 最 大时 差 为d e z , ， 满 足 s j 一 s , “笋( 2 .1 .2 ) 也 就 是 说 ， 活 动j 最 晚 不 能 超 过 活 动i 开 始 后d 尸开 始 定义 2 . 1 已 知活动i 的开始 时间为s , ， 则其后开始的活 动.1 的时间 窗口 定 义 为s , + d ., s , + 尸i - 第二节a o n ( a c t i v i t y - o n - n o d e )网 络 如果把一项工程形象地描绘到网络图上去，使活动对应于网络的节点 0 , 1 , - 二 ， n 十 1 ， 便形 成了a o n网 络。 下面简单介绍一下a o n网 络的 构造。 第二章时间约束的工程调度 设v 是 活 动 ( 节 点 ) 集， 对 于i, j e v ， 且h t j , 以 及 最 小 时 差锣 ， 最 大 时差俨 ，引 入弧(i ，乃的权 为8 n 鳄 ;引入背向 弧(j，小 其权定义为 凡” 一 d n. 设e 为a o n网 络 的 弧 集， 于 是 有 时 间 约 束 s i 一 s , - 8 n , ( i, j ) e e ( 2 .2 . 1 ) 其 中 s凡依 次 为 活 动 i ,j 的 开 始 时 间 在a o n网 络 中 从 节点 i 到 节 点 j 的 路 诱 导 出 一 个 最 小 时 差d 尸 = l (1 ? 0 ) 或 一 个 最 大 时 差d 笋 = 一( 1 5 0 ) 这 样 ， 时 差 的 概念 就 不 仅 仅 局 限 于 一 条 弧 的两 个 节点之间，而是可以扩充到网络中的任意两点之间。如果有m个活动 i, , i, , a ,i (i , i2 - g , 0 , j ) e _ o , v i e v =0 ( 2 . 3 . 1 ) 况s0 该问 题 的 可 行 域s t 可 以 表 示 为 r - 2 中 的 一 个 凸 多 面 体 。 若s t 笋 尹 ， 则有下述定理: 定理2 . 1 一个工程调度问题存在时间可行调度q相应的a o n网络不包含 任何正长度的回路。 第二章 时间约束的 工程调度 证明: 必要性 任 取 一 时 间 可行 调 度 ， 不 妨 记 为 s = ( s o + s . . . i s - 1 ) ( 其 中 s o = o , s , _ o , i e v ) ， 满 足 ( 2 .2 .1 ) 式 ， 假设 i 是 长 度 为 1 的 回 路 上的 一 个 节 点 ， 由( 2 .2 .1 ) 式 可 知 s , 十 氏 。 叹 ， ， 凡 . + 药 ，。 又 : ， ， 况 ， + 点 。 5 (i ， 11 ， ， 护 均 为 回 路上 的 节 点 ， 且汽 : + 凡 ，: +. 二 十 戈 ., = 1 ) ， 得 s , + l 5 s , ， 因 此有 1 5 0 0 充分性 假设 存在一个节 点 ( 不妨设为节 点0 ) ， 从它 可以 分别 通过一条非负长 度的 路到达其它任意一 个节点 ( 否则引 入一个新节点， 令其到其它每个节点的 弧长 均为0 ) . 令a 为 节 点 。 到 i ( i = .1,2 , , n + 1 ) 的 最 长 有向 路 的 长 度 ( 其 中t o = 0 ) , 由 最 长 路 定 义 得.1, + 凡 - 0 , (i , j ) e e 4 ( n + 1 ) , i = 1 , 2 , 一， n + l , i =0 , 其中p ( l) 和f ( i ) 分别为活动i 的 前趋集和 后继集。 设 ( 0 , ) p .j )-e 是 (d b ) 的 最 优 解 ， 则 (p, iq, j ) (=- e t c e 为 相 应 于 n 中 仅 包 含 一 条 从 根 节 点。 到 i ( i e v , i o ) 的 最 长 路 为 p , 的 生 成 树t , 。 ， 可以 解 释 为 t 中 弧(i, j ) 位 于 其 上 的 从 根 节 点 出 发 的 不 同 路 的 条 数 。 对于 ( b ) 的 最 优 解e s , 满 足 践 一 e s , = 凡， 其中( l, 乃e e t ) 和e s , = 0 , 可 以 推出 esh =艺s ( h e v , h m 0 ) 。 o j 卜 p ( h ) 最 早 开 始 时 间域 (i 6 v ) ( 即 工 程 开 始 和 活 动i 开 始 的 最 小 时 差) 等 于调 度 网络n + 中从节点0 到节点i 的 最长路的 长度d o , : 类似地， 最晚开 始时间 l s , ( i e v ) ( 即 工 程 开 始 和 活 动i 开 始 的 最 大 时 差) 等 于 一 d o e ， 即 从 节 点i 到 节 点 。 的 最 长 路 长 度d o， 的 相 反 数 。 进 而， 我 们 可 以 利 用 网 络 中 的 最 长 路 算 法 来 求 解 最早和最晚调度。步骤如下: 第 1 步初始化: 第二章时间约束的工程调度 第2 步 时= i (i , j = o ,l , 一” + 1 ) k=1 , 计算 心= m a x d ; 一 ， ，心. + 心“ ( i 0 j k ) d k = 、 、 一 rek-iiibk-,y 当 心 “ 心， + d 护 ( i # j k ) 时 ， 否则。 第3 步若k n + l ，则* = k + l 转步骤 2 0 第4 步得 到 任意 两 点 间 最 长 距 离 心= d * l9， 并 且当 凡 o 为第k 种资 源的可 用数量: 活动i 使用资源k 的 数 量， 记为 、e z , 2 0 ( r k _ r k 而 且 r o k = r . (,k = 0 ) , i e v , k e r ， 通 常凡，、为 常数。 若已 给 活 动 集 的 开 始 时 间 序 列5 片 50 ， 民 ， ，凡. ， 设 a ( s ,t ) t ( i e v is , s t 0 ( 3 .1 .2 ) 这是 点 t 时 刻 使 用 的 资 源 数 量 。ie a (s f ) 定义 第三章资源约束的工程调度 m a x ( p m a x 凡) ( 3 . 1 . 3) ( ij 卜e 为 工 程 的 最 短 工 期 的 一 个 上 界 ， 其 中 凡 是 工 程 网 络( a o n ) 中 活 动 偶 ( i, 乃 的 时 差 ， e 是a o n 的 活 动 偶 ( i, 乃 的 集 合 。 我们把资源约束加入时间约束模型，它必须满足 ( 3 . 1 . ” 式，则资源约束 工 程 调 度问 题p s jte m c .可 写 成 m i n 凡 ， s t . r . ( s , t ) r , , k e r , 0 5 t 5 d s i 一 s , 2 6 y , ( i, j ) e e s , 2 0 , v i e v s o = 0 . ( 3 . 1 . 4) 定义 3 . 1 3 满足 ( 3 . 1 . 1 ) 式的资源约束的工程调度称为资源可行的工程调 度， 记 为s e . 同 时 满 足 时 间 和 资 源 可 行 的 工 程 调 度 称 为 可 行 调 度， 记 为s ， 即 s = s t n s r . 若 s e s具 有 最 小 工 程 周 期s . , ， 则 称 为 最 优 调 度 。 o s 表 示 最 优 调度集。 显 然， 若存在一 个可行调 度， 那我们总可以找到 一个最 优调 度。 若执行时 间 为 p ， 及 最 大( 小) 权 s y 为 整 数 ， 那 么 最 优 调 度 也 为 整 数. 对 于 给定 的 调 度s = (s , ) ,. v ， 函 数 r k ( s , ) 称为 资 源k 的 资 源 概 况， 它 是 一 个阶梯函数，在其跳跃点右连续。在每个跳跃点至少有一个活动开始或结束， 跳跃点的数目至多2 n 个。资源概况可用 g a n tt图表描述，用方形区域的长度表 示执 行时间两，高 度表示活 动i 所用资 源量。 第二节严格序和有序多面体 在工 程活动 集v上 建立优先关系 解决资 源冲突问题， 需要引 入严格序概念。 定义3 .2 . 1 表示( i , j ep。 在v上的二 元关系p 是( i , 力的集合， i _ j ( a ) ( 非对称性)v i , j e v , i j 且j 1 不同时 成立; ( b ) ( 传递 性) 若h i 且i j ， 则h _ s , 十 r ， 这 时 称 j 最 早 开 始时间是i 的完成时间。 命题3 . 2 . 1 v上 严格序o是时 间可行的p有序网 络n ( o ) 不含有正 长度回 路。 证 明 : 根 据 o 是 时 间 可 行 的 定 义 可 知， 若 s r (o ) # 4 ， 则 o 是 时 间 可 行 的 ， 反 之 也 成 立 。 多 面 体 s , (o ) 对 应 于n ( o ) 的 时 间 可 行 调 度 集 。 由 定 理2 .1 ( n 存 在 时 间 可 行 调 度 pn 不 含 正 长 度 回 路) 可 知 ， 若s , ( o ) * 0 = n ( 0 ) 不 含 正 长 度 回 路;若n ( o ) 不 含正长 度回 路= s t ( o ) # 护( 即存在 可行调 度) .口 定 义3 .2 .已 给 调 度s , o ( s ) = ( (j ,j ) ls , ? s , + pr # j , i, j e v ) 称 为 调 度 诱导 严格序 ，o ( s ) 的 有 序多面 体s t ( o ( s ) ) 称 为s 的 调度多 面体， 有 序网 络 n ( 0 ( s ) ) 称为s 的 调度网络。 根 据 定 义3 .3 .4 可 知 s t ( o ) = ( s e s t 0 ( s ) 2 o 卜由 于; ， 0 , 一 以一。 ， 因 而 d s 都使得o ( s ) 是 严格 序。 若调度s 是时间 可行的 ( 即s , ( o (s ) ) $ 4 ) 则 s e s t ( o (s ) ) 。 若 调 度s 是 可 行 的 ， 就 有 s t ( o ( s ) c s 。 于是 有 下 面 的 命 题 : 命题 3 . 2 ) 由 时间可 行调度s 诱导 的严格序o ( s ) 是可行的p调度s 是可 行的。 证明 : 必 要 性 设侧s ) 是 可 行 的 ， 则 根 据 定 义 有 s t ( o ( s ) 9 s . 由 于 s 第三章资源约束的工程调度 是 时 间 可 行 的 ，由 定 义3 .2 .4 可 知 s e s t ( o ( s ) ， 因 而 s 是 可 行 的 。 充分 性 设s cz s ，则s 是时间可 行的， 而且是资 源可行的，由 于 o ( s ) r to , j )is , 2 : s , + pi j ,i , j e v i 因 而s e s t ( o ( s ) ) ， 而 且s t ( o (s ) c s 。 充 分 性 得 证 . 口 定理3 . 2 . 1 ( 基本结构定理) 设o 是v中所有最小可行 严格序( 有限) 集， 则s = y s t ( o ) . 0任0 证 明 : 先 证v o e 0 都 有s t ( o ) c s . 设 0 是v 上 的 最 小 可 行 严 格 序， 即 。 是 时 间 可 行 的 ， 而 且 是 资 源 可 行 的 。 所 以 有 序 多 面 体 s t ( o ) * y ， 从 而 有s t ( o ) c s . 再 证v s e s可 推 出 : 3 o e o 使 得s e s t ( o ) . 事 实 上， 由 命 题3 .2 .2 可 知， 调度s 诱导的 序o ( s ) 是 可行 严格序， 则令o = o ( s ) 即证。口 6 ) 第三节禁用集与资源冲突的解决 定义3 3 . 1 如果活动集f c犷 满足 艺 r ,t , 3 k “ r ( 3 . 3 . 1) 则 称f 为 禁用集. 若不存在禁用 集f c f ， 则称f 为极小禁用集. 极小 禁用集的 集合 记为f。 极大 可行集a cv 是指 不存在 可行集a c v ，使得i n a . 由 于禁用集概念仅仅用于资 源需求和资源数量，因而 可以 忽略时差 而安排 i e f 的 先后执行问 题。 为了 解决类型( 3 . 3 . 1 ) 的资 源冲突， 可以分 裂 ( 拆) f ， 即 移动j e f 而使i e f - 小完 成 ， 于 是 引 入 优先 关 系凡_ s , + p , ( 简 记 为i -+j ) . 例 如， 设f = (i ,j 根 据 ( 3 .3 . 1 ) 有 + 今 凡，业e r。( 3 .3 .2 ) 若 引 入 优 先 约 束s , 之 s , + 只， 则 资 源 冲 突 得 到 解决 定理3 3 . 1 v上时间可行严格序o是可行的q 对每个极小禁用集f e f， 有序网络n ( o ) 含有一条从i e f 到j e f 具有 至少为p 长度的 路。 证明: 必要性 ( 反证法) 0 是可行严 格序， 假设存在极小 禁用集f 任 f， 第三章资源约束的工程调度 使 得 i e f 到j e f 在n ( o ) 上 所 有 路 长 均 小 于p , ( v j e f ) . 于是( j * i ) 所 有 活 动i 必 与 i 重叠 . 因 此 ，v s e 凡(o ) 不是 资 源 可 行 的 ， 有s t (o ) a s ， 这 与 严 格序o是可行的相矛盾。 充分性 设o 是时间 可行 严格序， 在有序网络n ( o ) 上， 对每个极小禁用集f e f， 都 有 从i 到 i 的 长 度 不 小 于 p ， 的 路 是 指s j 2 s , + p , 显 然 ， 每 个 调 度s 6 s ,. ( o ) 满 足s i 2 s , 十 a ， 于 是f e f 可以 分 拆 为f - i ) ， 从 而 使 分 拆 后 的f 为 极 大 可 行 集 ( 有 限 次 分 拆) . 因 此 ， b f e f都 有o n f 为 可 行 集 ， 故 s r ( o ) i= 凡n 凡= $ e 定义3 3 . 2 设 f 为禁用集，o为时间可行严格序，如果对于f的每个极小 禁用集b 都存 在i , j e b ， 使得在n ( o ) 上都有从i 到i 的最长路 不小于p , ， 则称o 分拆f 。 若侧s ) 分 拆f ，则 称调 度s 划分 ( 分拆) 禁用集f 为可行子集. 时 间 约 束s , - s , - 9 , ( ( i, j ) e e ) 诱 导 的 优 先 关 系 作 为 严格 序o 来 分 拆 禁 用 集f , 则 指 对 于d (i, 乃 。 e ， 有(i ， 乃 e 0 ， 然 后 采 用 o 对f 来 解决 资 源 冲 突 命题3 3 . 1 调度s 分拆禁用集f av r z 0 ， 集合a ( s , t ) n f 是可行的. 命题3 3 .2 时间可行严格序口是可行的p 口分拆所有禁用集( 若o分拆所 有极小禁用集，则0分拆所有禁用集) 。 命题3 3 3 时间可行调度s是可行的4 *调度s 分拆所有禁用集。 定 理3 3 .2检 测 给 定的p s 卜 州c 二实 例 是 否 存 在 可 行 调 度问 题 是n p 一 完 全 。( 1) 第四节b a b 算法 3 . 4 . 1 枚举 方案 设s = m in s ,. = e s ， 由 于s 一 般不 是资 源可 行 的 ， 因而3 t e o , d ) ， 使 得 a ( s ,t ) 为 资 源 冲 突 集 ， 即艺、 r k , 3 k e r a (si) 定 义3 .4 .1 设 f 为 禁 用 集 ， 对于 b c_ f , ( b * 0 ) ， 若f 一 b 是 一 个 可 行 集 ， 则称b是f的延迟交错。集b是f的延迟交错，可以由下式给出 艺 、 r k , b k “ r ( 3 .4 . 1 ) 若不存在b c b是f的延迟交错， 则称b是f的极小延迟交错。 集b 是f的 第三章资源约束的工程调度 极小延迟交错，即 艺、+ 、 r k , v j e b 而 且 3 k e r ( 3 .4. 2 ) 若b是f的极小延迟交错，则f b是极大可行集。 解决 资 源冲 突 ， . 可以 不 考 虑 时 间 约 束: s , - s , - s v 。 延 迟交 错 是 解 决 冲 突 的 资 源， 延 迟 活 动 j 的 执 行 ， 即i, j 交 错 执 行 . 另 外， 一 般 地， 禁用 集f的 极 小 延迟 交 错 集 的 数目 随 f 的 基 数囚成 指数 增 长 求禁用集f的极小延迟交错集合 b 的算法构造如下:( 递归计算) b f e b ， 逐一选择m i n i m a l d e l a y i n g a l t e r n a t i v e s ( b , i , b ) ( 简记为m d a ) i f b是f的一个延迟交错t h e n i f b 是f的一个极小延迟交错 t h e n b := b u( b ) el s e f o r b j e b 周 i d o m in .d e l.a lt e r . ( b 切, j , b ) e n d ( * f o r * ) e n d ( * i f * ) e n d ( * i f ) 0 命题3 . 4 . 1 对于已 给禁用集f 和活动j e f, 检测是否 存在f的极小延迟 检 测 含 有 j , 是n p - c o m p le te . 命题3 . 4 . 2 对于已 给活动j , . 判别j是否 含在某个 极小禁用集fe f内 也 是n p - c o m p l e t e . 引理禁用集f的一个极小延迟交错是一个包含极小集，即该集至少包括 每个极小禁 用集f c f 的一 项活动j . 证明:反证法 假设 存在一个f的极小延 迟交错b ，使得极小禁用集 f c f 有b n f = 尹 。 于 是 集 合f b = ) f 是 可 行 集 . 这 与 f是 禁 用 集 相 矛 盾 。 定义 3 .4 . 2 设b 是极小延迟交错， 则称偶对( j , b ) 为 极小延迟 方式，其中 i ea， ， a=f b。 定理 3 .4 . 1 设f为禁 用集， 则对于 每个可行调度s e s ，存在f的极小延 迟 方 式(i , b ) 满 足 s , 2 s , + p , ， ( dj c b ) e 第三章资源约束的工程调度 证明 : 设s 是可 行调度，则o ( s ) 是 可行严格序.于是根 据定理3 . 3 . 1 可 知 ， 对 于 禁 用 集f 的 所 有 禁 用 子 集f， 存 在 两 个 活 动 i , j e f， 使 得 s , _ s , 十 a- 根据引理，对于禁用集f存在一个极小延迟交错b，其中b至少包括每个 极 小 禁 用 集f 的 一 项 活 动 ， 而 且 v j e b , 3 i , e f b 使 得s , 2 s ,