第2章排序与统筹方法ppt课件

《第2章排序与统筹方法ppt课件》由会员分享，可在线阅读，更多相关《第2章排序与统筹方法ppt课件（47页珍藏版）》请在金锄头文库上搜索。

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

2、工作所用时间最短或费用最少等等）。等）。落屎溯镍扯钉舶浓都诵峡卵罕膨篇靠讽啸帚桨村孟吠机鼓涝磺谁汞把崔军第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学 1 1车间作业计划模型车间作业计划模型 车间作业计划是指一个工厂生产工序的计划和安排。车间作业计划是指一个工厂生产工序的计划和安排。一、一台机器、一、一台机器、n个零件的排序问题个零件的排序问题二、两台机器、二、两台机器、n个零件的排序问题个零件的排序问题2杨逊较刺忠喀妖诫迂刹署标滇许填蔡狙事搔擎蝴氰佰还写裳氨件夕催思苇第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹

3、学学 1 1车间作业计划模型车间作业计划模型一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题 例例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？件在车间里停留的平均时间为最少？3零件零件加工时间加工时间（小时）

4、（小时）零件零件加工时间加工时间（小时）（小时）1231.82.00.54560.91.31.5馒丝烬额尊凿汉涡坑滋酚敛皋谱柱秉诽缉整疹岔努贺托回函缓著醚脆乐谣第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学 1 1车间作业计划模型车间作业计划模型 4 解：如果我们用解：如果我们用Pi表示安排在第表示安排在第i位加工的零件所需的时间，用位加工的零件所需的时间，用Tj表示安排在第表示安排在第j位加工的零件在车间里总的停留时间，则有位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平

5、均停留时间，如何得到一个使得各零件不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。法找到一种简便的算法。 对于某种加工顺序，我们知道安排在第对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为位加工的零件在车间里总的停留时间为Tj ， Tj = 可知这六个零件的停留时间为：可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) +

