第五章时序和路径规划

1、 应用运筹学应用运筹学 浙江大学管理学院浙江大学管理学院 杜红杜红 博士博士 副教授副教授时序规划时序规划最小树问题最小树问题通过一个网络的最短路径通过一个网络的最短路径通过一个网络的最大流量通过一个网络的最大流量n时序顺序时间时序顺序时间n时序规划时序规划 多项任务等待同一人或物处理，每项多项任务等待同一人或物处理，每项任务的单独完成的时间确定，且没有先任务的单独完成的时间确定，且没有先后关系（紧前、紧后）。怎样安排各项后关系（紧前、紧后）。怎样安排各项任务的顺序，使总效率最高？任务的顺序，使总效率最高？n系统时间加工时间排队时间系统时间加工时间排队时间n时序规划原则目标时序规划原则目标 到

2、达时间先进先出到达时间先进先出 最小富裕时间（到期时间加工时间）最小富裕时间（到期时间加工时间） 最接近完成者优先最接近完成者优先 在完成之前最少的机器开关次数在完成之前最少的机器开关次数 下一工作最短的排队下一工作最短的排队 关键比例最低关键比例最低 最重要的优先最重要的优先 加工工序之间的转换成本最低加工工序之间的转换成本最低 加工时间最短者优先加工时间最短者优先 最先到期的工作优先最先到期的工作优先 n平均排队（等待）时间最短问题平均排队（等待）时间最短问题 加工时间最短者优先加工时间最短者优先 （相同时间的可任意安排）（相同时间的可任意安排）n平均延误时间最短问题平均延误时间最短问题

3、最先到期的工作优先最先到期的工作优先n例例5 51 1：教材：教材 P105 P105 实例实例5.35.3n例例5 52 2：教材：教材 P106 P106 实例实例5.45.4 平均排队时间最短：加工时间短者优先平均排队时间最短：加工时间短者优先 A G C H E B F DA G C H E B F D加工时间加工时间 2 2 3 3 4 5 7 82 2 3 3 4 5 7 8等待时间等待时间 0 2 4 7 10 14 19 260 2 4 7 10 14 19 26总等待时间：总等待时间：82 82 平均等待时间：平均等待时间：10.2510.25 平均延误时间最短：最先到期者优

4、先平均延误时间最短：最先到期者优先 G B C A E F D HG B C A E F D H到期时间到期时间 2 7 8 13 14 20 30 362 7 8 13 14 20 30 36加工时间加工时间 2 5 3 2 4 7 8 32 5 3 2 4 7 8 3开始时间开始时间 0 2 7 10 12 16 23 310 2 7 10 12 16 23 31完工时间完工时间 2 7 10 12 16 23 31 342 7 10 12 16 23 31 34延误时间延误时间 0 0 2 0 2 3 1 0 0 0 2 0 2 3 1 0 总延误时间：总延误时间：8 平均延误时间：平均

5、延误时间：1n延误的工作项数最少延误的工作项数最少 先按先到期者优先的原则排初次次序先按先到期者优先的原则排初次次序 如果没有延误的工作，则是最优解。如果没有延误的工作，则是最优解。 如果有延误的工作，则找出其中的一如果有延误的工作，则找出其中的一项，找出到此项工作之前（包括该项）项，找出到此项工作之前（包括该项）加工时间最长的一项，并将之抽去，重加工时间最长的一项，并将之抽去，重新安排时间，如果已没有延误的工作，新安排时间，如果已没有延误的工作，则将被抽取的这一项放置最后；如仍有则将被抽取的这一项放置最后；如仍有被延误的工作，则再重复这一步。被延误的工作，则再重复这一步。按先到期者优先原则安

6、排的初次次序为：按先到期者优先原则安排的初次次序为： G B C A E F D HG B C A E F D H到期时间到期时间 2 7 8 13 14 20 30 362 7 8 13 14 20 30 36加工时间加工时间 2 5 3 2 4 7 8 32 5 3 2 4 7 8 3完工时间完工时间 2 7 10 12 16 23 31 342 7 10 12 16 23 31 34延误时间延误时间 0 0 2 0 2 3 1 00 0 2 0 2 3 1 0找出一项延误的工作是找出一项延误的工作是 C C ；C C 之前（包括之前（包括 C C）加工时间最长的是加工时间最长的是 B,

