运筹学讲义 §12.2统筹图中有关参数的计算 关键路线( critical path):统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路 华罗庚先生称关键路线为主要矛盾线 关键路线的长度:关键路线上各工序时间之和 关键工序:关键路线上的工序 如对统筹图 d 3 从总开工事项顶点①到总完工事项顶点O的各有向路及长度分别为 有向路 长度 ①→②→⑤→⑦ 2+5+5=12 ①→②→①→⑤→⑦|2+6+3+5=16 ①→@→④→⑥→⑦ 2+6+4+6=18 ①→④→⑤→⑦ 2+3+5=10 ①→④→⑥→⑦ 2+4+6=12 ①→③→④→⑤→⑦ +5+3+5=18 ①→→④→⑥→05+5+4+6=20° ①→③→⑥→⑦ 5+9+6=20 易见,①→⑧→④→⑥→①和①→③→)⑥→⑦都是关键路线 显然,关键路线的长度就是生产过程的完工期或最早可能完工期. 在关键路线上,一个(关键)工序的开工事项即为其紧前工序的完工事项.关键工序完工事项的 延长或缩短必将导致生产过程的完工期的推迟和提前 在非关键路线上,工序的开工可在其紧前工序完工后的一定时间范围内推迟,而不影响生产过程 的完工期 统筹方法的根本任务就是本着“向关键路线要时间,向非关键路线要资源”的指导思想,作出最 优或最满意的生产计划 关键路线的求解: 标号法:设统筹图中各顶点分别编号为①,②,…, 步骤:运 筹 学 讲 义 1 §12.2 统筹图中有关参数的计算 关键路线（critical path）：统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路. 华罗庚先生称关键路线为主要矛盾线. 关键路线的长度：关键路线上各工序时间之和. 关键工序：关键路线上的工序. 如对统筹图 从总开工事项顶点○1 到总完工事项顶点○7 的各有向路及长度分别为 有向路 长度 ○1 → ○2 → ○5 → ○7 ○1 → ○2 → ○4 → ○5 → ○7 ○1 → ○2 → ○4 → ○6 → ○7 ○1 → ○4 → ○5 → ○7 ○1 → ○4 → ○6 → ○7 ○1 → ○3 → ○4 → ○5 → ○7 ○1 → ○3 → ○4 → ○6 → ○7 ○1 → ○3 → ○6 → ○7 2+5+5=12 2+6+3+5=16 2+6+4+6=18 2+3+5=10 2+4+6=12 5+5+3+5=18 5+5+4+6=20* 5+9+6=20 易见，○1 → ○3 → ○4 → ○6 → ○7 和○1 → ○3 → ○6 → ○7 都是关键路线. 显然，关键路线的长度就是生产过程的完工期或最早可能完工期. 在关键路线上，一个（关键）工序的开工事项即为其紧前工序的完工事项.关键工序完工事项的 延长或缩短必将导致生产过程的完工期的推迟和提前. 在非关键路线上，工序的开工可在其紧前工序完工后的一定时间范围内推迟，而不影响生产过程 的完工期. 统筹方法的根本任务就是本着“向关键路线要时间，向非关键路线要资源”的指导思想，作出最 优或最满意的生产计划. 关键路线的求解： 标号法：设统筹图中各顶点分别编号为○1 ，○2 ，…，○n . 步骤：