管理运筹学第12章排序与统筹方法

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

2、如完成全部工作所用时间最短或费用最少等等）。等）。管管 理理 运运 筹筹 学学精选ppt2 1 1车间作业计划模型车间作业计划模型 车间作业计划是指一个工厂生产工序的计划和安排。车间作业计划是指一个工厂生产工序的计划和安排。 一、一台机器、一、一台机器、n个零件的排序问题个零件的排序问题 二、两台机器、二、两台机器、n个零件的排序问题个零件的排序问题管管 理理 运运 筹筹 学学精选ppt3 1 1车间作业计划模型车间作业计划模型一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题 例例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台某车间只有一台高精度的磨床，常常出现

3、很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？件在车间里停留的平均时间为最少？零件零件加工时间加工时间（小时）（小时）零件零件加工时间加工时间（小时）（小时）1231.82.00.54560.91.31.5管管 理理 运运 筹筹 学学精选ppt4 1 1车间作业计划模型车间作业计划模型 解：如果我们用解：如果我们用Pi表示

4、安排在第表示安排在第i位加工的零件所需的时间，用位加工的零件所需的时间，用Tj表示安排在第表示安排在第j位加工的零件在车间里总的停留时间，则有位加工的零件在车间里总的停留时间，则有 不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里位加

5、工的零件在车间里总的停留时间总的停留时间 ， . 可知这六个零件的停留时间为：可知这六个零件的停留时间为： 那么各个零件平均停留时间为那么各个零件平均停留时间为 从上式可知，对于一台机器从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。也就是按照时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。也就是按照3，4，5，6，1，

6、2的顺序来加工零件，可使各个零件的平均停留时间为最少。的顺序来加工零件，可使各个零件的平均停留时间为最少。6PP2P3P4P56654321PjiiiP1TjiijjjPPPPP1121.TjT654321654321543214321321211654321P2P3P4P5P6P)PPPPP(P)PPPP(P)PPP(P)PP(P)P(PPTTTTTT管管 理理 运运 筹筹 学学精选ppt51 1车间作业计划模型车间作业计划模型 按照按照3，4，5，6，1，2的顺序来加工零件，各个零件的停留时间的顺序来加工零件，各个零件的停留时间如表如表12-4所示。所示。 各个零件的平均停留时间为各个零件

7、的平均停留时间为 这与用这与用“先到先加工先到先加工”顺序所需平均停留时间顺序所需平均停留时间4.93相比较，有很相比较，有很大的进步。对于一台机器大的进步。对于一台机器n个零件的排序问题，我们按照加工时间个零件的排序问题，我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。少。 零件零件加工时间加工时间停留时间停留时间零件零件加工时间加工时间停留时间停留时间3450.50.91.30.51.42.76121.51.82.04.26.08).836.08.06.24.72.41.50h（表表12-4管管 理理

8、运运 筹筹 学学精选ppt6 1 1车间作业计划模型车间作业计划模型二、两台机器、二、两台机器、n n个零件个零件 例例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表磨床上加工，每台机器上各零件加工时间如表12-5所示。所示。表表12-5 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为为最少？最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加解：由于每个零件必

9、须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。工零件的顺序与在磨床上加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。车床、磨床在每个时间段的状况的图形所构成。零件零件车床车床磨床磨床零件零件车床车床磨床磨床1231.52.01.00.50.251.75451.250

10、.752.51.25管管 理理 运运 筹筹 学学精选ppt7 1 1车间作业计划模型车间作业计划模型 图图 12-1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的件越早加工，减少磨床等待的时间；另一方

11、面把在磨床上加工时间越短的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。零件加工任务所需总时间最少的零件排序方法。123451车床车床磨床磨床2345010管管 理理 运运 筹筹 学学精选ppt81 1车间作业计划模型车间作业计划模型 寻找例寻找例2的最优解：我们在表的最优解：我们在表12-5中找到所列出的最短加工时间是中找到所列出的最短加工时间是0.25,它是第二道工序磨床它是第二道工序磨床加工零件加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件的所需时间，由

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

13、个最短加工时间为下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件，这个加工时间是车床（第一工序）加工零件5的所需时间，故的所需时间，故把零件把零件5排在加工顺序的第一位上，同时把表中的零件排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表所在的行划去。如表12-6中蓝色线条所中蓝色线条所示。示。零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表表12-6管管 理理 运运 筹筹 学学精选ppt

