12第十二章 排序与统筹方法电子课件.pptx

《12第十二章 排序与统筹方法电子课件.pptx》由会员分享，可在线阅读，更多相关《12第十二章 排序与统筹方法电子课件.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学第十二章第十二章 排序与统筹方法排序与统筹方法北京理工大学 韩伯棠 教授2第十二章排序与统筹方法排序与统筹方法 本章包含车间作业计划模型和统筹方法。这两个问题尽管处理本章包含车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。最少等等）

2、。 3车间作业计划模型车间作业计划模型统筹方法本章内容本章内容124 1车间作业计划模型车间作业计划模型一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题二、两台机器、二、两台机器、n n个零件的排序问题个零件的排序问题车间作业计划是指一个工厂生产工序的计划和安排。车间作业计划是指一个工厂生产工序的计划和安排。5 1车间作业计划模型车间作业计划模型例例1.1.某车间只有一台高精度的磨床，现有六个零件同时要求加工某车间只有一台高精度的磨床，现有六个零件同时要求加工，六个零件加工所需时间如下表所示。应该按照什么样的加工顺，六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加

3、工，才能使得这六个零件在车间里停留的平均时间为最少序来加工，才能使得这六个零件在车间里停留的平均时间为最少？一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题零件加工时间（小时）零件加工时间（小时）1231.82.00.54560.91.31.56 1车间作业计划模型车间作业计划模型设设Pi表示安排在第表示安排在第i位加工的零件所需的时间，位加工的零件所需的时间，Tj表示安排在第表示安排在第j位加工的位加工的零件在车间里总的停留时间，则零件在车间里总的停留时间，则例例1 解：解：jiijpPPPT121j.可知这六个零件的停留时间为：可知这六个零件的停留时间为： T1 + T2

4、 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6.7 1车间作业计划模型车间作业计划模型那么各个零件平均停留时间为那么各个零件平均停留时间为623456654321PPPPPP总结：一台机器总结：一台机器n个零件的排序问题个零件的排序问题 只要系数越大，配上加工时间越少的，即按照加工时间排出加只要系数

5、越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。在越后面，可使各个零件的平均停留时间为最少。例例1中按照中按照3,4,5,6,1,2的顺序加工零件，则各个零件的平均停留时间最少的顺序加工零件，则各个零件的平均停留时间最少8 1车间作业计划模型车间作业计划模型二、两台机器、二、两台机器、n n个零件的排序问题个零件的排序问题例例2.2.某工厂定做一些零件，这些零件要求先在车床上车削，然后某工厂定做一些零件，这些零件要求先在车床上车削，然后再

6、在磨床上加工，每台机器上各零件加工时间如下表所示。应该再在磨床上加工，每台机器上各零件加工时间如下表所示。应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？工时间为最少？零件车床磨床123451.52.01.01.250.750.50.251.752.51.259 1车间作业计划模型车间作业计划模型解：如果这些零件在车床上和磨床上加工顺序都为解：如果这些零件在车床上和磨床上加工顺序都为1 1，2 2，3 3，4 4，5 5。我们用。我们用下面的线条图来表示各零件加工的开始时间与完成时间。下面的线条图来表示各零件加工

7、的开始时间与完成时间。 123451车车床床磨磨床床2345010由图得，加工时间的延长主要是由于磨床的停工待料造成的，只要减少由图得，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。磨床的停工待料的时间就能减少整个加工任务的总时间。10 1车间作业计划模型车间作业计划模型 在该表中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2 所在行。如表中红色线条所示。 零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二

8、工序）零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）1231.52.01.00.50.251.75451.250.752.51.25接着，又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件1所在的行划去。如表中黄色线条所示。 下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所示。下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排

9、在第二位上，同时把零件3所在的行划去。如表中黑色线条所示。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。寻找例寻找例2 2的最优解：的最优解：11 1车间作业计划模型车间作业计划模型总结：关于两台机器总结：关于两台机器n n个零件的排序问题个零件的排序问题 步骤步骤1 1：在加工所需时间表上选出最短加工时间：在加工所需时间表上选出最短加工时间tij，这是第，这是第i i工工序加工序加工j j 零件所需时间，当零件所需时间，当i i=1=1时，将零件时，将零件j j 的顺序尽量靠前，的顺序尽量靠前，若若i i=2=2时，将零件时，将零件j j的顺序尽量靠后。的顺