7、B, 抽去抽去 B B 后，重新安排后，重新安排时间：时间： 抽去工作抽去工作 B B 后的次序安排：后的次序安排： G C A E F D HG C A E F D H到期时间到期时间 2 8 13 14 20 30 362 8 13 14 20 30 36加工时间加工时间 2 3 2 4 7 8 32 3 2 4 7 8 3开始时间开始时间 0 2 5 7 11 18 260 2 5 7 11 18 26完工时间完工时间 2 5 7 11 18 26 292 5 7 11 18 26 29延误时间延误时间 0 0 0 0 0 0 00 0 0 0 0 0 0B B7 75 52929343

8、42727n时序规划扩展：时序规划扩展： 两台顺序机器完成一批工作两台顺序机器完成一批工作 每项工作在机器每项工作在机器1和机器和机器2上的加工时间不上的加工时间不一样，如何使系统效率最高？一样，如何使系统效率最高？ 3214机器机器1机器机器2工作工作n约翰逊原则约翰逊原则 找出各台机器上加工时间最短的一项工作，找出各台机器上加工时间最短的一项工作， 如果在机器如果在机器1上，这项工作最先做；上，这项工作最先做； 如果在机器如果在机器2上，这项工作最后做；上，这项工作最后做； 不断重复，从两端往内排。相同时间可任选不断重复，从两端往内排。相同时间可任选一个，一般先安排机器一个，一般先安排机器

9、1上工作。上工作。例例53：教材：教材P110 实例实例5.6工作：工作： A B C D E F G机器机器1： 2 5 10 8 4 12 9机器机器2： 14 7 3 10 5 6 6顺序：顺序：1开始：开始： 0 2 6 11 19 31 40 1完成：完成： 2 6 11 19 31 40 502开始：开始： 2 16 21 28 38 44 502完成：完成： 16 21 28 38 44 50 53 ACEBDGF最小树问题最小树问题n图及相关的概念图及相关的概念n图：点及点与点之间的连线（箭线：有向图）构成图：点及点与点之间的连线（箭线：有向图）构成n边与弧：两点之间连线为边或

10、弧（箭线）如：边与弧：两点之间连线为边或弧（箭线）如： 1-2，4-6n链与路：任意两点之间的点与边（弧）组成了一条链（路）。链与路：任意两点之间的点与边（弧）组成了一条链（路）。 如：如：1-2-4-6n圈与回路：链（路）的两端为同一点则形成一个圈（回路）。圈与回路：链（路）的两端为同一点则形成一个圈（回路）。 如：如：1-2-3n连通图：任意两点之间至少有一条链，没有孤立点。连通图：任意两点之间至少有一条链，没有孤立点。n网络：一个有向图的弧有某种网络：一个有向图的弧有某种“流转物流转物”流动时的图称为网络流动时的图称为网络n权：边或弧的权数，表示边或弧性质或数量。权：边或弧的权数，表示边

11、或弧性质或数量。453427987737298544最小树问题最小树问题n树的概念树的概念 连通图，但没有圈为树。由所有节点连通图，但没有圈为树。由所有节点(N)和相和相应的边应的边(N-1)组成。组成。总经理生产经理人力经理销售经理车间主任销售代表招聘经理最小树问题最小树问题n最小树最小树 一个网络中有很多树，其中边的长度一个网络中有很多树，其中边的长度（权数）之和为最小的树为最小树。（权数）之和为最小的树为最小树。n最小树的获取破圈法最小树的获取破圈法 从图中任取一个圈，去掉该圈的一条最从图中任取一个圈，去掉该圈的一条最大边，将此圈破去，然后重复破圈，直大边，将此圈破去，然后重复破圈，直至

12、无圈为止至无圈为止。 最小树问题最小树问题4323245172674例例54：求以下图的最小树：求以下图的最小树通过一个网络的最短路径通过一个网络的最短路径n问题问题 在一个网络中，给定一个始点在一个网络中，给定一个始点Vs，和一，和一个终点个终点Vt，求，求Vs 到到Vt的一条路，使路长的一条路，使路长最短。最短。n求解求解 能划分阶段的，可采用动态规划方法。能划分阶段的，可采用动态规划方法。 不能分阶段的，采用不能分阶段的，采用狄克斯屈狄克斯屈方法。方法。通过一个网络的最短路径通过一个网络的最短路径狄克斯屈（狄克斯屈（Dijstra）方法方法n开始节点标永久标记开始节点标永久标记0,S,其