14、9 同样，下一个最短加工时间为同样，下一个最短加工时间为1，这是车床加工零件，这是车床加工零件3的所需时间，故的所需时间，故把零件把零件3排在第二位上，同时把零件排在第二位上，同时把零件3所在的行划去。如表所在的行划去。如表12-6中黑色线条中黑色线条所示。所示。 这样就得到了最优加工顺序：这样就得到了最优加工顺序：5，3，4，1，2。一共只需。一共只需7个小时就能个小时就能完成全部加工。完成全部加工。 从例从例2中我们可以归纳出关于两台机器中我们可以归纳出关于两台机器n个零件的排序问题，使得全部个零件的排序问题，使得全部任务总的时间任务总的时间 最短的排序算法。最短的排序算法。 在加工所需时

15、间表上选出最短加工时间在加工所需时间表上选出最短加工时间tij，这是第，这是第i工序加工工序加工j零件所零件所需需时间，当时间，当i=1时，将零件时，将零件j的顺序尽量靠前，若的顺序尽量靠前，若i=2时，将零件时，将零件j的顺序尽量的顺序尽量靠后。在表上划去零件靠后。在表上划去零件j的所在行，回到步骤的所在行，回到步骤1。 1 1车间作业计划模型车间作业计划模型管管 理理 运运 筹筹 学学精选ppt102 2统筹方法统筹方法 统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：行分别讨论：一、计划网络图一、计划网络

16、图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。活动）进度表转换为统筹方法的网络图。 例例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。所示，请画出其统筹方法网络图。 表表12-8工序代号工序代号工序内容工序内容所需时间（天所需时间（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外

17、购生产原料外购生产原料自制主件自制主件主配件可靠性试验主配件可靠性试验601513388-aacb,d管管 理理 运运 筹筹 学学精选ppt112 2统筹方法统筹方法解解:用网络图表示上述的工序进度表用网络图表示上述的工序进度表 网络图中的点表示一个事件网络图中的点表示一个事件,是一个或若干个工序的开始或结束是一个或若干个工序的开始或结束,是相是相邻工序在时间上的分界点邻工序在时间上的分界点,点用圆圈表示点用圆圈表示,圆圈里的数字表示点的编号。弧圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上表示一个工序（或活动），弧的方向是从工序开始指向工序的结束

18、，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即对此弧所赋的权数对此弧所赋的权数 abcde601383815图图12-4管管 理理 运运 筹筹 学学精选ppt122 2统筹方法统筹方法 例例. 把例的工序进度表做一些扩充，如表把例的工序进度表做一些扩充，如表12-9，请画出其统筹方法，请画出其统筹方法的网络图。的网络图。 表表12-9工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序abcd60151338aacefgh810165b，d

19、de，管管 理理 运运 筹筹 学学精选ppt132 2统筹方法统筹方法 解：我们把工序扩充到图解：我们把工序扩充到图12-4发生了问题，由于是的紧前工发生了问题，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是，序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。题意不符。 为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。用来表示相邻工序的衔接关

20、系，不需要人力、物力等资源与时间。 152643a60b158e1013dc38f图图12-5管管 理理 运运 筹筹 学学精选ppt142 2统筹方法统筹方法 在网络图上添加、工序得网络图在网络图上添加、工序得网络图12-6。 在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图了一个点和虚工序如图12-7。1256734a6015bec13d388h510fg16图图12-6管管 理理 运运 筹筹 学学精选ppt152 2统筹方法统筹方法 在绘制统筹方法的网络图时，要注意图中不能有缺口和回路在绘制统筹方法的网络图

21、时，要注意图中不能有缺口和回路。1257834a6015bec13d388h510f616g图图12-700管管 理理 运运 筹筹 学学精选ppt162 2统筹方法统筹方法二、网络时间与关键路线二、网络时间与关键路线 在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。、每个工序的开始时间与结束时间。3、关键路线及其相应的关键工序。、关键路线及其相应的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时、非关键工序在不影响工程的完成时间的前提

22、下，其开始时间与结束时间可以推迟多久。间可以推迟多久。 例例5、某公司装配一条新的生产线，具体过程如表、某公司装配一条新的生产线，具体过程如表12-10,求：完成此求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间及结束时工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间及结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。推迟多久。管管 理理 运运 筹筹 学学精选ppt172 2统筹方法统筹方法表表12-10工序代号工序代号工序内容工序内容所需时间（天）所需时

