Decision Maths 1: Machine Scheduling | 决策数学1：机器调度知识点精讲

📚 Decision Maths 1: Machine Scheduling | 决策数学1：机器调度知识点精讲

Machine Scheduling (MS) is a core topic in Decision Maths 1, focusing on how to sequence tasks, allocate resources, and minimise completion time in manufacturing, project management, and service operations. This article provides a systematic revision guide to essential concepts such as activity networks, critical path analysis, Gantt charts, resource levelling, and Johnson’s algorithm for two‑machine flow shops.

机器调度（MS）是决策数学1的核心专题，研究如何安排任务顺序、分配资源、最小化制造、项目管理和服务运营中的完成时间。本文系统梳理活动网络、关键路径分析、甘特图、资源均衡和两台机器流水车间的约翰逊算法等重要知识点，助你高效备考。

1. Introduction to Scheduling Problems | 调度问题简介

Scheduling is the process of arranging, controlling and optimising work and workloads in a production process or a project. It involves determining the start and finish times of tasks, assigning machines or workers, and respecting precedence constraints and resource limits. Typical objectives are to minimise the overall makespan (total completion time), reduce idle time or meet deadlines.

调度是在生产过程或项目中对工作和工作量进行安排、控制和优化的过程。它涉及确定任务的开始和结束时间、分配机器或人员，并遵循前后约束和资源限制。常见目标是使总工时（makespan）最小、减少闲置时间或满足截止期限。

In Decision Maths 1, we often represent a project as a set of activities with durations and dependencies. The goal is to find a feasible schedule that minimises the project duration given zero or more machines. When multiple jobs must be processed on two machines in the same order, we apply specific algorithms like Johnson’s rule.

在决策数学1中，我们通常将一个项目表示为一组具有持续时间和依赖关系的活动。目标是在给定零个或多个机器的情况下找到可行的时间表，使项目工期最短。当多个作业必须在两台机器上按相同顺序加工时，我们应用特定的算法，如约翰逊规则。

2. Activity Networks and Critical Path Analysis (CPA) | 活动网络与关键路径分析

An activity‑on‑node network represents each activity as a box (node), with arrows showing dependencies. Dummy activities with zero duration are used only to maintain logical relationships. For each activity, we provide its duration and list immediate predecessors.

活动节点网络将每个活动表示为一个框（节点），箭头显示依赖关系。零工时的虚活动仅用于保持逻辑关系。对每个活动，我们给出其持续时间并列出现前活动。

Critical Path Analysis calculates the earliest start time (EST), earliest finish time (EFT), latest start time (LST) and latest finish time (LFT) for each activity. The forward pass (left to right) computes EST = max(EFT of predecessors); the backward pass (right to left) computes LFT = min(LST of successors). An activity is critical if its total float is zero, meaning any delay will delay the whole project.

关键路径分析计算每个活动的最早开始时间 (EST)、最早完成时间 (EFT)、最晚开始时间 (LST) 和最晚完成时间 (LFT)。正向扫描（从左到右）计算 EST = max(前驱的 EFT)；反向扫描（从右到左）计算 LFT = min(后继的 LST)。如果一个活动的总浮动时间为零，它就是关键的，任何延误都会推迟整个项目。

3. Forward and Backward Pass Detailed Steps | 前向扫描与后向扫描的详细步骤

Forward pass: Set the start node’s EST = 0. For each subsequent activity, EST = maximum EFT of all immediate predecessors, where EFT = EST + duration. The project duration is the largest EFT in the final node.

前向扫描：设起始节点的 EST = 0。对每一个后续活动，EST = 所有直接前驱中最大的 EFT，其中 EFT = EST + 工期。项目工期就是最终节点中最大的 EFT。

Backward pass: Set the final activity’s LFT equal to the project duration (or its EFT if all finish together). Then LFT = minimum LST of all immediate successors, where LST = LFT – duration. Continue backwards to the start.

反向扫描：将最后一个活动的 LFT 设为项目工期（如果同时结束则为其 EFT）。然后 LFT = 所有直接后继中最小的 LST，其中 LST = LFT – 工期。依次反向计算到起点。

All times are typically recorded in a table, and the critical path is the sequence of activities where LST = EST and LFT = EFT.

所有时间通常记录在表格中，关键路径就是 LST = EST 且 LFT = EFT 的活动序列。

4. Total Float, Free Float and Interfering Float | 总浮动、自由浮动和干扰浮动

Total float = LST – EST = LFT – EFT. It shows how much an activity can be delayed without affecting the overall project finish. Free float = (EST of earliest successor) – EFT of this activity. It shows how much an activity can be delayed without affecting any following activity. Interfering float = total float – free float.