10、序尽量靠后。 步骤步骤2 2：在表上划去零件：在表上划去零件j j的所在行，回到步骤的所在行，回到步骤1 1。12车间作业计划模型统筹方法统筹方法本章内容本章内容1213 2统筹方法统筹方法 统筹方法可以应用在各种不同的项目计划上，特别适用于生统筹方法可以应用在各种不同的项目计划上，特别适用于生产技术复杂，工作项目繁多且联系紧密的一些跨部门的工作计划产技术复杂，工作项目繁多且联系紧密的一些跨部门的工作计划，例如，新产品的研制开发，工厂、大楼、高速公路等大型工程，例如，新产品的研制开发，工厂、大楼、高速公路等大型工程项目的是建设，大型复杂设备的维修以及新系统的设计与安装等项目的是建设，大型复杂设

11、备的维修以及新系统的设计与安装等计划。计划。 统筹方法包括绘制计划网络图、进度安排、网络优化等环节统筹方法包括绘制计划网络图、进度安排、网络优化等环节 14 2统筹方法统筹方法一、计划网络图一、计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。活动）进度表转换为统筹方法的网络图。工序代号工序内容所需时间（天）紧前工序abcde产品设计和工艺设计外购配套零件外购生产原料自制主件主配可靠性试验601513388-aacb，d 例例3 3、某公司研制新产品的部分工序与所需时间以及它们

12、之间的相互、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表关系都显示在其工序进度表如表12-812-8所示，请画出其统筹方法网络图。所示，请画出其统筹方法网络图。 表表12-8 15 2统筹方法统筹方法用网络图表示上述的工序进度表用网络图表示上述的工序进度表 点表示一个事件点表示一个事件 弧表示一个工序弧表示一个工序 abcde601383815图图12-4abcde601383815图图12-4abcde601383815abcde601383815abcde601383815abcde60138381516 2统筹方法统筹方法 例、把例的工序进度表做一些

13、扩充，如表例、把例的工序进度表做一些扩充，如表12-912-9，请画出其统筹方法的网络，请画出其统筹方法的网络图。图。 表表12-912-9 工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序abcd60151338-aacefgh810165b,ddde,f,g17 2统筹方法统筹方法 解：引入虚工序解：引入虚工序 虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。，不需要人力、物力等资源与时间。 152643a60b

14、158e1013dc38f图图12-518 2统筹方法统筹方法 接着在网络图上添加、工序得网络图接着在网络图上添加、工序得网络图12-612-6。 601256734a15bec13d388h510fg16图图12-612-619 2统筹方法统筹方法 在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图虚工序如图12-712-7，即例，即例4 4的最终统筹方法网络图。的最终统筹方法网络图。 1257834a6015bec13d388h510f616g图图12-712-7 注意：注意：在绘制统筹方法的网络图

15、时，图中不能有缺口和回路。在绘制统筹方法的网络图时，图中不能有缺口和回路。20 2统筹方法统筹方法二、网络时间与关键路线二、网络时间与关键路线 在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出： 完成此工程项目所需的最少时间完成此工程项目所需的最少时间每个工序的开始时间与结束时间每个工序的开始时间与结束时间关键路线及其应用的关键工序关键路线及其应用的关键工序非关键工序在不影响工程的完成时间的前提下，其开始时间与结非关键工序在不影响工程的完成时间的前提下，其开始时间与结 束时间可以推迟多久束时间可以推迟多久21 2统筹方法统筹方法例例5 5、某公司装配一条新的生

16、产线，具体过程如表、某公司装配一条新的生产线，具体过程如表12-10,12-10,求：完成此工程的最少时间，关求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。间的前提下，其开始时间与结束时间可以推迟多久。 表表12-1012-10工序代号工序代号工序内容工序内容所需时间（天）所需时间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机

17、械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535-aaaacdd，egb，i，f，h22 2统筹方法统筹方法解：据表解：据表12-10,12-10,绘制网络图如图绘制网络图如图12-812-8。 12346785a60b45echj35i1030d204025f1815关键路线关键路线：网络中最长的路线，决定了完成整个工程所需的最少时间：网络中最长的路线，决定了完成整个工程所需的最少时间此图中此图中 - - - - -为关键路线为关键路线, ,由工序由工序a a，c c，f f，j j组成。组成。图图12-823 2