13、余为临时标记其余为临时标记T,-n找出与开始节点相邻的所有节点，为每一个设标记找出与开始节点相邻的所有节点，为每一个设标记L,1，其中，其中L值最小的节点标记右上角标上值最小的节点标记右上角标上*，使之成，使之成为永久标志。为永久标志。L为两节点间距离，为两节点间距离，1表示始于第一节点表示始于第一节点n从新的永久标志开始，找出从此节点出发可到达的所有从新的永久标志开始，找出从此节点出发可到达的所有节点，计算这些节点的最短距离（现有距离和经新的永节点，计算这些节点的最短距离（现有距离和经新的永久标志到达的距离的小的一个值），保持、新设或更改久标志到达的距离的小的一个值），保持、新设或更改这些节

14、点的标志为这些节点的标志为 最短距离，最短路径上前一节点标最短距离，最短路径上前一节点标号号，比较图中所有没有，比较图中所有没有*的标记（临时性标记），找出的标记（临时性标记），找出距离最短的一个节点，使之成为永久性标记。重复这一距离最短的一个节点，使之成为永久性标记。重复这一步，直到所有的节点都成为永久性标志为止。步，直到所有的节点都成为永久性标志为止。通过一个网络的最短路径通过一个网络的最短路径kijDi ,mLijDj,k从从i-j时：时： 如果如果Di+LijDj,则不改变则不改变j的标记；的标记； 如果如果Di+LijDj，则改为，则改为Di+Lij,i通过一个网络的最短路径通过一个

15、网络的最短路径n例例55 狄克斯屈方法狄克斯屈方法 ：教材教材P131 实例实例5.1235,41432657201510682410820110,S21,325,344,2T,-T,-T,-T,-T,-T,-20,115,141,6*通过一个网络的最短路径通过一个网络的最短路径从起始点到每一点的最短距离为：从起始点到每一点的最短距离为： 节点节点 最短距离最短距离 路径路径 2 20 12 3 15 13 4 25 134 5 35 1345 6 21 136 7 41 1367最短路径问题的应用最短路径问题的应用n例例56：设备更新问题：设备更新问题 某厂使用一种设备，每年年初设备科需要对

16、该设备的更新与否作出某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。若购置新设备，就要支付购置费；如果继续使用则需要支付决策。若购置新设备，就要支付购置费；如果继续使用则需要支付维修费，设备使用的年数越长，每年所需的维修费越多。现若第一维修费，设备使用的年数越长，每年所需的维修费越多。现若第一年年初购置了一台新设备，问在年年初购置了一台新设备，问在5年内如何制定设备更新计划，以年内如何制定设备更新计划，以便使新设备购置费和维修费的总费用最小？已知设备在便使新设备购置费和维修费的总费用最小？已知设备在5年内各年年内各年年初的价格及设备使用不同年数的维修费如下：年初的价格及设备使用

17、不同年数的维修费如下：最短路径问题的应用最短路径问题的应用n例例56：设备更新问题：设备更新问题 把求总费用最小问题化为最短路径问题。用点把求总费用最小问题化为最短路径问题。用点 i (i=1,2,3,4,5)表示第表示第 i 年买进一台新年买进一台新设备。增设一点设备。增设一点 6 表示第五年末。从表示第五年末。从i点到点到i+1, 6 各画一条弧，弧（各画一条弧，弧（i , j）表示在）表示在第第 i 年买进的设备一直使用到第年买进的设备一直使用到第 j 年年初（第年年初（第 j 1年年末）。求年年末）。求1点到点到6点的最短路径。点的最短路径。路径的权数为购买和维修费用。路径的权数为购买

18、和维修费用。 弧（弧（i , j）的权数为第）的权数为第i年的购置费年的购置费ai从第从第i年使用至第年使用至第j-1年末的维修费之和。年末的维修费之和。 从第从第i年使用至第年使用至第j-1年末的维修费：年末的维修费：b1+bj-i （使用寿命为（使用寿命为j-i年）年） 如：（如：（24）权数为：）权数为：a2+b1+b2=1156=22 具体权数计算结果如下：具体权数计算结果如下：通过一个网络的最短路径通过一个网络的最短路径n例例56 设备更新问题设备更新问题 ：使用使用Dijstra算法，上述问题最短路为算法，上述问题最短路为1-3-6或或1-4-6 即：第即：第1、3年年初购买设备，

