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

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

1、管管 理理 运运 筹筹 学学第十二章第十二章 排序与统筹方法排序与统筹方法第一节第一节 车间作业方案模型车间作业方案模型第二节第二节 统筹方法统筹方法 在本章中，我们将引见车间作业方案模型和在本章中，我们将引见车间作业方案模型和统筹方法。这两个问题虽然处置的方法有所不同，统筹方法。这两个问题虽然处置的方法有所不同，但当我们面临必需完成假设干项不能同时进展的但当我们面临必需完成假设干项不能同时进展的任务时，它们都将协助我们应该按照怎样的次序、任务时，它们都将协助我们应该按照怎样的次序、怎样的时间表来做这些任务，使得效果最正确怎样的时间表来做这些任务，使得效果最正确例如完成全部任务所用时间最短或费

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

3、情况，现有六个零件同时要求加工，这六个零件磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间加工所需时间如下表所示。如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才应该按照什么样的加工顺序来加工这六个零件，才干使得这六个零干使得这六个零件在车间里停留的平均时间为最少？件在车间里停留的平均时间为最少？零件零件加工时间加工时间小时小时零件零件加工时间加工时间小时小时1231.82.00.54560.91.31.5管管 理理 运运 筹筹 学学 1 1 车间作作业方案模型方案模型 例例1解：假解：假设我我们用用Pi表示安排在第表示安排在第i位加工的零件所需的位加工的零件所需的时

4、间，用，用Tj表表示安排在第示安排在第j位加工的零件在位加工的零件在车间里里总的停留的停留时间，那么有，那么有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工不同的加工顺序得到不同的各零件的平均停留序得到不同的各零件的平均停留时间，如何得到一个使，如何得到一个使得各零件的平均停留得各零件的平均停留时间最少的排序呢？最少的排序呢？这就是我就是我们最后要最后要处理的理的优化化问题，而且我，而且我们要要设法找到一种法找到一种简便的算法。便的算法。 对于某种加工于某种加工顺序，我序，我们知道安排在第知道安排在第j位加工的零件在位加工的零件在车间里里总的停的停留留时间为Tj ， Tj

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 车间作作业方案模型方案模型二、两台机器、二、两台机器、n n个零件个零件 例例2.2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在再在磨床上加工，每台机器上各零件加工时间如表磨床上加工，每台机器上各零件加工时间如表12-512-5所示。所示。表表12

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

8、由一根时间轴和中的线条图来表示各零件加工的开场时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的情况的图形所构成。车床、磨床在每个时间段的情况的图形所构成。零件零件车床车床磨床磨床零件零件车床车床磨床磨床1231.52.01.00.50.251.75451.250.752.51.25管管 理理 运运 筹筹 学学 1 1 车间作作业方案模型方案模型 图图 12-1 从上图中我们可以看出，加工时间的延伸主要是由于磨床的停工待料从上图中我们可以看出，加工时间的延伸主要是由于磨床的停工待料呵斥的，只需减少磨床的停工待料的时间就能减少整个加工义务的总时间。呵斥的，只需减少磨床的停工待料的时间

9、就能减少整个加工义务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工义务所需总时间最少的零件排序方法。零件加工义务所需总时间最少的零件排序方法。123451车床车床磨床磨床2345010管管 理理 运运 筹筹 学学1 1 车间作作业方案模型方案模

10、型 寻觅例寻觅例2的最优解：我们在表的最优解：我们在表12-5中找到所列出的最短加工时间是中找到所列出的最短加工时间是0.25,它是第二道工序磨床它是第二道工序磨床加工零件加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五放在加工顺序的末尾，即第五位，并在表中划去零件位，并在表中划去零件2 所在行。如表所在行。如表12-6中红色线条所示。中红色线条所示。 接着，我们又找到最短加工时间为接着，我们又找到最短加工时间为0.5，这一时间与磨床第二工序有关，我们把，这一时间与磨床第二工序有关，我们把 磨床加磨床加工时间

11、为工时间为0.5的零件的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件表中的零件1所在所在的行划去。如表的行划去。如表12-6中黄色线条所示。中黄色线条所示。 下一个最短加工时间为下一个最短加工时间为0.75，这个加工时间是车床第一工序加工零件，这个加工时间是车床第一工序加工零件5的所需时间，故的所需时间，故把零件把零件5排在加工顺序的第一位上，同时把表中的零件排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表所在的行划去。如表12-6中蓝色线条所中蓝色线条所示。示。零件零件车床车床第一工序第一工序磨床磨床第二工