18、统筹方法统筹方法下面给出找关键路线的办法下面给出找关键路线的办法 工序工序a a的最早的最早开始时间开始时间工序工序a a的最早的最早完成时间完成时间12a0，6060图图12-912-9首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES )ES )和最早结束时间（和最早结束时间（EF) EF) ，设一个工序所需的时间为，设一个工序所需的时间为t t，这对于，这对于同一个工序来说，有同一个工序来说，有EF=ES+tEF=ES+t。例该题中的工序例该题中的工序a，如图，如图12-9所示。所示。24 2统筹方法统筹方法 依照上

19、述最早开始时间法则以及依照上述最早开始时间法则以及EF=ES+tEF=ES+t的关系，可以依次算出此网的关系，可以依次算出此网络图中的各弧的最早开始时间与最早完成时间，如图络图中的各弧的最早开始时间与最早完成时间，如图12-1012-10所示所示 6123785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d60.80204025f70,881841015图图12-1012-106123785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11

20、030d60.80204025f70,881841015图图12-1012-1025 2统筹方法统筹方法 其次其次, ,从网络的收点开始计算出在不影响整个工程最早结束时间的从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间情况下各个工序的最晚开始时间( (缩写为缩写为LS)LS)和最晚结束时间（缩写为和最晚结束时间（缩写为LF),LF),显然对同一工序有显然对同一工序有LS=LF-tLS=LF-t，且任一工序的最晚结束时间等于其，且任一工序的最晚结束时间等于其所有紧后工序的最晚开始时间中的最早时间。所有紧后工序的最晚开始时间中的最早时间。 运用上述法则，从收点开始

21、可计算出每个工序的运用上述法则，从收点开始可计算出每个工序的LFLF与与LSLS如图如图12-1112-11所示。所示。 图图12-1112-1165i110.13525110,13512378a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170g80,1103080,110d60.802060,804080,120f70,8818117,135410107,11715120,13526 2统筹方法统筹方法 接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间接着，可以计算出每一个工序的时差，把在不影响工程最早

22、结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为的时差，对每个工序来说其时差记为T Ts s，有，有T Ts s=LS-ES=LF-EF=LS-ES=LF-EF例，对于工序例，对于工序b b来说，其时差为来说，其时差为 Ts=LF-EF=90-60=30 Ts=LF-EF=90-60=30 对于工序对于工序g g来说，其时差为来说，其时差为 Ts=LF-EF=80-80=0 Ts=LF-EF=80-80=0 由此可知工序由此可知工序b b是非关键工序，工序是非关键工序，工序g

23、 g为关键工序，一般说关键工序为关键工序，一般说关键工序的时差都为的时差都为0 0。27 2统筹方法统筹方法 最后将各工序的时差，以及其他信息构成工序时间表如表最后将各工序的时差，以及其他信息构成工序时间表如表12-1112-11所示。所示。 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,ia,d,g,i和和j j依次连接成的从发点到收点的关依次连接成的从发点到收点的关键路线。键路线。工序工序最早开始时间最早开始时间（ES）最晚开始时间最晚开始时间（LS）最早完成时间最早完成时间（EF）最晚完成时间最晚完成时间（LF）时差时差（LS-ES）是否为关键工是否为关键工序序abcd

24、efghij0606060607080100110135090107608011780120110135601057080100881101151351706013511780120135110135135170030470204702000是是否否否否是是否否否否是是否否是是是是28 2统筹方法统筹方法例例6. 6. 长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表培训组织的各项活动的信息如表12-1212-12所示，要求绘制出统筹方法的网络图，求出网络时所示，要求绘制出统

25、筹方法的网络图，求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。活动（工序）活动（工序）活动（工序）内容活动（工序）内容紧前活动（工序）紧前活动（工序）abcdefghi制定培训计划制定培训计划选聘培训教师选聘培训教师列出一些可供选择的培训地点列出一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备，器材，资料落实教学设备，器材，资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处理最后的一些事务处理最后的一些事务-a-cb，dcb，dg

26、f，g表表12-12三、完成工序所需时间不确定时的网络时间与关键路线三、完成工序所需时间不确定时的网络时间与关键路线29 2统筹方法统筹方法解：由表解：由表12-1212-12，绘出统筹方法的网络图如图，绘出统筹方法的网络图如图12-1212-12所示所示12356487abecdfghi 图图12-1230 2统筹方法统筹方法由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：但对所需时间做了三种估计：1.1.乐观时间。指所需最少时间，用乐观时间。指所需最少时间，用a a表示。表示。2.2.最可能时间。指正