6、 (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个零件的排序问题，只要系数越大，配上加工时个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，

7、加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。样碾诌巧劝撩熬折驭宦缩索哪惹迅牢瘴痪产袍邦努炎园切蚊谎菌贺毁脖锹第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学 1 1车间作业计划模型车间作业计划模型二、两台机器、二、两台机器、n n个零件个零件 例例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表磨床上加工，每台机器上各零件加工时间如表12-5所示。所示。

8、表表12-5 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为为最少？最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。工零件的顺序与在磨床上加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和中的线条图来表

9、示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。车床、磨床在每个时间段的状况的图形所构成。5零件零件车床车床磨床磨床零件零件车床车床磨床磨床1231.52.01.00.50.251.75451.250.752.51.25晰烈壁批倪攫菊厨律蚜氓干纯餐所骑共爵杜迭朱掩兑肉牧弟礁毅汀冷脓蛔第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学 1 1车间作业计划模型车间作业计划模型 图图 12-1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料

10、造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。零件加工任务所需总时间最少的零件排序方法。

11、6123451车床车床磨床磨床2345010囱劝反夕简酷纲鹤堂掷哮凝睫弹着荔殴幂允慕屁纪冶寞惋氨代喜佰延槽出第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学1 1车间作业计划模型车间作业计划模型 寻找例寻找例2的最优解：我们在表的最优解：我们在表12-5中找到所列出的最短加工时间是中找到所列出的最短加工时间是0.25,它是第二道工序磨它是第二道工序磨床床加工零件加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五放在加工顺序的末尾，即第五位，并在表中划去零件位，并在表中划去

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

13、5的所需时间，故的所需时间，故把零件把零件5排在加工顺序的第一位上，同时把表中的零件排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表所在的行划去。如表12-6中蓝色线条所中蓝色线条所示。示。7零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表表12-6列儿驰屎疫武龋弹叠喇婪献戮杉塞国着绷罢搏跺忌法讫绵咖根拇妥藐茁术第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学 1 1

14、车间作业计划模型车间作业计划模型 同样，下一个最短加工时间为同样，下一个最短加工时间为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。8另坛瓣地站总樟科娃哮瓢庭灶仁彻店睬澳灸奏澎吊诛荒法崩清焦侧徊垛泥第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面统筹方法包

16、括绘制计划网络图、进度安排、网络优化等环节，下面进进行分别讨论：行分别讨论：一、计划网络图一、计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为为活动）进度表转换为统筹方法的网络图。活动）进度表转换为统筹方法的网络图。 例例3、某公司研制新产品的部分工序与所需时间以及它们之间的相、某公司研制新产品的部分工序与所需时间以及它们之间的相互互关系都显示在其工序进度表如表关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。所示，请画出其统筹方法网络图。 表表12-89工序代号工序代号工序内容工序内容所需时间（

17、天所需时间（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配件可靠性试验主配件可靠性试验601513388-aacb,d烦妊健泵栓块瘪敞欧埂鸽防虫监畴起惶涕硅辈贬市秸勾谴慎列屡赘临嗣后第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法解解:用网络图表示上述的工序进度表用网络图表示上述的工序进度表 网络图中的点表示一个事件网络图中的点表示一个事件,是一个或若干个工序的开始或结束是一个或若干个工序的开始或结束,是是相相邻工序在时间上的分界点邻工序在时间上

18、的分界点,点用圆圈表示点用圆圈表示,圆圈里的数字表示点的编号。圆圈里的数字表示点的编号。弧弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即即对此弧所赋的权数对此弧所赋的权数 10abcde601383815图图12-4旁弥稻译阀忠碘耙莫丑盾侩捉嘻忌绵篱蛛尺不攫膛砒菇忽簇慌条滇琼鹏麻第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法

19、 例、把例的工序进度表做一些扩充，如表例、把例的工序进度表做一些扩充，如表12-9，请画出其统筹方，请画出其统筹方法的网络图。法的网络图。 表表12-911工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序abcd60151338aacefgh810165b，dde，腔疵檀吗膘木寓恭惩倘紧浚波膳彻屯窥泄畜痞鹿仆仪赚列挺伐玲营驾痞伍第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 解：我们把工序扩充到图解：我们把工序扩充到图12-4发生了问题，由于是的紧前发生了问题

20、，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是工序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，由于工序的结束也是，所以工序也成了工序的紧前工序，所以工序也成了工序的紧前工序，与题意不符。与题意不符。 为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。 12152643a60b158e1013dc38f图图12-5播整羹捍虞支谨遁囱肿尼焕墨俱气闷碾理垄运挂队趁钧者扭幢好钨俩仍

21、牲第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 在网络图上添加、工序得网络图在网络图上添加、工序得网络图12-6。 在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图了一个点和虚工序如图12-7。131256734a6015bec13d388h510fg16图图12-6吨朴睦法切浸喷函吻熙克豢纽搀祁砚硬垦享沦锰临压选郊酱乡氢环八唤拈第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 在绘制

22、统筹方法的网络图时，要注意图中不能有缺口和回路在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。141257834a6015bec13d388h510f616g图图12-700瘦蠢炬均职厉搬没弗幕密援揉拐小疾粥粘缎哨掌冠竭速五狗隙护铁外秒碟第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法二、网络时间与关键路线二、网络时间与关键路线 在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。、每个工序的开始

23、时间与结束时间。3、关键路线及其应用的关键工序。、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。间可以推迟多久。 例例5、某公司装配一条新的生产线，具体过程如表、某公司装配一条新的生产线，具体过程如表12-10,求：完成此求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间及结束时工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间及结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以间和非关键工序在不影响工程完成时间的

24、前提下，其开始时间与结束时间可以推迟多久。推迟多久。15训挚位淬丽僵拷续踪些惟厘吏么嚣串航维堂淹纫羊硬嗜峨恬驻惰蟹择婿仗第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法表表12-1016工序代号工序代号工序内容工序内容所需时间（天）所需时间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,

25、f,h铣楔裴冠峡酶河训功昌垢刀怠继笼殊敲测咀油篇策气暮楞社寅乖必钟鹃鹅第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法解：据表解：据表12-10,绘制网络图如图绘制网络图如图12-8。 图图12-8 如图如图12-8 ,-就是一条关键路线，我们要干完所有的就是一条关键路线，我们要干完所有的工序工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最最长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路长的路线就决定了完成整个工程所需的最少时间，这条路

26、线称为关键路线。线。1712346785a60b45echj35ig1030d204025f1815赎婶庐肄纷喇肺食膜叉诀艳狄砷攘酬蘸伴悔泄妖苹农局澡崩蜕伶政矽茅憋第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法下面我们给出找关键路线的办法下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（和最早结束时间（EF) ，设一个工序所需的时间为，设一个工序所需的时间为t，这对于同一，这对于同一个工序来说，有个工序来说，有