12、序第二工序零件零件车床车床第一工序第一工序磨床磨床第二工序第二工序1231.52.01.00.50.251.75451.250.752.51.25表表12-6管管 理理 运运 筹筹 学学 同样，下一个最短加工时间为同样，下一个最短加工时间为1，这是车床加工零件，这是车床加工零件3的所需时间，故的所需时间，故把零件把零件3排在第二位上，同时把零件排在第二位上，同时把零件3所在的行划去。如表所在的行划去。如表12-6中黑色线条中黑色线条所示。所示。 这样就得到了最优加工顺序：这样就得到了最优加工顺序：5，3，4，1，2。一共只需。一共只需7个小时就能个小时就能完成全部加工。完成全部加工。 从例从例

13、2中我们可以归纳出关于两台机器中我们可以归纳出关于两台机器n个零件的排序问题，使得全部个零件的排序问题，使得全部义务总的时间义务总的时间 最短的排序算法。最短的排序算法。 在加工所需时间表上选出最短加工时间在加工所需时间表上选出最短加工时间tij，这是第，这是第i工序加工工序加工j零件所需零件所需时间，当时间，当i=1时，将零件时，将零件j的顺序尽量靠前，假设的顺序尽量靠前，假设i=2时，将零件时，将零件j的顺序尽量的顺序尽量靠后。在表上划去零件靠后。在表上划去零件j的所在行，回到步骤的所在行，回到步骤1。 1 1 车间作作业方案模型方案模型管管 理理 运运 筹筹 学学2 2 统筹方法筹方法

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

15、。 表表12-8工序代号工序代号工序内容工序内容所需时间天所需时间天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购消费原料外购消费原料自制主件自制主件主配可靠性实验主配可靠性实验601513388-aacb,d管管 理理 运运 筹筹 学学2 2 统筹方法筹方法解解:用网络图表示上述的工序进度表用网络图表示上述的工序进度表 网络图中的点表示一个事件网络图中的点表示一个事件,是一个或假设干个工序的开场或终了是一个或假设干个工序的开场或终了,是是相相邻工序在时间上的分界点邻工序在时间上的分界点,点用圆圈表示点用圆圈表示,圆圈里的数字表示点的编号。弧圆圈里

16、的数字表示点的编号。弧表示一个工序或活动，弧的方向是从工序开场指向工序的终了，弧上表示一个工序或活动，弧的方向是从工序开场指向工序的终了，弧上是各工序的代号，下面标以完成此工序所需的时间或资源等数据，即是各工序的代号，下面标以完成此工序所需的时间或资源等数据，即为对此弧所赋的权数为对此弧所赋的权数 abcde601383815图图12-4管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 例、把例的工序进度表做一些扩展，如例、把例的工序进度表做一些扩展，如表表12-9，请画出其统筹方法的网络图。，请画出其统筹方法的网络图。 表表12-9工序代号工序代号所需时间天所需时间天紧前工序紧前工序工序代

17、号工序代号所需时间天所需时间天紧前工序紧前工序abcd60151338aacefgh810165b，dde，管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 解：我解：我们把工序把工序扩展到展到图12-4发生了生了问题，由于是的，由于是的紧前工序，故的前工序，故的终了了应该是的开是的开场，所以代表的弧的起点，所以代表的弧的起点应该是是，由于工序的，由于工序的终了也是了也是，所以工序，所以工序也成了工序的也成了工序的紧前工序，与前工序，与题意不符。意不符。 为此我此我们设立虚工序。虚工序是立虚工序。虚工序是实践践上并不存在而虚上并不存在而虚设的工序，用来表示相的工序，用来表示相邻工工序的序的衔

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

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

20、时间与终了时间可以推迟多久。间可以推迟多久。 例例5、某公司装配一条新的消费线，详细过程如表、某公司装配一条新的消费线，详细过程如表12-10,求：完成此求：完成此工程的最少时间，关键道路及相应的关键工序，各工序的最早开场时间和工程的最少时间，关键道路及相应的关键工序，各工序的最早开场时间和非关键工序在不影响工程完成时间的前提下，其开场时间与终了时间可以非关键工序在不影响工程完成时间的前提下，其开场时间与终了时间可以推迟多久。推迟多久。管管 理理 运运 筹筹 学学2 2 统筹方法筹方法表表12-10工序代号工序代号工序内容工序内容所需时间天所需时间天紧前工序紧前工序abcdefghij消费线设