19、或第年年初购买设备，或第1、4年年初购买设备年年初购买设备 五年最佳总费用为五年最佳总费用为53。132546162217182330594117301623413122作业题：作业题：n某地某地7个村镇之间现有交通距离如图个村镇之间现有交通距离如图求：求：1)从村从村1到其余各村的最短距离？到其余各村的最短距离？ 2)如要沿路架设电话线，如何使总长度最小同时又使每个村都如要沿路架设电话线，如何使总长度最小同时又使每个村都能安装上电话？能安装上电话？1211101512102516171526724通过一个网络的最大流量通过一个网络的最大流量n最大流量问题最大流量问题 在一定条件下，使网络系统

20、中从开始点在一定条件下，使网络系统中从开始点到结束点之间的某种物资流的流量达到到结束点之间的某种物资流的流量达到最大的问题。限制条件是每一条边的最最大的问题。限制条件是每一条边的最大通过能力（流量）不等。但有多条路大通过能力（流量）不等。但有多条路n最大流量求解最大流量求解n线性规划方法线性规划方法n福特富尔克逊标号法（福特富尔克逊标号法（“分步流动分步流动”） 最大流量的线性规划模型最大流量的线性规划模型n例例57：有下列石油运输管道图。某公司欲采用这个有下列石油运输管道图。某公司欲采用这个网络图从网络图从1地向销地地向销地7运送原油，弧的容量运送原油，弧的容量Cij（万升（万升/时）时）已

21、给定（因管道直径的变化，已给定（因管道直径的变化，Cij不完全相同）。问如何不完全相同）。问如何安排输送，方能使每小时运送的原油最多？安排输送，方能使每小时运送的原油最多？62321256432最大流量的线性规划模型最大流量的线性规划模型n设弧（设弧（i,j）上的流量为）上的流量为Fij, 总流量为总流量为F.n目标函数：目标函数：MAX F=F12+F14n约束条件：约束条件： 流入流出流入流出; FijCij; Fij0 2点：点：F12=F23+F25; 4点：点：F14=F43+F46+F47 3点：点：F23+F43=F35+F36; 5点点 ：F25+F35F57 6点：点：F36

22、+F46F67 ; 7点：点：F47+F57+F67=F12+F14n解：解：F12=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2 F36=2;F57=5;F67=3 最大流量最大流量F1062321256432思考题：最小费用最大流思考题：最小费用最大流n如果弧（如果弧（i,j）上的单位流量费用为）上的单位流量费用为Bij (百元百元/万升）。万升）。 图中每一条弧的权数前一位为流量限制图中每一条弧的权数前一位为流量限制Cij，后一位为单，后一位为单位费位费Bij。n怎样运送才能使运送最多的石油并使总的费用最小？怎样运送才能使运送最多的石油并使总的费

23、用最小？n提示：先求得最大提示：先求得最大F值；再求总流量为值；再求总流量为F时使总费用最小时使总费用最小的方案。的方案。n进一步思考：求最小费用问题。进一步思考：求最小费用问题。 如何求每小时运送如何求每小时运送6万升原油的最小费用？万升原油的最小费用？ 6,32,53,22,31,32,85,76,64,43,42,4最大流量的标注法最大流量的标注法n标记：标记：流入节点的流量，该流量的来源节点流入节点的流量，该流量的来源节点，第一个节点标记第一个节点标记，S。n选取已有标记的一个节点，找出从此节点能直选取已有标记的一个节点，找出从此节点能直接到达的一个节点，确定到达节点的最大流量，接到达的一个节点，确定到达节点的最大流量，相应地标上标记。重复这一步，尽快到达终点，相应地标上标记。重复这一步，尽快到达终点，得到一条从起点到终点的路径，此路径的最大得到一条从起点到终点的路径，此路径的最大流量为流入终点的流量。将此路径上的每一边流量为流入终点的流量。将此路径上的每一边的流动能力减去此流量。再从起始节点开始，的流动能力减去此流量。再从起始节点开始，按新的流动能力，重新进行标号，找出新的一按新的流动能力，重新进行标号，找出新的