《韩伯棠管理运筹学(第三版)-第十二章-排序与统筹课件》由会员分享，可在线阅读，更多相关《韩伯棠管理运筹学(第三版)-第十二章-排序与统筹课件（74页珍藏版）》请在金锄头文库上搜索。
1、第十二章第十二章 排序与统筹方法排序与统筹方法运运运运 筹筹筹筹 学学学学计划统筹计划统筹绩效最优绩效最优1第九章第九章 排序与统筹方法排序与统筹方法第一节第一节 车间作业计划模型车间作业计划模型第二节第二节 统筹方法统筹方法 在在本本章章中中，我我们们将将介介绍绍车车间间作作业业计计划划模模型型和和统统筹筹方方法法。这这两两个个问问题题尽尽管管处处理理的的方方法法有有所所不不同同，但但当当我我们们面面临临必必须须完完成成若若干干项项不不能能同同时时进进行行的的工工作作时时，它它们们都都将将帮帮助助我我们们应应该该按按照照怎怎样样的的次次序序、怎怎样样的的时时间间表表来来做做这这些些工工作作，
2、使使得得效效果果最最佳佳（例例如如完完成成全全部部工作所用时间最短或费用最少等等）。工作所用时间最短或费用最少等等）。2 1 1 车间作业计划模型车间作业计划模型 车车间间作作业业计计划划是是指指一一个个工工厂厂生生产产工工序序的计划和安排。的计划和安排。一、一台机器、一、一台机器、n个零件的排序问题个零件的排序问题二、两台机器、二、两台机器、n个零件的排序问题个零件的排序问题3一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题 例例1.某某车车间间只只有有一一台台高高精精度度的的磨磨床床，常常常常出出现现很很多多零零件件同同时时要要求求这这台台磨磨床床加加工工的的情情况况，现
3、现有有六六个个零零件件同时要求加工，这六个零件加工所需时间如下表所示。同时要求加工，这六个零件加工所需时间如下表所示。 应应该该按按照照什什么么样样的的加加工工顺顺序序来来加加工工这这六六个个零零件件，才才能能使使得得这这六六个个零零件件在在车车间间里里停停留留的的平平均均时时间间为为最最少少？ 1 1 车间作业计划模型车间作业计划模型4 例例1解：如果我们用解：如果我们用Pi表示安排在第表示安排在第i位加工的零位加工的零件所需的时间，用件所需的时间，用Tj表示安排在第表示安排在第j位加工的零件在车位加工的零件在车间里总的停留时间，则有间里总的停留时间，则有 Tj = P1 + P2 + Pj
4、-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。们要设法找到一种简便的算法。 对于某种加工顺序，我们知道安排在第对于某种加工顺序，我们知道安排在第j位加工的位加工的零件在车间里总的停留时间为零件在车间里总的停留时间为Tj ， Tj = 1 1 车间作业计划模型车间作业计划模型5可知这六个零件的停留时间为：可知这六个零件的停留时间为
5、： T1 + T2 + 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. 那么各个零件平均停留时间为那么各个零件平均停留时间为 从从上上式式可可知知，对对于于一一台台机机器器n个个零零件件的的排排序序问问题题，只只要要系系数数越越大大，配配上上加加工工时时间间越越少少的的，即即按按照照加加工工时时间间排排出
6、出加加工工顺顺序序，加加工工时时间间越越少少的的零零件件排排在在越越前前面面，加加工工时时间间越越多的零件排在越后面，可使各零件的平均停留时间最少。多的零件排在越后面，可使各零件的平均停留时间最少。 1 1 车间作业计划模型车间作业计划模型6二、两台机器、二、两台机器、n n个零件个零件 例例2. 某某工工厂厂根根据据合合同同定定做做一一些些零零件件，这这些些零零件件要要求求先先在在车车床床上上车车削削，然然后后再再在在磨磨床床上上加加工工，每每台台机机器器上上各零件加工时间如下表所示。各零件加工时间如下表所示。 应应该该如如何何安安排排这这五五个个零零件件的的先先后后顺顺序序才才能能使使完完
7、成成这五个零件的总的加工时间为最少？这五个零件的总的加工时间为最少？ 1 1 车间作业计划模型车间作业计划模型7 解解：由由于于每每个个零零件件必必须须先先进进行行车车床床加加工工，再再进进行行磨磨床床加加工工，所所以以在在车车床床上上加加工工零零件件的的顺顺序序与与在在磨磨床床上上加加工工零零件件的的顺顺序序是是一一样样的的。如如果果这这些些零零件件在在车车床床上上和和磨磨床床上上加加工工顺顺序序都都为为1，2，3，4，5。我我们们用用图图12-1中中的的线线条条图图来来表表示示各各零零件件加加工工的的开开始始时时间间与与完完成成时时间间，这这种种图图是是由由一一根根时时间间轴轴和和车车床床
8、、磨磨床床在在每每个个时时间间段段的的状况的图形所构成。状况的图形所构成。 1 1 车间作业计划模型车间作业计划模型8图图 12-1 从从上上图图中中我我们们可可以以看看出出，加加工工时时间间的的延延长长主主要要是是由由于于磨磨床床的的停停工工待待料料造造成成的的，只只要要减减少少磨磨床床的的停停工工待待料料的的时间就能减少整个加工任务的总时间。时间就能减少整个加工任务的总时间。 为为了了减减少少磨磨床床的的停停工工待待料料，我我们们应应该该一一方方面面把把在在车车床床上上加加工工时时间间越越短短的的零零件件越越早早加加工工，减减少少磨磨床床等等待待的的时时间间；另另一一方方面面把把在在磨磨床
9、床上上加加工工时时间间越越短短的的零零件件越越晚晚加加工工，以以便便充充分分利利用用前前面面的的时时间间，这这样样我我们们就就得得到到了了使使完完成成全全部零件加工任务所需总时间最少的零件排序方法。部零件加工任务所需总时间最少的零件排序方法。123451车车床床磨磨床床23450101.52.01.0 1.25 0.750.50.251.752.51.259 寻找例寻找例2的最优解：我们在上表中找到所列出的最的最优解：我们在上表中找到所列出的最短加工时间是短加工时间是0.25,它是第二道工序磨床加工零件它是第二道工序磨床加工零件2的所的所需时间，由于这个时间与磨床有关，故我们把零件需时间，由于
10、这个时间与磨床有关，故我们把零件2放放在加工顺序的末尾，即第五位，并在表中划去零件在加工顺序的末尾，即第五位，并在表中划去零件2 所所在行。如表中红色线条所示。在行。如表中红色线条所示。 1 1 车间作业计划模型车间作业计划模型10接接着着，我我们们又又找找到到最最短短加加工工时时间间为为0.5，这这一一时时间间与与磨磨床床（第第二二工工序序）有有关关，我我们们把把磨磨床床加加工工时时间间为为0.5的的零零件件1放放到到除除第第五五外外的的加加工工顺顺序序的的末末尾尾，即即第第四四位位加加工工，同同时时把把表表中中的的零零件件1所所在在的的行行划划去去。如如表表中中黄黄色色线线条条所示。所示。
11、 1 1 车间作业计划模型车间作业计划模型11 下下一一个个最最短短加加工工时时间间为为0.75，这这个个加加工工时时间间是是车车床床（第第一一工工序序）加加工工零零件件5的的所所需需时时间间，故故把把零零件件5排排在在加加工工顺顺序序的的第第一一位位上上，同同时时把把表表中中的的零零件件5所所在在的的行行划划去去。如如表表中中蓝蓝色色线线条条所示。所示。 1 1 车间作业计划模型车间作业计划模型12同同样样，下下一一个个最最短短加加工工时时间间为为1，这这是是车车床床加加工工零零件件3的的所所需需时时间间，故故把把零零件件3排排在在第第二二位位上上，同同时时把把零零件件3所所在在的的行行划划
12、去去。如如表表中中黑黑色色线线条条所示。所示。 1 1 车间作业计划模型车间作业计划模型13这样就得到了最优加工顺序：这样就得到了最优加工顺序：5，3，4，1，2。0.751.01.251.52.01.251.752.50.5 0.255磨床磨床车床车床3412534127这样一共只需这样一共只需7个小时就能完成全部加工。个小时就能完成全部加工。 1 1 车间作业计划模型车间作业计划模型14 从从例例2中中我我们们可可以以归归纳纳出出关关于于两两台台机机器器n个个零零件件的的排排序序问问题题，使使得得全全部部任任务务总总的的时时间间最最短短的排序算法。的排序算法。 步步骤骤1: 在在加加工工所
13、所需需时时间间表表上上选选出出最最短短加加工工时时间间tij，这是第，这是第i工序加工工序加工j零件所需时间，零件所需时间， 步步骤骤2: 当当i=1时时，将将零零件件j的的顺顺序序尽尽量量靠靠前前，若若i=2时，将零件时，将零件j的顺序尽量靠后。的顺序尽量靠后。 步步骤骤3: 在在表表上上划划去去零零件件j的的所所在在行行，回回到到步步骤骤1。 1 1 车间作业计划模型车间作业计划模型15思考题：思考题：m台台机机器器n个个零零件件的的排排序序问问题题如何解决？如何解决？ 1 1 车间作业计划模型车间作业计划模型162 2 统筹方法统筹方法 统统筹筹法法又又称称网网络络计计划划法法。它它是是
14、以以网网络络图图反反映映、表表达达计计划划安安排排，据据以以选选择择最最优优工工作作方方案案，组组织织协协调调和和控控制制生生产产（项项目目）的的进进度度（时时间间）和和费费用用（成成本本），使使其其达达到到预预定定目目标标，获获得得更更佳佳经经济济效效益益的的一一种种优优化化决决策策方法。方法。 1957年年，美美国国化化学学公公司司Du Pont的的与与Rand通通用用电电子子计计算算机机公公司司的的为为了了协协调调公公司司内内部部不不同同业业务务部部门门的的工工作作, 共共同同研研究究出出关关键键路路线线方方法法（简简记记作作CPM）.首首次次把把这这一一方方法法用用于于一一家家化化工工
15、厂厂的的筹筹建建，结结果果筹筹建建工工程程提提前前两两个个月月完完成成.随随后后又又把把这这一一方方法法用用于于工工厂厂的的维维修修，结结果果使使停停工工时时间间缩缩短短了了47个个小小时时，当当年年就就取取得得节节约约资资金金达百万元的要观效益。达百万元的要观效益。17 1958年年，美美国国海海军军武武器器规规划划局局特特别别规规划划室室研研制制含含约约3000项项工工作作任任务务的的北北极极星星导导弹弹潜潜艇艇计计划划，参参与与的的厂厂商商达达11000多多家家。为为了了有有条条不不紊紊地地实实施施如如此此复复杂杂的的工工作作，特特别别规规划划室室领领导导人人W.Fazar积积极极支支持
16、持与与推推广广由由专专门门小小组组创创建建的的计计划划评评审审技技术术（简简记记作作PERT）。结结果果研制计划提前两个完成，取得了极大的成功。研制计划提前两个完成，取得了极大的成功。 CPM在在民民用用企企业业与与PERT在在军军事事工工业业中中的的显显著著成成效效,自自然然引引起起了了普普遍遍的的重重视视。很很快快CPM与与PERT就就被被应应用用于于工工业业、农农业业、国国防防与与科科研研等等等等复复杂杂的的计计划划管管理理工工作作中中,随随后后又又推推广广到到世世界界各各国国。在在应应用用推推广广CPM与与PERT的的过过程程中中,又又派派生生出出多多种种各各具具特特点点，各各有有侧侧
17、重重的的类类似似方方法法。但但是是万万变变不不离离其其宗宗，各各种种有有所所不不同同的的方方法法，其基本原理都源于其基本原理都源于CPM与与PERT。18CPM与与PERT两两种种方方法法实实质质上上大大同同小小异异，因因此此，人人们们把把CPM与与PERT及及其其他他类类似似方方法法统统称称为为网网络络计计划划技技术术，简简称称为为网网络络技技术术或或网网络方法，简记为络方法，简记为统筹法统筹法。 统统筹筹方方法法包包括括绘绘制制计计划划网网络络图图、进进度度安安排、网络优化等环节，下面进行分别讨论：排、网络优化等环节，下面进行分别讨论：一、计划网络图一、计划网络图 统统筹筹方方法法的的第第
18、一一步步工工作作就就是是绘绘制制计计划划网网络络图图，也也就就是是将将工工序序（或或称称为为活活动动）进进度度表表转换为统筹方法的网络图。转换为统筹方法的网络图。2 统筹方法统筹方法19网络图画法网络图画法(一一)、结构、结构网网络络图图中中的的点点表表示示一一个个事事件件,是是一一个个或或若若干干个个工工序序的的开开始始或或结结束束,是是相相邻邻工工序序在在时时间间上上的的分分界界点点,点点用圆圈表示用圆圈表示,圆圈里的数字表示点的编号。圆圈里的数字表示点的编号。弧弧表表示示一一个个工工序序（或或活活动动），弧弧的的方方向向是是从从工工序序开开始始指指向向工工序序的的结结束束，弧弧上上是是各
19、各工工序序的的代代号号，下下面面标标以以完完成成此此工工序序所所需需的的时时间间（或或资资源源）等等数数据据，即为对此弧所赋的权数。即为对此弧所赋的权数。例如：例如：5a122 2 统筹方法统筹方法20(二二)、画法注意事项：、画法注意事项：(1)、从左、从左右右1234567824331212 2 统筹方法统筹方法21(2)、两事项间只有一个工序、两事项间只有一个工序bij75a32 2 统筹方法统筹方法22(3)、不允许回路、不允许回路1232 2 统筹方法统筹方法23(4)、虚工序的运用、虚工序的运用120 正确表达工序的前行、后续关系正确表达工序的前行、后续关系(连结、连结、隔离隔离)
20、 解解决决画画法法中中问问题题：网网络络图图中中只只有有一一个个始始点点和和一一个个终终点点，中中间间点点前前后后均均要要有有弧弧相相连连接接，不允许中断。不允许中断。2 2 统筹方法统筹方法241234657824031302012 2 统筹方法统筹方法25ijk750a3b2 2 统筹方法统筹方法26例例1、假设某工作有、假设某工作有a, b, c, d四个工序四个工序, c在在 a, b完工后开始，完工后开始， d在在 b完工后开始。完工后开始。cabdabcd2 2 统筹方法统筹方法27例例3、某公司研制新产品的部分工序与所需时间以及、某公司研制新产品的部分工序与所需时间以及它们之间的
21、相互关系都显示在其工序进度表如表它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。所示，请画出其统筹方法网络图。 2 2 统筹方法统筹方法28解：用网络图表示上述的工序进度表。解：用网络图表示上述的工序进度表。abcde6013838152 2 统筹方法统筹方法29 例例、把把例例的的工工序序进进度度表表做做一一些些扩扩充充，如如下表，请画出其统筹方法的网络图。下表，请画出其统筹方法的网络图。 2 2 统筹方法统筹方法30152643a60b158e1013dc38f7g168由于是的由于是的紧前工序，故紧前工序，故的结束应该的结束应该是的开始，是的开始，所以代表
22、的所以代表的弧的起点应该弧的起点应该是是，由于工，由于工序的结束也序的结束也是是，所以工，所以工序也成了工序也成了工序的紧前工序的紧前工序，与题意不序，与题意不符。符。为此我们设立为此我们设立虚工序。虚工虚工序。虚工序是实际上并序是实际上并不存在而虚设不存在而虚设的工序，用来的工序，用来表示相邻工序表示相邻工序的衔接关系，的衔接关系，不需要人力、不需要人力、物力等资源与物力等资源与时间。时间。2 2 统筹方法统筹方法31152643a60b158e1013dc38fg16在统筹方法的在统筹方法的网络图中不允网络图中不允许两个点之间许两个点之间多于一条弧，多于一条弧，因此需增加一因此需增加一个点
23、和虚工序个点和虚工序2 2 统筹方法统筹方法32152643a60b158e1013dc38f716g8h5在在绘绘制制统统筹筹方方法法的的网网络络图图时时，要要注注意意图图中中不能有缺口和回路。不能有缺口和回路。2 2 统筹方法统筹方法33练习练习工序工序 内容内容 工时工时(天天) 紧前工序紧前工序 A 初步研究初步研究 1 / B 研究选点研究选点 2 A C 准备调研方案准备调研方案 4 A D 联系调研点联系调研点 2 B E 培训工作人员培训工作人员 3 B,C F 准备表格准备表格 1 C G 实地调研实地调研 5 D,E,F H 写调研报告写调研报告 2 G I 开会汇总开会汇
24、总 3 H12325FE200C413DBAGHI1234567892 2 统筹方法统筹方法35二、网络时间与关键路线二、网络时间与关键路线路路线线：在在网网络络图图上上从从始始点点（发发点点）开开始始，沿沿弧弧的的方方向向（即即按按各各工工序序的的顺顺序序）连连续续不不断断地地到到终终点点（收点）的一条路线。（收点）的一条路线。例如：例如：12325FE200C413DBAGHI1234567892 2 统筹方法统筹方法36关关键键路路线线：网网络络中中最最长长的的路路线线，通通常常可可用用双双线线标标出出。关关键键路路线线的的长长等等于于该该路路线线上上各各工工序序的的时时间间之之和和，又
25、称为工程时间或工期，其它路线称为非关键路线。又称为工程时间或工期，其它路线称为非关键路线。关关键键（非非关关键键）工工序序：关关键键路路线线上上的的各各工工序序，其其它工序称为非关键工序。它工序称为非关键工序。12325FE200C413DBAGHI123456789工期工期T182 2 统筹方法统筹方法37显显然然，缩缩短短工工期期就就是是要要缩缩短短关关键键路路线线的的长长度度，也也就就是是说说要要加加快快关关键键工工序序的的进进度度。而而缩缩短短非非关关键键路路线的长度或缩短非关键工序的时间均不能缩短工期。线的长度或缩短非关键工序的时间均不能缩短工期。12325FE200C413DBAG
26、HI123456789工期工期T182 2 统筹方法统筹方法38在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。、关键路线及其应用的关键工序。4、非非关关键键工工序序在在不不影影响响工工程程的的完完成成时时间间的的前前提提下下，其开始时间与结束时间可以推迟多久。其开始时间与结束时间可以推迟多久。 例例5、某某公公司司装装配配一一条条新新的的生生产产线线，具具体体过过程程如如下下表表,求求：完完成成
27、此此工工程程的的最最少少时时间间，关关键键路路线线及及相相应应的的关关键键工工序序，各各工工序序的的最最早早开开始始时时间间和和非非关关键键工工序序在在不不影影响响工工程程完完成成时时间间的的前前提提下下，其其开开始始时时间间与与结结束时间可以推迟多久。束时间可以推迟多久。2 2 统筹方法统筹方法392 2 统筹方法统筹方法40解：据表绘制网络图如图。解：据表绘制网络图如图。12346785a60b45echj35ig1030d204025f1815如如图图 ,-就就是是一一条条关关键键路路线线，我我们们要要干干完完所所有有的的工工序序就就必必须须走走完完所所有有这这样样的的路路线线，由由于于
28、很很多多工工序序可可以以同同时时进进行行，所所以以网网络络中中最最长长的的路路线线就就决决定定了了完完成成整整个个工工程程所所需需的的最最少少时时间间，这这条条路路线线就就是是关关键键路路线。线。2 2 统筹方法统筹方法41下面我们给出找关键路线的办法下面我们给出找关键路线的办法 首首先先，从从网网络络的的发发点点开开始始，按按顺顺序序计计算算出出每每个个工工序序的的最最早早开开始始时时间间（ES )和和最最早早结结束束时时间间（EF) ，设设一一个个工工序序所所需需的的时时间间为为t，这这对对于于同同一一个个工工序序来来说说，有有: EF=ES+t。工序工序a的最早的最早开始时间开始时间工序
29、工序a的最早的最早完成时间完成时间11a0，60602 2 统筹方法统筹方法42g80,11030d60.8020e60.100h100,11515j135,170a0,6060其其次次,从从网网络络的的收收点点开开始始计计算算出出在在不不影影响响整整个个工工程程最最早早结结束束时时间间的的情情况况下下各各个个工工序序的的最最晚晚开开始始时时间间(缩缩写写为为LS)和和最最晚晚结结束束时时间间（缩缩写写为为LF),显显然然对对同同一一工工序序有有: LS=LF-t85b60,1054535i110,1354025f70, 881841017263c60,702 2 统筹方法统筹方法43f70,
30、8810107,1174080,120e60.1003080,110g80,110d60.802060,80i110.13515120,135j135,17035135,170a0,60600,60 运运用用此此法法则则，可可以以从从首首点点开开始始计计算算出出每每个个工工序序的的LF与与LS，如下图所示。，如下图所示。185b60,1054590,135c60,70h100,11525110,13518117,1354接接着着，可可以以计计算算出出每每一一个个工工序序的的时时差差，把把在在不不影影响响工工程程最最早早结结束束时时间间的的条条件件下下，工工序序最最早早开开始始（或或结结束束）的
31、的时时间间可可以以推推迟迟的的时时间间，成成为为该该工工序序的的时时差差，对每个工序来说其时差记为对每个工序来说其时差记为Ts有有 Ts=LS-ES=LF-EF723644 最最后后将将各各工工序序的的时时差差，以以及及其其他他信信息息构构成成工工序序时时间间表如下表所示。一般来说，关键工序的时差为零。表如下表所示。一般来说，关键工序的时差为零。这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连接成的依次连接成的从发点到收点的关键路线。从发点到收点的关键路线。2 2 统筹方法统筹方法45练练习习：设设某某工工程程的的资资料料如如以以下下网网络络图图所所示示，用时差的
32、方法求关键线路。用时差的方法求关键线路。1253411252248967423abcde4fghijk2 2 统筹方法统筹方法46三、完成工序所需时间与关键路线三、完成工序所需时间与关键路线 当当完完成成工工序序所所需需时时间间不不确确定定的的情情况况下下如如何何求求网络时间和关键路线？网络时间和关键路线？ 例例6. 长长征征研研究究院院培培训训中中心心负负责责明明年年春春天天的的各各干干部部的的工工商商管管理理培培训训,培培训训中中心心列列出出有有关关培培训训组组织织的的各各项项活活动动的的信信息息如如表表12-12所所示示,要要求求绘绘制制出出统统筹筹方方法法的的网网络络图图，设设法法求求
33、出出网网络络时时间间和和关关键键路路线线，并并确确定定开开始始这这个个组组织织工工作作的的时时间间以以保保证证培培训训工工作作如期举行。如期举行。2 2 统筹方法统筹方法472 2 统筹方法统筹方法4812356487abecdfghi49 由由于于是是第第一一次次搞搞培培训训，缺缺乏乏统统计计来来确确定定完完成成每每个个活动所需时间，但对所需时间做了三种估计：活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用乐观时间。指所需最少时间，用a表示。表示。2.最可能时间。指正常时间，用最可能时间。指正常时间，用m表示。表示。3.悲悲观观时时间间。指指不不顺顺利利情情况况下下，
34、最最多多时时间间，用用b表表示示。如下表（单位：周）所示：如下表（单位：周）所示：50 显然这三种完成活动所需时间都具有一定概率，显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似由经验，我们可以可以假定这些时间的概率分布近似服从服从 分布。我们可以用如下公式计算出完成活动分布。我们可以用如下公式计算出完成活动所需的平均时间：所需的平均时间： 以及方差以及方差 2 2 统筹方法统筹方法51例如：完成工作例如：完成工作g g所需平均时间：所需平均时间：同时求出方差为同时求出方差为2 2 统筹方法统筹方法52 同同样样可可以以求求出出每每个个活活动动的的完完成
35、成所所需需平平均均时时间间及及方方差差，如下表：如下表： 2 2 统筹方法统筹方法53i13,152i13,15 下下面面就就用用平平均均时时间间代代替替完完成成活活动动所所需需时时间间，并并在在网网络络图图上上标标上上每每个个活活动动最最早早开开始始时时间间和和最最早早结结束束时时间间，如图如图12-14所示。所示。2345876同样也可以标上最晚开始时间和最晚完成时间等。同样也可以标上最晚开始时间和最晚完成时间等。a0,2g5,9b2,5e5,6d2,4f6,8c0,2h9,133222142412345876a0,2g5,9b2,5e5,6d2,4f6,8c0,2h9,1321,3110
36、,1145,949,1323,520,232,5213,15211,13图图12-14图图12-15154 从从表表12-15上上我我们们找找到到了了一一条条从从发发点点到到收收点点由由关关键键工工序序a,b,g,h,i组组成成的的关关键键路路线线，用用双双线线标标出出来来。则则完完成成培培训训工工作作所所需需的的平平均均时时间间为为各各关关键键路路线线的的时时间间之和：之和： =2+3+4+4+2=15（周）（周） 同同时时完完成成时时间间近近似似服服从从一一定定的的概概率率分分布布正正态态分分布布，则则均均值值为为关关键键路路线线上上各各关关键键活活动动之之均均值值之之和和15，方差也为关
37、键路线上各关键活动方差之和，方差也为关键路线上各关键活动方差之和1.05。 由由此此我我们们可可以以计计算算出出此此项项培培训训组组织织工工作作不不同同完完工时间的概率，如工时间的概率，如16周内完工的概率。周内完工的概率。 2 2 统筹方法统筹方法55 为求此概率，可以先求为求此概率，可以先求u值。值。 式中的式中的T为预定完工时间为预定完工时间16，E（T）=15， 算算得得u=0.976。查查正正态态分分布布函函数数表表可可知知概概率率为为0.8355。即。即16周内完工的概率为周内完工的概率为83.55%.2 2 统筹方法统筹方法56其正态分布图如图其正态分布图如图12-16所示：所示
38、：16图图12-162 2 统筹方法统筹方法57四、网络优化四、网络优化 得得到到初初始始的的计计划划方方案案，但但通通常常要要对对初初始始方方案案进进行行调调整整与与完完善善。根根据据计计划划目目标标，综综合合考考虑虑资资源源和和降降低低成成本等目标，进行网络优化，确定最优的计划方案。本等目标，进行网络优化，确定最优的计划方案。 1.时间时间-资源优化资源优化做法：做法：1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。）利用非关键工序的时差，错开各工序的开始时间。 3）统统筹筹兼兼顾顾工工程程进进度度的的要要求求和和现现有有资资源
39、源的的限限制制，多多次综合平衡。次综合平衡。2 2 统筹方法统筹方法58下下面面列列举举一一个个拉拉平平资资源源需需要要量量最最高高峰峰的的实实例例。在在例例5中中，若若加加工工工工人人为为65人人，并并假假定定这这些些工工人人可可完完成成这这5个个工工序序任任一一个个，下下面面来来寻寻求求一一个个时时间间-资资源源最最优优方方案案。如表如表12-16所示：所示： 表表12-162 2 统筹方法统筹方法59 d(58人）人）2015h(39人人) g(42人）人） i(26人）人） 在在图图的的上上半半部部中中，工工序序代代号号后后的的数数字字是是人人数数，线线下下面面的的数数字字是是非非关关
40、键键工工序序时时差差长长度度。图图的的下下半半部部表表示示从从第第60天天至至 135天天 内内 的的 75天天里里，所所需需机机械械加加工工工工人人数数，这这样样的的图图称称为为资资源源负荷图。负荷图。274635 f(22人）人）1858人人64人人80人人81人人42人人26人人65人人60 80 100 120 1303025图图12-17 若若上上述述工工序序都都按按最最早早开开始始时时间间安安排排，那那么么从从第第60天天至至第第135天天的的75天天里里，所所需需的的机机械械加加工工工工人人人人数数如如图图12-17所示。所示。60 h(39人）人） g(42人）人） d(58人
41、）人） i(26人）人） 同同时时我我们们应应优优先先安安排排关关键键工工序序所所需需的的工工人人，再再利利用用非非关关键键工工序序的的时时差差，错错开开各各工工序序的的开开始始时时间间，从从而而拉拉平平工工人人需需要要量量的的高高峰峰。经经过过调调整整，我我们们让让非非关关键键工工序序f从从第第80天天开开始始，工工序序h从从第第110天天开开始始。找找到到了了时时间间-资资源源优优化化的的方方案案，如如图图12-18所所示示，在在不不增增加加工工人人的的情情况况下下保保证证了了工工程程按期完成。按期完成。246753 f(22人）人）工人数工人数65人人60 80 100 120 1305
42、8人人42人人64人人26人人65人人图图12-18612.时间时间-费用优化费用优化 需需要要考考虑虑时时间间与与费费用用的的问问题题：在在既既定定的的时时间间前前工工程程完完工工的的前前提提下下，使使得得所所需需的的费费用用最最少少，或或者者在在不不超超工工程程预预算算的的条条件件下下使使工工程程最最早早完完工工。这这些些是是时时间间-费费用优化要研究和解决的问题。用优化要研究和解决的问题。 直直接接费费用用：为为了了加加快快工工程程进进度度，需需要要增增加加人人力力、设设备备和和工工作作班班次次，这这需需要要增增加加一一笔笔费费用用，成成为为直直接接费费用。用。 间间接接费费用用：由由于
43、于工工程程早早日日完完工工，减减少少了了管管理理人人员员的的工工资资办办公公费费等等费费用用称称为为间间接接费费用用。一一般般说说工工序序越越短短，直接费用越多，间接费用越少。直接费用越多，间接费用越少。2 2 统筹方法统筹方法62 工序的最快完成时间：指完成时间的最高限度。工序的最快完成时间：指完成时间的最高限度。 我我们们设设完完成成工工序序j的的正正常常所所需需时时间间为为Tj;直直接接费费用用为为cj;完完成成工工序序j的的最最快快完完成成时时间间为为Tj,直直接接费费用用为为cj。这这样样我我们们可可以以计计算算出出缩缩短短工工序序j的的一一天天工工期期所所增增加加的的直接费用，用直
44、接费用，用kj表示，称为直接费用变动率。有表示，称为直接费用变动率。有 时间时间-费用优化问题可建立两个线性规划模型。费用优化问题可建立两个线性规划模型。 模模型型一一，在在既既定定的的时时间间T完完工工的的前前提提下下，问问各各工工序序的的完完成成时时间间为为多多少少才才使使因因缩缩短短工工期期而而增增加加的的直直接接费费用最少。用最少。2 2 统筹方法统筹方法63设设工工序序（i ,j)的的提提前前完完工工时时间间为为Yij,我我们们用用Tij,Tij分分别别表表示示正正常常完完工工时时间间与与最最快快完完工工的的时时间间，则则有有工工序序（i ,j)的的实实际际完完工工时时间间为为：Ti
45、j-Yij。我我们们用用Cij,Cij表表示示用用正正常常完完工工时时间间和和最最快快完完成成时时间间完完成成工工序序所所需需要要的的费费用用，Kij为为工工序序（i ,j)的的直直接接费费用用变变动动率率。得得到到这这个个问问题题的的线性规划模型如下：线性规划模型如下：S.t. Xj-Xi Tij-Yij,对一切弧（对一切弧（i, j) Yij Tij-Tij, 对一切弧（对一切弧（i, j) Xn-X1 T, Xi 0， Yij 0。2 2 统筹方法统筹方法64例例7. 例例5所所提提供供的的信信息息都都作作为为本本例例的的信信息息，另另外外还还给给出出了了在在装装配配过过程程中中各各道道
46、工工序序所所需需正正常常完完工工时时间间与与最最快快完完工工时时间间，以以及及对对应应正正常常完完工工时时间间与与最最快快完完工工时时间间的的所所需需的的直直接接费费用用和和每每缩缩短短一一天天工工期期所所需需增增加加的的直直接接费费用用，如如表表12-17所示。所示。2 2 统筹方法统筹方法6566c 该该工工程程要要求求在在150天天内内完完工工，问问每每个个工工序序应应比比正正常常完完工工时时间间提提前前多多少少天天完完成成，才才能能使使整整个个工工程程因因缩缩短短工工期期而而增增加加的的直直接接费费用用为为最最少少。如如果果工工期期要要求求在在140天完工呢？天完工呢？12345678
47、abfehgijd2 2 统筹方法统筹方法67解解：根根据据此此网网络络图图建建立立数数学学模模型型。设设此此网网络络图图上上第第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）
48、x7-x5 15-y57 x7-x6 25-y6768 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 统筹方法统筹方法69 模模型型二二，我我们们知知道道直直接接费费用用是是随随着着完完成成时时间间的的缩缩短短而而增增加加，而而间间接接费费用用却却会会随随着着完完成成时时间间的的缩缩短短而而减减少少，设设单单位位时时间间的的间间接接费费用用为为d,计计划划期期的的间间接接费费用用与与总总工工
49、期期成成正正比比，即即为为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。2 2 统筹方法统筹方法70 例例8 如如果果在在例例7中中，每每天天的的间间接接费费用用为为330元元，求求使使包包括括间间接接费费用用与与直直接
50、接费费用用在在内内的的总总费费用用最最少少的的整整个个工程最优完成时间工程最优完成时间T和各个工序最优完成时间。和各个工序最优完成时间。 解解：决决策策变变量量的的含含义义同同例例7。此此数数学学模模型型的的目目标标函数为：函数为：minf=330(x8-x1)+120y27+300y23 +400y24+500y25+230y37 +350y46+290y67 此此模模型型的的约约束束条条件件与与例例7的的约约束束条条件件基基本本相相同同，只只要要在在例例子子的的约约束束条条件件中中去去掉掉x8 150就就得得到到了了例例8模模型的约束条件了。型的约束条件了。 计算得到以下结果：计算得到以下
51、结果： f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0.71x3 =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天天完完工工，其其余余的的工工序序按按正正常常时时间完工。间完工。2 2 统筹方法统筹方法72列出项目和工序的明细表；列出项目和工序的明细表；改平行、交叉工序；改平行、交叉工序；延用时差，抽调非关键工作上的人力物力延用时差，抽调非关键工作上的人力物力到支援关键工作，以加快关键工作的进度；到支援关键工作，以加快关键工作的进度；在最小成本的工作上赶工。在最小成本的工作上赶工。调整优化方法小结：调整优化方法小结：2 2 统筹方法统筹方法73第九章第九章 排序与统筹方法排序与统筹方法本章结束本章结束74