27、 EF=ES+t。 18工序工序a的最早的最早开始时间开始时间工序工序a的最早的最早完成时间完成时间12a0，6060图图12-9密个迈怎龟幽驹触定因艰蚕泻鸦荫舞皱恤宜尝循殆脓颗毅先拱匿其吵曹泵第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 19 图图12-10 其次其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间况下各个工序的最晚开始时间(缩写为缩写为LS)和最晚结束时间（缩写为和最晚结束时间（缩写为LF),显然对同一工序有显然对同一工序

28、有 LS=LF-t1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d60.80204025f70,881841015碍累投枫纂安涩昼邮蜡擦碾俯集觉执虫郧社奢抹燎道菜瘟架隔秽溶肋裕僵第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 20 运用此法则，可以从首点开始计算出每个工序的运用此法则，可以从首点开始计算出每个工序的LF与与LS，如图，如图12-11所示。所示。 图图12-11 接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间

29、接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，称为该工序的条件下，工序最早开始（或结束）的时间可以推迟的时间，称为该工序的时差，对每个工序来说其时差记为的时差，对每个工序来说其时差记为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,

30、135屿初冈钞祥绳垣沈膀竣强撞练息烬托吐爬贡旱拱阉航涡籽丧衫谜絮蔓惟徐第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 最后将各工序的时差，以及其他信息构成工序时间表如表最后将各工序的时差，以及其他信息构成工序时间表如表12-11所所示。示。 表表12-11 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连成的从发点到收点的依次连成的从发点到收点的关键路线。关键路线。21爆涸蔷绅炔稳迷债录标结悠饮牧碳掳兢喇驳脏造潦屁澈志盟并侣柜僳匣悼第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理

31、 运运 筹筹 学学三、完成工序所需时间与关键路线三、完成工序所需时间与关键路线 当完成工序所需时间不确定的情况下如何求网络时间和关键路线？当完成工序所需时间不确定的情况下如何求网络时间和关键路线？ 例例6. 长征研究院培训中心负责明年春天的各干部的工商管理培训，长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表培训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举

32、行。组织工作的时间以保证培训工作如期举行。 解：由表解：由表12-12，绘出统筹方法的网络图如图，绘出统筹方法的网络图如图12-12所示。所示。2212356487abecdfghi 图图12-122 2统筹方法统筹方法藤菜惦掣苛乙荷殃痈科稀戳痞硬募榆双帖败当狗层儿错摈陀藻配你莹吁桐第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 活动（工序）活动（工序）活动（工序）内容活动（工序）内容紧前活动紧前活动（工序）（工序） a b c d e f g h i 制定培训计划制定培训计划选聘培训教师选聘培训教师列出一些可供选择的培训地点列出

33、一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备，器材，资料落实教学设备，器材，资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处理最后的一些事务处理最后的一些事务 - a - c b,d e b,d g f,h23表表12-12露旬恬喂闯墩张汾吱顿屏旺恰戮挺焕凝棍锄幢锻楞泣汐暮错铜墨敏沏渴摩第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 由于是第一次搞培训，缺乏经验和有关统计资料来确由于是第一次搞培训，缺乏经验和有关统计资料来确定定完成每个活动所需时间，但对所

