第2章 工程网络图及有关排序问题.docx
《第2章 工程网络图及有关排序问题.docx》由会员分享，可在线阅读，更多相关《第2章 工程网络图及有关排序问题.docx（20页珍藏版）》请在冰点文库上搜索。
第2章工程网络图及有关排序问题
第二章工程网络图及有关排序问题
§2.1工程网络
在实践中经常会遇到合理地安排工作次序、统筹使用各种资源，以便在最短时间内完成预定的任务的一类问题，统筹方法就是解决这类问题行之有效的一种数学方法。
统筹方法利用工程网络图（也称统筹图）来表示组成任务的各个环节及其先后次序，并据此对工程网络作进一步的分析和计算，以帮助人们进行合理地安排任务的各个环节，科学地进行决策和管理，达到优化完成任务的目的。
在国内外许多科学技术和管理科学的文献中，统筹方法经常被称作CPM方法或PERT技术，这是因为在统筹方法形成的历史过程中有两件事起了很大的作用。
这两件事都发生在20世纪50年代；美国的兰德公司为杜邦公司改善内部管理而提出的关键路线法（CriticalPathMethod，简称CPM方法），使后者大大提高了效益；美国的特种技术规划局采用计划评估技术（ProgramEvaluationandReciewTechniques，简称PERT技术），使美国提前两年完成了战略核武器——北极星核潜艇的建造。
这两件成功应用统筹方法的案例刺激了各种行业竞相采用PERT/CPM技术编制项目的计划，加快了统筹方法的普及过程，以致后来在有些国家，把是否使用CPM方法或PERT技术核验投标计划书法定为政府部门接受公司投标国家项目的先决条件。
与此几乎同时，在20世纪50—60年代，在华罗庚先生的倡导和推动起来，总结为统筹方法。
他的《统筹方法评估及补充》一书为在我国普及统筹方法起了很大的作用。
我们从一个最简单的例子来了解这种方法的思想，设想我们要以茶待客，为此要完成下面各项事情，并把各件事情所需时间列于其后（为简单计，时间取为整数）：
洗茶杯，1分钟；
找茶叶并放入茶杯，1分钟；
烧开水，5分钟；
冲茶，1分钟。
我们把完成“以茶待客”这件任务用图2-1表示。
这样的图称为工程网络图。
图中每条有向线段表示一件事情，称为一个“工序”；有向线段旁边的数字表示完成该事情需要的时间；圆圈称为“事项”，表示完成任务过程中的状态。
工序可以单独用字母表示（如图2-1所示）。
每个工序和两个事项相联系，分别称为该工序的始点和终点。
工序也可以用它的始终点表示，例如，工序A可表示为工序1-2。
如果一个事项只有从它出发的工序而没有指向它的工序，则该事项称为“初始事项”，如图中的事项①，如果一个事项只有工序指向它而没有从它出发的工序，则该事项称为“最终事项”，如图2-1中的事项④。
图中，工序A称为工序B的紧前工序，工序B称为工序A的紧后工序。
工程网络图表示了各事情的先后次序关系：
对每一个事项来说，只有当指向该事项的所有工序都完成后，才可以开始动手做从该事项出发的工序。
换言之，每个工序只有在它的所有的紧前工序都完成后才可以动手做。
例如，图2-1表示：
只有洗好茶杯才能放茶叶；只有放好茶叶且烧开了水才能为客人冲茶。
从图中分析可以得到：
我们可以先烧水，再去洗茶杯、放茶叶，等水开了后再为客人冲茶。
这样的安排可以用最短的时间完成所有的事情。
由此可知，客人最少要6分钟以后才能喝到茶，也就是完成所有事情的最短“工期”是6分钟。
工程网络图还说明，为缩短客人的等待时间，可以考虑的办法是用更短的时间把水烧开，或者缩短冲茶的时间，而不是在缩短洗茶杯、放茶叶的时间上动脑筋。
实践中有许多更复杂的事物也可以应用统筹方法来研究。
例如前面提到的杜邦化学公司的例子。
该公司下属有许多工厂，各个工厂的产品之间往往有一些联系。
例如，某个工厂的产品是另一个工厂的原料，则公司的管理人员必须协调好两个工厂的生产计划，及时监控前者的生产进度。
再如，同一个工厂内往往有许多产品都要使用用一个设备生产，工厂管理人员就要周密地考虑安排这些产品生产的先后次序，使得生产不会因待料而停工。
又如，前述的美国建造战略核武器——北极星核潜艇，需要几千个承包设计制造公司的协作，有的零部件需要完成上万道工序，这就更需要对整个计划进行周密的安排和管理。
下面我们用一些例子来说明如何由实际问题画出正确的工程网络图。
例1表2-1所示是某个机床要加工的5种零件的先后次序关系，试根据表格画出相应的工程网络图来。
表2-1
工件编号
1
2
3
4
5
前期工件
-
-
1，2
2
1
分析先看零件5的情况。
我们可以画出工程网络图。
如图2-2（a）所示。
对零件3的情况。
可以画出工程网络图，如图2-2（b）所示。
现在要把它们拼在一起，但不能画成如图2-2（c）所示的那样，因为工件5不以工件2作为紧前工序，而必须加进一个虚工序，画出相应的工程网络图2-2（d）。
虚工序只不过是用来帮助表示有关工序的先后次序关系。
同样，对工件4，要把它拼到上面的图中时，还要加进一个虚工序，最后得到工程网络图如图2-2（e）所示。
这里要注意，“完成”虚工序的时间为零，因而它只表示事物的先后次序关系。
但是即使完成虚工序不要任何时间，但却是不可省略的。
如在图2-2（e）中，我们省去任何一个虚工序，图中的工序关系就与问题的要求不符。
例2图2-3标出了自行车有关零件的名称。
把自行车零件组装成一辆自行车，主要有以下几个工序：
A——组装车架，包括装前叉，车把和前后挡泥板；
B——安装并校正前轮；
C——安装并校正后轮（含飞轮）；
D——安装中轴，包括装轮盘和脚蹬；
E——在轮盘和飞轮间连接链条；
F——安装左、右脚蹬；
G——安装前后车间和车座。
对于熟练的装配工，各工序所需要的时间如表2-2所示。
表2-2
工序
A
B
C
D
E
F
G
时间（分钟）
7
5
7
7
5
4
10
如果由一个人完成全部组装工作至少需要45分钟。
自行车组装过程中的有些工序的前后次序是确定的。
例如，在后轮与中轴轮盘装好之前无法连接后轮上的飞轮与轮盘之间的链条等等。
根据经验，如下的装配顺序是必须遵循的：
1）在安装并校正前后轮之前组装车架；
2）车闸的安装要在前后轮转好之后再进行；
3）连接飞轮和轮盘间的链条要在后轮和中轴装好之后再进行；
4）先装中轴，再装脚蹬。
5）现安排两个工人合作组装一辆自行车，每道工序只能由一个完成。
请你为这两位工人安排一个组装的工序流程，使他们在最短的时间内装配好这辆自行车，并请算出最短时间。
（北京市1999年决赛）
我们在这里先根据题意画出相应的工程网络图。
问题解答的其余部分将在以后的例题中给出。
我们根据此题提供的情景先列出工序之间的关系表2-3，再画出相应的工程网路图（见图2-4）。
表2-3
工序
A
B
C
D
E
F
G
紧前工序
-
A
A
-
C,D
D
B,C
§2.2
工程网络图的要求及其检验方法
有上述可知，工程网络图的工作要正确地反映各工序之间的关系，但是作为整体来说，工程网络图还有其自身的要求。
首先，适应每件事情总有“一个”开始和“一个”结束的思维习惯，我们要求整个工程网络图只有一个初始事项和一个最终事项。
这个要求可以用适当添加虚工序和事项来达到。
例如图2-5（a）中原有两个初始事项①和②，3个最终事项③，④，⑤，可以添加一些虚工序，如图2-5（b）所示，使新的工程网络图上只有一个初始事项和一个最终事项。
其次，正确的工程网络图要求整个图内不含有“圈”。
所谓“圈”是图中从某个事项出发经过若干个首尾相连的工序又回到起点的一个工序序列。
如图2-6（a）中的B-C-D和图2-6（b）中的B-C-D与A-B-C-E都是圈的例子。
如果说“整个工程网络图只有一个初始事项和一个最终事项”的要求是一种“表达形式上”的要求，而且也很容易得到满足，那么“工程网络图无圈”的要求却是“本质性”的。
这是因为，有圈的工程网络图在实践中是无法实现的。
例如，在完成图2-6（a）中的工序A后工程就无法进行下去：
因为要完成工序B就必须先完成工序D，因而不能先做工序B；而要完成工序D就必须先完成工序C，因而不能先做工序D；而要完成工序C就必须先完成工序B，因而不能先做工序C。
这样，在B,C,D中就无法选择最先做的工序，因而整个事情也无法进行下去。
这说明，出现圈的工程网络图必定有错误，必须纠正。
那么，如何来检查一张工程网络图有没有圈呢？
最简单的方法是“穷竭法”，即“跟踪”每一个首尾相连的工序序列，看它是否回到起点。
这种方法对简单的工程网络图是有效的，但是当工程网络图中包括有大量的工序时，这种做法很难确保检查了所有的工序序列而没有遗漏。
我们需要能检查工程网络图有没有圈的普遍而简便的方法。
“工序删去法”就是一种这样的方法。
这种方法的做法如下。
首先，从工程网络图中找寻初始事项，然后删去该事项和从该事项出发的所有工序。
再在新的工程网络图中找寻初始事项，重复上述过程。
如果图中没有圈的话，则在这个过程中可以把图中的所有工序全部删去。
图2-7（a）—图2-7（c）给出了按工序删去法检验图图2-7（a）的过程。
从图2-7（c）再删一次，就可以把图中的所有工序全部删去。
如果遇到如图2-6（a）这样的含有圈的图，照上述步骤将删成如图2-8所示，此后就不可能再删去任何一道工序了。
§2.3
工程网络图的分析方法
1.最短工期
工程网络图可以帮助我们分析整个工程的最短工期。
为此，我们先要引进一些必要的概念。
以图2-9为例，我们把初始事项到最终事项的一个首尾相连的工序序列称为路线，例如1-2-3-4是一条路线，1-3-4也是一条路线。
一条路线中所有工序时间的总和称为该路线的长，例如，路线1-2-3-4的长为3，路线1-3-4的长为6。
一张工程网络图中最长的路线称为关键路线。
图2-9的关键路线是1-3-4，关键路线的长为6。
从图2-9分析可知，完成所有事情的最短时间为6，也就是关键路线的长。
这是一个普遍成立的规律：
工程的最短工期等于工程网络图中关键路线的长。
关键路线如此重要，如何从工程网络图中找出关键路线呢？
对于简单的工程网络图，可以根据关键路线的定义，找出图中所有路线，计算各路线的长，通过比较后得到的最长的路线就是关键路线。
最长的路线有时可能有多条（这些路线的长都取得同一个最大值），每条都称为关键路线。
例如在图2-10中，1-3-4是一条关键路线，需要普遍而简便的方法，计算每个事项的“最早出发时间”和“最迟到达时间”就是一种这样的方法。
这种算法也适合于计算机编程以处理复杂的情况。
下面仍以和例1相同的工程网路图来说明计算方法，为陈述方便，假设图2-9中的各工序时间以小时计。
所谓事项最早时间（也称事项最早出发时间），是指该事项后面的工序最早什么时间可以开工，或者等价地，该事项前面所有的工序最早什么时间可以完工。
因而工程网络图中各事项的最早时间是由前向后推算的。
规定初始事项的最早时间为0。
图中事项①是初始事项，按规定它的最早时间为0点，我们在事项①旁边记上数字0（见图2-11）。
工序A在0点开工，则1点完成，因而事项②的最早时间是1点，在事项②旁边记上数字1。
对事项③来说，其前面的一个工序B最早1点开工，在2点可以完工。
而其前面的另一个工序C最早在0时开工，在5点可以完工。
综合起来，事项③前面的所有工序最早在5点完工，因而事项③的最早时间为5，我们在事项的③旁边记上数字5。
对最终事项④来说，前面只有一个工序D，该工序的最早开工时间为5点，而该工序需要1小时完成，因而该事项的最早时间为6。
由最早时间的含义可知，最终事项的最早时间也就是完成整个工程的最短时间，即工程的最短工期。
在一般情况下，设指向某事项i的工序有n个（见图2-12）：
A1，A2，…，An，完成这些工序分别需要时间t1，t2，…，tn，且这些工序的起点事项最早时间都已经计算得到，分别记为E1，E2，…，En，则事项i的最早时间Ei由下式计算：
所谓事项最迟时间（也称事项最迟到达时间）是在规定事项后面各工序最迟完工时间的条件下，该事项前面的工序最迟什么时间要完工，或等价地，该事项后面的工序最迟什么时候必须开工，能保证后面的所有工序能在规定的时间前完工。
因而工程网络图（见图2-13）中各事项的最迟时间是由后向前推算的。
规定最终事项的最迟时间为最短工期。
我们仍以例1来说明计算方法。
事项④是最终事项，规定它的最迟时间为工程的最短工期（即上面求得的该事项的最早时间）6，我们在事项④旁边其最早时间~记号的后面写上数字6。
对事项③来说，工序D要求6点以前完工，则工序D至迟要在5点以前开工，因而事项③的最迟时间是5点，我们在事项③旁边~记号后面写上数字5。
对事项②来说，其后面只有一个工序B，由前计算最初要在5点完工，而本身需要时间1小时，因而工序B最迟要在4点开工，事项②最迟时间是4点。
我们在事项②旁边~记号后面写上数字4。
对事项①来说，其后面的一个工序在5点完工，其需要时间5小时，工序C最迟要在0点开工。
综合起来，最迟要在0点前到达事项①（例如做好准备工作），因而事项①的最迟时间为0，我们在事项①旁边~记号后面写上数字0。
一般地，若从某事项i出发的工序有n个：
A1，A2，…，An（见图2-14），完成这些工序分别需要时间t1，t2，…，tn，且这些工序的终点事项的最迟时间都已经计算得到，分别记为L1，L2，…，Ln，则事项i的最迟时间Li由下式计算：
在计算得到每个事项的最早时间和最迟时间后，就可以由此找到关键路线。
我们仍以图2-13来说明。
从图中可见，事项①、③、④的两个时间相同。
说明在规定初始事项的最早时间为0时，它不可能提前到达；在规定最终事项的最迟时间为整个工程的最短工期时（这个时间就是最终事项的最早时间），它也不能比最迟时间更晚到达。
因而在上述两个条件下，到达这些事项的时间没有调整的余地。
换言之，事项①、③、④必定在工程网络图中的最长路线即关键路线上，把这些事项按时间又早到晚的顺利连接起来的工序组成了关键路线。
这样可以得到，1-3-4是关键路线。
现在用这种方法对如下较复杂的工程网络图（图2-15）进行计算。
我们先计算得到各事项的两种时间如图2-16所示。
再按照上述的方法找关键路线。
将事项分成两类，最早时间和最迟时间相同的事项归一类，如图2-16中的事项①、③、④、⑥；其余的事项归另一类。
第一类事项在关键路线上。
将连接这些事项的工序按时间由早到晚的顺序排列出来，就得到工程网络图的关键路线。
图2-16中1-3-4-6是关键路线。
我们现在来完成例2的解答。
由计算可得关键路线为A-C-0-G。
关键路线长为24（见图2-17）。
由于关键路线确定了整个工期的长短，说明关键路线一定要尽早完成。
于是必须指定一个工人依次完成关键路线上的各个工序，另一个人完成其余的工序。
将两人的分工按工作的先后次序列于表2-4中（将两人工作对换也是另一种可取的安排）。
表2-4
工人
甲
乙
工序
A-C-G
D-B-F-E
注意，这里我们应该检验两人的配合是否合理。
当甲着手完成工序A时，乙应同时开始着手工序D，这样两人会同时完工。
接下来甲可以着手完成工序C，此时乙虽然可以选择完成工序B或F，但考虑配合甲接下来要做的工序G，乙必须选择G的紧前工序B。
这样，当乙完成工序B时，甲还未完成工序C。
乙接下来可以选择紧前工序已经完成的F（而不能选紧前工序尚未完成的E）。
当他完成F时，2分钟前甲已经完成了工序C，并且甲已经在做工序G，乙可以着手完成最后的工序E。
例3有一批产品的加工要经过10道工序，分别记为A,B,C,D,E,F,G,H,I,J。
若加工工序X必须要在完成工序Y后才能开工，我们就称Y是X的紧前工序，现将各工序的加工次序及所需时间（单位：
小时）列表2-5。
表2-5
工序（小时）
A
B
C
D
E
F
G
H
I
J
时间（小时）
3
2
4
2
5
2
1
1
4
3
紧前工序
-
-
B
B
A,C
A,C
D
E
E,F,G
D
1）现有两台性能相同的机器可同时加工该批产品，问完成这批产品的最短加工时间是多少（假定每道工序只能安排在一台机器上，并且必须在整批产品完成前一道工序后才开始下道工序的加工）？
2）经过技术改造，其中一台机器已将其效率提高为原先的两倍（即加工时间缩短一半）。
问：
此时应如何安排两台机器的加工任务，才能使完工时间最短？
（上海市2000年决赛）
解
（1）首先按工序关系，画出工程网络图（如图2-18所示）。
并且求出关键路线B-C-E-I，最短工期为15小时。
然后，根据加工顺序要求安排加工任务，工期为15小时，可以用图2-19表示两人的分工情况：
图2-19下方的轴标出了时间尺度，两人的分工用依次相连的线段表示，线段的长等于工序的时间。
从图中可以检验，两人的分工满足了各个工序的先后次序关系。
例如，动手完成工序I时，其紧前工序E，F，G都已经完工。
（2）由全部工序完工总时间为27小时，如果第一台机器效率提高一倍，则至少需要9小时完工。
分工时，应优先将关键路线上的工序分配给第一台机器，当出现第一台机器完成关键路线上的工序需要等待第二台机器完成某个相应的紧前工序时，适当安排第一台机器去完成原本安排第二台机器的任务。
调整后的分工可以用图2-20表示，工期为9小时。
2.缩短工期
工程的最短工期是由关键路线长决定的，由此可以推出：
要缩短工期必须想法缩短关键路线上工序的时间。
这里应该注意两个问题：
1）能否缩短某个工序的时间要从实际出发。
例如图2-21（a）中的工程似乎缩短工序1-3的时间为好。
但是如果这个工序表示的是浇注水泥，工程师要求有一定的时间让水泥固化，因而不能缩短这个工序的时间。
2）缩短了关键路线上的工序后，新的工程网络图的关键路线可能会改变。
例如图2-21（a）中的关键路线是1-3-4，最短工期是15。
设想我们要把总工期缩短为12。
将关键路线上的工序等比例缩短后变成图2-21（b）的情况。
虽然原先的关键路线缩短成了12，但是新的图上关键路线变成了1-2-3-4，关键路线的长为13，并没有达到缩短工期为12的目标，此时应对新的工程网络图重新计算关键路线和讨论缩短有关工序的问题。
3.等待时间
我们用例子说明与等待时间有关的加工次序问题。
例4现有9个工件（编号A-I）所需加工时间（小时）及前期要求完成的工件号如表2-6所示。
表2-6
工件号
A
B
C
D
E
F
G
H
I
加工时间（小时）
17
12
9
15
5
10
11
20
15
前期工件
G,B
D
D
H
A
D
F,I
-
C
所有工件在一台机床上加工。
由于机床故障，开始加工时离协议完成所有工件加工的时间只有40小时。
按协议，每个工件比计划每拖延1小时完成，要付违约金10元。
请安排一个合理地加工次序，可使所附违约金最少。
请列出你安排的加工次序，并计算出违约金总数（上海市2006年决赛）。
解根据加工次序画出下面的工程网络图（见图2-22）。
取含工件最多（不一定是关键路线）的工件次序：
H-D-C-I-G-A-E，连同工件所需时间画出示意图，见图2-23。
现在考虑在上述序列适当的位置插入工件B和F。
在上述序列中插入B，其时间为12小时。
按加工次序要求，B应在D后A前。
这样B有4个位置可选择：
在D和C之间；在C和I之间；在I和G之间；在G和A之间，按最短等待时间的排序原理：
为缩短等待时间，应尽可能先安排加工时间短的工件，在安排加工时间长的工件（参看《高中应用数学选讲》第100页，“n个零件在一台机器加工的排序问题”），B的合理位置应在C和I之间或G和A之间。
忽略工件序列中位置相同的工件，我们只要比较图2-24所示的两个序列的等待时间。
图2-24所示的两个序列的等待时间分别为：
12*3+15*2+11=77和15*3+11*2+12=79。
这样，我们得到插入B后的序列为：
H-D-C-B-I-G-A-E，连同工件所需时间画出示意图如图2-25所示。
最后还要在上述序列中插入F，其时间为10。
由加工次序的要求，F应在D后G前，共有4个位置可考虑：
在D和C之间；在C和B之间；在B和I之间；在I和G之间。
按最短等待时间的排序原理，F的合理位置应在C和B之间。
这样，各工件的加工次序如图2-26所示。
即H-D-C-F-B-I-G-A-E。
计算违约金时从C开始，并且把C的时间改为4（违约时间从开始加工C后5小时开始计）。
可得超计划的加工时间和等待时间共280小时，应支付违约金2800元。
需要注意的是：
按最短等待时间排序原理把工件依次插入工序序列的方法是一种“局部最优”方法，即得到的序列可能是较优的排序序列，但并不一定就是最佳序列。
换言之，这种方法只是求最优解的近似方法。
这个事实可以用下面的例子予以说明。
例5某化学公司在定期检测时发现生产管道中共有9处阀门（A-I）发生有害气体泄漏。
每处阀门在每小时内有害气体的泄漏量大体相等，约为0.01立方米。
阀门的堵漏工作可在不停产的情况下实施。
由于各阀门所处位置不同，因此堵漏所需时间不同，且堵漏时必须遵从一定的顺序关系，情况见表2-7（时间以小时表示）。
表2-7
泄漏阀门
A
B
C
D
E
F
G
H
I
堵漏时间（小时）
11
9
6
10
8
7
15
17
10
需先检修好的阀门
-
C
-
I,H
A
E,G,I,H
D,B
C
-
（1）现公司只有一台阀门堵漏设备。
问：
如何安排，可使有害气体的泄漏总量最少？
要求计算出堵漏开始到结束期间有害气体的泄漏总量。
（2）如公司再增添一台性能相同的阀门堵漏设备，问：
此时应如何安排，可使有害气体的泄漏总量最少？
同时要求计算出堵漏期间有害气体的泄漏总量（上海市2007年决赛）
解这是一个安排有序工作的问题。
将检修一个阀门看作一道工序，可根据堵漏先后次序要求画出统筹图如图2-27所示。
（1）
根据题意可知，用一台设备堵漏，用于堵漏的总时间与安排堵漏次序无关，但泄漏量依赖于等待时间，与堵漏次序有关。
因此，要求泄漏量最少，就是要求安排适当地堵漏次序，使所有阀门等待的总时间最短。
在图2-27中选择含工序最多（不一定是关键路线）的工序序列C-H-D-G-F，再将其他需检修的阀门按某种次序逐个插入到该工序序列中。
A.先看按时间长短在序列C-H-D-G-F（见图2-28）中依次插入E,B,I,A（对应的时间为8小时，9小时，10小时，11小时）。
a.对应工序序列C-H-D-G-F的时间序列为6-17-10-15-7，我们要插入E，其时间为8小时。
E应在F前，有5个位置可考虑：
在C前；在C和H之间；在H和D之间；在D和G之间；在G和F之间。
要使总等待时间最短，应该使时间断的工序尽量安排在前面。
这样E的位置应该在C和H之间。
得到序列C-E-H-D-G-F（见图2-29）。
b.对应工序序列C-E-H-D-G-F的时间序列为6-8-17-10-15-7，我们要插入B，其时间为9小时。
B应在C后G前，有4个位置可考虑：
在C和E之间；在E和H之间；在H和D之间；在D和G之间。
若B放在C和E之间，得到序列C-B-E，对应的时间数列为6-9-8，显然不如6-8-9即C-E-B的排列好。
同样讨论其他位置，可知道合理的选择应是在E和H之间或在H和D之间。
两种选择的优劣可以从计算下面两个序列（见图2-30）的等待时间得出（因为这两种选择不会影响该序列以外工序的等待时间）。
由此应选择B-H。
得到序列如图2-31
升级会员 