21、计消费线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,f,h管管 理理 运运 筹筹 学学2 2 统筹方法筹方法解：据表解：据表12-10,绘制网制网络图如如图12-8。 图12-8 如如图12-8 ,-就是一条关就是一条关键道路，我道路，我们要干完一切的工序要干完一切的工序就必需走完一切就必需走完一切这样的道路，由于很多工序可以同的道路，由于很多工序可以同时进展，所以网展，所以网络中最中最长的道路就决的

22、道路就决议了完成整个工程所需的最少了完成整个工程所需的最少时间，这条道路称条道路称为关关键路路线。12346785a60b45echj35ig1030d204025f1815管管 理理 运运 筹筹 学学2 2 统筹方法筹方法下面我们给出找关键道路的方法下面我们给出找关键道路的方法 首先，从网络的发点开场，按顺序计算出每个工序的最早开场时首先，从网络的发点开场，按顺序计算出每个工序的最早开场时间间ES )和最早终了时间和最早终了时间EF) ，设一个工序所需的时间为，设一个工序所需的时间为t，这对于同，这对于同一一个工序来说，有个工序来说，有 EF=ES+t。 工序工序a的最早的最早开场时间开场时

23、间工序工序a的最早的最早完成时间完成时间11a0，6060图图12-9管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 图图12-10 其次其次,从网络的收点开场计算出在不影响整个工程最早终了时间的情从网络的收点开场计算出在不影响整个工程最早终了时间的情况下各个工序的最晚开场时间况下各个工序的最晚开场时间(缩写为缩写为LS)和最晚终了时间缩写为和最晚终了时间缩写为LF),显然对同一工序有显然对同一工序有 LS=LF-t1236785a0,6060b60,10545e60.100c60,70h100,115j,17035i110.g80,11030d60.80204025f70,8818410

24、15管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 运用此法那么，可以从首点开场计算出每个工序的运用此法那么，可以从首点开场计算出每个工序的LF与与LS，如图，如图12-11所示。所示。 接着，可以计算出每一个工序的时差，把在不影响工程最早终了时间接着，可以计算出每一个工序的时差，把在不影响工程最早终了时间的条件下，工序最早开场或终了的时间可以推迟的时间，成为该工序的条件下，工序最早开场或终了的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为的时差，对每个工序来说其时差记为Ts有有 Ts=LS-ES=LF-EF1236785a0,60600,60b60,1054590,e60

25、.100c60,70h100,115j,17035,170i110.g80,1103080,110d60.802060,804080,12025110,f70,8818117,410107,11715120,管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 最后将各工序的时差，以及其他信息构成工序时间表如表最后将各工序的时差，以及其他信息构成工序时间表如表12-11所所示。示。 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次衔接成的从依次衔接成的从发点到收点的发点到收点的关键道路。关键道路。管管 理理 运运 筹筹 学学三、完成工序所需时间与关键道路三、完成工序所

26、需时间与关键道路 当完成工序所需时间不确定的情况下如何求网络时间和关键道路？当完成工序所需时间不确定的情况下如何求网络时间和关键道路？ 例例6. 长征研讨院培训中心担任明年春天的各干部的工商管理培训，培长征研讨院培训中心担任明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制出所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键道路，并确定开场这个组织统筹方法的网络图，设法求出网络时间和关键道路，并确定开场这个组织任务的时间以保证培训任务如期举行。任务的时间以保证培训任务如期举行。 解：由表解：由表1

27、2-12，绘出统筹方法的网络图如图，绘出统筹方法的网络图如图12-12所示。所示。12356487abecdfghi 图图12-122 2 统筹方法筹方法管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 活动工序活动工序活动工序内容活动工序内容紧前活动紧前活动工序工序 a b c d e f g h i 制定培训方案制定培训方案选聘培训教师选聘培训教师列出一些可供选择的培训地点列出一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备，器材，资料落实教学设备，器材，资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处置最后的一些事

28、务处置最后的一些事务 - a - c b,d e b,d g f,g管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用乐观时间。指所需最少时间，用a表示。表示。2.最能够时间。指正常时间，用最能够时间。指正常时间，用m表示。表示。3.悲观时间。指不顺利情况下，最多时间，用悲观时间。指不顺利情况下，最多时间，用b表示。如表表示。如表12-13所示：所示： 表表12-13 单位：周单位：周 活动活动 乐

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