27、常时间，用最可能时间。指正常时间，用m m表示。表示。3.3.悲观时间。指不顺利情况下，最多时间，用悲观时间。指不顺利情况下，最多时间，用b b表示。如表表示。如表12-1312-13所示：所示： 活动活动乐观时间乐观时间最可能时间最可能时间悲观时间悲观时间abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5表表12-13单位：周单位：周31 2统筹方法统筹方法显然这三种完成活动所需时间都具有一定概率，由经验，我们可以显然这三种完成活动所需时间都具有一定概率，由经验，

28、我们可以可以假定这些时间的概率分布近似服从可以假定这些时间的概率分布近似服从分布。我们可以用如下公式计分布。我们可以用如下公式计算出完成活动所需的平均时间：算出完成活动所需的平均时间： 以及方差以及方差 例如：完成工作例如：完成工作g g所需平均时间：所需平均时间： 同时求出方差为同时求出方差为64bmaT262)(ab460.75.340.364bmaTg9432 2统筹方法统筹方法同样可以求出每个活动的完成所需平均时间及方差，如表同样可以求出每个活动的完成所需平均时间及方差，如表12-1412-14： 表表12-1412-14 活动活动T（平均时间）（平均时间）方差方差abcdefghi2

29、322124420.0280.4450.1110.0280.0280.1110.4450.1110.02833 2统筹方法统筹方法 下面用平均时间代替完成活动所需时间，并在网络图上标上每个活下面用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图动最早开始时间和最早结束时间，如图12-1412-14所示。所示。12345876a0,2g5,9b2,5e5,6d2,4f6,8c0,2i13,15h9,13322214242图12-1434 2统筹方法统筹方法 同样也可以标上最晚开始时间和最晚完成时间等，如图同样也可以标上最晚开始时间和最晚完成时间等，如图12-

30、1512-15所示。所示。12345876a0,2b2,5e5,6d2,4f6,8c0,2i13,15h9,1321,3110,1145,949,1323,520,232,5213,15211,13图图12-1512-15g5,935 2统筹方法统筹方法 求出时差求出时差T Ts s=LF-EF=LF-EF，把这些填入工序时间表，把这些填入工序时间表12-1512-15中中表12-15活动活动最早开始时间最早开始时间（ES）最晚开始时间最晚开始时间（LS）最早完成时间最早完成时间（EF）最晚完成时间最晚完成时间（LF）时差时差（LS-ES）是否为关键工是否为关键工序序abcdefghI0202

31、565913021310115913252468913152535111391315001155000是是是是否否否否否否否否是是是是是是由上表得关键路线是由关键工序由上表得关键路线是由关键工序a，b，g，h，i组成的。则完成培训工作所需的平均时间组成的。则完成培训工作所需的平均时间为各关键路线的时间之和：为各关键路线的时间之和： =2+3+4+4+2=15（周）（周）ihgbaTTTTT由上表得关键路线是由关键工序由上表得关键路线是由关键工序a，b，g，h，i组成的。则完成培训工作所需的平均时间组成的。则完成培训工作所需的平均时间为各关键路线的时间之和：为各关键路线的时间之和： =2+3+4

32、+4+2=15（周）（周）ihgbaTTTTT36 2统筹方法统筹方法四、网络优化四、网络优化1.1.时间时间- -资源优化资源优化 做法：做法： 1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。）利用非关键工序的时差，错开各工序的开始时间。 3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。37 2统筹方法统筹方法列举一个拉平资源需要量最高峰的实例。在例列举一个拉平资源需要量最高峰的实例。在例5 5中，若完成工序中，若完成工序d d，f,g,h,if,g,h,i加工工

33、人为加工工人为6565人，并假定这些工人可完成这人，并假定这些工人可完成这5 5个工序任一个个工序任一个，下面来寻求一个时间，下面来寻求一个时间- -资源最优方案。如表资源最优方案。如表12-1612-16所示：所示： 工序工序需要工人人数需要工人人数最早开始时间最早开始时间所需时间所需时间时差时差d5860200f22701847g4280300h391001520i2611025038 2统筹方法统筹方法 若上述工序都按最早开始时间安排，那么从第若上述工序都按最早开始时间安排，那么从第6060天至第天至第135135天的天的7575天里天里，所需的机械加工工人人数如图，所需的机械加工工人人

34、数如图12-1712-17所示。所示。 64242人人42735 f(22 f(22人）人）18h(39h(39人人) )155858人人6464人人8080人人8181人人2626人人6565人人60 80 100 120 130 d(58 d(58人）人） i(26 i(26人）人） g(42 g(42人）人）302025图图12-1712-17时间时间/ /天天39 2统筹方法统筹方法 应优先安排关键工序所需的工人，再利用非关键工序的时差错开各应优先安排关键工序所需的工人，再利用非关键工序的时差错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非工序的开始时间，从而拉平工人

35、需要量的高峰。经过调整，我们让非关键工序关键工序f f从第从第8080天开始，工序天开始，工序h h从第从第110110天开始。找到了时间天开始。找到了时间- -资源优资源优化的方案，如图化的方案，如图12-1812-18所示，在不增加工人的情况下保证了工程按期完所示，在不增加工人的情况下保证了工程按期完成。成。60 80 100 120 13065人人58人人42人人64人人26人人65人人246753 f(22 f(22人）人） h(39 h(39人）人） d(58 d(58人）人） i(26 i(26人）人） g(42 g(42人）人）工人数工人数图图12-1812-18时间时间/ /天

36、天40 2统筹方法统筹方法2.2.时间时间- -费用优化费用优化 在既定的时间前工程完工的前提下，使得所需的费用最少，或者在在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间不超工程预算的条件下使工程最早完工。这些是时间- -费用优化要研费用优化要研究和解决的问题。究和解决的问题。工序的最快完成时间：指完成时间的最高限度。我们设完成工序工序的最快完成时间：指完成时间的最高限度。我们设完成工序j j的正常的正常所需时间为所需时间为TjTj；直接费用为；直接费用为cjcj；完成工序；完成工序j j的最快完成时间为的最快完成时间为Tj,Tj,直接

37、费直接费用为用为cjcj。这样我们可以计算出缩短工序。这样我们可以计算出缩短工序j j的一天工期所增加的直接费用，的一天工期所增加的直接费用，用用kjkj表示，称为直接费用变动率。有表示，称为直接费用变动率。有 jjjjjTTcck费用又分为直接费用和间接费用费用又分为直接费用和间接费用41 2统筹方法统筹方法时间时间-费用优化问题可建立两个线性规划模型。费用优化问题可建立两个线性规划模型。 模型一，在既定的时间模型一，在既定的时间T T完工的前提下，问各工序的完成时间为多少才使因缩短工期而完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。增加的直接费用最少。 设工序（

38、设工序（i ,j)i ,j)的提前完工时间为的提前完工时间为Yij, ,我们用我们用Tij,Tij分别表示正常完工时间与最快完分别表示正常完工时间与最快完工的时间，则有工序（工的时间，则有工序（i ,j)i ,j)的实际完工时间为：的实际完工时间为：Tij-Yij。我们用。我们用Cij,Cij表示用正常完表示用正常完工时间和最快完成时间完成工序所需要的费用，工时间和最快完成时间完成工序所需要的费用，Kij为工序（为工序（i ,j)i ,j)的直接费用变动率的直接费用变动率。得到这个问题的线性规划模型如下：。得到这个问题的线性规划模型如下： minf= （Kij*Yij) （i,j) S.t.

39、Xj-Xi Tij-Yij,对一切弧（对一切弧（i, j)i, j) Yij Tij-Tij, 对一切弧（对一切弧（i, j)i, j) Xn-X1 T, Xi 0， Yij 0。42 2统筹方法统筹方法 模型二，设单位时间的间接费用为模型二，设单位时间的间接费用为d,d,计划期的间接费用与总工期成计划期的间接费用与总工期成正比，即为正比，即为d(xd(xn n-x-x1 1),),那么求使包括间接费用与直接费用在内的总费用那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间最少的整个工程最优完成时间T T和各个工序最优完成时间的模型为：和各个工序最优完成时间的模型为： 目标函数目标函数min f=d(xn-x1)+ s.t. xj-xi Tij-yij，对一切弧对一切弧（i ,j) yijTij-Tij ，对一切弧对一切弧（i ,j) xi 0， yij 0。j)(i,ijij)y(k43谢谢 谢！谢！