1、1第九章第九章 排序与统排序与统筹方法筹方法*马飞雄马飞雄/GDUFS2第九章第九章 排序与统筹方法排序与统筹方法第一节第一节 车间作业计划模型车间作业计划模型第二节第二节 统筹方法统筹方法 在本章中，我们将介绍车间作业计划模型和统筹方法。在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳照怎样的次序、怎样的时间表来做这些工作，使得效果最佳
2、（例如完成全部工作所用时间最短或费用最少等等）。（例如完成全部工作所用时间最短或费用最少等等）。*马飞雄马飞雄/GDUFS3 1 1 车间作业计划模型车间作业计划模型 车间作业计划是指一个工厂生产工序车间作业计划是指一个工厂生产工序的计划和安排。的计划和安排。一、一台机器、一、一台机器、n个零件的排序问题个零件的排序问题二、两台机器、二、两台机器、n个零件的排序问题个零件的排序问题*马飞雄马飞雄/GDUFS4一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题 例例1.某车间只有一台高精度的磨床，常常出现很某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现
3、有六个零件多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。同时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？才能使得这六个零件在车间里停留的平均时间为最少？零件零件 加工时间（小时）加工时间（小时）零件零件 加工时间（小时）加工时间（小时）1231.82.00.54560.91.31.5 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS5 例例1解：如果我们用解：如果我们用Pi表示安排在第表示安排在第i
4、位加工的零位加工的零件所需的时间，用件所需的时间，用Tj表示安排在第表示安排在第j位加工的零件在车位加工的零件在车间里总的停留时间，则有间里总的停留时间，则有 Tj=P1+P2+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第对于某种加工顺序，我们知道安排在第j位加工的位加
5、工的零件在车间里总的停留时间为零件在车间里总的停留时间为Tj，Tj=jiiP1 jiiP1 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS6可知这六个零件的停留时间为：可知这六个零件的停留时间为：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.那么各个零件平均停留时间为那么各个零件平均停留时间为623456654321pppppp 从上式可知，对于一台机器从上式可知，对于一台机器n个零件的排序问
6、题，只要系数个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各零件的平均停留时间最少。后面，可使各零件的平均停留时间最少。1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS7二、两台机器、二、两台机器、n n个零件个零件 例例2.某工厂根据合同定做一些零件，这些零件要某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机求先在车床上车削，然后再在磨床
7、上加工，每台机器上各零件加工时间如下表所示。器上各零件加工时间如下表所示。应该如何安排这五个零件的先后顺序才能使完应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？成这五个零件的总的加工时间为最少？零件零件 车床车床 磨床磨床 零件零件 车床车床 磨床磨床1231.52.01.00.50.251.75451.250.752.51.25 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS8 解：解：由于每个零件必须先进行车床加工，再进行磨床加工，由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是所以在车床上
8、加工零件的顺序与在磨床上加工零件的顺序是一样的。如果这些零件在车床上和磨床上加工顺序都为一样的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图。我们用图12-1中的线条图来表示各零件加工的开始中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。个时间段的状况的图形所构成。零件零件 车床车床 磨床磨床 零件零件 车床车床 磨床磨床1231.52.01.00.50.251.75451.250.752.51.25 1 1 车间作业计划模型车间作业计划模型*图图 12-
9、1 从上图中我们可以看出，加工时间的延长主要是从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件越晚加工，间；另一方面把在磨床上加工时间越短的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全以便充分利用
10、前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。部零件加工任务所需总时间最少的零件排序方法。123451车车床床磨磨床床23450101.52.01.0 1.25 0.750.50.251.752.51.25*马飞雄马飞雄/GDUFS10 寻找例寻找例2的最优解：我们在上表中找到所列出的最的最优解：我们在上表中找到所列出的最短加工时间是短加工时间是0.25,它是第二道工序磨床加工零件它是第二道工序磨床加工零件2的所的所需时间，由于这个时间与磨床有关，故我们把零件需时间，由于这个时间与磨床有关，故我们把零件2放放在加工顺序的末尾，即第五位，并在表中划去零件在加工顺
11、序的末尾，即第五位，并在表中划去零件2 所所在行。如表中红色线条所示。在行。如表中红色线条所示。零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)1231.52.01.00.50.251.75451.250.752.51.25 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS11接着，我们又找到最短加工时间为接着，我们又找到最短加工时间为0.5，这一时间与磨，这一时间与磨床（第二工序）有关，我们把磨床加工时间为床（第二工序）有关，我们把磨床加工时间为0.5的零的零件件1放到除第五外的加工顺序的末尾，
12、即第四位加工，放到除第五外的加工顺序的末尾，即第四位加工，同时把表中的零件同时把表中的零件1所在的行划去。如表中黄色线条所在的行划去。如表中黄色线条所示。所示。零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)1231.52.01.00.50.251.75451.250.752.51.25 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS12 下一个最短加工时间为下一个最短加工时间为0.75，这个加工时，这个加工时间是车床（第一工序）加工零件间是车床（第一工序）加工零件5的所需时间，的所需时间，故把
13、零件故把零件5排在加工顺序的第一位上，同时把排在加工顺序的第一位上，同时把表中的零件表中的零件5所在的行划去。如表中蓝色线条所在的行划去。如表中蓝色线条所示。所示。零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)1231.52.01.00.50.251.75451.250.752.51.25 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS13同样，下一个最短加工时间为同样，下一个最短加工时间为1，这是车床加，这是车床加工零件工零件3的所需时间，故把零件的所需时间，故把零件3排在第二位上，排在第二
14、位上，同时把零件同时把零件3所在的行划去。如表中黑色线条所在的行划去。如表中黑色线条所示。所示。零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)零零件件车床车床(第一工序第一工序)磨床磨床(第二工序第二工序)1231.52.01.00.50.251.75451.250.752.51.25 1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS14这样就得到了最优加工顺序：这样就得到了最优加工顺序：5，3，4，1，2。0.751.01.251.52.01.251.752.50.5 0.255磨床磨床车床车床3412534127这样一共只需这样一共只需7个小时就能完成全
15、部加工。个小时就能完成全部加工。1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS15 从例从例2中我们可以归纳出关于两台机器中我们可以归纳出关于两台机器n个个零件的排序问题，使得全部任务总的时间最短零件的排序问题，使得全部任务总的时间最短的排序算法。的排序算法。步骤步骤1:在加工所需时间表上选出最短加工时在加工所需时间表上选出最短加工时间间tij，这是第，这是第i工序加工工序加工j零件所需时间，零件所需时间，步骤步骤2:当当i=1时，将零件时，将零件j的顺序尽量靠前，的顺序尽量靠前，若若i=2时，将零件时，将零件j的顺序尽量靠后。的顺序尽量靠后。步骤步骤3:在表上划去零件在表
16、上划去零件j的所在行，回到步的所在行，回到步骤骤1。1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS16思考题：思考题：m台机器台机器n个个零件的排序问题零件的排序问题如何解决？如何解决？1 1 车间作业计划模型车间作业计划模型*马飞雄马飞雄/GDUFS172 2 统筹方法统筹方法 统筹法又称网络计划法。它是以网络图反映、统筹法又称网络计划法。它是以网络图反映、表达计划安排，据以选择最优工作方案，组织协调表达计划安排，据以选择最优工作方案，组织协调和控制生产（项目）的进度（时间）和费用（成和控制生产（项目）的进度（时间）和费用（成本），使其达到预定目标，获得更佳经济效益的一本
17、），使其达到预定目标，获得更佳经济效益的一种优化决策方法。种优化决策方法。1957年，美国化学公司年，美国化学公司Du Pont的的M.R.Walker与与Rand通用电子计算机公司的通用电子计算机公司的J.E.Kelly为了协调公司为了协调公司内部不同业务部门的工作内部不同业务部门的工作,共同研究出关键路线方法共同研究出关键路线方法（简记作（简记作CPM）.首次把这一方法用于一家化工厂的首次把这一方法用于一家化工厂的筹建，结果筹建工程提前两个月完成筹建，结果筹建工程提前两个月完成.随后又把这一随后又把这一方法用于工厂的维修，结果使停工时间缩短了方法用于工厂的维修，结果使停工时间缩短了47个个
18、小时，当年就取得节约资金达百万元的要观效益。小时，当年就取得节约资金达百万元的要观效益。*1958年，美国海军武器规划局特别规划室研制含约年，美国海军武器规划局特别规划室研制含约3000项项工作任务的北极星导弹潜艇计划，参与的厂商达工作任务的北极星导弹潜艇计划，参与的厂商达11000多家。为多家。为了有条不紊地实施如此复杂的工作，特别规划室领导人了有条不紊地实施如此复杂的工作，特别规划室领导人W.Fazar积极支持与推广由专门小组创建的计划评审技术（简积极支持与推广由专门小组创建的计划评审技术（简记作记作PERT）。结果研制计划提前两个完成，取得了极大的成功。）。结果研制计划提前两个完成，取得
19、了极大的成功。CPM在民用企业与在民用企业与PERT在军事工业中的显著成效在军事工业中的显著成效,自然引自然引起了普遍的重视。很快起了普遍的重视。很快CPM与与PERT就被应用于工业、农业、就被应用于工业、农业、国防与科研等等复杂的计划管理工作中国防与科研等等复杂的计划管理工作中,随后又推广到世界各国。随后又推广到世界各国。在应用推广在应用推广CPM与与PERT的过程中的过程中,又派生出多种各具特点，各又派生出多种各具特点，各有侧重的类似方法。但是万变不离其宗，各种有所不同的方法，有侧重的类似方法。但是万变不离其宗，各种有所不同的方法，其基本原理都源于其基本原理都源于CPM与与PERT。*马飞
20、雄马飞雄/GDUFS19CPM与与PERT两种方法实质上大同小异，两种方法实质上大同小异，因此，人们把因此，人们把CPM与与PERT及其他类似方法及其他类似方法统称为网络计划技术，简称为网络技术或网统称为网络计划技术，简称为网络技术或网络方法，简记为络方法，简记为统筹法统筹法。统筹方法包括绘制计划网络图、进度安统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：排、网络优化等环节，下面进行分别讨论：一、计划网络图一、计划网络图 统筹方法的第一步工作就是绘制计划网统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表络图，也就是将工序（或称为活动）进度表转换
21、为统筹方法的网络图。转换为统筹方法的网络图。2 统筹方法统筹方法*马飞雄马飞雄/GDUFS20网络图画法网络图画法(一一)、结构、结构网络图中的点表示一个事件网络图中的点表示一个事件,是一个或若干个工是一个或若干个工序的开始或结束序的开始或结束,是相邻工序在时间上的分界点是相邻工序在时间上的分界点,点用点用圆圈表示圆圈表示,圆圈里的数字表示点的编号。圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，面标以完成
22、此工序所需的时间（或资源）等数据，即为对此弧所赋的权数。即为对此弧所赋的权数。例如：例如：5a122 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS21(二二)、画法注意事项：、画法注意事项：(1)、从左、从左右右1234567824331212 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS22(2)、两事项间只有一个工序、两事项间只有一个工序bij75a32 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS23(3)、不允许回路、不允许回路1232 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS24(4)、虚工序的运用、虚工序的运用120 正确表达工序的前行、后续关系正确表达工序的前行、后续
23、关系(连结、连结、隔离隔离)解决画法中问题：网络图中只有一个始解决画法中问题：网络图中只有一个始点和一个终点，中间点前后均要有弧相连接，点和一个终点，中间点前后均要有弧相连接，不允许中断。不允许中断。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS251234657824031302012 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS26ijk750a3b2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS27例例1、假设某工作有、假设某工作有a,b,c,d四个工序四个工序,c在在 a,b完工后开始，完工后开始，d在在 b完工后开始。完工后开始。cabdabcd2 2 统筹方法统筹方法*马飞
24、雄马飞雄/GDUFS28例例3、某公司研制新产品的部分工序与所需时间以及、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。所示，请画出其统筹方法网络图。工序工序代号代号工序工序内容内容所需时间所需时间（天（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配可靠性试验主配可靠性试验601513388-aacb,d2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS29解：用网络图表示上述的工序进度表。解
25、：用网络图表示上述的工序进度表。abcde601383815工序工序代号代号工序工序内容内容所需时间所需时间（天（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配可靠性试验主配可靠性试验601513388-aacb,d2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS30 例、把例的工序进度表做一些扩充，如例、把例的工序进度表做一些扩充，如下表，请画出其统筹方法的网络图。下表，请画出其统筹方法的网络图。工序工序代号代号所需时间所需时间（天）（天）紧前紧前工序工序工序工序代号代号所需时所需时间间(天天)紧前工紧
26、前工序序abcd60151338aacefgh810165b，dde,2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS31工序工序代号代号所需时间所需时间（天）（天）紧前紧前工序工序工序工序代号代号所需时所需时间间(天天)紧前工紧前工序序abcd60151338aacefgh810165b，dde,152643a60b158e1013dc38f7g168由于是的由于是的紧前工序，故紧前工序，故的结束应该的结束应该是的开始，是的开始，所以代表的所以代表的弧的起点应该弧的起点应该是是，由于工，由于工序的结束也序的结束也是是，所以工，所以工序也成了工序也成了工序的紧前工序的紧前工序，与题意不序，与
27、题意不符。符。为此我们设为此我们设立虚工序。立虚工序。虚工序是实虚工序是实际上并不存际上并不存在而虚设的在而虚设的工序，用来工序，用来表示相邻工表示相邻工序的衔接关序的衔接关系，不需要系，不需要人力、物力人力、物力等资源与时等资源与时间。间。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS32工序工序代号代号所需时间所需时间（天）（天）紧前紧前工序工序工序工序代号代号所需时所需时间间(天天)紧前工紧前工序序abcd60151338aacefgh810165b，dde,152643a60b158e1013dc38fg16在统筹方法在统筹方法的网络图中的网络图中不允许两个不允许两个点之间多于点之
28、间多于一条弧，因一条弧，因此需增加一此需增加一个点和虚工个点和虚工序序2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS33工序工序代号代号所需时间所需时间（天）（天）紧前紧前工序工序工序工序代号代号所需时所需时间间(天天)紧前工紧前工序序abcd60151338aacefgh810165b，dde,152643a60b158e1013dc38f716g8h5在绘制统筹方法的网在绘制统筹方法的网络图时，要注意图中络图时，要注意图中不能有缺口和回路。不能有缺口和回路。2 2 统筹方法统筹方法*练习练习工序工序 内容内容 工时工时(天天)紧前工序紧前工序 A 初步研究初步研究 1 /B 研究选点研
29、究选点 2 A C 准备调研方案准备调研方案 4 A D 联系调研点联系调研点 2 B E 培训工作人员培训工作人员 3 B,C F 准备表格准备表格 1 C G 实地调研实地调研 5 D,E,F H 写调研报告写调研报告 2 G I 开会汇总开会汇总 3 H*马飞雄马飞雄/GDUFS3512325FE200C413DBAGHI1234567892 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS36二、网络时间与关键路线二、网络时间与关键路线路线：在网络图上从始点（发点）开始，沿弧路线：在网络图上从始点（发点）开始，沿弧的方向（即按各工序的顺序）连续不断地到终点的方向（即按各工序的顺序）连续不
30、断地到终点（收点）的一条路线。（收点）的一条路线。例如：例如：12325FE200C413DBAGHI1234567892 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS37关键路线：网络中最长的路线，通常可用双线标关键路线：网络中最长的路线，通常可用双线标出。关键路线的长等于该路线上各工序的时间之和，出。关键路线的长等于该路线上各工序的时间之和，又称为工程时间或工期，其它路线称为非关键路线。又称为工程时间或工期，其它路线称为非关键路线。关键（非关键）工序：关键路线上的各工序，其关键（非关键）工序：关键路线上的各工序，其它工序称为非关键工序。它工序称为非关键工序。12325FE200C413D
31、BAGHI123456789工期工期T182 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS38显然，缩短工期就是要缩短关键路线的长度，显然，缩短工期就是要缩短关键路线的长度，也就是说要加快关键工序的进度。而缩短非关键路也就是说要加快关键工序的进度。而缩短非关键路线的长度或缩短非关键工序的时间均不能缩短工期。线的长度或缩短非关键工序的时间均不能缩短工期。12325FE200C413DBAGHI123456789工期工期T182 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS39在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。
32、、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。时间与结束时间可以推迟多久。例例5、某公司装配一条新的生产线，具体过程如下表、某公司装配一条新的生产线，具体过程如下表,求：求：完成此工程的最少时间，关键路线及相应的关键工序，各工完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前序的最早开始时间和非关键工
33、序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。提下，其开始时间与结束时间可以推迟多久。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS40工序代号工序代号工序内容工序内容所需时间所需时间(天天)紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,f,h2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS41解：据表绘制网络图如图。解：据表
34、绘制网络图如图。12346785a60b45echj35ig1030d204025f1815如图如图,-就是一条关键路线，我们要干完就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线就是关了完成整个工程所需的最少时间，这条路线就是关键路线。键路线。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS42下面我们给出找关键路线的办法下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最
35、首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（早开始时间（ES)和最早结束时间（和最早结束时间（EF)，设一个工序所需的，设一个工序所需的时间为时间为t，这对于同一个工序来说，有，这对于同一个工序来说，有:EF=ES+t。工序工序a的最早的最早开始时间开始时间工序工序a的最早的最早完成时间完成时间11a0，60602 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS43g80,11030d60.8020e60.100h100,11515j135,170a0,6060其次其次,从网络的收点开始计算出在不影响整个工程最从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的
36、最晚开始时间早结束时间的情况下各个工序的最晚开始时间(缩写缩写为为LS)和最晚结束时间（缩写为和最晚结束时间（缩写为LF),显然对同一工序显然对同一工序有有:LS=LF-t85b60,1054535i110,1354025f70,881841017263c60,702 2 统筹方法统筹方法*f70,8810107,1174080,120e60.1003080,110g80,110d60.802060,80i110.13515120,135j135,17035135,170a0,60600,60 运用此法则，可以从首点开始计算出每个工序的运用此法则，可以从首点开始计算出每个工序的LF与与LS，如
37、下图所示。，如下图所示。185b60,1054590,135c60,70h100,11525110,13518117,1354接着，可以计算出每一个工序的时差，把在不影响接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为对每个工序来说其时差记为Ts有有 Ts=LS-ES=LF-EF7236*马飞雄马飞雄/GDUFS45 最后将各工序的时差，以及其他信息构成工序时间最后将各工序的时差，以及其他信息构成工序
38、时间表如下表所示。一般来说，关键工序的时差为零。表如下表所示。一般来说，关键工序的时差为零。这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连接成的依次连接成的从发点到收点的关键路线。从发点到收点的关键路线。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS46练习：设某工程的资料如以下网络图所示，练习：设某工程的资料如以下网络图所示，用时差的方法求关键线路。用时差的方法求关键线路。1253411252248967423abcde4fghijk2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS47三、完成工序所需时间与关键路线三、完成工序所需时间与关键路线 当完成工
39、序所需时间不确定的情况下如何求网络时间当完成工序所需时间不确定的情况下如何求网络时间和关键路线？和关键路线？例例6.长征研究院培训中心负责明年春天的各干部的工长征研究院培训中心负责明年春天的各干部的工商管理培训商管理培训,培训中心列出有关培训组织的各项活动的信息培训中心列出有关培训组织的各项活动的信息如表如表12-12所示所示,要求绘制出统筹方法的网络图，设法求出要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。保证培训工作如期举行。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS48
40、活动活动(工序工序)活动（工序）内容活动（工序）内容紧前活动紧前活动(工序工序)a bc d e f ghi 制定培训计划制定培训计划选聘培训教师选聘培训教师列出一些可供选择的培训地点列出一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备落实教学设备,器材器材,资料资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处理最后的一些事务处理最后的一些事务 -a -c b,d e b,d g f,g2 2 统筹方法统筹方法*12356487abecdfghi活动活动活动（工序）内容活动（工序）内容紧前活动紧前活动a bc d e f
41、ghi 制定培训计划制定培训计划选聘培训教师选聘培训教师列出一些可供选择的培训地点列出一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备落实教学设备,器材器材,资料资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处理最后的一些事务处理最后的一些事务 -a -c b,d e b,d g f,g*由于是第一次搞培训，缺乏统计来确定完成每由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用乐观时间。指所需最少时间，用a表示。表示。
42、2.最可能时间。指正常时间，用最可能时间。指正常时间，用m表示。表示。3.悲观时间。指不顺利情况下，最多时间，用悲观时间。指不顺利情况下，最多时间，用b表示。表示。如下表（单位：周）所示：如下表（单位：周）所示：活动活动 乐观时间乐观时间最可能时间最可能时间悲观时间悲观时间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*马飞雄马飞雄/GDUFS51 显然这三种完成活动所需时间都具有一定概率，显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时
43、间的概率分布近由经验，我们可以可以假定这些时间的概率分布近似服从似服从 分布。我们可以用如下公式计算出完成活分布。我们可以用如下公式计算出完成活动所需的平均时间：动所需的平均时间：以及方差以及方差 64bmaT 22)6(ab 2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS52例如：完成工作例如：完成工作g g所需平均时间：所需平均时间：同时求出方差为同时求出方差为460.75.340.364 bmaTg942 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS53 同样可以求出每个活动的完成所需平均时间及方差，同样可以求出每个活动的完成所需平均时间及方差，如下表：如下表：活动活动 T（平均时
44、间）（平均时间）方差方差活动活动T方差方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.0282 2 统筹方法统筹方法*i13,152i13,15 下面就用平均时间代替完成活动所需时间，并在下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时网络图上标上每个活动最早开始时间和最早结束时间，如图间，如图12-14所示。所示。2345876同样也可以标上最晚开始时间和最晚完成时间等。同样也可以标上最晚开始时间和最晚完成时间等。a0,2g5,9b2,5e5,6d2,4f6,8c0,2h9,1
45、33222142412345876a0,2g5,9b2,5e5,6d2,4f6,8c0,2h9,1321,3110,1145,949,1323,520,232,5213,15211,13图图12-14图图12-151*马飞雄马飞雄/GDUFS55 从表从表12-15上我们找到了一条从发点到收点由关键工序上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线，用双线标出来。则完成培训工作组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）（周）同时完成时间近似服从一定的概率分布正态
46、分布，则均同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和值为关键路线上各关键活动之均值之和15，方差也为关键路，方差也为关键路线上各关键活动方差之和线上各关键活动方差之和1.05。由此我们可以计算出此项培训组织工作不同完工时间的由此我们可以计算出此项培训组织工作不同完工时间的概率，如概率，如16周内完工的概率。周内完工的概率。ihgbaTTTTT 2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS56 为求此概率，可以先求为求此概率，可以先求u值。值。式中的式中的T为预定完工时间为预定完工时间16，E（T）=15，算得算得u=0.976。查正态分布函数表可知
47、概率为。查正态分布函数表可知概率为0.8355。即。即16周内完工的概率为周内完工的概率为83.55%.)(TETu 025.105.1 2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS57其正态分布图如图其正态分布图如图12-16所示：所示：1615)(025.1 TE 图图12-162 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS58四、网络优化四、网络优化 得到初始的计划方案，但通常要对初始方案进得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方低成本等目标，进行
48、网络优化，确定最优的计划方案。案。1.时间时间-资源优化资源优化做法：做法：1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。次综合平衡。2 2 统筹方法统筹方法*马飞雄马飞雄/GDUFS59下面列举一个拉平资源需要量最高峰的实例。在例下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为中，若加工工人为65人，并假定这些工人可完成这人，并假定这些工人可完成这5个工序任一个，下面来
49、寻求一个时间个工序任一个，下面来寻求一个时间-资源最优方案。资源最优方案。如表如表12-16所示：所示：表表12-16工序工序需要人数需要人数最早开始时间最早开始时间所需时间所需时间时差时差d5860200f22701847g428030h391001520i261102502 2 统筹方法统筹方法*d(58人）人）2015h(39人人)g(42人）人）i(26人）人）在图的上半在图的上半部中，工序代号部中，工序代号后的数字是人数，后的数字是人数，线下面的数字是线下面的数字是非关键工序时差非关键工序时差长度。图的下半长度。图的下半部表示从第部表示从第60天天至至135天内的天内的75天里，所需
50、机械天里，所需机械加工工人数，这加工工人数，这样的图称为资源样的图称为资源负荷图。负荷图。274635 f(22人）人）1858人人64人人80人人81人人42人人26人人65人人60 80 100 120 1303025图图12-17 若上述工序都按最早开始时间安排，那么从第若上述工序都按最早开始时间安排，那么从第60天至第天至第135天的天的75天里，所需的机械加工工人人数如天里，所需的机械加工工人人数如图图12-17所示。所示。*h(39人）人）g(42人）人）d(58人）人）i(26人）人）同 时 我 们 应 优同 时 我 们 应 优先安排关键工序所先安排关键工序所需的工人，再利用需的
