[NOIP 2006 提高组] 作业调度方案

GitHub 跳转原题关系图返回列表

按给定顺序逐个安排操作，在工件前序完成后寻找目标机器最早连续空闲时间段。

OJ: luogu

题目 ID: P1065

难度:普及/提高-

标签:模拟调度python

日期: 2026-06-19 02:34

题意

有 m 台机器和 n 个工件。每个工件有 m 道工序，每道工序指定机器和加工时间。题目给出安排顺序，要求每次把当前工序尽量早地插入目标机器的空闲时间段，同时满足同一工件前序工序已完成。

思路

用三个数组维护状态：

next_operation[job]：某个工件下一道要安排的工序编号；
job_finish_time[job]：某个工件上一道工序完成时间；
busy[machine][time]：某台机器某个时刻是否被占用。

处理安排顺序中的一个工件 job 时：

找到它当前工序的目标机器和加工时长；
开始时间不能早于 job_finish_time[job]；
从这个时间开始向后找，直到找到一段长度为 duration 的连续空闲时间；
标记这段机器时间为占用；
更新工件完成时间和答案。

这正好模拟了题目要求的“尽量靠前插入”。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：多行整数矩阵可以逐行 input().split()。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：二维列表要逐行创建，避免浅拷贝。
布尔矩阵 busy[machine][time] 适合表示时间轴占用。
遇到冲突时把 start 推到冲突时间之后，可以减少无效检查。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#include <bits/stdc++.h>
using namespace std;

const int MAXM = 25;     // 最大机器数
const int MAXN = 25;     // 最大工件数
const int MAXT = 10005;  // 时间轴上限

int m, n;
int order_list[MAXM * MAXN];        // 安排顺序：按顺序列出每次要安排的工件编号
int machine_id[MAXN][MAXM];         // machine_id[job][step] 工件 job 的第 step 道工序在哪台机器
int cost_time[MAXN][MAXM];          // cost_time[job][step] 工件 job 的第 step 道工序加工时长

int next_step[MAXN];                // 工件 job 下一次要安排第几道工序
int finish_time[MAXN];              // 工件 job 已安排完的最后时间（最早可开始下一道工序的时间）
bool busy[MAXM][MAXT];              // busy[machine][time] 标记该机器该时刻是否被占用

/* ===== 输入层：读取全部原始数据 ===== */
void read_input() {
    cin >> m >> n;
    int tot = m * n;

    for (int i = 1; i <= tot; i++)
        cin >> order_list[i];

    for (int job = 1; job <= n; job++)
        for (int step = 1; step <= m; step++)
            cin >> machine_id[job][step];

    for (int job = 1; job <= n; job++)
        for (int step = 1; step <= m; step++)
            cin >> cost_time[job][step];
}

/* ===== 调度层：核心调度逻辑 ===== */

// 在机器 mac 上从 start 时刻向后找一段长度为 len 的连续空闲时间。
int find_available_slot(int mac, int start, int len) {
    while (true) {
        bool ok = true;
        for (int t = start; t < start + len; t++) {
            if (busy[mac][t]) {
                start = t + 1;     // 遇到冲突，跳到冲突时刻之后继续找
                ok = false;
                break;
            }
        }
        if (ok) break;
    }
    return start;
}

int schedule_all() {
    int tot = m * n;
    int answer = 0;

    for (int i = 1; i <= tot; i++) {
        int job = order_list[i];           // 当前要安排的工件
        int step = ++next_step[job];       // 当前安排的是该工件的第几道工序
        int mac = machine_id[job][step];   // 目标机器
        int len = cost_time[job][step];    // 加工时长

        // 开始时间不能早于该工件上一道工序完成的时间
        int start = finish_time[job];

        // 在目标机器上找到最早的一段连续空闲时间段
        start = find_available_slot(mac, start, len);

        // 占用该机器上的 [start, start+len) 时间段
        for (int t = start; t < start + len; t++)
            busy[mac][t] = true;

        finish_time[job] = start + len;
        if (answer < finish_time[job])
            answer = finish_time[job];
    }
    return answer;
}

/* ===== 主控层：组装各层 ===== */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();

    int ans = schedule_all();

    cout << ans << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36machine_count, job_count = map(int, input().split())
order = [x - 1 for x in map(int, input().split())]
machine_for = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(job_count)]
duration_for = [list(map(int, input().split())) for _ in range(job_count)]

max_time = job_count * machine_count * 20 + 1
busy = [[False for _ in range(max_time)] for _ in range(machine_count)]
next_operation = [0 for _ in range(job_count)]
job_finish_time = [0 for _ in range(job_count)]
answer = 0