总浮动 = LST – EST = LFT – EFT，它表示在不影响整个项目完工的前提下活动可以延迟的时间。自由浮动 =（最早后继活动的 EST）– 本活动的 EFT，它表示不影响任何后续活动的延迟量。干扰浮动 = 总浮动 – 自由浮动。

These measures are essential for resource smoothing and scheduling. Critical activities have total float = 0, while non‑critical activities offer flexibility.

这些度量对资源平滑和调度至关重要。关键活动的总浮动为 0，而非关键活动具有灵活性。

5. Gantt Charts for Project Scheduling | 项目调度中的甘特图

A Gantt chart is a bar chart showing activities against time. Each activity is drawn as a horizontal bar, starting at its EST (for an early‑start schedule) or LST (for a late‑start schedule). The length represents duration. Dependencies are not explicitly drawn but are implied by the start times.

甘特图是一个以时间为横轴显示活动的条形图。每个活动画成一个水平条，从最早开始时间（早开始调度）或最晚开始时间（晚开始调度）开始，长度代表工期。依赖关系没有显式画出，但通过开始时间体现。

Gantt charts are especially useful for visualising resource usage. By arranging bars we can check for resource conflicts. The early‑start schedule places all activities as soon as possible, which may cause high resource peaks; the late‑start schedule delays activities as much as possible, often smoothing resource demands.

甘特图对可视化资源使用特别有用。通过排布条形我们可以检查资源冲突。早开始调度让所有活动尽早开始，可能导致资源高峰；晚开始调度使活动尽量推迟，常能平滑资源需求。

6. Resource Scheduling and Resource Histograms | 资源调度与资源直方图

Resources, such as workers or machines, are often limited. A resource histogram shows the number of resource units required over time for a given schedule. If the required number exceeds availability, we must resolve the conflict by shifting non‑critical activities within their floats.

资源（如工人或机器）通常有限。资源直方图显示在给定调度下各时段所需资源单位的数量。如果所需数量超过可用量，我们必须通过在其浮动范围内移动非关键活动来解决冲突。

Resource levelling aims to minimise fluctuations in resource demand, while resource smoothing attempts to keep demand within a fixed limit without delaying the project. Both techniques rely on float information and Gantt charts.

资源均衡旨在最小化资源需求的波动，而资源平滑则试图在不推迟项目的前提下将需求控制在固定限额之内。这两种技术都依赖于浮动信息和甘特图。

7. Johnson’s Algorithm for Two‑Machine Flow Shop | 两台机器流水车间的约翰逊算法

When n jobs must be processed first on Machine A then on Machine B, Johnson’s rule minimises the makespan. The algorithm:

当 n 个作业必须先由机器 A 加工再由机器 B 加工时，约翰逊规则可使总工时最短。算法步骤如下：

Step 1: List all jobs with their processing times on A and B.

步骤1：列出所有作业及其在 A 和 B 上的加工时间。
Step 2: Find the job with the smallest processing time. If the minimum is on A, schedule that job as early as possible; if on B, schedule it as late as possible. Remove it from the list.

步骤2：找出最小加工时间的作业。如果最小时间在 A 上，将该作业尽量往前安排；如果在 B 上，则尽量往后安排。将其从列表中移除。
Step 3: Repeat Step 2 for the remaining jobs until a complete sequence is built.

步骤3：对剩余作业重复步骤2，直到构建出完整序列。
Step 4: Use a Gantt chart or calculations to determine the makespan, idle times on each machine.

步骤4：使用甘特图或计算确定总工时以及每台机器的闲置时间。

The resulting sequence is optimal. Johnson’s algorithm can be extended to three machines under certain conditions, but Decision Maths 1 usually covers only two.

得到的序列是最优的。约翰逊算法在特定条件下可扩展到三台机器，但决策数学1通常只涉及两台。

8. Calculating Makespan and Idle Time | 总工时与闲置时间的计算

For a given sequence (S₁, S₂, …, Sₙ), we can compute the completion times stepwise:

对于给定序列 (S₁, S₂, …, Sₙ)，我们可以逐步计算完成时间：

Machine A completion time of job i: C(A, i) = C(A, i‑1) + aᵢ (where aᵢ is its A processing time).

机器 A 上作业 i 的完成时间：C(A, i) = C(A, i‑1) + aᵢ（其中 aᵢ 是其在 A 的加工时间）。
Machine B completion time of job i: C(B, i) = max( C(B, i‑1), C(A, i) ) + bᵢ. Idle time on B between jobs = max(0, C(A, i) – C(B, i‑1)).

机器 B 上作业 i 的完成时间：C(B, i) = max( C(B, i‑1), C(A, i) ) + bᵢ。作业间机器 B 的闲置时间 = max(0, C(A, i) – C(B, i‑1))。