34、需时间做了三种估计：完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指在顺利情况下乐观时间。指在顺利情况下,完成活动所需最少时间，用完成活动所需最少时间，用a表示。表示。2.最可能时间。指在正常情况下最可能时间。指在正常情况下,完成活动所需时间，用完成活动所需时间，用m表示。表示。3.悲观时间。指不顺利情况下，完成活动所需最多时间，悲观时间。指不顺利情况下，完成活动所需最多时间，用用b表示。如表表示。如表12-13所示所示. 24燥冰岛摹铸俩栅抠噶贤胀悄颅链科箱置襄诊址维谚松诽柠氓胜词惯芒揖戎第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学

35、表表12-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.525镐嫡惯誓空填深耍整倘藻谗沽煤钧渴暮泣卉革华施技腥咨掺瘸赏实减非叭第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 显然这三种完成活动所需时间都具有一定概率，由经验，我们可以显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布

36、近似服从可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计分布。我们可以用如下公式计算出完成活动所需的平均时间：算出完成活动所需的平均时间： 以及方差以及方差 例如：完成活动例如：完成活动g g所需平均时间：所需平均时间： 同时求出方差为同时求出方差为26痘悸恒途万淀颤曲脓祸有丫扫绩伎属掣榨痔倒嚏垫差泪陕粳船胚立筒哭叭第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 同样可以求出每个活动的完成所需平均时间及方差，如表同样可以求出每个活动的完成所需平均时间及方差，如表12-14： 表表12-1427活动活动T（平均时间（平

37、均时间) (方差方差)活动活动T （平均时间（平均时间)方差方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.028阜晚痹拽裕翻惊闺瘦满钟嘻坦塞望缨五念弛扫考俯掌祭硒溺伐箩玛酬眨晋第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 下面就用平均时间代替完成活动所需时间，并在下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时网络图上标上每个活动最早开始时间和最早结束时间，如图间，如图12-14所示。所示。2812345876a

38、0,2g5,9b2,5e5,6d2,4f6,8c0,2i13,15h9,13322214242图12-14但寇侨苔澳青洁翱趾缝卢鱼猴揪鸟德止诊班土柑晚玛倦伍燕岩茫贯剧财暖第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学同样也可以标上最晚开始时间和最晚完成时间等。同样也可以标上最晚开始时间和最晚完成时间等。2912345876a0,2g5,9b2,5e5,6d2,4f6,8c0,2i13,15h9,1321,3110,1145,949,1323,520,232,5213,15211,13图12-15沟抬统己娘渠喀刮谜歧疤娜西瓤件活载聘不仓抡二招砂麦恍央店碳

39、检驱忠第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学活动最早开始时间（ES）最晚开始时间（LS）最早完成时间（EF）最晚完成时间（LF）时差（LS-ES）是否为关键工序a00220是b22550是c01231否d23451否e5106115否f6118135否g55990是h9913130是i131315150是30表 12-15崎搽谬莱谬惶家霉簧沂屉汁码砰止滞熔涟琉送篓膀眠帽笑寞囱需嚣尖赁狗第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 从表从表12-15上我们找到了一条从发点到收点由关

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

41、项培训组织工作不同完工时间的概率，如16周周内完工的概率。内完工的概率。 为求此概率，可以先求为求此概率，可以先求 值。值。 式中的式中的T为预定完工时间为预定完工时间16，E（T）=15， 算得算得 =0.976。查正态分布函数表可知概率为。查正态分布函数表可知概率为0.8355。即。即16周内完工周内完工的概率为的概率为83.55%.31邦裔尘猩纹踪汐呻济嘱晚京朽鞠琵膘谚亦须诚供冷疟邹家咖丝某妈仪湛蚤第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法其正态分布图如图其正态分布图如图12-16所示：所示：3216图图12-1615颈

42、希胡孜凰瘦垒戚肃服屈囱恨弗蔗砌奋久窥亮朋细黍项付坦钓杜埠钨网秦第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法四、网络优化四、网络优化 得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划目标，综合考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划方案。划方案。 1.时间时间-资源优化资源优化 做法：做法： 1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。 2）利用非关键