23、间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,f,h管管 理理 运运 筹筹 学学精选ppt182 2统筹方法统筹方法解：据表解：据表12-10,绘制网络图如图绘制网络图如图12-8。 图图12-8 如图如图12-8 ,-就是一条关键路线，我们要干完所有的工序就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行

24、，所以网络中最就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路线。线。12346785a60b45echj35ig1030d204025f1815管管 理理 运运 筹筹 学学精选ppt192 2统筹方法统筹方法下面我们给出找关键路线的办法下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（和最早结束时间（EF) ，设一个工序所需的时间为，

25、设一个工序所需的时间为t，这对于同一，这对于同一个工序来说，有个工序来说，有 EF=ES+t。 工序工序a的最早的最早开始时间开始时间工序工序a的最早的最早完成时间完成时间12a0，6060图图12-9管管 理理 运运 筹筹 学学精选ppt202 2统筹方法统筹方法 图图12-10 其次其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间况下各个工序的最晚开始时间(缩写为缩写为LS)和最晚结束时间（缩写为和最晚结束时间（缩写为LF),显然对同一工序显然对同一工序 LS=LF-t1236785a0,6060b

26、60,10545e60,100c60,70h100,115j135,17035i110,135g80,11030d60,80204025f70,881841015管管 理理 运运 筹筹 学学精选ppt212 2统筹方法统筹方法 运用此法则，可以从首点开始计算出每个工序的运用此法则，可以从首点开始计算出每个工序的LF与与LS，如图，如图12-11所示。所示。 图图12-11 接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，称为该工序的条件下，工序最早开始（或结束）的时间可

27、以推迟的时间，称为该工序的时差，对每个工序来说其时差记为的时差，对每个工序来说其时差记为Ts有有 Ts=LS-ES=LF-EF1236785a0,60600,60b60,1054590,135e60,100c60,70h100,115j135,17035135,170i110,135g80,1103080,110d60,802060,804080,12025110,135f70,8818117,135410107,11715120,135管管 理理 运运 筹筹 学学精选ppt222 2统筹方法统筹方法 最后将各工序的时差，以及其他信息构成工序时间表如表最后将各工序的时差，以及其他信息构成工序时

28、间表如表12-11所所示。示。 表表12-11 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连成的从发点到收点的依次连成的从发点到收点的关键路线。关键路线。管管 理理 运运 筹筹 学学精选ppt23三、三、完成工序所需时间不确定时的网络时间和关键路线完成工序所需时间不确定时的网络时间和关键路线 当完成工序所需时间不确定的情况下怎样求网络时间和关键路线呢，当完成工序所需时间不确定的情况下怎样求网络时间和关键路线呢，下面我们结合案例介绍求解办法下面我们结合案例介绍求解办法. . 例例6. 长征研究院培训中心负责明年春天的各干部的工商管理培训，长征研究院培训中心负责明

29、年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表培训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。织工作的时间以保证培训工作如期举行。 解：由表解：由表12-12，绘出统筹方法的网络图如图，绘出统筹方法的网络图如图12-12所示。所示。12356487abecdfghi 图图12-122 2统筹方法统筹方法管管 理理 运运 筹筹 学学精选ppt242 2统筹方法统筹方法 活动

30、（工序）活动（工序）活动（工序）内容活动（工序）内容紧前活动紧前活动（工序）（工序） a b c d e f g h i 制定培训计划制定培训计划选聘培训教师选聘培训教师列出一些可供选择的培训地点列出一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备，器材，资料落实教学设备，器材，资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处理最后的一些事务处理最后的一些事务 - a - c b,d e b,d g f,h表表12-12管管 理理 运运 筹筹 学学精选ppt252 2统筹方法统筹方法 由于是第一次搞培训，缺乏经验和有关统计

31、资料来确定由于是第一次搞培训，缺乏经验和有关统计资料来确定完成每个活动所需时间，但对所需时间做了三种估计：完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指在顺利情况下乐观时间。指在顺利情况下,完成活动所需最少时间，用完成活动所需最少时间，用a表示。表示。2.最可能时间。指在正常情况下最可能时间。指在正常情况下,完成活动所需时间，用完成活动所需时间，用m表表示。示。3.悲观时间。指不顺利情况下，完成活动所需最多时间，用悲观时间。指不顺利情况下，完成活动所需最多时间，用b表示。如表表示。如表12-13所示所示. 管管 理理 运运 筹筹 学学精选ppt26表表12-13 单位：周单位