30、如：完成任务例如：完成任务g g所需平均时间：所需平均时间： 同时求出方差为同时求出方差为管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 同样可以求出每个活动的完成所需平均时间同样可以求出每个活动的完成所需平均时间及方差，如表及方差，如表12-14： 表表12-14活动活动T平均时平均时间间方差方差活动活动T方差方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.028管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 下面就用平均时间替代完成活动所需时间，下面就用平均时间替代完成活动所需时间，并在网络图上标上每个活

31、并在网络图上标上每个活动最早开场时间和最早终了时间，如图动最早开场时间和最早终了时间，如图12-14所示。所示。12345876同样也可以标上最晚开场时间和最晚完成时间等。同样也可以标上最晚开场时间和最晚完成时间等。a0,2g5,9b2,5e5,6d2,4f6,8c0,2i13,15h9,1332221424212345876a0,2g5,9b2,5e5,6d2,4f6,8c0,2i13,15h9,1321,3110,1145,949,1323,520,232,5213,15211,13图12-14图12-15管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 从表从表12-15上我们找到了一

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

33、此我们可以计算出此项培训组织任务不同完工时间的概率，如16周周内完工的概率。内完工的概率。 为求此概率，可以先求为求此概率，可以先求u值。值。 式中的式中的T为预定完工时间为预定完工时间16，ET=15， 算得算得u=0.976。查正态分布函数表可知概率为。查正态分布函数表可知概率为0.8355。即。即16周内完工周内完工的概率为的概率为83.55%.管管 理理 运运 筹筹 学学2 2 统筹方法筹方法其正态分布图如图其正态分布图如图12-16所示：所示：16图图12-16管管 理理 运运 筹筹 学学2 2 统筹方法筹方法四、网络优化四、网络优化 得到初始的方案方案，但通常要对初始方案得到初始的

34、方案方案，但通常要对初始方案进展调整与完善。根据计进展调整与完善。根据计划目的，综合思索资源和降低本钱等目的，进展网络划目的，综合思索资源和降低本钱等目的，进展网络优化，确定最优的计优化，确定最优的计划方案。划方案。 1. 1.时间时间- -资源优化资源优化 做法：做法： 1 1优先安排关键工序所需的资源。优先安排关键工序所需的资源。 2 2利用非关键工序的时差，错开各工序的利用非关键工序的时差，错开各工序的开场时间。开场时间。 3 3统筹兼顾工程进度的要求和现有资源的统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。限制，多次综合平衡。 下面列举一个拉平资源需求量最顶峰的实例。下面列举一

35、个拉平资源需求量最顶峰的实例。在例在例5 5中，假设加工工人中，假设加工工人为为6565人，并假定这些工人可完成这人，并假定这些工人可完成这5 5个工序任一个，个工序任一个，下面来寻求一个时间下面来寻求一个时间- -资源最优方案。如表资源最优方案。如表12-1612-16所示：所示： 管管 理理 运运 筹筹 学学2 2 统筹方法筹方法表表12-16工序工序需求人需求人数数最早开最早开场时间场时间所需时所需时间间时差时差d5860200f22701847g428030h391001520i26110250 假设上述工序都按最早开场时间安排，那么从第假设上述工序都按最早开场时间安排，那么从第60天

