逻辑与策略 · 方法讲解
先找不能更快的下界，再排出达到下界的时间表。
视频暂时无法加载，仍可阅读正文与文字稿，或下载MP4观看。
甲需工人操作3分钟，乙需工人操作2分钟；甲乙无先后要求。机器须等甲乙都完成后，自动运行4分钟。每道工序不可中断，开始时资源均可用，切换无耗时。机器自动运行不占工人；做完机器即全部完工。比较一名工人与两名工人的最短工期。
一名工人：甲0至3，乙3至5，机器5至9。最短9分钟。两名工人：甲0至3，乙0至2，机器3至7。最短7分钟。
对应左侧：一名工人
9分钟
甲乙共用工人，先后合计5分钟；机器再用4分钟，因此至少9分钟。
时间条完整显示供对照，逐步强调工序。浅色条表示尚未强调，不表示工序已被删除。切换题目后条件与解释同步更新。
会时间加减，能比较多个结束时刻，理解“同时”“先后”“都完成后”。不要求先学图论。前置工序是某项开始前必须完成的工序；资源是工人、机器等同一时刻容量有限的对象。
统一假设：时长已知且不随安排改变；工序不可中断；每项只执行一次；可在时刻0开工；不计搬运、切换、休息及启动耗时。自动工序占机器而不占工人，人工工序始终占用一名工人。若题目另有条件，必须重建模型。
本页限少量工序的依赖与资源排程。S班表示项目编排深度，非已核实的机构或学期官方课纲。所有题目为自拟教学题。
用箭头“甲→机器”表示机器必须等甲完成，不表示同一人操作。若某工序有多个前置，最早开始时刻为所有前置结束时刻中的最大值，再加自身时长得到最早结束时刻。没有前置的工序可从0开始，但还要检查资源是否可用。
如果资源充足，所有已满足前置的工序都能同时开始，那么沿图计算即可得到最短工期。最长依赖链称为关键路径（Critical path）。链上工序不能重叠，所以链长是下界；资源充足时，按最早时刻开工的安排达到它。若依赖中出现环且每项时长为正，则无法按“完成后才能开始”执行，不能套此递推。
开头一人题中，甲与机器链长3＋4＝7，乙与机器链长2＋4＝6，所以最长依赖链为7。工人总工作量为3＋2＝5。即使取7与5中较大的7，也仍不是最短工期。因为机器需要两项前置都完成，而这两项又共用一人，两项全部完成至少要5分钟；此后机器还要4分钟，所以工期至少为9。
这是把资源限制与依赖关系合在一起的下界。一般地，一份资源所需的总占用时间是一个下界；有m份可互换资源，总负荷除以m也只是下界，是否能达到还受依赖、不可中断和工序长度约束。不能把一个下界未经构造就当成答案。
找必须顺序执行的链，或必须完成的资源负荷，再检查它们之间是否有共同前置与后续。
逐项列开始、结束、占用资源；查每个前置已完成，并查同一资源没有重叠。若实际工期等于下界，最短工期即被证明。
若构造比当前下界长，只能说明“已知下界≤最优工期≤这份安排”。应改进安排、加强下界，或对少量可行顺序做完整分类。发现几份慢安排不能证明更快的安排不存在。
例题一 · 同一依赖，资源不同
条件与开头一致：甲乙各需一名工人，无先后限制；机器在两项都完成后自动运行4分钟。不可中断，切换无耗时。求两名工人和一名工人的最短工期。
边界：若机器必须有人全程看守，本例机器阶段仍在甲乙之后，答案没有变化；但“自动运行可腾出工人”的机制会在后续题失效，不能据此忽略是否看守。
例题二 · S班结构变式
只有一名工人和一台机器。甲需工人2分钟；甲完成后乙可自动运行6分钟，不占工人。丙无前置，需工人4分钟。丁需工人1分钟，必须等乙、丙都完成后开始。所有工序不可中断，切换无耗时。求最短工期，并证明。
反证经验法：若先做较长的丙，丙0—4、甲4—6、乙6—12、丁12—13，需13分钟。“长工序先做”在此失败；问题在于它推迟了自动工序启动。
甲需工人4分钟，乙需工人3分钟，无先后关系。两项都完成后，机器自动运行5分钟，全部完工。工序不可中断、切换无耗时。分别求一名工人、两名工人的最短工期。
一名工人：甲乙不能重叠，两项都完成至少需4＋3＝7分钟，再接机器5分钟，下界12。安排甲0—4、乙4—7、机器7—12，达到下界，最短12分钟。
两名工人：甲0—4、乙0—3并行，机器4—9。链“甲→机器”长4＋5＝9，下界与安排相等，最短9分钟。不能把乙结束的3当作机器开工时刻，因为甲仍未完成。
一名工人、一台机器。甲需工人3分钟；甲后乙自动运行5分钟且不占工人；丙独立需工人4分钟；丁需工人2分钟，须等乙丙都完成。不可中断、切换无耗时。求最短工期，判断先丙是否最优。
依赖链甲→乙→丁给出下界3＋5＋2＝10分钟。安排：甲0—3；乙3—8；丙3—7；丁8—10。工人7—8空闲，但实际10分钟达到下界，所以最短10分钟。
若先丙0—4，甲4—7，乙7—12，丁12—14，工期14分钟，因此先丙不最优。丁必须等乙和丙，开始时刻为两者结束时刻中更晚的8，而不能用7。
| 错误推断 | 反例或修正 |
|---|---|
| 最长依赖链就是答案 | 例一一人题，链长7，实际最短9。关键路径只有在资源支持相应并行时才可直接决定工期。 |
| 把所有时长相加就是最短 | 例二合计2＋6＋4＋1＝13，但乙与丙可并行，最短9。 |
| 机器自动就不占任何资源 | 自动阶段仍占机器；若再有一道也需同一台机器，必须另查机器冲突。 |
| 有两个前置就把它们相加 | 前置可并行时取结束时刻的较大值；共用资源时还要先排程。 |
| 每一分钟都忙才是最优 | 例二工人6—8空闲仍达到9分钟下界。 |
| 可随意拆开工序塞入空档 | 本页工序不可中断。若允许中断，或工时随人数变化，必须另行说明。 |
回顾：列时长与占用资源 → 画前置关系 → 求可靠下界 → 排开始与结束时刻 → 逐项查依赖和冲突 → 用下界等于构造证明最优。少量工序可完整比较顺序；本页不声称给出一般复杂排程的万能公式。
完整文字稿默认展开；点击标题可定位到视频的对应章节。
统筹先看两件事：谁必须先做，谁会占用同一资源。
甲工序三分钟，乙两分钟，都要工人。两项完成后，机器再自动运行四分钟。
若有两名工人，甲乙同时开始，三分钟后都完成，机器运行到第七分钟。
甲再接机器，至少要七分钟。这份安排达到七分钟，所以它是最短工期。
现在只留一名工人。甲乙不能重叠，都完成至少要三加二，五分钟。
机器必须再等四分钟，因此总工期至少九分钟。原来的七分钟下界不够强。
先甲零到三，再乙三到五，最后机器五到九，没有冲突，恰好九分钟。
换一个问题：甲要工人两分钟，随后乙自动运行六分钟。丙独立，要工人四分钟。
丁要工人一分钟，必须等乙和丙完成。先做甲，再利用机器运行时做丙。
甲零到二，乙二到八，丙二到六，丁八到九。甲乙丁的依赖链也要九分钟。
最短工期的证明，要把不能更快的下界，和确实做到的安排配成一对。
只算关键路径，必须核对资源允许。少量工序还要比较顺序，别把所有时间直接相加。
时间条横轴为分钟，按时长比例绘制；依赖图中结点的位置与箭头长短不表示耗时。青绿表示工人占用，暖色表示机器自动运行。不同工序用名称区分，不能只凭颜色认工序。
本页题目为自拟。依据为明确列出的模型条件、完整下界证明与时间表核验；未借用未经核实的题库或课纲。下载视频 · 下载完整离线包