for job in order:
    operation = next_operation[job]
    machine = machine_for[job][operation]
    duration = duration_for[job][operation]

    start = job_finish_time[job]
    while True:
        can_place = True
        for time in range(start, start + duration):
            if busy[machine][time]:
                start = time + 1
                can_place = False
                break
        if can_place:
            break

    for time in range(start, start + duration):
        busy[machine][time] = True

    finish = start + duration
    job_finish_time[job] = finish
    next_operation[job] += 1
    answer = max(answer, finish)

print(answer)

复杂度

设最终时间轴长度为 T，共有 n*m 个操作。直接时间轴模拟复杂度约为 $O(nmT)$ ，本题数据范围很小，可以通过。空间复杂度是 $O(mT)$ 。

总结

调度题不要急着找复杂算法。题目已经规定唯一的靠前插入规则，按顺序找目标机器最早可行空档即可。

P1065 [NOIP 2006 提高组] 作业调度方案

题目描述

我们现在要利用 $m$ 台机器加工 $n$ 个工件，每个工件都有 $m$ 道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

每个工件的每个工序称为一个操作，我们用记号 j-k 表示一个操作，其中 $j$ 为 $1$ 到 $n$ 中的某个数字，为工件号； $k$ 为 $1$ 到 $m$ 中的某个数字，为工序号，例如 2-4 表示第 $2$ 个工件第 $4$ 道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。

例如，当 $n=3,m=2$ 时，1-1,1-2,2-1,3-1,3-2,2-2 就是一个给定的安排顺序，即先安排第 $1$ 个工件的第 $1$ 个工序，再安排第 $1$ 个工件的第 $2$ 个工序，然后再安排第 $2$ 个工件的第 $1$ 个工序，等等。

一方面，每个操作的安排都要满足以下的两个约束条件。

对同一个工件，每道工序必须在它前面的工序完成后才能开始；
同一时刻每一台机器至多只能加工一个工件。

另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。

由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为 1 1 2 3 3 2。

还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。

例如，取 $n=3,m=2$ ，已知数据如下（机器号/加工时间）：

工件号	工序 1	工序 2
$1$	$1/3$	$2/2$
$2$	$1/2$	$2/5$
$3$	$2/2$	$1/4$

则对于安排顺序 1 1 2 3 3 2，下图中的两个实施方案都是正确的。但所需要的总时间分别是 $10$ 与 $12$ 。

方案 1，用时 $10$ ：

时间	1	2	3	4	5	6	7	8	9	10
机器 1 执行工序	`1-1`	`1-1`	`1-1`	`2-1`	`2-1`	`3-2`	`3-2`	`3-2`	`3-2`	无
机器 2 执行工序	`3-1`	`3-1`	无	`1-2`	`1-2`	`2-2`	`2-2`	`2-2`	`2-2`	`2-2`

方案 2，用时 $12$ ：

时间	1	2	3	4	5	6	7	8	9	10	11	12
机器 1 执行工序	`1-1`	`1-1`	`1-1`	`2-1`	`2-1`	无	无	`3-2`	`3-2`	`3-2`	`3-2`	无
机器 2 执行工序	无	无	无	`1-2`	`1-2`	`3-1`	`3-1`	`2-2`	`2-2`	`2-2`	`2-2`	`2-2`

当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件 $(1.)(2.)$ 的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件 $(1.)(2.)$ 的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。

显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。

输入格式

第 $1$ 行为两个正整数 $m$ , $n$ ，用一个空格隔开，其中 $m(<20)$ 表示机器数， $n(<20)$ 表示工件数。

第 $2$ 行： $m \times n$ 个用空格隔开的数，为给定的安排顺序。

接下来的 $2n$ 行，每行都是用空格隔开的 $m$ 个正整数，每个数不超过 $20$ 。

其中前 $n$ 行依次表示每个工件的每个工序所使用的机器号，第 $1$ 个数为第 $1$ 个工序的机器号，第 $2$ 个数为第 $2$ 个工序机器号，等等。

后 $n$ 行依次表示每个工件的每个工序的加工时间。

可以保证，以上各数据都是正确的，不必检验。

输出格式

$1$ 个正整数，为最少的加工时间。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
82 3
1 1 2 3 3 2
1 2 
1 2 
2 1
3 2 
2 5 
2 4

输出 #1

text

说明/提示

NOIP 2006 提高组第三题

[NOIP 2006 提高组] 作业调度方案

目录

题意

思路

Python 知识

代码

复杂度

总结