32、：周 活动活动 乐观时间乐观时间最可能时间最可能时间悲观时间悲观时间 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管管 理理 运运 筹筹 学学精选ppt272 2统筹方法统筹方法 显然这三种完成活动所需时间都具有一定概率，由经验，我们可以显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计分布。我们可以用如下公式计算出完成活动所需的平均时间：算出完成活动所需的

33、平均时间： 以及方差以及方差 例如：完成活动例如：完成活动g g所需平均时间：所需平均时间： 同时求出方差为同时求出方差为64bmaT262)(ab460.75.340.364bmaTg94管管 理理 运运 筹筹 学学精选ppt282 2统筹方法统筹方法 同样可以求出每个活动的完成所需平均时间及方差，如表同样可以求出每个活动的完成所需平均时间及方差，如表12-14： 表表12-14活动活动T（平均时间（平均时间) (方差方差)活动活动T （平均时间（平均时间)方差方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.028

34、2管管 理理 运运 筹筹 学学精选ppt292 2统筹方法统筹方法 下面就用平均时间代替完成活动所需时间，并在下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时网络图上标上每个活动最早开始时间和最早结束时间，如图间，如图12-14所示。所示。12345876a0,2g5,9b2,5e5,6d2,4f6,8c0,2i13,15h912-14管管 理理 运运 筹筹 学学精选ppt30同样也可以标上最晚开始时间和最晚完成时间等。同样也可以标上最晚开始时间和最晚完成时间等。12345876a0,2g5,9b2,5e5,6d2,4f6,8c0

35、,2i13,15h9,1321,3110,1145,949,1323,520,232,5213,15211,13图12-15管管 理理 运运 筹筹 学学精选ppt31表 12-15活动最早开始时间（ES）最晚开始时间（LS）最早完成时间（EF）最晚完成时间（LF）时差（LS-ES）是否为关键工序a00220是b22550是c01231否d23451否e5106115否f6118135否g55990是h9913130是i131315150是管管 理理 运运 筹筹 学学精选ppt322 2统筹方法统筹方法 从表从表12-15上我们找到了一条从发点到收点由关键工序上我们找到了一条从发点到收点由关键工

36、序a,b,g,h,i组成的组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：的时间之和： =2+3+4+4+2=15（周）（周） 同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和，方差也为关键路线上各关键活动方差之和1.05。 由此我们可以计算出此项培训组织工作不同完工时间的概率，如由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周

37、周内完工的概率。内完工的概率。 为求此概率，可以先求为求此概率，可以先求 值，值， 式中的式中的T为预定完工时间为预定完工时间16，E（T）=15， 算得算得 =0.976，查正态分布函数表可知概率为，查正态分布函数表可知概率为 ，即在即在16周内完工的概率为周内完工的概率为83.55%.)(TET 025. 105. 1ihgbaTTTTT8355. 0)976. 0()（管管 理理 运运 筹筹 学学精选ppt332 2统筹方法统筹方法其正态分布图如图其正态分布图如图12-16所示：所示： 如果我们要求以如果我们要求以99%的概率来保证培训组织工作如期做完，使培训工作的概率来保证培训组织工作