43、工序的时差，错开各工序的开始时间，拉平资源需要量的高）利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高峰。峰。 3）统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平）统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平衡，才能得到比较合理的计划方案。衡，才能得到比较合理的计划方案。 下面列举一个拉平资源需要量最高峰的实例。在例下面列举一个拉平资源需要量最高峰的实例。在例5中，若机械加工工人人数中，若机械加工工人人数为为65人，并假定这些工人可完成这人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间个工序任一个，下面来寻求一个时间-资源最优资源最优方案

44、。如表方案。如表12-16所示：所示： 33予玛徊烘桂龄夫遗悠雁旨虾曼吉凤熔徊紧馈泞贮凹滤烦琅塘丑融妆季影魄第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法表表12-1634工序工序需要人需要人数数最早开最早开始时间始时间所需时所需时间间时差时差d5860200f22701847g4280300h391001520i26110250 若上述工序都按最早开始时间安排，那么从第若上述工序都按最早开始时间安排，那么从第60天至第天至第135天的天的75天天里，所需的机械加工工人人数如图里，所需的机械加工工人人数如图12-17所示。所示。诡

45、痢狞最翌巍何孝溪穗垂湃奇缘说惦蕾曹俺松鲤霉篡较窘抨妈键虎陵茬份第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 在图的上半部中，工序代号后的数字是所需机械加工工人数，点划在图的上半部中，工序代号后的数字是所需机械加工工人数，点划线线下面的数字是非关键工序时差长度。图的下半部表示从第下面的数字是非关键工序时差长度。图的下半部表示从第60天至天至135天天内内的的75天里，所需机械加工工人数，这样的图称为资源负荷图。天里，所需机械加工工人数，这样的图称为资源负荷图。 35274635 f(22人）人）18h(39人人)1558人人64人

46、人80人人81人人42人人65人人60 80 100 120 130 d(58人）人） i(26人）人） g(42人）人）302025图图12-1726人人65人人工人数工人数时间时间/天天他沁敛渍凉抗匣机廊夷事嫁绩健熙巨曙瓢边膊贱敬兢贰涛据造掷渗玖妖幸第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 同时我们应优先安排关键工序所需的工人，再利用非关键工序的时同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过

47、调整，我我们让非关键工序们让非关键工序f从第从第80天开始，工序天开始，工序h从第从第110天开始。找到了时间天开始。找到了时间-资资源源优化的方案，如图优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完所示，在不增加工人的情况下保证了工程按期完成。成。36246753 f(22人）人） h(39人）人） d(58人）人） i(26人）人） g(42人）人）工人数工人数65人人60 80 100 120 13058人人42人人64人人26人人65人人图图12-18时间时间/天天渝腮汰枣具蹭撰还永换佩勿叶末讳纠殿架凉回栖环透揭色孪嗽装卒诚蕊凛第2章排序与统筹方法ppt课件第2章

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

49、直接费用。 间接费用：由于工程早日完工，减少了管理人员的工资办公费等费间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用用称为间接费用。一般说工序作业时间越短，直接费用越多，间接费用越称为间接费用。一般说工序作业时间越短，直接费用越多，间接费用越少。少。37兼潜休雄层王裂蹿誉敛柜韶旬梳冯揍忿政拾獭伙笼歇吞赏融抗克场竭赚凉第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 缩短工序的作业时间有一定的限度，这个限度称为工序的最快完成时间。缩短工序的作业时间有一定的限度，这个限度称为工序的最快完成时间。 我们设完成工序我们设完成工

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

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

52、j,对一切弧（对一切弧（i, j) yij Tij-Tij, 对一切弧（对一切弧（i, j) xn-x1 T, xi 0， yij 0。38獭剃乾珍菏忧肋捂莱便纺谨和愚薛隘坎喉窥友聂晋君鄙官弘虫擦赎墨讣拥第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 例例7. 例例5所提供的信息都作为本例的信息，另外还给出所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费间，以及对应正常完工时间与最快完工时

53、间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表用和每缩短一天工期所需增加的直接费用，如表12-17所示所示。 39伶岸历剿家方迸苹撂蓝系策傣蒂灵坏艾能猪被喉谜盆蓟垢疏愚赖事聪戌坝第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学表表12-1740缩短一天工期增加的直接费用（费用变动率元/天）工序正常情况下采取措施后 正常完工时间/天 工序直接费用/元 最快完工时间/天 工序直接费用/元a(1,2)60100006010000-b(2,7)454500306300120c(2,3)10280054300300d(2,4)2070001011000

54、400e(2,5)40100003512500500f(3,7)183600105440230g(4,6)3090002012500350h(5,7)153750105750400i(6,7)256250159150290j(7,8)35120003512000-/ijc裹槛吟价镰座脱绰锐静秤搅探众逃滦嚣街屡澜咋界松茂规欲筐玲生钢肘贼第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 该工程要求在该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天内完工，问每个工序应比正常完工时间提前多少天天完成，才能使整个工程因缩短工期

55、而增加的直接费用为最少。如果工期完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要要求在求在140天完工呢？天完工呢？4112345678abfechgijd图图12-19释戈吩拥璃攻肛屎许军恃爹幂招恶蕉凳炒搞肘燕木瞧楼基萎进巩焦辉绕弊第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法解：网络图如图解：网络图如图12-19所示，根据此网络图建立数学模型。所示，根据此网络图建立数学模型。 设此网络图上第设此网络图上第i点发生的时间为点发生的时间为xi，工序提前完工的时间为，工序提前完工的时间为yij。 目标函数目标函数mi

56、nf=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-y7842挞娱锰搏燕谍组京鄂傅吵缘根饮郎乘腮亲拟骑虞驾细兑猿裤奉醚脆圃醛巳第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方

57、法统筹方法 x1 =0, y12 0, y27 15, y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y67 10 y78 0 x8 150 xi 0，yij 0.（对一切可能的（对一切可能的ij)43轻茎龟翘侥剿庸历峡驳迸弘搂嘛怠轨蒸搏荧辑洒眷茫锐黑魏蓖境乐钳肩搅第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学用“管理运筹学”软件进行计算，很快得到以下结果：44兑蘑肪侧傍拳碧簧纶茄果贤尿丝寞旭恰牲内束屁供曳耳函题额床亭目涉扼第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方

58、法统筹方法 模型二，我们知道直接费用是随着完成时间的缩短而增加，而间模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为计划期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个和各个工序最优完成时间的模型为：工序最优完成时间的模型为： 目标函数目标函数min f=d(xn-x1)+ s.t. xj

59、-xi Tij-yij，对一切弧（，对一切弧（i ,j) yij Tij-Tij ，对一切弧（，对一切弧（i ,j) xi 0， yij 0。45磋疲芯责洲织提群体裁连绥蕴雇蠢豁漳转谁碟跪脱淫忙炼弱岁笼踌绰呈哇第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学2 2统筹方法统筹方法 例例8 如果在例如果在例7中，每天的间接费用为中，每天的间接费用为330元，求使包括间接费用与直接费元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。和各个工序最优完成时间。 解：决策变量解：决

60、策变量xi和和yij的含义同例的含义同例7。 此数学模型的目标函数为：此数学模型的目标函数为： min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+400y57+290y67 此模型的约束条件与例此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去的约束条件基本相同，只要在例子的约束条件中去掉掉x8 150就得到了例就得到了例8模型的约束条件了。模型的约束条件了。 计算得到以下结果：计算得到以下结果： f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0.46

61、井估绦秦签底堪欲装斌推诞政棒伴译但跺坍绝散钾绅洒辕况狂愈皑裤免穷第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件管管 理理 运运 筹筹 学学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天完工，其余的工序按天完工，其余的工序按正正常时间完工。常时间完工。47噶潞桩癸鞋广秤锚揩逐葵拦沟誊洼龙廖窘靠蚤杂澈杀彝羌寄湾凉詹遍邻潮第2章排序与统筹方法ppt课件第2章排序与统筹方法ppt课件