（应用数学专业论文）配送运输问题的模型与优化方法.pdf

ab s tr a c t ab s t r a c t l o g i s t i c s i s t h e k e y l i n k o f e n t e r p r i s e v a l u e c re a t i o n a n d t h e v a l u e re a l i z a t i o n , a n d i t i s a l s o a n e w d o m a i n f o r e n t e r p r i s e t o r e d u c e t h e c o s t . t h e t h in g p a s s e s s m o o t h l 尹i s t h e e n t e r p r i s e s b a s i c re q u e s t a n d m a i n e m b o d i m e n t o f c o re c o m p e t i t i v e p o w e r .r e c e n t y e a r s , l o g i s t i c s ,t a k e n a s t h i r d p ro fi t re s o u r c e ,h a s b e e n d e v e l o p i n g r a p i d l y . wi t h t h e d e v e l o p m e n t o f t e c h n o l o g y 油e m o d e s a n d t h e m e a n s e n t e r p r i s e w i l l g a i n t h e c o m p e t i t i v e s u p e r i o r i t y o n l y w h e n t h e y o f c o m p e t i t i o n c o n t r a c t e d wi t h r e l a t e d c l i e n t t o f o r m t h e s u p p l y -c h a i n t o d e c re a s e c o s t a n d p r o v i d e kn i g h t i c e .l o g i s t i c s d e l i v e ry e n t e r p r i s e p l a y t h e im p o r ta n t r o l e in t h e s i d e o f t h e c o s t a n d p r o v i d i n g r a p id a n d a c c u r a t e a s t h e c a r r i e r o f ma t e r i a l :ceol 欧elm曲 咖脉sercor fl o w i n g .h o w t o l o w d i s t r i b u t io n c o s t i s c o n c e m e d .t m n s p o r ta t i o n i s t h e k e y p a rt o f t h e l o g i s t i c s d i s t r ib u t io n , s o d ec l i n e o f t r a n s p o r ta t i o n c o s t i s f o c u s e d o n . t h i s p a p e r i s n a m e d a s “ m a t c h t h e o p t i m i z a t i o n m e t h o d a n d m o d e l d i l iv e r t r a n s p o r t a t i o n p r o b l e m . i n th e p r o c e d u re o f s h o p p i n g w it h o r d e l i v e r i n g g o o d s ,t h e c o m p a n y m u s t t a k e t h e s u p p l i e r s a n d c u s t m o m e r s d i ff e r e n t r e q u i r e m e n t o f t i m e i n t o a c c o u n t , a n d s a t i s f y t h e m e ff i c i e n t l y .i n t h i s p a p e r , w e u s e t h e m i n i m i z e a n d m a x i m i z e t i m e l a g s t o d i s c u s s t h e s c h e d u l 吨p r o b l e m a b o v e a n d g iv e a t e m p o r a l c o n s t r a i n t s m o d e l t o s o l v e i t .e s p e c i a l l y w h e n t h e c u s t m o m e r s r e q u i r e m e n t o f t h e t i m e i s c o n t i n u o u s l y c h a n g e d ,w e w i l l t r a n s f o r m t h e m o d e l 勿 a d d i n g t o s o m e v a r i a b l e s . mo v e o v e r , g i v e t h e d u a l p r o b l e m a n d t h e s o lu t i o n p r o c e d u r e i t s e lf . t h i s p a p e r d i v i d e s i n t o s i x p a r t s t o t a l l y .t h e f i r s t s e c t i o n i s s i m p l e t o h a v e e l a b o r a t e d b a c k g r o u n d , m e t h o d a n d t h e re s e a r c h p u r p o s e o f a r t i c l e ; t h e s e c o n d h a s d i s c u s s e d s u p p l y b r i e fl y re l a t e d k n o w l e d g e a n d t h e c o n c e p t o f c h a i n a n d a o n n e t w o t h e p a r t o f fi ft h fl o w s a c c o r d i n g t o t h i n g t o m a t c h t h e f a s t d e v e l o p m e n t a n d c o m p u t e r s e n t ,m a t c h t o s e n d t h e h u g e a p p l i c a t i o n p r o s p e c t t h a t t r a n s p o r t a t i o n o p t i m i z a t i o n s y s t e m i s f a c e w i t h , a p p l i c a t i o n m a i 工 a b o f t h i s p a p e r c a l c u l a t e s s o ft w a r e p a c k a g e ,h a v e c a r r i e d o u t t h e v e r i f i c a t i o n o f m o d e l ; t h e p a r t o f s i x t h i s t h e s u m m a r y o f f u l l t e x t ,h a v e s u m m a r i z e d fu l l t e x t b r i e fl y e a c h z h a n g m a j o r c o n t e n t ,s u g g e s t t h a t m o d e m e n t e r p r i s e o n l y c a r r i e s o u t t o m a t c h o n t i m e t o d i l i v e r g o o d s ,c a r r y i n g o u t t o m a t c h i n t i m e s e n d , u s e r j u s t h a s r e s o u r c e a s s u r a n c e ,m a y re s t a s s u r e d l a n d e n f o r c e m e n t t h e lo w 0 s t o c k s i n s t o c k , s o r e a c h p a ir w i n s .t h i s j u s t i s h i g h h o r i z o n t a l t o m a t c h t o d i l i v e r g o o d s . k e y w o r d s : d i l i v e r g o o d s s u p p l y c h a i n a o n n e t w o r k t e m p o r a l c o n s t r a i n t s 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电 子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版; 在不以赢利为目的的前 提下，学校可以 适当复制论文的部分或全部内 容用于学术活动。 学 位 论 文 作 者 签 名 ， 麻耗 美 。 年 f ， 月7t日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 瘫 朴 奠 、 解密时间:年月，日 各密级的最长保密年限及书写格式规定如下: 义 争 二、 少尸卜j 1钊.月 内部 5 年 ( 最长5 年， 可少于5 年) 秘密1 0 年 ( 最长1 0 年， 可少于1 0 年) 机密 2 0 年 ( 最长2 0 年， 可少于2 0 年) -一一、 二 一 _ _一_一 厂 十 飞_ 挤 飞 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己 经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 己 公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均已 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名: 奋柱夹 护。 年 i i 月 珍日 第一章引言 第一章 引言 随着经济 全球化和知 识经济的到来， 无国 界化企业 经营的趋势愈来愈明显， 全球范围的 采购、 生产、销售促使市场竟争呈 现出明 显的国 际化和一体化，同 时，品种的多样化、产品寿命周期的缩短以及用户需求的个性化，导致不确定 性不断增加，加剧了市场竟争的激烈程度。严峻的市场竟争迫使生产企业集中 更多的精力从事其主要业务，提高企业的竟争力和经济效益，就必须与企业外 部相关的 供应商、销 售商、配送 运输企 业等 “ 第 三方” ， 通过优势互补， 建立起 战略伙伴关系，协同合作，共同进行供应链管理，以更大的优势参与市场竟争 以求生存，以实 现产品 和服务低成本， 无差错， 快速 有效， 高质量地传递到用 户手中。 近年来，随着物流 管理理论的充实 完善和在实践方面 探索的深入， 物流配 送运输已 成为货物运输企 业在经营方 式发 展上的高 级阶段， 成为我国 运输业在 新世纪发展的新领域、新的经济增长点。 作为供应链重要环节的配送运输，为客户提供的是个性化的服务。与公共 物流服务不同的是，配送运输企业的服务对象多为同一区域相关行业的客户， 服务时间千差万别，企业不仅要满足目前的需求，留有适当富余量以满足用户 需求合理波动所产生的额外需求，提供优质服务，还要尽量降低运输成本，确 保运输所得利润最大。也就是说协调并合理安排运输时间、运输成本与服务质 量之间的 关系就成了 该企业所要解决的问题 之一，即 配送运输问 题的模 型与 优 化方法也就应运而生. 现代物流管 理所要解决的 基本问 题，简 单地说就是 如何按时、按质、按量， 并且以 系统最低的成本费用把货物运到生产 和流 通领域中 去。当 存货在时空 上 被合理定 位、 有助于销售时，产品就会增值， 这说明 运输在供应链各环节中是 最重要的基础环节，其他环节都须在此环节的保障下合理连接构成供应链。此 外， 供应链中 很重要的 配送环节，就其实质来说是在 较小 范围 ( 较短距离)内 面向 具体服务对象 ( 用户) 的运输活动， 这也充分说明 在供应链各环节中， 运 输是构成物流价 值链最重要、最富活力 的要素。 运输不仅在现代物流过程中的 功能与作用至关重要， 而且在供应链总成本 构成中， 运输成本也是 其最重要的 组成部分。运输过 程的 优化管理成本控制对 第一章引言 整个供应链成 本的 有效控制和降 低具有决定性作 用。 运输时间 可以影响、 甚至 决定供应链上其 他企业的 盈利情况。除 运输成本、 运输速度外、 运输一 致性也 在相当 大程度上 对物流服务质量产生 重大影响。 运输速度与 运输一 致性是 运输 时效性和可靠性的 反映. 运输缺乏时 效性和可靠性就 会产生 严重的物流供 应障 碍，迫使企 业加大 安全储备存货量， 增加物流成 本、 库存成本， 增大物流风险， 甚至导致供应链的 瘫痪。因 此， 如何实 现在最短的时间内以 最低的成本提 供最 大价值，对配送运输企业本身和供应链各环节都是至关重要的。 综上所述，本文将以某物流公司为研究对象，利用现代网络优化技术，讨 论怎样协调各个环 节，实 现快速响应和 满足客户需求，以确保供应链的服务 质 量，降低运输成本，达到多盈的目的，从而兼顾社会效益和经济效益。 物流的魅力在于其潜在着很大的利润空间，只要不断挖掘，将会产生很多 意想不到的利润之源。提高物流经营水平，降低物流成本是现代物流追求的永 恒主题。本文在对物流配送业务进行详细介绍的基础上，对供应链管理过程中 出 现的 最大最小时差概念 进行了集中研究， 从而探讨某物流公司在进货和配 送 过程中， 如何高效地满足供应商和客户 对时间的 不同 要求，以 此建立时 间约束 模型，解决调度中的问题。 在建立时间约 束模型解决调度问 题的 研究中， 针对客户对运输时间的 要求 是连续变化的情况，引入了参数规划的模型和解法。最后，基于物流配送的快 速发展和计算 机配送运输调 度系统面临着的巨大 应用前景， 本文采用 m a tlab 计算软件包，进行了模型的验证。 第二章 供 应链与 物流节点 第二章 供应链与物流节点 现代物流的观 念及其 经营行为的 变革不仅 在流通领域产生了飞 跃， 而且在 制造业、运输业、批发零售业之间产生了深远的影响.物流、信息流、资金流 的 全面整合与有效 控制，实现了产品 供应链全过程的 价值和 运作的 最优化，因 此，供应链已成为企业间竞争的关键领域。于是确信的承诺、按时的交货、迅 速响应客户不断变化着的需求成为企业在竞争中不可缺少的要求.这一部分我 们将会简单介绍供应链、供应链管理方法的相关知识。 2 . 1 供应链概述 2 . 1 . 1供应链 我国 标准物流术语对供应链的定 义是: “ 供应链” ( s u p p l y c h a i n ) 是生产 及流通过程中，涉及将物品或服务提供给最终用户的上游与下游企业所形成的 网链结构。 对于 供应链， 不同 企业、 不同 领域根 据自 己不同的需要有不同的 认识。实 际上，供应链是包含物流系统在内的一个新型的流通系统，这是因为供应链的 概念广义上涉及了企业的生产、流通，再进入到下一个企业的生产、流通这样 一 种社会再生 产的 过程;中 义上涉及了一 个企 业从原材料经过供应、 生产、销 售、服务， 一直到用户的 完整经营过程; 狭义上仅仅涉及了 一个企业的 供应问 题。 供应链是一个网络结构，由围绕核心企业的供应商、供应商的供应商和用 户、用户的用户组成，每个企业都是一个节点，节点企业与节点企业是一种需 求与供应的关系。 2 . 1 . 2物流节点 物流节点又 称物流接点，是物 流网 络中连接物流线路的结节之处， 所以又 第二章供应链与物流节点 称物 流结节点。 物流结点的 种类很多， 在不同 线路 上结点的 名称也各异. 物流结点是现代 物流中具 有较重要地 位的组成部分， 这是因 为物流学形成初 期， 学 者们和实业家都比 较偏重于研 究物流若 千基本功能， 如 运输、 储存、 包装 等， 而对结点的作用认 识不足。 物流系 统化的 观念越是增强， 就越是 强调总 体的 协调、 顺畅， 强调总 体的最 优， 而结点 正 是处 在能连结系统的 位置上， 总体的 水 平往往通过结点体现， 所以 物流结点的 研究是随现代 物流的 发展而发展的， 也是 现代物流学研究不同于以往之处。 现代物流网络中的物流结点对优化整个物流网络起着重要作用，从发展来 看， 它不仅执行一般的物流 职能，而 且越来越多地执行指挥调度、信息等神经 中枢的 职能， 是整个物流网 络的 灵魂所 在，因而更加受到 人们的重视。 现代物流发展了若干类型的结点，在各个物流系统中，结点都起着若干作 用，但随整个系统目标不同以及结点在网络中的地位不同，结点的主要作用往 往不同。根据主要作用结点可分为以下几类: 1 转运型 结点。 以 连接不同 运输方 式为主要职能的结点 ; 铁道运输线上的货 站、编组站、车站，不同运输方式之间的转运站、终点站，水运线上的港口、 码头，空运中的空港等都属于此类结点。一般而言，由于这种结点处于运输线 上， 又以 转运为主， 所以 货 物在这种结点 上停滞的时间较 短。 z储存型结点。以存放货物为主要职能的结点，货物在这种结点上停滞时 间较长. 在物流系 统中， 储备仓库、营 业仓库、中转仓 库、 货栈等都是属于此 种类型的结点。 尽管不少发达国 家仓库职能在近代发生了 大幅度的变 化， 一大部分仓库转 化成不以 储备为主 要职能 的流通仓库甚 至流通中心， 但是， 在现代世界上任何 一个有一定经济规 模的国 家，为了 保证国民经济的正常 运行， 保证企业经营的 正常开展， 保证市 场的 流转，以 仓库为 储备的形式仍是不可 缺乏的，总还是有 一大 批仓库 仍会以 储备为主要 职能。 在我国， 这种类型的仓 库还占 主要成分。 3 流 通型结点。 以 组织物资 在系 统中 运动为主要职能的结点， 在社会系统中 则是组织物资流通为主 要职能的 结点。 现代物流中常提到的 流通仓库、流通中 心、配送中心就属于这类结点。 需要说明的是， 在各种以 主要功能分 类的结点中，都可以承担着其他职能 而不完全排除其他职能。 如转运型结 点中， 往往设置有储存货 物的 货场或站库， 从而具有一定的储 存功能， 但是，由 于其所处的位置，其主要职能是转运， 所 第二章供应链与物流节点 以按这主要功能归入到转运型结点之中。 4综合性结点。 在物流系统中 集中 于一个结点中 全面实现两种以上主要功 能，并且在结点中并 非独立完成各自 功能， 而是将若 干功能有机结合于一体， 有完善设施、有效衔接和协调工艺的集约型结点。这种结点是适应物流大量化 和复杂化，适应物流更为精密准确，在一个结点中要求实现多种转化而使物流 系统简化、高效的要求出现的，是现代物流系统中结点发展的方向之一。 2 . 1 . 3供应链的特点 1时代 性。 现在随 着网 络经济时代的 到来，尤 其是互联网 这个公众 平台 的 形成， 使信息 跨越过去 封闭 的界限进行传 递成为可能， 也使信息共享成为 可能 ， 这就把供应链从过去两个 环节之间的短链 延伸成跨越整个社会再生产的 长链成 为可能。 2远程性.这和经 营运作的远程化有 关。 一 个产品 从原材料的原材料开 始， 到用户的用户为止，原材料来自于全世界，生产协作企业分布于全世界，用户 需求遍布全世界，这种远程化的结果就需要新的 供应方式。现在人们已 探索出 用供应链来解决这个问题. 3复杂性。 供应链在每个环节都要根据横向择优的原则，选择多个协作企 业，整个供应链不但有很长的链节还有很多结点。 4择优性。 供应链的结点企业根据自己 的核 心竞 争能力，同时参与多 个供 应链，作为一个结点或链节。 5面向 用户需 求。 供 应链的 形成、 存 在、 重构， 都是基于一定的 市场需 求 而发生的，并且在供应链的运作过程当中，用户的需求是拉动供应链中信息流、 服务流 、资金流的驱动源。 6交叉性。 节点企业可以是这个供应链的 成员，同时 也可以是另一个供 应 链的成员，众多的供应链形成交叉结构，增加了协调管理的难度。 此外供应链还具有虚拟性的特点， 可以 通过组织 协作的 方式，依托信息网 络的支持，使这个虚拟的企业保持很高的竞争能力。 第二章 供应 链与 物流节点 2 . 2 供应链管理的 基本内 容 在全球供应链中，管理者必须随时 准备应付以 下情况发生: 产品 在市场上 领先性的丧失，昂贵的运输费用，过高的库存水平，销售预测不准确，以及在 解决技术 难题中的滞后，所有这些问 题的 解决， 都必须要有一套对于整个供应 链各个环节的有效而协调的管理策略. 供应链管理 ( s u p p l y c h a i n m a n a g e m e n t . s c m )从单一的企业角度来看， 它是指企 业通过改善上、 下游供应链关系， 整合和优化供应链中的 信息 流、物 流、资金流，以获得企业的竞争优势。 现在， 供应链管理是将整个企业商务 流程和商务价值进行优化。从 供应商 的供应商到 客户的 客户， 供应链管理采用了电 子商务的理念、 信息技术、网 络 技术去管理企 业内 部、 上游客户 和下游客 户。 在这里， 从最初的产品设 计到原 材料的采购，通过生产，装运，分销，仓贮，直到最终产品传递到客户，商业 循环中每一个步骤都体现了完整性与协调性。所以，现在所说的供应链管理， 实际上是使供应链形成整合的、一体化的商业行为方式。这种有效的商业行为 方式， 充满着 种种的 挑战，需要企业 精心策 划、 精心实施才能得以 实现。 这就 是现代供应链管理的思想，也称为整合的供应链管理。 供应链管理是企业的有效性管理，表现了企业在战略和战术上对企业整个 作业流程的优化。它整合和优化了供应商、制造商、零售商的业务效率，使商 品以正确的数量、正确的质量、在正确的地点、以正确的时间、以最佳的成本 进行生产和销售，实现总成本最小或总收益最大。 一般地，可以 将供应 链管理分为内 部供应 链管理，包括企业内 部的 采购， 计划，制造，销售及其相互间的协作关系;外部供应链管理指供应商链各个环 节间的协作关系。 供应链管理的目 标即是通过调和总成本最低化，客户服务最优化，总库存 最少化，总周期时间最短化以及物流质量最优化等目标之间的冲突，实现供应 链绩效最大化。 第三章aon网络简介 第三章 a o n网络简介 在项目 计划管理中 仅仅满足于编制出 项目 进度计划， 并以 此来进行资源调 配和 工期控制是远远不够的， 还必须依据主、 客观条 件， 在满足工期要求的同 时， 合理安排时间 与资 源， 力求达到资源消 耗合理和经 济效益最佳。研究工程 在给定时间内完成活动，首先需要讨论活动间的最大最小时间间隔;其次需要 考虑工程的节点活动网络设计，进而讨论时间约束问题。 在活动网络技 术中，有两种方法，一种是早期发展起来的弧活 动法 ( a c t iv ity - o n - a r r o w m e t h o d . a o a方 法) ， 用箭 线表示活动， 节点连结箭 线以示依 赖关系， 这种方法也叫双代号网 络图 ;一种是七十年代中期发 展来的 节点活 动 法( a c tiv ity - o n -n o d e m e th o d .a o n 方 法 ) ， 用节 点 代 表 活 动 而 用 节 点 间 箭 头 表 示 活动的 依赖关系，这种方法也 叫单 代号网 络图。 a o n工程网 络以a o n为 基础， 运用时差 来描述出 最早 开始 ( 结束) 时间 s s , s c 和最迟开始 ( 结束) 时间c s , c c 。 在a o n网络中， 最早 ( 迟) 开始时间 和最小 ( 大)时间作为其基本参数，可以反映活动与紧前活动的优先关系，这 点上a o n网络比a o a网络具有更多的优点。 3 . 1 最小 ( 大)时差 设工 程由n 0 个不可中断的 实际 活动构 成， 此外引 入虚活动0 , n + 1 分别表 示工程的开 始和结束。 活动0 , 1 , 2 ,， n + 1 分 别用网 络 节点0 , 1 , 2 ,， n + 1 表示， 这样v = ( 0 , 1 , 2 ， 二， n + l 既是 活动集， 又是网 络的节点 集。 a o n 网络，即活动用节点来表示的网络. 设君 为 活 动i 的 处 理 时 间(d u r a t i o n o r p r o c e s s i n g t i m e ) ， 其中 p o = p . i = 0 . 只e n ， 进 而， 设又- 0 为活 动 i 的开 始时间， 其中虚活 动0 , n + 1 的开始时间分 别 是s o : = 0 ,嵘， : = t , t 为 工 程 周 期 。 通常用s s ( s t a r t - t o - s t a r t ) 关系定义 活动间的 优先关系。 类似地，可以 引 入 c s ( c o 口 p l e t i o n - t o - s t a r t ) , s c ( s t a r t - t o - c o m p l e t i o n ) 和c c ( c o m p l e t i o n - t o - c o m p l e t i o n )时差， 这四 种时差可以 容易的 相互转换。 第三章aon网络简介 定 义1对 两 个 活 动i , j , 给出 时 差罗 e z _ 0 来 定 义 它 们 之间 的 关 系 : 凡一 s , _ d 尸 (3 .1 ) 即 活 动 j 不 能 在 活 动i 开 始 d 尸个 单 位 之 前处 理， 锣 称 为 最 小 时 差 图3 . 1活动 a a ; : 1 与活动 间的最小时差 示意图 若 活 动 j 可 以 在活 动i 刚 完 成 便开 始， 则 楞 = p , ， 式( 3 .1 ) 表 示 一 个 先 后 约束; 若活动 可以 在活 动i 完成之前开始，则活 动i 和活 动j 可以 交错， 并且 有楞 _ 0 时 间 活 动i 应 该 完 成， 若 终 止 活 动i 仅 需 要 在 工 程 结 束 时 完 成 ， 则d tn , = p i k - p,c_- 呈岁-4 ) d ， 拭 图3 . 3终止活动 i 的最小时差示意图 3 设 活 动i 是 非 终 止 活 动 ， 若 对 于 每 个 实 际 活 动j 具 有d 尸， 而 且 d 尸+ 君 _ d .。 同 样， 若 活 动i 不 是 终止 活动 ， 但希 望在 工程 终 止前q , e z ? 0 时间 完 成，则j 黑 。 ， q j + 君 ， 即 s n+ 1 一 s , _ d , + , 定 义3 对 两 个 活 动i , j , 还 存 在 最 大 时 差 d , e z _ 0 s i 一 s , s d y 这 是 指 活 动 j 开 始 不 能 迟 于 活 动i 开 始d 尸时 间 单 位 ( 3 . 2 ) 第三章aon网络简介 匡二】! :5 d 图3 . 5活动1 与活 动 间 的最 大时差示意图 关于最小、最大时差的几点说明: 1在 实 际中 ， 君 ， d n., d n-通 常 假 定 为 整 数， 时 间 度 量 取 分 、 小时 、 天 等， 然而， 所有讨论的内 容都可以由 实数 来替 代而无困难。 2假 定 最 小 、 最 大 时 差 为 非 负 数 并 不 失 一 般性 。 若 有鳄 0 ， 根 据 ( 3 . 1 ) 式 可 得 : s , 一 s i 5 d 笋 这表示对于活 动 j ， 1 有正的最 大时 差。同 理，负的最大时 差可以由 正的最小时 差替 代。 ( 令d j 0 = - d y- 0 ) 3假 设 己 给dd 尸和d 尸_ 犷 ， 则 对 于 活 动i 于s , 开 始 后 活 动j 开 始 的 时 间 窗口为: s ,十 尸 s /十 d o- 其窗 口 长 度 为 产 - d 尸之 0 . 4若s i 一 s , - 0 ， 于 是s , - s , 。 ， 即 活 动i 不 能 在 j 之后 开 始， 因 此 ， 锣 := o 或 i . = 0 成 立 。 5 若 几 个 活 动同 时 开 始 ， 如s l = sh = s h = 一 s ,. i i f2 i .二 i. ， 那 么可以这样给出 d 罗:=:=d 忽. :=0 而 且d 犷 := o s y 一 s ti 5 d 罗 s ,. 一 s ., d e 综上可得 第三章aon网络简介 s 、 一 凡 j m a + d m u 两种特别的最大时差: 已 给 活 动i 的 截 止 时 间 妈e n , 试2 只 ， 即 活 动i 应 在 试 之 前 完 成， 换 言 之 ， 活动i 最晚 在工 程开始之后的d 黔 : - 试一 君 这段时间 开始。 工 程 开 拍 ， - d 黔 ! ! ! 一 一洲心 一-1 4 图3 .6截止时间为试的活动i 的最大时 差示意图 若 活 动i 在 工 程 结 束 之 前 最 早s ; e n s , 2 p , ) 时 间 开 始 ， 则 71 , := s . 工 程 结 束 武 : ,= s : 图3 .7在工程结束前开始的活动 i 的最大时差示意图 3 . 2 最大 ( 小)时差的 应用 在实际中的时间约 束问 题可以 借助最小、 最大时 差来表示， 例如: 1 活 动i , j 先 后 执 行 ， 没 有 延 迟， 即 s i - s , = p , ， 这 个 约 束的 保 证 可以 引 入 俨 = p , , 而 且d 尸声 p r 若 活 动i , j 同 时 开 始， 则 令罗 r d - = 0 0 2 若 活 动i 恰 在t, e z 2 。 时 开 始， 则 令d - :- d o-, - t , . 同 理 可以 引 入 严 格 在 某时 终 止 ( 令d o r = d o. := t , 一 p r 即 可) . 3 若 活 动i 最 早 在t , e z _ 。 开 始 ， 而 最 迟 在t , e z 2 。 开 始 ， 则 令4 .7 := t ;r ， d .- ,:= t r 第三章aon网络简介 由于时差是关联这两个活动的开始时间，因而称为s t a r t - t o - s t a rt时差。 类似 地，可以引入 c o m p l e t i o n - t o - s t a r t . s t a rt - t o - c o m p l e t i o n和 c o m p l e ti o n - t o - c o m p le ti o n时 差。 这四 种时差 可以 容 易 地互 相 转换， 作为一 个例子， 将 c s 时差转换为s s 时差，反过来也一样。 设 s s d 尸和 s s d -为 原 来 的 时 差s s . 而 c s d 尸和 ,9 d 黔为c s 的 时 差 ， 设 g , = s ; + 君 为活 动i 的 完 成时 间， 于是 c s d . _ s i 一 c , 5 c s d - ( 3 .3 ) s s d - s i 一 s , s s d - ( 3 .4 ) 由式 ( 3 .3 )有 c s d s i 一 s , 一 p , 5 c s d , c s d , + p , 5 s , 一 s , _ c s d y- + p , 根据式 ( 3 .4 )可以 ( 假定最小时差，最大时差是唯一的)定义: c s d y- = s s d 尸一 p , c s d 尸= s s d y-一 p , ( 3 .5 ) 式 ( 3 . 5 )的证明通过图示显然成立。 s ; 一 c ; 时差与c s 时差转换示意图 is ps 图3 . 8 类似地，可将s c时差， c c时差分别转化为s s 时差。 下面将s c时差转化 为s s 时差。 设 c , = 凡+ p , 为 活 动 .1 的 完 成 时 间 ， 于 是 第三章ao n网 络简介 s c d , q一 s , s s d 尸 _ s ， 一 s , s s s