Total makespan = C(B, n). Total idle time on B = sum of those gaps. The algorithm sequence ensures this makespan is the minimum possible for the two‑machine flow shop.

总工时 = C(B, n)。机器 B 的总闲置时间是这些间隙之和。该算法序列能保证这是两台机器流水车间可能的最小总工时。

9. Gantt Chart for Flow Shop Sequencing | 流水车间排序的甘特图

After obtaining the optimal sequence, we draw a Gantt chart with two rows (Machine A and Machine B). For each job, Machine A’s bar starts after the previous job’s A bar finishes; Machine B’s bar can start only when B is free and the job has finished on A. This visual representation confirms makespan and idle times.

得到最优序列后，我们绘制两行甘特图（机器 A 和机器 B）。对每个作业，机器 A 的条形在前一个作业的 A 条形结束后开始；机器 B 的条形只有在 B 空闲且作业在 A 上完成后才能开始。这种可视化方式可以确认总工时和闲置时间。

Gantt charts are also used to compare different heuristic sequences (e.g. shortest processing time first). Johnson’s sequence typically gives the shortest overall time, but other sequences may balance workloads differently.

甘特图也用于比较不同的启发式序列（如最短加工时间优先）。约翰逊序列通常给出最短的总时间，但其他序列可能以不同方式平衡工作负荷。

10. Heuristic Scheduling Rules for Complex Problems | 复杂问题的启发式调度规则

For problems with more than two machines or unrelated parallel machines, optimal algorithms may not exist in polynomial time. Decision Maths 1 introduces simple priority dispatching rules:

对于多于两台机器或非相关并行机的问题，可能不存在多项式时间的最优算法。决策数学1引入简单的优先分派规则：

FCFS: First Come First Served – process in arrival order.

FCFS：先到先服务 – 按到达顺序加工。
SPT: Shortest Processing Time first – minimise average flow time.

SPT：最短加工时间优先 – 使平均流动时间最小。
LPT: Longest Processing Time first – can minimise makespan on parallel machines.

LPT：最长加工时间优先 – 可在并行机上最小化总工时。
EDD: Earliest Due Date – reduce lateness.

EDD：最早截止日期 – 减少延误。
Critical Ratio: (time until due) / (processing time) – smallest ratio first.

关键比：（距截止时间）/（加工时间） – 比率最小的优先。

Students should evaluate these rules by computing average completion time, maximum lateness, or makespan. No single rule is universally best; the choice depends on the objective.

学生应通过计算平均完成时间、最大延迟或总工时间来评估这些规则。没有哪个规则是普遍最优的，选择取决于目标。

11. Assumptions and Limitations in Scheduling Models | 调度模型的假设与限制

All models in Decision Maths 1 assume deterministic processing times, no machine breakdowns, and that all jobs are available at time zero. Pre‑emption (interrupting a job) is usually not allowed unless specified. Resources are often treated as renewable and single units. Real‑world complications such as setup times, release dates, or stochastic times are ignored.

决策数学1中的所有模型都假设加工时间是确定的，机器不会故障，所有作业在零时刻都已可用。除非特别说明，通常不允许抢占（中断作业）。资源通常被视为可再生且以单一单位处理。现实中的调整时间、释放日期或随机时间等复杂因素被忽略。

Understanding these assumptions helps in critically evaluating scheduling solutions and recognising when advanced methods (beyond D1) are needed.

理解这些假设有助于批判性地评估调度方案，并意识到何时需要超出 D1 的高级方法。

12. Checklist for Decision Maths 1 Scheduling Questions | 决策数学1调度问题检查清单

Draw and label an activity network; check all predecessors.

绘制并标注活动网络；核对所有前驱。
Perform forward and backward passes accurately; record EST, EFT, LST, LFT.

准确进行正反向扫描；记录 EST, EFT, LST, LFT。
Identify critical path(s) and calculate floats.

识别关键路径并计算浮动时间。
Construct Gantt chart (early‑start and/or late‑start).

构建甘特图（早开始和/或晚开始）。
Draw resource histogram and level resources within floats.

绘制资源直方图并在浮动范围内平衡资源。
Apply Johnson’s algorithm to sequencing problems with two machines; write the optimal order and compute makespan.

对两台机器的排序问题应用约翰逊算法；写出最优顺序并计算总工时。
Use heuristic rules to generate sequences and compare performance measures.

使用启发式规则生成序列并比较性能指标。
Interpret results in the context of the problem, referencing idle time, delay or resource conflicts.

在问题背景下解释结果，涉及闲置时间、延误或资源冲突。

Published by TutorHao | Further Maths Decision 1 Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Decision Maths 1: Machine Scheduling | 决策数学1：机器调度知识点精讲