36、至第天的天至第天的75天天里，所需的机械加工工人人数如图里，所需的机械加工工人人数如图12-17所示。所示。管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键工序时差长度。图的下半部表示从第工序时差长度。图的下半部表示从第60天至天内的天至天内的75天里，所需机械天里，所需机械加工工人数，这样的图称为资源负荷图。加工工人数，这样的图称为资源负荷图。 274635 f(22人人18h(39人人)1558人人64人人80人人81人人42人人26人人65人人60 80 100 1

37、20 130 d(58人人 i(26人人 g(42人人302025图图12-17管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 同时我们应优先安排关键工序所需的工人，再利用非关键工序的时同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开场时间，从而拉平工人需求量的顶峰。经过调整，我差，错开各工序的开场时间，从而拉平工人需求量的顶峰。经过调整，我们让非关键工序们让非关键工序f从第从第80天开场，工序天开场，工序h从第从第110天开场。找到了时间天开场。找到了时间-资源资源优化的方案，如图优化的方案，如图12-18所示，在不添加工人的情况下保证了工程按期完所示，在不添

38、加工人的情况下保证了工程按期完成。成。246753 f(22人人 h(39人人 d(58人人 i(26人人 g(42人人工人数工人数65人人60 80 100 120 13058人人42人人64人人26人人65人人图图12-18管管 理理 运运 筹筹 学学2 2 统筹方法筹方法2.时间时间-费用优化费用优化 需求思索时间与费用的问题：在既定的时间前工程完工的前提下，使需求思索时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间是时间-费用优化要研讨和处理的问题。

39、费用优化要研讨和处理的问题。 直接费用：为了加快工程进度，需求添加人力、设备和任务班次，这直接费用：为了加快工程进度，需求添加人力、设备和任务班次，这需求添加一笔费用，成为直接费用。需求添加一笔费用，成为直接费用。 间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。普通说工序越短，直接费用越多，间接费用越少。称为间接费用。普通说工序越短，直接费用越多，间接费用越少。管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 工序的最快完成时间：指完成时间的最高限制。工序的最快完成时间：指完成时间的最高限制。 我们设完成

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

41、加的直接费用最少。 设工序设工序i ,j)的提早完工时间为的提早完工时间为Yij,我们用我们用Tij,Tij分别表示正常完工时间与最分别表示正常完工时间与最快快完工的时间，那么有工序完工的时间，那么有工序i ,j)的实践完工时间为：的实践完工时间为：Tij-Yij。我们用。我们用Cij,Cij表示用表示用正正常完工时间和最快完成时间完成工序所需求的费用，常完工时间和最快完成时间完成工序所需求的费用，Kij为工序为工序i ,j)的直接费用的直接费用变动率。得到这个问题的线性规划模型如下：变动率。得到这个问题的线性规划模型如下： minf= Kij*Yij) i,j)S.t. Xj-Xi Tij-

42、Yij,对一切弧对一切弧i, j) Yij Tij-Tij, 对一切弧对一切弧i, j) Xn-X1 T, Xi 0， Yij 0。管管 理理 运运 筹筹 学学2 2 统筹方法筹方法例例7. 例例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需添加的直接费用，如表所需的直接费用和每缩短一天工期所需添加的直接费用，如表12-17所示。所示。 表表12-

43、17工序工序Tij正常正常完工完工Cij直接直接费用费用Tij最快最快完工完工Cij直直接费用接费用直接费用直接费用变动率变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 该工程要求在该工程要求在150天内完工，问每个工序应比正常完工时间提早多少天天内完工，问每个工

44、序应比正常完工时间提早多少天完成，才干使整个工程因缩短工期而添加的直接费用为最少。假设工期要完成，才干使整个工程因缩短工期而添加的直接费用为最少。假设工期要求在求在140天完工呢？天完工呢？12345678abfechgijd图图12-19管管 理理 运运 筹筹 学学2 2 统筹方法筹方法解：绘出如图解：绘出如图12-19所示，根据此网络图建立数学模型。所示，根据此网络图建立数学模型。 设此网络图上第设此网络图上第i点发生的时间为点发生的时间为xi，工序提早完工的时间为，工序提早完工的时间为yij。 目的函数目的函数minf=120y27+300y23+400y24+500y25+230y37

45、+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管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 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)运算得到结果：运算得到结果

46、：f=6400。管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 模型二，我们知道直接费用是随着完成时间的缩短而添加，而间接模型二，我们知道直接费用是随着完成时间的缩短而添加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,方案方案期的间接费用与总工期成正比，即为期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优和各个工序最优完成时间的模型为：完成时间的模型为： 目的函

47、数目的函数min f=d(xn-x1)+ s.t. xj-xi Tij-yij，对一切弧，对一切弧i ,j) yij Tij-Tij ，对一切弧，对一切弧i ,j) xi 0， yij 0。管管 理理 运运 筹筹 学学2 2 统筹方法筹方法 例例8 假设在例假设在例7中，每天的间接费用为中，每天的间接费用为330元，求使包括间接费用与直接费元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。和各个工序最优完成时间。 解：决策变量的含义同例解：决策变量的含义同例7。 此数学模型的目的函数为：此数学模型的目的函数为：

48、 min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+290y67 此模型的约束条件与例此模型的约束条件与例7的约束条件根本一样，只需在例子的约束条件中去的约束条件根本一样，只需在例子的约束条件中去掉掉x8 150就得到了例就得到了例8模型的约束条件了。模型的约束条件了。 计算得到以下结果：计算得到以下结果： f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0.管管 理理 运运 筹筹 学学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天完工，其他的工序按正天完工，其他的工序按正常时间完工。常时间完工。