第 卷 第 期 武 汉 测 绘 科 技 大 学 学 报年 月广 义 回 溯 方 法 及 并 行 计 算 机 系 统的 最 优 任 务 调 度李 鸣 山 吕 芝 艳武 汉 测 绘 科 技 大 学 计 算 机 科 学 与 工 程 系 , 武 汉 市 路 喻 路 号 , 。 。摘 要问 题 。关 健 词分 类 号给 出 了 广 义 回 溯 方 法 , 并 用 此 方 法 较 有 效 地 解 决 了 平 行 计 算 机 系 统 的 最 优 任 务 静 态 调 度广 义 回 溯 方 法 并 行 计 算 机 系 统 最 优 任 务 调 度本 文 所 指 的 并 行 计 算 机 系 统 是 指 紧 藕 合 的 多 处 理 机 系 统 , 系 统 的 处 理 机 个 数 是 有 限 的 。 该系 统 的 最 优 任 务 调 度 问 题 是 某 个 作 业 由 若 干 个 任 务 组 成 , 完 成 这 些 任 务 所 需 时 间 及 它 们 之 间的 优 先 关 系 在 调 度 设 计 之 前 是 已 知 的 , 要 设 计 一 个 任 务 在 各 个 处 理 机 上 分 配 的 方 案 , 使 作 业 总的 执 行 时 间 最 小 。 本 文 给 出 了 并 行 计 算 机 系 统 最 优 任 务 调 度 问 题 的 数 学 模 型 , 并 结 合 解 该 问 题给 出 了 广 义 回 溯 方 法 。 经 一 组 随 机 数 据 测 试 , 本 文 算 法 的 效 率 是 令 人 满 意 的 , 而 且 评 价 函 数 的计 算 也 是 简 单 的 。并 行 计 算 机 系 统 最 优 任 务 调 度 问 题 的 数 学 模 型并 行 计 算 机 系 统 最 优 任 务 调 度 问 题 可 用 如 下 元 组 描 述, , , , , , ,其 中 , 尸 , , , 为 个 处 理 机 的 集 合 一 , , , , 为 个 任 务 的 集 合 一, , , 一 , 、 , 是 完 成 任 务 , 所 需 时 间 , 镇 一 , , , , , , 是 任 务 、 的 完 成 时刻 , 成 一 必 , , , 为 阶 布 尔 方 阵 。 若 任 务 、 是 任 务 , 的 直 接 前 驱 , 则 久 , 否 则。 。 , 为 起 始 任 务 , 二 为 结 束 任 务 。 约 束 条 件 为当 , , 则 , 一 , 、 , 簇 ,已 知 , , , , 确 定 , , , , 。 , 使 , 最 小 。通 常 , 一 个 作 业 总 有 一 个 起 始 任 务 , 它 是 其 它 任 务 的 前 驱 任 务 总 有 一 个 结 束 任 务 , 它 是 其它 任 务 的 后 继 任 务 。 如 果 没 有 起 始 任 务 或 结 束 任 务 , 则 可 以 人 为 地 安 排 这 样 的 任 务 , 完 成 它 才所 需 的 时 间 为 零 , 这 不 影 响 对 问 题 的 讨 论 。 显 然 , 任 务 集 合 中 的 “ 前 驱 ” 或 “ 后 继 ” 关 系 是 一 、拟 序 关 系 。算 法 的 基 本 思 想设 某 一 作 业 有 个 任 务 、 , , , , , 其 中 是 起 始 任 务 , , 是 结 束 任 务 完 成 各 个 任收 稿 日 期 一 一 李 鸣 山 , 男 , 岁 副 教 授 , 现 从 事 人 工 智 能 和 算 法 理 论 研 究 。第 期 李 鸣 山 等 广 义 回 溯 方 法 及 并 行 计 算 机 系 统 的 最 优 任 务 调 度务 所 需 的 时 间 , , , , 。 及 各 个 任 务 之 间 的 “ 前 驱 ” 、 “ 后 继 ” 关 系 是 已 知 的 由 矩 阵 描 述 。因 为 任 务 之 间 的 “ 前 驱 ” 或 “ 后 继 ” 关 系 是 拟 序 关 系 , 所 以 任 务 之 间 的 关系 可 用 这 样 的 有 向 图 表 示 从 起 始 任 务 开 始 , 从 上 到 下 各 任 务 分 层 排列 , 图 中 的 边 关 联 两 个 有 直 接 “ 前 驱 ” 和 “ 后 继 ” 关 系 的 任 务 。 图 表 示 某个 作 业 含 有 个 任 务 , 和 。 分 别 是 起 始 任 务 和 结 束 任 务 , 各 结 点 处任 务 , 下 面 的 整 数 即 完 成 该 任 务 所 需 时 间 。 只 要 适 当 选 择 时 间 单位 , 总 可 以 认 为 是 整 数 。 有 向 图 的 边 的 箭 头 已 略 去 了 。假 设 有 个 处 理 机 , , , , 。 我 们 用 一 棵 高 为 的 元 有 序树 描 述 解 最 优 任 务 调 度 问 题 的 过 程 , 该 树 即 问 题 的 状 态 空 间 树 。 若 某 个第 层 根 结 点 是 第 层 的 结 点 , 表 示 的 状 态 是 任 务 。 由 处 理 机完 成 , 则 的 个 子 结 点 所 表 示 的 状 态 依 次 是 任 务 认 由 处 理 机 , , , 。 完 成 。 从 根 结 点 开 始 , 首 先 将 任 务 一 。 都 安 排 在 处 理 机 上 执 行 , 即 各 任 务 以 串行 方 式 在 , 上 执 行 。 在 状 态 空 间 树 中 , 即 是 从 根 结 点 开 始 , 每 次 都 是 扩 展 第 一 个 子 结 点 , 一 直到 叶 结 点 见 图 , 得 到 一 个 初 始 解 。 此 时 结 束 任 务 , 的 完 成 时 刻 , 是 完 成 各 任 务 所 需 时 间之 和 十 。 。 以 此 值 作 为 与 最 优 解 对 应 的 二 值 的 初 值 。从 叶 结 点 处 作 回 溯 。 因 为 , 是 结 束 任 务 , 它 是 。 一 的 直接 后 继 , 于 是 结 点 右 面 的 结 点 都 不 必 考 虑 , 即 任 务 , 安 排 在处 理 机 , , , 的 结 束 时 刻 与 安 排 在 , 是 相 同 的 。 由 结 点回 溯 到 结 点 一 的 第 子 结 点 十 , 即 考 察 将 任 务 一 , 安 排在 处 理 机 执 行 是 否 可 能 获 得 更 优 解 。 计 算 结 点 处 限 界函 数 的 值 关 于 值 的 计 算 方 法 稍 后 给出 以 便 确 定 是 否 有 必 要 扩 展 该 结 点 。一 般 地 , 若 结 点 , 表 示 的 状 态 是 任 务 , 已 由 处 理 机 , 完成 , 则 , 处 的 值 是 沿 扩 展 结 点 到 达 叶 结 点 时 , 结束 任 务 , 完 成 时 刻 , 的 下 界 。 若 此 值 小 于 当 前 的 图值 , 说 明 扩 展 , 可 能 获 得 更 优 解 , 于 是 扩 展 生 成 它 的 第一 子 结 点 , 即 将 任 务 八 交 由 处 理 机 执 行 。 若 , 处 的 值 不 小 于 当 前 的 值 ,则 表 明 扩 展 , 不 可 能 获 得 更 优 的 解 , 于 是 不 扩 展 。 此 时 分 两 种 情 况 若 , 不 是 序 号 为 的 子结 点 , 则 生 成 它 的 右 结 点 , 即 将 任 务 改 为 由 处 理 机 完 成 若 , 是 序 号 为 的 子 结 点 , 则回 溯 到 上 一 层 , 此 时 也 需 根 据 。 的 父 结 点 是 否 是 序 号 为 的 子 结 点 确 定 是 继 续 回 溯 还 是 生 成它 的 右 子 结 点 。 不 论 哪 种 情 形 , 每 当 生 成 一 个 新 的 结 点 , 都 要 计 算 该 结 点 处 的 值 , 以便 确 定 下 一 步 做 法 。当 回 溯 到 第 层 结 点 它 对 应 任 务 。 完 成 情 况 , 回 溯 过 程 结 束 。 这 是 因 为 是 起 始 任务 , 它 是 所 有 其 它 任 务 的 前 驱 , 因 此 它 由 哪 个 处 理 机 完 成 并 不 影 响 总 的 运 行 时 间 。 而 是 乙的 直 接 后 继 , 不 论 它 由 哪 个 处 理 机 执 行 , 该 处 理 机 完 成 的 时 刻 总 等 于 十 。任 一 结 点 , 处 限 界 函 数 的 计 算 如 此 进 行 设 , 处 于 第 层 , 此 时 任 务 , , , , 的 完 成 时 刻 分 别 是 , , , 。 对 任 务 , , , 。 由 矩 阵 找 出 它 们 的 后 继 任 务 直至 结 束 任 务 , 若 某 个 任 务 有 多 个 直 接 后 继 任 务 , 则 取 所 需 时 间 最 大 者 , 这 样 就 得 到 了 个 任 务序 列 。 计 算 各 任 务 序 列 所 需 时 间 之 和 , , , , 及 它 们 分 别 与 , , , 之 和 。 取 这 个和 数 中 最 大 者 , 显 然 它 是 沿 结 点 二 , 扩 展 结 点 到 达 叶 结 点 时 , 结 束 任 务 。 的 完 成 时 刻 的 一 个武 汉 测 绘 科 技 大 学 学 报 年适 当 的 下 界 , 将 它 作 为 结 点 , 处 的 值 。上 述 回 溯 方 法 实 质 上 是 在 穷 尽 搜 索 过 程 中 利 用 限 界 函 数 避 免 生 成 那 些 不 可 能 导 致 最 优 解的 结 点 , 从 而 当 回 溯 结 束 时 得 到 的 必 定 是 最 优 解 。图 是 对 图 的 任 务 图 按 上 述 回 溯 方 法 求 解 最 优 解 的 过 程 。 图 中 值 即 值 ,叶 结 点 对 应 初 始 解 , 即 由 处 理 机 , 以 串 行 方 式 依 次 执 行 任 务 。 。 结 束 任 务 的 完 成时 刻 是 , 十 十 。 一 , 以 此 值 作 为 。 的 最 优 值 的 初 值 。 在 结 点 处 , 一 ,十 , , , 斗 一 。 一 , 它 就 是 结 点 处 的 值 。 该 值 小 于 当 前 值 , 故扩 展 结 点 有 可 能 获 得 更 优 的 解 , 于 是 扩 展 该 结 点 , 生 成 它 的 第 一 子 结 点 左 子 结 点 。 结 点是 叶 结 点 , 对 应 的 值 是 , 我 们 得 到 了 一 个 比 初 始 解 更 优 的 解 , 并 以 作 为 新 的 值 。以 下 步 骤 类 似 地 进 行 。 当 扩 展 到 结 点 时 , 该 处 的 值 等 于 , 它 大 于 当 前 值, 故 扩 展 它 是 无 意 义 的 , 应 生 成 它 的 右 结 点 。 在 叶 结 点 处 得 到 更 优 解 , 的 新 值 为。 当 回 溯 到 结 点 , 它 对 应 的 状 态 是 任 务 在 处 理 机 上 执 行 , 此 时 回 溯 结 束 。 因 此 结 点对 应 的 解 是 最 优 解 , 对 应 的 最 优 值 是 , 该 最 优 解 所 对 应 的 各 任 务 在 处 理 机 和 九上 的 安 排 如 图 所 示 。 一 般 说 来 , 这 一 类 问 题 的 最 优 解 不 是 唯 一 的 。算 法我 们 将 给 出 的 算 法命 名 为 ,用 一 种 类 语言 描 述 。 算 法 中 所 用 的一 些 符 号 含 义 是 明 显的 , 对 一 些 非 关 键 部 分只 写 了 过 程 名 , 对 变 量 、的 说 明 也 略 去 了 。算 法 中 所 用 变 量 名和 过 程 名 如 下少 为 处 理 机 数 ,为 任 务 数 , 为 处 理 机计 数 , 为 任 务 计 数 ,为 状 态 树 层 次 , 它 也 是任 务 号 。 若 任 务 , 在 处理