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

《管理运筹学第12章排序与统筹方法》由会员分享，可在线阅读，更多相关《管理运筹学第12章排序与统筹方法（21页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、型车间作业计划模型 例例1解：如果我们用解：如果我们用Pi表示安排在第表示安排在第i位加工的零件所需的时间，用位加工的零件所需的时间，用Tj表示安排表示安排在第在第j位加工的零件在车间里总的停留时间，则有位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。

5、法找到一种简便的算法。 对于某种加工顺序，我们知道安排在第对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为位加工的零件在车间里总的停留时间为Tj ， Tj = 可知这六个零件的停留时间为：可知这六个零件的停留时间为： 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

6、. 那么各个零件平均停留时间为那么各个零件平均停留时间为 从上式可知，对于一台机器从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。4管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学 11车间作业计划模型车间作业计划模型二、两台机器、二、两台机器、n n个零件个零件

7、例例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表磨床上加工，每台机器上各零件加工时间如表12-5所示。所示。表表12-5 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。工零件的顺序与在磨床上

8、加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。车床、磨床在每个时间段的状况的图形所构成。零件零件车床车床磨床磨床零件零件车床车床磨床磨床1231.52.01.00.50.251.75451.250.752.51.255管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学 11车间作业计划模型车间作业计划模型

9、 图图 12-1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件越晚加

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

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

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

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

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

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

16、可靠性试验601513388-aacb,d9管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学22统筹方法统筹方法解解:用网络图表示上述的工序进度表用网络图表示上述的工序进度表 网络图中的点表示一个事件网络图中的点表示一个事件,是一个或若干个工序的开始或结束是一个或若干个工序的开始或结束,是相是相邻工序在时间上的分界点邻工序在时间上的分界点,点用圆圈表示点用圆圈表示,圆圈里的数字表示点的编号。弧圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的

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

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

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

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

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

22、工序内容所需时间（天）所需时间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,f,h16管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学22统筹方法统筹方法解：据表解：据表12-10,绘制网络图如图绘制网络图如图12-8。 图图12-8 如图如图12-8 ,-就是一条关键路线，我们要干完所有的工序就是一条关键路线，我们要干完所有的工序就必须

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

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

25、然对同一工序有显然对同一工序有 LS=LF-t1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d60.80204025f70,88184101519管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学22统筹方法统筹方法 运用此法则，可以从首点开始计算出每个工序的运用此法则，可以从首点开始计算出每个工序的LF与与LS，如图如图12-11所示。所示。 接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束

26、）的时间可以推迟的时间，成为该工序的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为的时差，对每个工序来说其时差记为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,13520管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学22统筹方法统筹方法 最后将各工序的时差，以及其他信息构成工序时间表如表最后将各工序的时差，以及其他信息构成工序时间表如表12-11所所示。示。 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连接成的从发点到收点的依次连接成的从发点到收点的关键路线。关键路线。21