38、如期做完，使培训工作如期举行，也就是说，概率为如期举行，也就是说，概率为99%的完工时间应为多少周。在标准正态分布的完工时间应为多少周。在标准正态分布函数表中可查出函数表中可查出 的的 值为值为2.33，从公式从公式 得得 T=17.39(周）周）.也就是说只要在培训工作前也就是说只要在培训工作前17.39周周开始做培训组织工作就能保证培训工作如期举行。开始做培训组织工作就能保证培训工作如期举行。 9.90) （16图图12-1615)(025. 1TE15)(TET 管管 理理 运运 筹筹 学学精选ppt342 2统筹方法统筹方法四、网络优化四、网络优化 得到初始的计划方案，但通常要对初始方

39、案进行调整与完善。根据计得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划目标，综合考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划方案。划方案。 1.时间时间-资源优化资源优化 做法：做法： 1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。 2）利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高）利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高峰。峰。 3）统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平）统筹兼顾工程进度的要求和现有资源的限制，往

40、往要经过多次综合平衡，才能得到比较合理的计划方案。衡，才能得到比较合理的计划方案。 下面列举一个拉平资源需要量最高峰的实例。在例下面列举一个拉平资源需要量最高峰的实例。在例5中，若机械加工工人人数中，若机械加工工人人数为为65人，并假定这些工人可完成这人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间个工序任一个，下面来寻求一个时间-资源最优资源最优方案。如表方案。如表12-16所示：所示： 管管 理理 运运 筹筹 学学精选ppt352 2统筹方法统筹方法表表12-16工序工序需要人需要人数数最早开最早开始时间始时间所需时所需时间间时差时差d5860200f22701847g4280

41、300h391001520i26110250 若上述工序都按最早开始时间安排，那么从第若上述工序都按最早开始时间安排，那么从第60天至第天至第135天的天的75天天里，所需的机械加工工人人数如图里，所需的机械加工工人人数如图12-17所示。所示。管管 理理 运运 筹筹 学学精选ppt362 2统筹方法统筹方法 在图的上半部中，工序代号后的数字是所需机械加工工人数，点划线在图的上半部中，工序代号后的数字是所需机械加工工人数，点划线下面的数字是非关键工序时差长度。图的下半部表示从第下面的数字是非关键工序时差长度。图的下半部表示从第60天至天至135天内天内的的75天里，所需机械加工工人数，这样的图

42、称为资源负荷图。天里，所需机械加工工人数，这样的图称为资源负荷图。 274635 f(22人）人）18h(39人人)1558人人64人人80人人81人人42人人65人人60 70 80 90 100 110 120 130 d(58人）人） i(26人）人） g(42人）人）302025图图12-1726人人65人人工人数工人数时间时间/天天管管 理理 运运 筹筹 学学精选ppt372 2统筹方法统筹方法 同时我们应优先安排关键工序所需的工人，再利用非关键工序的时同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我差，错开各

43、工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序们让非关键工序f从第从第80天开始，工序天开始，工序h从第从第110天开始。找到了时间天开始。找到了时间-资源资源优化的方案，如图优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完所示，在不增加工人的情况下保证了工程按期完成。成。246753 f(22人）人） h(39人）人） d(58人）人） i(26人）人） g(42人）人）工人数工人数65人人 60 70 80 90 100 110 120 13058人人42人人64人人26人人65人人图图12-18时间时间/天天管管 理理 运运 筹筹 学学精选ppt

44、382 2统筹方法统筹方法2.时间时间-费用优化费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间是时间-费用优化要研究和解决的问题。费用优化要研究和解决的问题。 直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。需要增加一笔费用，成为直接费用。 间接费用：由于工程早日完工，减少了管

45、理人员的工资办公费等费用间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序作业时间越短，直接费用越多，间接费用越称为间接费用。一般说工序作业时间越短，直接费用越多，间接费用越少。少。管管 理理 运运 筹筹 学学精选ppt392 2统筹方法统筹方法 缩短工序的作业时间有一定的限度，这个限度称为工序的最快完成时间。缩短工序的作业时间有一定的限度，这个限度称为工序的最快完成时间。 我们设完成工序我们设完成工序j的正常所需时间为的正常所需时间为Tj;直接费用为直接费用为cj;完成工序完成工序j的最快完成时的最快完成时间为间为Tj,直接费用为直接费用为cj。这样我们可以

46、计算出缩短工序。这样我们可以计算出缩短工序j的一天工期所增加的直接的一天工期所增加的直接费用，用费用，用kj表示，称为直接费用变动率。有表示，称为直接费用变动率。有 时间时间-费用优化问题可建立两个线性规划模型。费用优化问题可建立两个线性规划模型。 模型一，在既定的时间模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。缩短工期而增加的直接费用最少。 设工序（设工序（i ,j)的提前完工时间为的提前完工时间为yij,我们用我们用Tij,Tij分别表示正常完工时间与最快分别表示正常完工时间与最快完工的时间，则

47、有工序（完工的时间，则有工序（i ,j)的实际完工时间为：的实际完工时间为：Tij-yij。我们用。我们用cij,cij表示用正表示用正常完工时间和最快完成时间完成工序所需要的费用，常完工时间和最快完成时间完成工序所需要的费用，kij为工序（为工序（i ,j)的直接费用的直接费用变动率。得到这个问题的线性规划模型如下：变动率。得到这个问题的线性规划模型如下： min f= （kij*yij) （i,j)s.t. xj-xi Tij-yij,对一切弧（对一切弧（i, j) yij Tij-Tij, 对一切弧（对一切弧（i, j) xn-x1 T, xi 0， yij 0。jjjjjTTcck管管

48、 理理 运运 筹筹 学学精选ppt402 2统筹方法统筹方法 例例7. 例例5所提供的信息都作为本例的信息，另外还给出所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表用和每缩短一天工期所需增加的直接费用，如表12-17所示所示。 管管 理理 运运 筹筹 学学精选ppt41表表12-17/ijijijijijTTcck缩短一天工期增加的直接费用（费用变动率元/天

49、）工序正常情况下采取措施后 正常完工时间/天 工序直接费用/元 最快完工时间/天 工序直接费用/元a(1,2)60100006010000-b(2,7)454500306300120c(2,3)10280054300300d(2,4)2070001011000400e(2,5)40100003512500500f(3,7)183600105440230g(4,6)3090002012500350h(5,7)153750105750400i(6,7)256250159150290j(7,8)35120003512000-/ijc/ijTijTijc管管 理理 运运 筹筹 学学精选ppt422 2

50、统筹方法统筹方法 该工程要求在该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天内完工，问每个工序应比正常完工时间提前多少天天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在求在140天完工呢？天完工呢？12345678abfechgijd图图12-19管管 理理 运运 筹筹 学学精选ppt432 2统筹方法统筹方法解：网络图如图解：网络图如图12-19所示，根据此网络图建立数学模型。所示，根据此网络图建立数学模型。 设此网络图上第设此网络图上第i点发生的时间为点发生的时间为xi，工序提前完工的时

51、间为，工序提前完工的时间为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-y67 x8-x7 35-y78管管 理理 运运 筹筹 学学精选ppt442 2统筹方法统筹方法 x1 =0, y12 0, y27 15, y

52、23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y67 10 y78 0 x8 150 xi 0，yij 0.（对一切可能的（对一切可能的ij)管管 理理 运运 筹筹 学学精选ppt45 用用“管理运筹学管理运筹学”软件进行计算，很快得到以下结果软件进行计算，很快得到以下结果： 也就是说我们缩短工序也就是说我们缩短工序g和工序和工序i的的10天工期，我们可以付出最少天工期，我们可以付出最少的直接费用的直接费用6400元，提前元，提前20天即在天即在150天里完成整个工程。天里完成整个工程。0,15010,1150,1000 ,1000 ,800 ,970 , 0 ,6

53、010 , 0 , 064005784673762552442337827267121yxyxyxyxyxyxyyxyyxf管管 理理 运运 筹筹 学学精选ppt46 如果工期要求在如果工期要求在140天里完成，那么我们只要在上述的线性规划的模天里完成，那么我们只要在上述的线性规划的模型里把约束条件中的最后一个：型里把约束条件中的最后一个： x8 150，改为，改为x8 140， 其余一切不变，用其余一切不变，用”管理运筹学软件管理运筹学软件”运算，得到如下结果：运算，得到如下结果： 为了使工程在为了使工程在140天里完成，我们至少要付出天里完成，我们至少要付出14900元的直接费用，元的直接

54、费用，各工序的开始时间和缩短的工期如解所示。各工序的开始时间和缩短的工期如解所示。, 01, 0415, 501, 01, 09, 0 ,955, , 07, 01 , 78. 0 , 0 ,600 , 0 , 0149007685774663752544237823212271yxyxyxyxyxyxyyxyyxf，管管 理理 运运 筹筹 学学精选ppt47 对于例对于例7这样的问题我们也可以用统筹法予以解决：这样的问题我们也可以用统筹法予以解决： 若要求我们在若要求我们在150天里完成工程，缩短了正常工期的天里完成工程，缩短了正常工期的20天。我们在关天。我们在关键路线上，找出直接费用变动率最低的关键工序，最大限度的缩短其完键路线上，找出直接费用变动率最低的关键工序，最大限度的缩短其完成的时间。成的时间。 从表