排序与统筹方法MNEW

第十一章 排序与统筹方法统筹方法统筹方法1 车间作业计划模型车间作业计划的基本概念计划模型I计划模型II1.基本概念车间作业计划:指一个工厂生产工序的计划和安排.:现有n个零件需要加工,加工时间分别为Pj,安排在第j位加工的零件在车间里总的停留时间Tj:Tj=P1+P2+Pj1.基本概念平均停留时间:前n个零件的总时间为:T1+T2+T3+Tn,平均停留时间为(T1+T2+T3+Tn)/n2.模型I一台机器,N个零件:零件加工时间(小时)零件加工时间(小时)11.840.922.051.330.561.5如何安排加工顺序,才能使得这六个零件在车间里停留平均时间为最少?零件加工时间Pi 停留时间Tj零件加工时间Pi停留时间Tj11.81.840.95.222.03.851.36.530.54.361.58按1、2、3、4、5、6顺序加工零件，各个零件平均停留时间为：(1.8+3.8+4.3+5.2+6.5+8)/6=4.93随意排:123456零件加工时间Pi 停留时间Tj零件加工时间Pi停留时间Tj30.50.551.33.4+1.3=4.722.02.561.56.240.9.25+0.9=3.411.88按1、2、3、4、5、6顺序加工零件，各个零件平均停留时间为：(0.5+2.5+3.4+4.7+6.2+8)/6=4.22按324561的顺序加工:零件加工时间Pi 停留时间Tj零件加工时间Pi停留时间TjN1Pn1Pn1N4Pn4T3+pn4N2Pn2pn1+pn2N5Pn5T4+Pn5n3pn3T2+Pn3N6Pn6T5+pn6按n1、n2、n3、n4、n5、n6顺序加工零件，各个零件平均停留时间为：(T1+T2+T3+T4+T5+T6)/6=(p1+(p1+p2)+(p1+p2+p3)+(p1+p2+p3+p4)+(p1+p2+p3+p4+p5)+(p1+p2+p3+p4+p5+p6)任意顺序:n1,n2,n3,n4,n5,n6:按n1、n2、n3、n4、n5、n6顺序加工零件，各个零件平均停留时间为：(T1+T2+T3+T4+T5+T6)/6=(p1+(p1+p2)+(p1+p2+p3)+(p1+p2+p3+p4)+(p1+p2+p3+p4+p5)+(p1+p2+p3+p4+p5+p6)=(1p6+2P5+3P4+4P3+5P2+6P1)/6=(6p1+5P2+4P3+3P4+2P5+1P6)/6要使平均停留时间最少,只要系数大的时间短即可.即要对加工时间:任意顺序:n1,n2,n3,n4,n5,n6:本题加顺序:3,4,5,6,1,2时间:0.5,0.9,1.3,1.5,1.8,2.0停留时间:0.5,1.4,2.7,4.2,6.0,8.0各个零件平均停留时间为:3.83.模型II两台机器,n个零件:零件车削磨床零件车削磨床11.50.541.252.522.00.2550.751.2531.01.75先削后磨,如何安排加工顺序,才能使得完成这五个零件的为最少?车床12345磨床12345先车削,后车磨0.50.251.52.01.01.250.751.752.51.25按FCFS：先来先服务。12345车床53214磨床53214先车削,后车磨1.250.250.751.02.01.51.251.750.52.5按53214如何确定加工顺序,才能总加工时间最少?事实上总费时多的原因是第二台机器需要等待,要延时多,而第一台并不需要延时。因此，要减少尽少磨车床中零件的加工等待时间。一方面要把短时间的车削加工往提前排，另一方面，要把磨床上加工时间短的越晚加工，把磨床上加工时间长的往后延。零件 车削磨床工序零件 车削磨床工序11.50.541.252.522.00.2550.751.2531.01.75加工顺序零件号534120.2 5,0.5,0.7 5,1.0,1.2 5,1.5,2.0,2.5两台机器,n个零件的排序问题1.在加工时间表上选出最短加工时间tij,其中i为工序,j为零件号,当为i=1时,将零件J的加工顺序尽量靠前,若i=2时,将零件j的加工顺序尽量靠后;2.在表上划去零件j的所在行，回到步骤练习题：，New:p279.1,2网络图1435cdbea2622322 统筹方法一、计划网络图二、网络时间与关键路线三、完成工序所需时间不确定时 的网络时间与关键路线四、网络优化一、计划网络图网络计划技术的基本概念网络图的绘制一、计划网络图基本概念：工程：一项施工任务、科研试制项目、生产以及较复杂的工作任务，统称为工程。工序：为了完成某项工程，在工艺技术和组织管理上相对独立的活动称为工序。如：车床削、磨，两个工序，用a,b表示。一、计划网络图基本概念：事件事件：表示一个工序的开始或结束，它是相邻工序在时间上的分界点，用编号表示。网络图网络图：由工序、事件及标有完成各道工序所需时间等参数所构成的有向图，就是网络图。例1：某公司研制新产品的部分工序与所需时间以及它们之间的相互关系如下表：试画出其统筹方法网络图。工序代号工序内容所需时间紧前工序A产品设计与工艺设计60-B外购配套零件15AC外购生产原料13Ad自制主件38Ce主配件可靠性试验8B,d二、网络图的绘制网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。工作名称时间12A60ij一个科研项目网络图12345a60c13e8b15d38例2：某公司研制新产品的部分工序与所需时间以及它们之间的相互关系如下表：试画出其统筹方法网络图。工序代号工序内容所需时间紧前工序工序代号所需时间紧前工序A产品设计与工艺设计60-F10DB外购配套零件15AG16DC外购生产原料13AH5E,f,gd自制主件38Ce主配件可靠性试验8B,d一个科研项目网络图12356a60c13e8b15d384f10一个科研项目网络图12356a60c13e8b15d384f107h5g16一个科研项目网络图12357a60c13e8b15d384f108h5g166二、网络图的绘制从开始节点到结束节点的一条路经叫做路线一个网络图的有多条路线，每条路线有一个总时间总时间最长的路线叫做关键路线，关键路线的总时间叫做工期看下面的例子网络图的路线当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是网络图的画法作业的串联作业的并联网络图的画法作业的交叉作业的合并绘制网络图的基本原则两事件间只能有一项作业改为绘制网络图的基本原则网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线不能出现缺口尽量少交叉，采用暗桥；有层次性。使用暗桥网络图的绘制步骤确定目标，做好准备工作任务分解和分析绘制网络图表4-1 调查项目的任务分解和分析作业代号 作业说明周期(天)紧前作业A系统地提出问题4-B研究选点问题7 AC准备调研方案10 AD收集资料，安排工作8 BE挑选和训练调研人员12 B、CF准备有关表格7 CG实地调查5 D、E、FH分析调查数据，写调查报告4 G绘制作业图的方法试探性绘制法计算机辅助绘制法流程图过渡绘制法试探性绘制法：试探试探性绘制法：修改流程图过渡绘制法：流程图流程图过渡绘制法：加事项流程图过渡绘制法：去方框流程图过渡绘制法：修改二、网络时间与关键路线从网络图中求出：完成此工程项目所需的最少时间；每个工序的开始时间与结束时间；关键路线及其相应的关键工序；非关键工序在不影响工程的完成时间的前提下，其开始时间与结束推迟多久。例5 某公司装配一条新的生产线。工序代号工序内容所需时间紧前工序A生产线设计60-B外购零配件45AC下料、锻件10AD工装制造120AE木模40AF机械加工118CG工装制造230DH机械加工215D,eI机械加工325Gj装配调试35B,I,f,h12457a60c10i25b45d206h158j35g303e40f18寻找关键路线：（1）从网络起点按顺序计算出每个工序的最早开始时间（ES）和最早结束时间（EF）1260A0,60对同一个工序：EF=Es+t;对相邻工序：EF=ES（Max）+t1245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,170寻找关键路线：（2）从网络收点开始计算出每个工序的最迟（晚）开始时间（LS）和最迟（晚）结束时间（LF）对同一个工序：LS=LF-t;对相邻工序：LS=LF-t1245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,17035135,17025110,13515120,1354080,1203080,11018117,1354590,13510107,1172060,80600,60寻找关键路线：（3）计算出每个工序的时间差TS TS=LS-ES=LF-EF,对工序B来说，TS=90-60=30工序在60-90天之内任何时间内开工，都不会影响工期。称为非关键工序。对工序g来说，TS=80-80=0不能提前，也不能推后，否则会影响总工期。称为关键工序。例5 某公司装配一条新的生产线。工序最早开始ES最晚开始LS最早完成EF最晚完成LF时差关键否A0060600是B609010513530NC601077011747ND606080800是E608010012020F701178813547G80801101100是H10012011513520I1101101351350是j1351351701700是1245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,17035135,17025110,13515120,1354080,1203080,11018117,1354590,13510107,1172060,80600,60得关键路线：Adgij三、完成工序所需时间不确定时的网络时间与关键路线：如果完成工序所需时间不确定的情况下怎样来求网络时间和关键路线？例6。某培训中心准备对各部门领导干部进行培训。活动工序活动内容紧前活动A 制定培训计划-B选聘培训教师AC列出可选培训点-D确定培训点CE确定培训的日程安排B,dF落实教学设备、资料EG发培训通知及确定学员名单b,dh订旅馆房间Gi处理最后的一些事务F,h 通过调查的时间估计：活动工序乐观时间最可能时间悲观时间A1.52.02.5B2.02.56C123D1.522.5E0.511.5F123G33.57h345i1.522.5要求：绘出统筹方法的网络图，设法求出网络时间和关键路线。12345678iabcdegfh 统筹方法网络图一、先画出网络图：二、工序（活动）时间：乐观时间（全绿灯）：顺利情况下，完成活动所需时间-a 最可能时间（正常）：指正常情况下，完成活动所需时间-m悲观时间（很不顺）：指在不顺利情况下，完成工作所需时间-b。作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差工序时间计算方法6/)(64abbmaTe分布amb平均时间平均时间按期完成计划的概率每项作业的时间是一个随机变量，近似服从 分布，均值和标准差为工期也是一个随机变量，它的期望值为各关键作业时间期望之和。6/)(64),(ijijijijijabbmajiT按期完成计划的概率当作业数足够多时，工期近似服从正态分布),(2KTNT按期完成计划的概率其中按期完成的概率222664KKKPiiiPiiPiiiiKabbmaT)(21)(2/2KDTTzDTTdzeTTPKD12345678ia0，2bcdegfh 统筹方法网络图一、先画出网络图：2b0，22a0，222421224a12345678ia0，2bcdegfh 统筹方法网络图一、先画出网络图：2b0，22e5，622421224ag5，9c0，2d2，4f6，8h9，13i13，1512345678ia0，2bcdegfh 统筹方法网络图一、先画出网络图：2b2，52e5，62421224ag5，9c0，2d2，4f6，8h9，13i13，15213，15211，1349，13110，1145，923，521，332，520，2例5 某公司装配一条新的生产线。工序最早开始ES最晚开始LS最早完成EF最晚完成LF时差关键否A00220B22550C01231D03451E2106115F6118135G55990H9913130I131315150YesYesYesYesYes12345678ia0，2bcdegfh关键路线：abghi:平均时间的总和：2+3+4+4+2=152b2，52e5，62421224ag5，9c0，2d2，4f6，8h9，13i13，15213，15211，1349，13110，1145，923，521，332，520，2由于完成培训工作所需时间是一个随机事件，是可变的，它服从一定的概率分布，根据概率论知识，各工序的时间服从分布，那么完成整个任务的时间和近似服从正态分布，从而可以估计不同守工时间的概率。例如，E(T)=Ta+Tb+Tg+Th+Ti=15,2=各方差之和=1.05那么完成整个工作的时间服从N(E(T),2)的正态分布.因此,可以利用此分布来估计在一定时间内完成整个工作的可能性.培训工作的平均完成时间为E（T）（约15周），波动变化反映在幅度方差为2，具体完成的时间是动态变化不确定的。那么我们可以根据时间服从N(E(T),2)的正态分布来估算完成时间的可能性（概率）即利用此分布来估计在一定时间内完成整个工作的可能性.如：上述平均时间是15周，2=1.05,那么,培训工作能在16周内完成的可能性有多大?835.0)976.0()(976.0025.11025.11516025.105.1)(),(22查标准正态分布表tETNT如果要以99%的把握来保证培训工作如期完成,那么应在几周前开始准备?39.1733.2025.115)(33.2)1,0(,99.0)(,%99),(22TTTETNNT得查意即的把握完成任务要求以由于如果要以99%的把握来保证培训工作如期完成,那么应在几周前开始准备?如果要以100%的把握来保证培训工作如期完成,那么应在几周前开始准备?125.205025.115)(599.4)1,0(,1)(,%100),(22TTTETNNT得查意即的把握完成任务要求以由于四、网络优化 得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。划方案。工期限定，资源需要平衡资源有限，工期希望最短工期缩短，总费用最小四、网络优化 1.时间时间-资源优化资源优化 做法：做法：1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。综合平衡。下面列举一个拉平资源需要量最高峰的实例。在例下面列举一个拉平资源需要量最高峰的实例。在例5中，中，若加工工人为若加工工人为65人，并假定这些工人可完成这人，并假定这些工人可完成这5个工序任一个工序任一个，下面来寻求一个时间个，下面来寻求一个时间-资源最优方案。如表资源最优方案。如表12-16所示：所示：工序需要工人数最早开工时间所需时间时差D5860200F22701847G4280300H391001520i26110250安排d-i各工序的总人数为651245760c10i25b45d206h15天8j35g303e40f18d58人f22人g42人i26人h39274635 f(22人）人）18h(39人人)1558人人64人人80人人81人人42人人26人人65人人60 80 100 120 130 d(58人）人）i(26人）人）g(42人）人）302025图图12-1710dd+fF+ggG+hH+ii607080901001101201305880人644281人6526人607080901001101201305880人644281人6526人工序需要工人数最早开工时间所需时间时差D5860200F2270801847G4280300H391001101520i26110250安排d-i各工序的总人数为65idF+ggH+i607080901001101201305864426526人 同时我们应优先安排关键工序所需的工人，再利用非关键工序的时同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序们让非关键工序f从第从第80天开始，工序天开始，工序h从第从第110天开始。找到了时间天开始。找到了时间-资源资源优化的方案，如图优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完所示，在不增加工人的情况下保证了工程按期完成。成。2.时间-费用优化工期不变，就是关键工作时间不能调整资源不平衡将导致资源不足利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。2 2 统筹方法统筹方法2.时间时间-费用优化费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间是时间-费用优化要研究和解决的问题。费用优化要研究和解决的问题。直接费用：为了加快工程进度，必须设法缩短关键工序的时间，这样需直接费用：为了加快工程进度，必须设法缩短关键工序的时间，这样需要增加人力、设备和工作班次，从而需要增加一笔费用，成为直接费用。要增加人力、设备和工作班次，从而需要增加一笔费用，成为直接费用。间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。称为间接费用。一般说工序越短，直接费用越多，间接费用越少。2 2 统筹方法统筹方法 工序的最快完成时间：指完成时间的最高限度。工序的最快完成时间：指完成时间的最高限度。我们设完成工序我们设完成工序j的正常所需时间为的正常所需时间为Tj;直接费用直接费用为为cj;完成工序完成工序j的最快完成时的最快完成时间为间为Tj,直接费用为直接费用为cj。这样我们可以计算出缩短工序。这样我们可以计算出缩短工序j的一天工期所增加的直接的一天工期所增加的直接费用，用费用，用kj表示，称为直接费用变动率。有表示，称为直接费用变动率。有 时间时间-费用优化问题可建立两个线性规划模型。费用优化问题可建立两个线性规划模型。模型一，在既定的时间模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。缩短工期而增加的直接费用最少。设工序（设工序（i,j)的提前完工时间为的提前完工时间为Yij,我们用我们用Tij,Tij分别表示正常完工时间与最快分别表示正常完工时间与最快完工的时间，则有工序（完工的时间，则有工序（i,j)的实际完工时间为：的实际完工时间为：Tij-Yij。我们。我们用用Cij,Cij表示用正表示用正常完工时间和最快完成时间完成工序所需要的费用，常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（为工序（i,j)的直接费用的直接费用变动率。得到这个问题的线性规划模型如下：变动率。得到这个问题的线性规划模型如下：minf=（Kij*Yij)（i,j)S.t.Xj-Xi Tij-Yij,对一切弧（对一切弧（i,j)Yij Tij-Tij,对一切弧对一切弧（i,j)Xn-X1 T,Xi 0，Yij 0。jjjjjTTcck2 2 统筹方法统筹方法例例7.例例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。所示。表表12-17工序工序Tij正常正常完工完工Cij直接直接费用费用Tij最快最快完工完工Cij直直接费用接费用直接费用直接费用变动率变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-2 2 统筹方法统筹方法 该工程要求在该工程要求在150天内完工，问每个工序应比正常完工时间提天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要最少。如果工期要求在求在140天完工呢？天完工呢？12345678abfechgijd图图12-192 2 统筹方法统筹方法解：绘出如图解：绘出如图12-19所示，根据此网络图建立数学模型。所示，根据此网络图建立数学模型。设此网络图上第设此网络图上第i点发生的时间为点发生的时间为xi，工序提前完工的时间为，工序提前完工的时间为yij。目标函数目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x1 60-y12,x7-x2 45-y27 x3-x2 10-y23 x4-x2 20-y24 x5-x2 40-y25 x7-x3 18-y37 x6-x4 30-y46 x5-x4 0虚拟弧（虚拟弧（4，5）x7-x5 15-y57 x7-x6 25-y672 2 统筹方法统筹方法 x1=0,y12 0,y27 15,y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 x8 150 xi 0，yij 0.（对一切可能的（对一切可能的ij)运算得到结果运算得到结果：f=6400。2 2 统筹方法统筹方法 模型二，我们知道直接费用是随着完成时间的缩短而增加，模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为费用为d,计划期的间接费用与总工期成正比，即为计划期的间接费用与总工期成正比，即为d(xn-x1),那么那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间完成时间T和各个工序最优完成时间的模型为：和各个工序最优完成时间的模型为：目标函数目标函数min f=d(xn-x1)+s.t.xj-xi Tij-yij，对一切弧，对一切弧（i,j)yij Tij-Tij，对一切弧（，对一切弧（i,j)xi 0，yij 0。j)(i,ijij)y(k2 2 统筹方法统筹方法 例例8 如果在例如果在例7中，每天的间接费用为中，每天的间接费用为330元，求使包括间接费用与直接费用元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。和各个工序最优完成时间。解：决策变量的含义同例解：决策变量的含义同例7。此数学模型的目标函数为：此数学模型的目标函数为：min f=330(x8-x1)+120y27+300 y23 +400y24+500y25+230y37+350y46+290y67 此模型的约束条件与例此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去掉的约束条件基本相同，只要在例子的约束条件中去掉x8 150就得到了例就得到了例8模型的约束条件了。模型的约束条件了。计算得到以下结果：计算得到以下结果：f=55700.x1=0,y12=0,y67=10,x2=60,y27=0,y78=0.2 2 统筹方法统筹方法x3 =125,y23=0,x4=107,y24=0,x5=110,y25=0,x6=110,y37=0,x7=125,y46=0,x8=160,y57=0,也就是说整个工程工期为也就是说整个工程工期为160天时总费用最少为天时总费用最少为55700元，各个元，各个工序开始时间如解所示，工序工序开始时间如解所示，工序 i 要提前要提前10天完工，其余的工天完工，其余的工序按正序按正常时间完工。常时间完工。习题P281 习题 1-7本章结束。Thanks 一个例子各工作都按最早开始时间开始调整非关键工作的开始时间资源有限，要求工期最短下图表示的项目只有10人工作第一次调整第二次调整工期缩短，总费用最少一般情况下，若采取措施缩短工期，则间接费用将减少，直接费用将增加，总费用由一个最低点。直接成本的处理按线性处理，作业的费用率为CNNCTTCCP图4-52 一个例子ij),(PTTNC解题思路以正常时间进行网络分析，求得关键路线在关键路线上，寻找最小费率的工作，缩短其时间，使工期最多到次长路线的长度。缩短工期必须对所有关键路线进行，此时应选择费率总和最小的组合方案。第一步求关键路线作业(1,2)(2-3)(3-4)费率313工期=11天第二步选择(2,3)缩短工期工期=10天增加费用1可选方案IIIIII缩短的作业(1,2),(1,3)(2,3),(1,3)(3,4)总费用率3+1=41+1=23第三步按第I方案缩短工期工期=9天增加费用1+2=3再按方案III缩短周期可选方案III缩短的作业(1,2),(1,3)(2,4),(3,4)总费用率3+1=41+3=4工期=8天增加费用3+3=6第四步按第I、II方案缩短4天工期=4天增加费用6+16=22调整(1,2)与(2,3)，并缩短(3,4)工期=3天增加费用22+5=27总合算费用，绘制直接费用图工期111098743增加直接费用0136102227总费用最小的优化一般应考虑间接费用，工期缩短，总的间接费用减少例如，上例中，间接费用率为：4.5/天，则因为最后一部直接费率5/天4.5/天，因此最后一步的工期不能缩短，工期应为4天，此时可节省费用3.5+1.5+4*0.5=7。事项参数的计算事件（项）最早时间事件（项）最迟时间0)1()()(maxEijEiETTiTjTiiijT)()()()(minnTnTTjTiTELijLiL图上计算法矩阵法计算事项时间TL0414 14 14 26 3135TE004407 101130814007140 12260531043501425368172536847作业时间参数的计算作业开始最早时间作业结束最早时间作业开始最迟时间作业结束最迟时间总时差单时差作业最早时间作业最迟时间),(),(),()(),(jiTjiTjiTiTjiTESEFEES),(),(),()(),(jiTjiTjiTjTjiTLFLSLLF时差),(),(),()(),(),(),(),(jiTkjTjiTjTrjiTjiTjiTjiTREFESEFEijLSLFESLSij总时差单时差时差之间的关系表4-3 作业时间参数计算作业时间T(i,j)开始 结束开始 结束A4-04040B7 A4117143C10 A4144140D8 B111918267E12 B,C142614260F7 C142119265G5 D,E,F263126310H4 G313531350作业代号最早时间最迟时间总时差紧前作业关键路线的确定方法总时差为零的作业即是关键作业，关键作业构成关键路线破圈法也可采用最长路线法。