（应用数学专业论文）带有日程表约束的资源受限工程调度.pdf

p r o j e c t s c h e d u li n g h a s a t t r a c t e d a n e v e r g ro w i n g a t t e n t i o n i n r e c e n t y e a r s b o t h fr o m s c i e n c e a n d p r a c ti ce.t h i s p r o b l e m c a n b e d e s c r i b e d a s b e l o w : w e s c h e d u l e t h e a c t i v it i e s o n w h ic h t h e re a r e d i f f e r e n t ty p e s o f t i m e c o n s t r a i n t s s u b j e c t t o a r b i t r a ry ( e v e n t i m e d e p e n d e n t ) re s o u r c e c o n s t r a i n t s i n o r d e r t o m e e t t h e o b j e c t i v e f u n c t i o n o p t i - m a l . p ro j e c t s c h e d u l i n g i s v e ry i m p o r t a n t f o r m a k e - t o - o r d e r c o m p a n i e s w h e re t h e c a p a c - i ti e s h a v e b e e n c u t d o w n i n o r d e r t o m e e t s c a r c e re s o u r c e . l i k e w i s e , p r o j e c t s c h e d u l i n g i s v e ry a t t r a c t e d f o r re s e a r c h e r s ,b e c a u s e t h e m o d e l s i n t h i s a r e a a re r i c h , d i ffic u l t t o s o l v e a n d e x t e n s i v e l y a p p li e d .t h e d e v e l o p m e n t o f s c i e n c e c a n p r o m o t e t h e p r o g r e s s o f t e c h - n i q u e s . c o r r e ti y u s i n g t h e m e t h o d s o f p ro j e c t s c h e d u l i n g c a n h e l p t h e c o m p a n i e s m a k e r e a s o n a b l y d e c i s i o n s , o r g a n i z e p r o d u c t i o n a n d i n t e n s i f y m a r k e t c o m p e ti ti o n . a c c o r d i n g t o m o d e rn m a n a g e m e n t c o n c e p t s , th i s a r t i c l e p ro v id e s t h e m o d e l o f t h e p r o b l e m o f re s o u r c e - c o n s t r a i n e d p r o j e c t s c h e d u l i n g w i t h t h e c a l e n d a r i z a ti o n ( t o b e b r i e f d e n o t e t h e p ro b l e m c a l e n d a r i z a ti o n ) a n d m a k e s t h e o re t i c a l a n a l y s i s o f t h e m o d e l . a l s o , t h i s a r t i c l e p res e n t s t h e d e s i g n o f t h e b r a n c h - a n d - b o u n d m e t h o d t o s o l v e c a l e n d a r i z a ti o n . i t c a n p r o v i d e f e a s i b l e w a y s a n d t e c h n i q u e s f o r t h e c o m p a n i e s i m p ro v i n g t h e i r m a n a g e m e n t k e y w o r d s : re s o u r ce c o n s t r a in t s ,b r a n c h a n d b o u n d m e t h o d ,s c h e d u le , t e m p o r a l 南开大学学位论文版权使用授权书 本 人完全了 解南开大学关于收集、 保存、使用学位 论文的 规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本; 学校有 权保 存学 位论文的印 刷本和电 子版， 并采用影印、缩印、 扫描、数字化或其它手段保存论文; 学校有权提供 目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门 或者机构送交论文的复印 件 和电 子版; 在不以 赢利为目 的的 前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : - l t 4 - 2 叫年 上月 z 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教 师签名: 姜碱 学位论文作者签名: y tl 7 解密时间: 年月日 各密级的最长保密年限及书写格式规定如下: 内部 5 年 ( 最长5 年，可 少于5 年) 秘密1 0 年 ( 最长1 0 年，可 少于1 0 年) 机密2 0 年 ( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名: 艰, it砍 年 夕月z 日 第一章 引言 第一章 引言 近年来， 无论从科学研究还是实际应用方面， 工程调度日益引起人们的关注。 这是因为工程 ( 也称项目) 的内 涵非常广泛， 小到一栋楼房的 建设、 一项具有创 意的广告活动， 大到新产品的研制开发与推广、 关系民生的社会工程都属于工程 概念的范畴， 这些工程都可以用工程调度的思想进行统筹和安排， 因此工程调度 科学广泛的应用到电力， 水利， 化工， 生产制造等部门。 其中应用最多的是建筑 业和制造业。 工程调度问题可以描述为: 在满足资源紧缺的情况下， 将在时间上受限于各 种约束关系的活动遵循目 标函数最优排序。 工程调度问 题对按订单生产的企业来 讲意义重大， 企业组织生产必须具有资源稀缺的 经营理念; 同样的， 它也吸引了 学者们的视线， 因为这个问题的模型非常丰富且应用广泛。 在某种程度上， 许多 熟知的优化问题都是调度问 题的特例。比如， 作业 ( 生产计划) 调度问题， 建筑 业最小化工期问 题都属于调度问题的范畴. 除此之外， 从计算效率来考察， 工程 调度也是非常具有挑战性的。 近年来， 工程调度的发展迅速， 研究者创作了大量 的 三段式标记来区分识别不同 类的 调度问 题， 另一方面， 一些工程调度的学者在 三段式标记中用不同的符号表示同类问 题。 由 于这个问题的各类模型和记号没有 统一的 标准， 表示方法混乱无章， 致使我们在查阅资料时， 不清楚文献中符号表 示的 哪 类问 题。 这促使我们必须对这个问 题记号 作统一的 标准。 h e r r o e l e n e t a l . 1 最早对这个问题进行了研究， 遗憾的是他们的设计与我们普遍接受的机器调度问 题不一致. 此后， b r u c k e r e t a l . 2 给出了 统一的 模型和记号， 填补了 机器调度和 工程调度之间的缺口. 这篇文章采用了 b ru c k e r 等人的记号， 我们在第一章简要 叙述工程调度不同类型问题的模型， 记号和求解方法. 随着学术研究的 进展， 工程调度理论和方法日 趋成熟. 科学的发展推动了 技 术的 进步， 工程调度已 越来越多的应用到实践中， 为我们的管理、 决策和生 产给 予指导. 现代社会市场竞争日 益激烈， 生产制造领域的精益生产也不断深化， 这 促使企业必须运用科学的生产与管理方法不断提高运作效率， 增加利润， 增强市 场竞争力。 本文正是根据企业现代化管理这一实际问 题， 提出了加入日 程表约束 的资源受限工程调度问题的数学模型， 并对该模型进行理论分析和论证。 本文研 第一章 引言 究的是可中断活动的最小执行时间取正整数的情形， 同以前的调度问 题， 活动开 始、 结束时刻， 执行周期， 最大、 最小时间延迟均取整数值， 具体内容将在第三章 给出。 此外本文在第四章给出了求解日 程表约束资源受限工程调度问 题的分枝定 界算法及算法设计， 为企业提升管理效率提供了可行的方法和技术。 第二章 资源受限工程调度问 题的概述 第二章 资源受限工程调度问题的概述 2 . 1 活动网络 活动网 络( a c t i v i t y n e t w o r k ) 是工 程调度主要借助和讨论的 基本对象， 是对 工程项目 的 一种图 形 化描 述方式 3 。 顾名思义， 活动网 络就是由 活动组成的网 络， 这个网络中 还表达了 活动间的关系以 及活动所需的资源. 活动网 络的基本元素包 括: 活动， 活动间的 关系， 资源。 一个工程项目 有很多 活动组成， 这些活动也常常被称为作业、 任务、 操作等。 为了 达到工程目 标， 每个活动的实施将采用某种执行模式， 而每个活动的执行模 式可能只有一种， 或者是从几种候选的执行模式选取一个， 而活动的执行模式决 定了活动实施的一种途径， 在这个模式中有对应的活动执行周期以 及活动所需的 各种资源的量以 及活动的 执行( 处理) 中 将要发生的 现金的流入和流出。 工程项目 是一个系统， 因此， 活动之间存在内在的逻辑关系， 这种逻辑关系 由 两方面决定， 一个是工艺关系， 另一个是组织关系。 逻辑关系反映了活动执行 的先后顺序， 这种先后顺序可以是紧密衔接的， 也就是说一个活动完工后紧接着 可以开始另一个活动， 称为结束一 开始关系， 也可以是更具一般性的表达方式， 即 活动之间的关系属于4 种关系中的 一种: 开始一 开始， 开始一 结束， 结束一 开始， 结 束一 结束。 工程活动需要多种资源的投入才能完成， 根据再生性的不同， 资源分为四种 类型: 可再生资源， 不可再生资源， 双重约束资源和部分可再生资源。 可再生资 源在工程的每一个周期都会形成约束， 这些资源在数量上受限， 但是在每一个周 期的开始， 它们均可再次使用， 比 如人力资源和机器资源。 大部分研究考察的 都 是这类资源。 不可再生资源的可获性对于整个工程周期而言， 不对某个时段进行 限制。 每一个单位的不可再生资源一旦使用了， 在剩余工期内不再恢复。 比如工 程的投资预算。 双重约束资源不仅在每个时刻有约束， 而且整个工期内 存在全局 约束。 现金常被视为双重性质资源。 部分可再生资源是随着每个周期子集的变化， 第二章 资源受限工程调度问题的概述 这些资源可再次使用， 而在每个周期的子集中不可重用。 2 . 2 活动网络的描述 活动网络的描述有两种形式: a o a 网络图， a o n 网络图， 二者都是有序的连 通图， 然而后者应用广泛. 这篇文章采用了a o n 形式， 下面作简单的解释. 一般的， 设 工 程包含 n 个作业( 活动) ， 记为1 , 2 , . . . , n . 为了 研究问 题的 方便， 引 入唯一的 开 始活动 。 和 结束活动。 + 1 ， 工 程结构 用 a o n ( a c t i v i ty - o n - n o d e ) 网 络图 来描 述， 其中 节点 表示活动， 弧表示活动间的 优先约束， 可用i 一 9 或( i , j ) 表示 则 g=( ve ) 表 示由 优 先 约 束导出 的 工 程网 络图 。 定 义 p r e 武 匀 为 活 动 的 紧 前 活 动 集， 而 s u c c ( i ) 为 活 动 i 的 紧 后 活 动 集. 定 义 x=( -x 1 , 0 2 , . . . , o n ) 为活 动1 , z , . . . ， 。 的 处理时间向量。 而且假设活动在处理过程中不能中断， 即活动2 一旦开始执行， 则 必须不间断的 处理， 直到活动执行完毕. 这个假设通常满足实际调度问 题的 背景。 我们在处理活动的时候， 往往需要借助某种资源，比如人力， 机械， 反应器 等等。 第一章对资源作了分类， 接下来给出 每类资源的记号: 可再生 ( 更新) 资 源r p ， 不可再生 ( 更新) 资源r i ， 一般的， 不对双重性质资源作专门的记号， 因 为它包含在上两种资 源中。 如果只能按照一种方式执行活动， 则称调度问 题为单 模式 工 程 调 度， 在 此 情 形 下， rv=0 。 记 ( p i 为 活 动 的 处 理时 间 ， 记 凡为 每 单位时 间 可 再 生 资 源 k 。 9 2 p 可 使 用 量 的 上限 ， 哎为 活 动 i 使 用 资 源 k 的 数 量， t 为 给 定 的 工程工期。 不失一般性， 假设上述参数均取整数. 特别的， 如果活动的执行模式 有多 种选择， 则 称调度问 题为多模式工程调度。 在此情形下， 记f l i 为活动该 模式 集 合， 即 活 动 葱 的 可 选 执 行 模 式的 集合， 活 动 葱 对 应模 式 。 的 处 理时 间 为 ， 。 ， 单 位时 间 可 用 的 可 再 生 资 源 k 的 数 量 为 呱 ， 整 个 活 动 处 理 期 间 可 用 的 不 可 再 生 资 源 k 的 数 量 为 r il l ， 而 瑕 记 整 个 工 程 期 间 不 可 再 生 资 a k kv的 使 用 上 限 。 不 失 一 般 性 ， 上述参数也取整数。 活 动的 处 理( 执 行) 即 是 确 定活 动的 开 始 时间 和 执 行模 式， 记 s i ( 叼为 活 动 i 的 开 始( 结 束) 时 刻， 相 应 地， s =( 8 1 , 8 2 , ， ) 是 一 个调 度， c=( c i , c a , ， ) 是 完成时 刻的向 量。 v t , v r 分 别记时间， 资 源可行调度的 集合， 从 而， w =w t n v r 则 为 可 行 调 度 的 集 合 . 符 号 d ijrn in 与sd j - 表 示 活 动 , 7 开 始 时 刻 之 间 的 最 小 与 最 大 时 差 第二章 资 源受限工程调度问题的 概述 ( 即时间延迟) 。 所有的时刻和时差参数也取整数值。 2 . 3 资源受限工程调度问题的分类 h e r r o e l e n 的 分 类 方 案借鉴了 三段 标记 法形 如 a lq 卜 ， b r u c h e r 也 采 用了 这 种 表 示( 该标记法是由 g r a h a m 和b l a z e w i c z 创立的) 。 下面简要介绍三断的描述内容. 段a 表示资 源属 性， 至多 包含三个参数: a l , a 2 , a 3 。 其中 a l 表示资源的 种类， 它可能 是空的或 者标记为 ， 也 可能是 一种资 源或者 m 种资源; a 2 表示资源种 类的 性质， 即 可再生资 源、 不可再生资 源、 双重性质资 源和部分可再生资 源; a 3 描述 资源的 可得性， 通常是对于可再生资 源而言的， 若资源可得量固定不变， 参数记 为 ， 随时间变化的记为v a 。 举个例子， 符号与表示意义如下: p s单模式工程调度 p s m , 00。 种可再生资 源， 可用资源量无上界限 制( 即无资源约束) p s m , o , p单 模式工 程 调 度， 。 种 资 源， 每 单 位时 刻 至多 可 用o 单 位， 每个活动至多 可用 p 单 位 m p s多模式工程调度 m p s m , a , p ; f c , ,r , w 种不可再生资 源， 整个 工程最多可用二 单位， 每个活动至多可用。 单位 段a 描述工程调度问 题中的活动属性. 参数/3 l 表示活动在处理过程中能否被 中断， 如果活动可中断， 则在中断周期后的某一时段恢复执行。 资源受限工程调度 问 题 大多 考察 活动 不可中 断的 案例， 本文研究 考虑了 活动可中 断的 情形; 参数02 表 示活动的 紧前关系约束特征。 如果 参数 )3 a 为 p r e c ， 表示紧前关系是严格的 。 延 迟完 成一 开 始关系， 与 c p m / p e r t 假设相同; 如果 参数 逸为t e m p ， 表示一般的带 有最小 和最大 延迟的 情形; 除 此之外， 段 0 还包括表示活动处理时间的 参数， 工期约 束的 参数。 例如: i n t r e e , o u t t r e e , t r e e 所有活动的处理时间均是1 活动的处理时间随机的， 不确定 工程工期 活动间具有0 延迟完成一 开始时间约束 活动间的优先约束分为链， 入树， 出树， 树等 活动的最大和最小时间延迟确定的广义时间 约束 段， 描述工程的绩优评价， 即是工程调度问 题的目 标函 数。 一般的， 目 标函数 第二章 资源受限工程调度问 题的 概述 取正则函数或非正则函数， 比 较典型的正则函数是工程工期c . ， 本文取此函数 作为衡量标准。 下面给出正则函数的定义: 定 义2 3 . 1 设工 程有n 个 活动 ， c=( c 1 , c 2 , . . . , c n ) 是活 动完 成时 刻 的 向 圣， s = ( 8 1 , 8 2 . . . . . . 9 . ) 为 资 源 约 束 调 度问 题的 一 个 可 行 调 度， 侧s ) 为 其 最 小 化目 标函 数 ， 如 果 s ) 是 s 的 单 调 递 增 函 数 ， 即 若 s s ， 则 有 到 s ) 到 匀 ， 也 就 是 c ; 44 , i e 1 1 , 2 , . . . , n ， 而 且 3 j e 1 , 2 , - , n s .t .c j t ) 可在 o ( b i ) 内 得 到. 由 于活动的处理过程中 存在中断， 所以 活动的开始时刻和完成时刻之间不存 在一一对应关系。 因 此， 给定活动i 开始时 刻s i ， 其完成时刻不能 利用b a r t u s c h 1 3 的 公式。 这儿， 我们做个假设， 要求活动云 只能在中断周期的开始时刻被中断， 且当 此中 断 周 期 结 束 后， 活 动 i 立即 继 续 处 理. 这 表明 ， 若 b i ( t ) =1 ， 则 活动 i 在时 刻 t - 定在处理加工， 因 此， 给定 活动i 的 开 始时 刻s i ， 其完成时 刻以s i ) 唯一 确定， 由 ci(si) = ii11rt : 、 + ， .厂 bi(t )d t = p i ( 3 . 4 ) 计算可得。 由 上式易得， 日 程表约束工程调度问 题中， 活动的 完成时刻c i 依赖于其开始 时 刻 s i 和 活 动日 程 表 b i . 对可中 断 活 动 e v y i , c , ( s i ) 一 s i ? p i ; 不 可中 断 活 动 i e v ,i . c i ( s i ) 一 s i = p o 3 . 1 . 2 .小与最大开始. 开始时间延迟 同活动的完成时刻类似， 活动间的 最小与最大开始一 开始时间延迟也与日 程 表 相 关 我 们 引 入 时 间 延 迟 日 程 表 b 。 来 描 述 d i-j 与 成 罗 理 o 通 常 ， 我 们 在 建 立 问 题 模型时， 可以根据问 题的实际背景将它们一一确定。 一般的， 我们可以取最小时 间 延 迟 心 的 时 间 延 迟日 程 表 b ij 与 b i 或 b i 一 致， 但 最 大 时 间 延 迟 i 的 时 间 延 迟 日 程 表 b i i 需 单 独 描 述 ， 因 为 它 往 往 包 含 活 动日 程 表 b , 的 空 闲 时 间 ， 其中 ， 活 动 h 恰 好位于工程网络n 的 脚到 9 的 一条路中. 举例如下: 例3 . 1 . 1 假设活 动 i , j 沐 之间 的 开 始 ， 开始时间 延 迟关系 如图 3 . 2 ， 其中 姗” = 第三章 日 程表约束资源受限工程调度问 题的 模型 图 3 .2 活 动 i , j , h 的 开始一 开 始时间 延迟 关系图 b i ( t ) , b j ( t ) , b h ( t ) 一一嘴 )一 一 一 -一叫 曰一-一. -， ， 望 b h ( t ) -一-一习一一 -一-习. ， ， ， ， ， ， ， ， ， ， ， ， b i ( t ) , b j ( t ) 图 3 .3 活动 , j , h 的中断日 程表 2 , d h- j-=1 , i = 3 , p i =3 , p h =2 , p j = 么并 且 活 动 , j , h 均 是 可 中 断 活 动 ， 活 动i , j 具 有相同 的中 断日 程表， 三者具体的 活动中 断日 程 表如图 3 .3 所示. 这儿， 日 程表仅描述了 从t =0 至1 3 的中断情形. 假设活动i 的开始时刻已 经确定，不舫设s i = 0 ，定义活动间的最小时间 延 迟 d i-h i , 渺 对 应 的 时 间 延 迟日 程 表 分 别 是 活 动 的 中 断 日 程 h i , b h . 此 外 ， 从 图 3 .2 中 知 道 ， 活 动 i , j 之 间 存 在 开 始 开 始 最 大 时 间 延 迟 记弓 “ ， 由 于 存 在 n k i 到 j - 条 路 ， 活 动 h 恰 好 为 路 中 节 点 ， 因 此 不 能 定 义 正 ij 0 z 对 应 的 时 间 延 迟日 程 表 为 b i ， 若 否， 则会产生冲突. 由 于 s i = 0 , d ih i a = 2 ， 所以 活动 h 满 足时间 延迟 关系 的 最 早开 始时 刻大 于 等 第三章 日程表约束资源受限工程调度问 题的模型 于 2 ， 对照时间 延迟日 程表认 ， 得到e s n =5 .同 样的方法得到活动j 满 足时间 延 迟 渺 = 1 的 最 早 开 始 时 刻 e s j = 8 , 若 定 义 碍 “ 对 应 的 时 间 延 迟日 程 表 为 b i , 又 因 为 成 罗 0 s = 3 , 得 到 l s j = 4 , 与 上 比 较 得 e s i = 8 4 = l s ? ， 矛 质 . 由 上面的 分 析知 道: 给定 b ij ， 若 要确 定活 动的 总 处理时间， 仅考 察介 于活 动 的 开 始时 刻 与 活 动 j 的 开 始时 刻 之间 的 并 且满 足 b ij 二1 的 时 刻 即 t : = t b ij =1 , t 位于 活 动 i 和 j 的 开 始时 刻的间 隔内 ( 3 . 5 ) 如 果 、 0 , 玛=1 恒 成 立 ， 即 是我们以前接触的最小和最大时间延迟无日 程表约束的情形。 通过上段的分析， 我们得到: 由 最小和最大开始一 开始时间延迟导出的活动葱 和 活 咖的 开 始时 刻 s i 与 s i 之 间 的 真 实 时 差 气依 赖 于 活 动 的 开 始 时 刻 s i 和日 程 表 b i j ， 式子表示如下， 。 (、 ， :一 m in t _ 0 ， ebij(-r)d rss : 、 ， 一 、 (i, j) e e ) (3.6) 这 儿 ， 如 果 活 动 i f l j 的 开 始 时 刻 之 间 存 在 最 小 延 迟 ， 令 b ij : = d m inij: 如 果 活 动 和 j 的 开 始 时 刻 之 间 存 在 最 大 延 迟 ， 令 i ii := - d 7。 则 s i + d ij ( 8 i ) 是 区 间 (s i , t ) 或 t , 8 i ) 上 的 总 处 理 时 间 大 于 等于 】b ij ! 的 最 早时 刻。由 于 t - 0 , b i ( t ) 0 , 1 恒 成 立，因 此a ij ( s i ) i _ ib ij i ， 且 ij ( s i ) 与 i ii 具 有 相同 的 符 号。 由 此， 得到日 程表约束工程调度问题必须满足的又一个时间约束: s i 一 ， a ii ( s i ) (4 f b =i(t )d 7-“ “ ( ( 2 , i ) e + ) ( ( i l l ) e + ) ) 若 i ii 0 . 上 式 表 示 活 动 f i li 的 开 始 时 刻 之 间 的 时 间 间 隔 厂 b i7 ( t ) d - 大 于 等 于 i ii ; 否 则 ， 表 示 活 动 i 和 i 的 开 始 时 刻 之 间 的 时 间 间 隔 一 刀 b ii ( 二 ) d : 小 于 等 于 一 i ii 。 因 此， 给 定 活 动 的 开 始时 刻s ; ， 活动 .9 的 满 足约 束 ( 3 . 8 ) 的 最小 开 始时 间 9 i 为 t ， 且 t :一 m in t : ” ，厂 bii(t)dr : 、 ( 3 . 9 ) 令 b +i 表 示日 程 表 b ii 的 中 断 次 数， 给 定 活 动 葱 的 开 始时 刻 s i ， 活咖的 开 始时 刻s ; 可以 在 o ( b ii ) 时间 内 得到. 第三章 日 程表约束资源受限工程调度问题的模型 通过3 . 1 . 1 和3 . 1 .2 的 分析， 我们得出日 程表约束资源受限工程调度问 题所要满 足的日 程表约束为 l 咧一 1 l j s , b ij ( ,r ) d r 6 l ( v , 二 s i , s i 十 ) ) ( ( i , j ) 任 e + ) ) ( 3 . 1 0 ) 3 .2 工程的工期 一般的， 工程的 工期是预先给定的， 如果建立模型时， 这个量是未知的， 我 们可用下面的方法计算最小工期的上界a ，以此粗略估算工程的工期。 方法与无 日 程 表 约 束的 调 度问 题 类似， 我 们比 较 活 动 e v ) 处 理时间 的 上界 p ; 与 活动 i , j 间 ( 其中 ( i 1 j ) e ) 的 实 际时 间 延迟的 上 界 风， 对 较大的 值作 和， 用 这 个和 值 估 算 工 程 工 期。 但 是 ， 由 于日 程 表 约 束 调 度问 题中 c i 和 凡与 活 动 i 的 开 始 时 刻 s i 有 关， 因此， 在计算a 之前， 需要预先给定一个日 程表可行调度。 无日 程表约束的 调度 问 题则 不同 ， 直 接 将活 动i 的 处 理时间 p i 和活 动 i , j 间( 其中 ( i , 力e ) 的 时间 延 迟i ii 代 入公 式 a: 一 艺-(p i, m a x(i,j )e e b ij ) 计算即可。 计 算日 程 表约 束 调 度问 题的 最小 工 期的 上界 a 分 为 两 步: 首 先 对 v ( i , j ) e e , 任 意 给 定 s i ( e s i ) ， 确 定 a ij l s i ) 的 上 界 凡， 如 果 i ii 0 ， 由 a ij ( s i ) 叼得 匈 d ii ( s i ) ; 否 则 ， 凡取 介 于 活 动 i 的 开 始时 刻 州= t ) 和 满 足 t t + 凡的 最早时 刻 t 之间的 最大 延 迟， 即 取 值为 ij ( t ) 二 扩 一 t ， 这 ) l t 是 满 足区 间t , 约 上的 总 处 理时 间 为 4的 最 早时 刻。 由 此 得到 ， 8 ;凡 e e , 八9 闭 否则 ( 3 . 1 1 ) 其次， 计 算 活动 v ) 的 处 理时 间 的 上 界 p ; . 给定 活 动 r 的 一 个 可能的 开 始时 刻 ， 我 们 唯 一 确 定 其 完 成 时 刻 ci ( s t ) ， 从 而 可 以 得 到 实 际 的 处 理 时 间 为 p + ( s t ) = g ( s t ) 一 s t , 然 后 对上 述 p t ( s + ) 求 最大 值， 即 为 p t a 然而， 活 动 的 开 始时 刻 是 未 定的， 这 是 我 们 第 一 步需要 确 定的 . 由日 程 表 约束 条 件 ( 3 .3 ) 知 道: 给 定 t ( _ e s t ) ， 活动 的 最 早开始时 刻s t jt 是满 足条件 h t t , t +动， b , ( 月=1 恒成立的 最小的 t _ t . 从 第三章 日 程表约束资源受限工程调度问题的模型 而， p i ( s i ) = m i n i , _ i c i ( t ) v t t , t + e i ) , b i ( 二 ) =1 恒 成 立 一 t ， 再 对 其 求 最 大 值即可。 式子表示: a :一 麟 臀 c, (t ) 1 b- t , t + e i ) , b i ( 。 一 1 恒 成 立 一 t ( 3 .1 2 ) 由上面的分析， 我们得到: 如果日 程表约束资源受限工程调度问题存在日 程 表可行调度， 将其代入( 3 . 1 1 ) 和( 3 . 1 2 ) ， 得到该问 题的最小工期的 上界为 j := 艺m a x (p i , 们 自x j c s u c c ( i ) 凡)( 3 . 1 3 ) 3 . 3 资源约束 活动处理需要特定的资源， 取自 资源集合9 t 。 这篇文章研究日 程表约束下， 单 模式活动处理模式资源受限 调度问 题。 即处理活动时仅使用可再生资源。 资源供 给和活动对资源的需求情况由资源报表给出， 分别称为资源供给报表和活动需求 报表。 一般的， 每种资源的可使用量是有上界限制的， 而且在整个工程执行周期 内资源的供给可能随着时间的 变化而变化， 不是一个常值， 通常用分段常值函数 资表示资源报表。 例如， 资源k 8 t 的供给表示如下: i l k : 0 , 司一 n 其中 r k ( t ) 表示 在工 程 执 行周 期 某时 刻 t 可以 使用的 资 源k 的 数 量。 类 似的 ， 活 动 需 求报表也用分段常值函数表示。 例如， 活动i 的对资源k 任 况 的需求表示如下: r i ,k : 0 , 闪 一 n 其中 r i ,k ( t ) 表示活动 的 开 始时 刻 后， 处 理周 期的 第t 时 刻， 活 动 对资 源 k 的 需 求. 为了表示的方便， 我们引入虚活动和时间约束， 对资源供给报表做一转化， 将分段常 值函数转化成整个工程周期上的常值函数。 以资源供给报表r i 为例， 具 体操作如下: 1 . 首先将工程工期按资源供给分成若干段， 满足每个时间 段的资源供给数量是 常 值 不 妨 设0 , z i i , z 1 , 司， ， z-, a 1 是 其上 资 源 供 给是 单 个常 值的 区 间 ， b 1 , b 2 , , b m + l 是对应区间 上的 资 源供 给量。 2 . 计算 m “: =m a x b l 海， ， 娠+ i 1 4 第三章 日 程表约束资源受限工程调度问 题的模型 3 . 其次， 对 每个 b k b . “ 的 子区 间 z k - 1 , z k j 引 入虚 活 动 凡， 其中 虚活 动 q k 的 处 理 时间 为 p 6 k =z k 一 x k _ 1 ， 对资 源 i 的 需 求 为 r o k ,i = 一 奴 ， 而 且 必修 满 足 时间 约 束s o k =8 0 + z k - 1 ( 严 格固 定活 动的开 始时 间) 。 这样， 在 每 个低供 给 区间引入虚活动， 令其处理时使用虚设的资源。 4 . 最后， 将分段常值函数转化成整个工程周期上的常值函数。 即令 r i : 0 ,一 b . 以前研究的工程调度， 活动的处理过程不允许中断， 活动对资源k 的需求报 表也可以仿照上面的方法， 将分段常值函数转化成整个活动周期上的常值函数， 具体参 考 1 3 。 这里， 日 程表约束资源受限 工 程调度中 ， 某些活 动处 理过程中 允许 中断， 所以我们对活动的需求报表不作处理。 显然， 任意调度若是资源可行的， 必定满足: 工程处理的任意时刻使用资源 的 数 量， 都 不 超出 资 源的 供给 量一 般的， 我 们 用 r i 替 代 记 号 b - , r k ( s , 幻 表示 对 于给定调度s ， 在时刻t 正在处理的活动对资源k 的总需求量， 得到日 程表约束工 程调度问题的资源约束为 r k ( s , t ) r k ( k r , o t _ b ;1 ( ( i , j ) e e + ) ) r k ( s , t ) 凡( k e r , o t 司 8 0 =0 由于日程表约束资源受限工程调度问题有资源稀缺的限制， 属于资源约束工 程调度问 题的一类， 因此我们可得下面的定理: 定理”. 1日 程表约束资源受限工程调度问 题是n p一h a r d 问 题. 为了 证明这个定理， 我们首先做个准备工作: 表述证明中涉及的定义与定理。 定义3 . 3 . 1如果一个问 题的每一个实例只有“ 是” 或“ 否” 两种答案， 则称这 个问 题为判定问题. 称有肯定答案“ 是” 的实 例为“ 是” 实例， 称答案为“ 否” 的 实例为“ 否” 实例或非“ 是” 实例. 定 义3 . 3 . 2 对一 个 ，# i 定问 题， 若 存在 一