资源受限讲义.pptVIP

资源受限工程调度问题分类、模型与算法 刘士新 东北大学系统工程研究所 2002年9月20日 报告主要内容 问题简介 问题举例 问题的参数特性 SRCPSP的数学描述 SRCPSP的优化方法 MRCPSP的数学描述 MRCPSP的优化方法 DTCTP的数学描述 DTCTP的有效工期/成本曲线 DTCTP的优化方法 SRLP的数学描述 SRLP的优化方法 MRLP的数学描述 MRLP的优化方法 RCPSP/Max问题 存在问题及进一步的发展方向 谢 谢！ Page * * 学术讨论报告 资源受限工程调度问题分类、模型与算法 资源受限工程调度问题简介 单执行模式资源受限工程调度问题（SRCPSP） 多执行模式资源受限工程调度问题（MRCPSP） 离散时间/成本权衡工程调度问题（DTCTP） 单执行模式资源水平问题（SRLP） 多执行模式资源水平问题（MRLP） 带最小/最大时间滞后的资源受限工程调度问题（RCPSP/Max） 产生：PERT、CPM考虑资源限制因素 应用：建筑工程、软件开发、单件或小批量生产企业 面向工程（Project- oriented）管理、制造方式出现 理论意义：NP—Hard问题 存在问题：传统集中的、顺序结构的调度、控制方法 资源分类： 可更新资源：机床、劳动力资源 不可更新资源：能源、原料 双重约束资源 一个可行的执行模式选择： (1,1), (2, 2), (3,2) ,(4,1), (5,2), (6, 1), (7,1), (8,1) 一个不可行的执行模式选择： (1,1), (2, 1), (3,1) ,(4,1), (5,1), (6, 1), (7,1), (8,1) 网络复杂性 可更新资源因素 不可更新资源因素 可更新资源强度 不可更新资源强度 精确算法 分支定界 启发式算法 基于优先规则：串行调度、并行调度 样本算法：根据优先系数确定被调度概率 智能优化算法：GA、SA、TS、Hybrid 编码：工作编号、优先权系数、优先规则 解码：串性调度方案、并行调度方案 临域解的产生：交换基因、变异 其它优化方法 基于启发式的整数规划 精确算法 分支定界：由SRCPSP扩展而来 启发式算法 基于优先规则：工作模式组合的优先规则 智能优化算法：GA、SA、TS、Hybrid 编码：双链表结构，（工作顺序，执行模式）、 （执行模式，优先权系数）、 （执行模式、优先规则） 解码：串性调度方案、并行调度方案 临域解的产生：交换基因、变异 动态规划算法 分支定界算法 遗传算法（GA） 编码：工作执行模式链表 解码： 临域解： 适值函数：惩罚不可行解 启发式算法 基于优先规则 遗传算法 基于分支定界策略的近似算法 利用SRLP和SRCPSP问题的相似性 解的形式相同 约束条件基本相同：紧前关系、资源 SRLP的最优计划对应某资源约束下的SRCPSP的最优计划 采用分支定界策略 资源从基本需求开始逐渐增加，基本需求值计算方法如下 遗传算法 基于分支定界策略的近似算法 利用MRLP和MRCPSP问题的相似性 采用分支定界策略 增加了更复杂的工作间相互关系约束：最小/最大时间滞后 Start—Start Start—Finish Finish—Start Finish—Finish 传统PERT/CPM存在的问题 时间参数的估计 CP没考虑资源约束 问题：执行前、执行中（学生综合症、摩非定律）、执行后 考虑资源约束后 执行过程中的意外：重调度？调整计划？ 一种解决办法：戈德拉特提出的TOC在项目管理中的应用 优点：强调人性化管理、改进企业文化 对静态调度的执行提供了动态的保护方法 缓冲区（时间缓冲、资源缓冲）、关键链 Drum——Buffer——Rope