当前位置：首页 > news >正文

经典算法独立任务最优调度问题

news 来源：原创 2025/5/15 13:24:36

独立任务最优调度问题

题目描述

用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai ，若由机器B 来处理，则需要时间bi 。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai >=bi，而对于某些j,j≠i，有aj < bj 。既不能将一个作业分开由2 台机器处理，也没有一台机器能同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。

研究一个实例：

a = (a₁, a₂, a₃, a₄, a₅, a₆) = (2, 5, 7, 10, 5, 2)
b = (b₁, b₂, b₃, b₄, b₅, b₆) = (3, 8, 4, 11, 3, 4)

对于给定的 2 台处理机 A 和 B 处理 n 个作业，找出一个最优调度方案，使得 2 台机器处理完这 n 个作业的总时间最短。

输入格式

第 1 行是一个正整数 n (n ≤ 200)，表示要处理的作业数量。
第 2 行有 n 个正整数，表示处理机 A 处理第 i 个作业所需的时间。
第 3 行有 n 个正整数，表示处理机 B 处理第 i 个作业所需的时间。

输出格式

输出一个整数，表示最短的处理时间。

样例输入

6
2 5 7 10 5 2
3 8 4 11 3 4

样例输出

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n, sum = 0, ans = INT_MAX;cin >> n;vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];for (int i = 1; i <= n; i++) cin >> b[i];vector<int> last(sum + 1), now(sum + 1);for (int i = 1; i <= n; i++) {for (int j = 0; j <= sum; j++) {if (j < a[i]) now[j] = last[j] + b[i];else now[j] = min(last[j] + b[i], last[j - a[i]]);}last = now;}for (int i = 0; i <= sum; i++) ans = min(ans, max(last[i], i));cout << ans;return 0;
}//by wqs

这个问题是一个经典的**“二机调度”问题，目标是在两台机器之间分配任务，使得它们并行处理的总时间最短**。我们不能把一个任务拆分，也不能让同一时刻一台机器干多个任务。

我们使用动态规划来解决这个问题。

🧠 思路解析

✅ 1. 状态定义

我们定义 dp[i][j] 为：

前 i 个任务中，有一部分分配给机器 A，其处理时间总和为 j，
那么机器 B 在这种分配下所需的总处理时间为 dp[i][j]。

这表示的是一个“子集划分”的过程：在前 i 个任务里，部分分配给机器 A，剩下的给机器 B，j 是当前机器 A 的时间总和。

最终，我们要求的就是在所有 j（即所有可能的机器 A 时间）中：

max(j, dp[n][j]) 的最小值（因为两个机器是并行工作的，总时间由 慢的一台机器决定）。

✅ 2. 初始状态

dp[0][0] = 0，表示还没有任务时，A 和 B 都没工作。

✅ 3. 状态转移

对于第 i 个任务（1 <= i <= n）：

如果我们把它交给机器 A，耗时 a[i]：

dp[i][j + a[i]] = min(dp[i][j + a[i]], dp[i-1][j])

如果我们把它交给机器 B，耗时 b[i]：

dp[i][j] = min(dp[i][j], dp[i-1][j] + b[i])

注意，状态转移从上一个任务的状态进行。

✅ 4. 空间优化

我们只关心第 i-1 行到 i 行的转移，可以用滚动数组优化空间，即只用两个一维数组 last 和 now。

✅ 5. 最终答案

遍历所有可能的机器 A 的时间 j：

ans = min(ans, max(j, dp[n][j]))

这就是并行完成任务的最短时间。

✅ 总结关键点

核心是划分子集，使得两组时间最大值最小。
动态规划用于遍历所有可能的分配方案。
使用 max(A时间, B时间) 表示总耗时，目标是让它尽量小。
用滚动数组优化空间，时间复杂度为 O(n * sum(a))。

要我为你把这个逻辑画成图解或流程图吗？