计算机辅助设施布置

计 算 机 辅 助 设 施 布 置 布 置 规 划 工 作 的 很 大 一 部 分 内 容 是 对已 有 布 置 设 计 的 细 小 改 变 ， 例 如 确 定新 机 器 的 放 置 位 置 、 工 厂 的 部 分 改 造 、物 料 搬 运 作 业 研 究 等 。完 成 新 生 产 线 或 新 工 厂 的 规 划 是 很 重要 的 工 作 ， 除 非 是 因 为 战 争 和 大 规 模的 扩 展 ， 一 般 情 况 下 布 置 规 划 人 员 很少 有 机 会 考 虑 这 么 大 的 问 题 。 布 置 的 定 量 分 析l图 表 法 设 施 布 置 技 术l计 算 机 辅 助 设 施 布 置 基 于 部 门 的 “ 密 切 程 度 ”等 级 或 者 “ 物 流 强 度 ”来 确 定 部 门 间 相 对 位 置提 出 模 型 和 算 法 ， 可 以 帮 助 布 置 分 析 人 员 开 发或 改 进 布 置 ， 同 时 提 供 目 标 判 据 ， 以 简 化 对 该过 程 中 出 现 的 不 同 布 置 方 案 的 选 择 。 Apple的 工 厂 布 置 方 法1、 获 取 基 本 数 据 ；2、 分 析 基 本 数 据 ；3、 设 计 生 产 工 艺 ；4、 规 划 物 料 流 动 模 式 ；5、 考 虑 通 用 的 物 料 搬 运 规 划 ；6、 计 算 设 备 需 求 ；7、 规 划 各 个 工 作 站 ；8、 选 择 特 定 的 物 料 搬 运 设 备 ；9、 协 调 相 关 作 业 组 别 （ Coordinate groups of related operations ） ； 10、 设 计 作 业 单 位 相 互 关 系 图 ； 11、 确 定 存 储 需 求 ；12、 规 划 服 务 和 辅 助 作 业 单 位 ；13、 确 定 空 间 需 求 ；14、 给 各 个 作 业 单 位 分 配 面 积 ；15、 考 虑 建 筑 类 型16、 构 造 总 体 布 置 方 案 ；17、 与 相 关 人 员 一 起 评 价 、 调 查 和 检查 布 置 方 案 ；18、 获 得 批 准 ；19、 正 式 批 准 布 置 方 案20、 实 施 布 置不 管 是 从 设 计 过 程 还 是 内 容 说 ， 没 有 两 个 布 置 设 计 项 目 是 完 全 相 同 的 。 在 完 成 一 个 初 始 布 置 方 案前 ， 一 般 会 跳 过 上 面 的 一 些 步 骤 ， 但 是 因 为 开 发 设 计 时 很 多 事 情 是 不 可 预 见 的 ， 所 以 以 后 会 重 新回 到 前 面 的 步 骤 ， 进 行 检 查 或 者 重 做 。 计 算 机 辅 助 设 施 布 置 研 究 对 象l设 施 位 置 问 题 厂 址 选 择l设 施 布 置 问 题 厂 区 规 划 设 施 位 置 问 题l位 置 问 题 厂 址 选 择 ： 新 建 一 家 工厂 时 ， 如 何 在 有 限 的 数 个 可 选 地 点 选择 一 个 最 佳 厂 址 ， 其 目 标 往 往 是 原 材料 和 产 品 运 输 费 、 建 设 费 用 以 及 生 产费 用 最 小 。l求 解 方 法 ：v运 输 问 题 解 法v重 心 法v最 优 化 解 法 （ 图 论 ） 等 。 设 施 布 置 问 题l最 优 算 法 （ 最 优 化 理 论 ）l次 优 算 法v穷 举 法v面 向 新 建 型 系 统 布 置 程 序v面 向 改 进 型 系 统 布 置 程 序 算 法 分 类n 按 照 需 要 的 数 据 类 型从 至 表 的 定 量 物 流 数 据相 关 表 之 类 的 定 性 数 据同 时 接 受 相 关 表 和 从 至 表n 按 照 目 标 函 数 分 类使 得 流 量 与 距 离 乘 积 的 和 最 小 基 于 距 离 目 标使 得 相 邻 值 最 大 基 于 相 近 程 度 1 1min m m ij ij iji jz f c d 1 1max m m ij iji jz f x 1 11 11 0m m ij iji jm m iji jij ijf xZ fi j x x 归 一 化 的 相 邻 值如 果 部 门 和 相 邻 ， 则 ， 否 则 ( , ) ( , )( , ) ( , ) (1 )m mij ij ij iji j F i j Fm mij iji j F i j Fijf x f xX fZ f f 如 果 有 等 级 ， 则 可 能 为 负 值 移 动 单 位 物料 的 单 位 距离 成 本 算 法 分 类n 按 照 布 置 方 式 划 分离 散 型 表 现 方 式 ， 每 个 部 门 的 面 积 四 舍 五 入 到最 近 的 整 格 子 数连 续 型 表 现 方 式 ， 不 采 用 格 子 结 构 设 施 布 置 问 题 最 优 算 法l二 次 分 配 问 题 模 型 （ QAP, Quadratic Assignment problem ）l 如 果 新 设 施 之 间 没 有 相 关 性 ， 只 考 虑 与 现 存 设 施 的 位置 关 系 线 性 分 配 ；l 如 果 新 设 施 之 间 存 在 互 相 联 系 时 ， 称 为 二 次 分 派 问 题 。l 二 次 分 配 问 题 是 如 何 布 置 m个 设 备 给 n个 地 点 ， 使 得 布置 方 案 的 物 料 搬 运 费 最 小 。 l 目 标 函 数 ： 一 般 以 物 料 搬 运 费 用 最 低 。 单 行 机 床 布 局 问 题 数 学 模 型 举 例 ： 设 一 生 产 线 为 单 行 布 局 ， 共 有 n台 机 床 ，设 机 床 分 别 为 ti， i 1， 2， n。 ti布 局 位 置 坐标 为 xi ， 沿 布 局 方 向 上 的 长 度 尺 寸 为 li 。 在 一 个生 产 周 期 内 ， 工 件 在 机 床 ti与 tj之 间 的 往 返 搬 运次 数 为 fij ， 单 位 距 离 搬 运 费 用 为 Cij ， 且 机 床 ti和之 tj间 的 最 小 间 距 为 dij ， 如 图 所 示 。 x jli xi ljdij 单 行 机 床 布 局 问 题 数 学 模 型目 标 函 数 ： 一 般 以 物 料 搬 运 费 用最 低 。 |min 1 1 1 jini nij ijij xxfcZ 约 束 条 件 为 ： 机 床 互 不 干 涉 ， 即1） |xi xj| dij （ li lj） /22） xi 0 ， i 1， 2， n 多 行 机 床 布 局 问 题 数 学 模 型l 举 例 ： 设 一 生 产 线 为 多 行 布 局 ， 共 有 m台 机 床 ， 可以 布 置 区 域 有 n个 地 点 。 ),.,2,1,.,2,1.(01 ),.,2,1.(1 ),.,2,1.(1min11 1 11 1 njmix mix njx xxfcZijnj ijmi ij klijmk nl ikjlmi nj ；或第 i个 设 施 分 配到 第 j个 场 址 中 ，它 们 与 在 第 l场址 上 的 第 k个新 设 施 有 互 相联 系Cjl： 第 j场 址与 l场 址 之 间单 位 搬 运 费 用fik： 设 施 i与 k之 间 的 物 流 强度 设 施 布 置 问 题 次 优 算 法n穷 举 法n面 向 新 建 型 系 统 布 置 程 序v 图 论 法v CORELAP， 计 算 机 辅 助 相 关 布 置 规 划 （ 将 SLP运 用 到 计 算 机 上实 现 ， 得 到 一 个 使 各 设 施 间 接 近 度 最 大 的 布 置 方 案 ）v ALDEP， 自 动 化 布 置 设 计 （ 在 给 定 系 统 边 界 内 产 生 许 多 可 行 布 置方 案 ， 并 给 出 各 方 案 的 评 价 ）n面 向 改 进 型 系 统 布 置 程 序 v CRAFT， 计 算 机 辅 助 设 施 相 对 定 位 技 术 （ 在 原 有 布 置 方 案 上 求 得改 进 布 置 ， 得 到 一 个 以 降 低 系 统 物 流 搬 运 成 本 的 布 置 方 案 ）v COFAD， 计 算 机 辅 助 设 施 设 计 （ 是 对 CRAFT的 改 进 ， 考 虑 了 搬运 设 备 及 其 成 本 评 价 ， 得 到 更 全 面 的 设 计 方 案 ， 针 对 不 同 的 物 流系 统 ， COFAD有 COFAD II和 COFAD III等 ） 设 施 布 置 问 题 穷 举 法l次 优 算 法 穷 举 法l又 称 枚 举 法 ， 适 于 在 给 定 设 施 布 置地 点 组 的 场 合 。l步 骤 ： 列 出 所 有 布 置 方 案 ， 通 过 比较 布 置 方 案 目 标 函 数 值 的 大 小 ， 找出 其 中 的 一 个 或 几 个 最 优 布 置 方 案 。 穷 举 法 举 例l 举 例 ： 等 面 积 设 备 布 置 问 题 。 如 图 有 A、 B、 C、D四 个 地 点 ， 分 别 用 P1 , P2 , P3 , P4 ， 表 示 ， 在四 个 地 点 布 置 四 台 机 床 ， 分 别 用 t1 , t2 , t3 , t4表 示 。 假 设 四 台 机 床 的 占 地 面 积 相 等 ， 可 以 布置 在 任 一 地 点 上 。 A B CD A B CD加 工 工 艺 从 至 表 0123P4 1012P3 2101P2 3210P1 P4P3P2P1从 至地 点 对 之 间 的 物 料 搬 运 距 离07010100P 4 7003020P3 1030050P2 10020500P1 P4P3P2P1从 至地 点 对 之 间 的 物 料 搬 运 量 穷 举 法 的 计 算 过 程l列 出 所 有 24个 布 置 方 案 ：l例 如 ， 排 列 t1 , t2 , t3 , t4搬 运 成 本 为510 t1 t2 t3t41 1 1 4 3 2C C C 穷 举 法 的 计 算 过 程t 2 t1 t4t3l列 出 所 有 24个 布 置 方 案l例 如 ， 排 列 t1 , t2 , t3 , t4搬 运 成 本 为 510l通 过 比 较 布 置 方 案 目 标 函 数 值 的 大 小 ，找 出 其 中 最 优 布 置 方 案 。l搬 运 成 本 为 370。 t3 t4 t1t2 设 施 布 置 问 题 面 向 新 建 型 系 统布 置 程 序l根 据 某 种 规 则 ， 逐 一 对 所 有 设 施 的 位 置做 出 安 排 ， 最 终 得 出 较 好 的 布 置 方 案 的算 法 。v改 进 生 成 树 算 法v图 论 法vCORELAP程 序 Computerized Relationship Layout Planning 设 施 布 置 问 题 改 进 生 成 树 算 法 步 骤l 适 用 于 求 解 单 行 机 床 布 局 问 题l 1） 求 得 单 位 距 离 物 料 搬 运 费 用 矩 阵 F；l 2） 从 矩 阵 F中 查 找 fij 最 大 值 ， 即 计 算 fi * j *相 邻 布 置 ， 记为 ti ， tj l 3)继 续 计 算 最 大 值 fp* q * =maxfi *k ， fj*lv若 p* = i* ， 则 将 机 床 t q * 与 机 床 ti *相 邻 布 置 ， 记为 t q * ， ti ， tj ； 否 则 ， p* = j* ， 则 将 机 床 t q *与 机 床 tj *相 邻 布 置 ， 记 为 ti ， tj ， t q * v从 矩 阵 F中 消 去 p*行 p*列 ；l 4)重 复 上 述 步 骤 ， 直 至 所 有 机 床 布 置 完 毕 。 改 进 生 成 树 算 法 举 例l举 例 ： 已 知 某 一 生 产 线 由 6台 机 床 组 成 ，各 机 床 间 物 料 搬 运 量 fij及 单 位 搬 运 成 本Cij分 别 如 下 ：从 至 机 床 1 2 3 4 5 6机 床 1 0 40 80 21 62 902 40 0 72 12 24 283 80 72 0 14 41 94 21 12 14 0 21 12 5 62 24 41 21 0 316 90 28 9 12 31 0各 机床 间物 料搬 运量 fij 单 位 搬 运 成 本 Cij从 至 机 床 1 2 3 4 5 6机 床 1 0 4 4 6 4 52 4 0 2 5 2 33 4 2 0 5 3 34 6 5 5 0 5 85 4 2 3 5 0 46 5 3 3 8 4 0 改 进 生 成 树 算 法 求 解 过 程从 至 机 床 1 2 3 4 5 6机 床 1 0 160 320 126 248 4502 160 0 144 60 48 843 320 144 0 70 123 274 126 60 70 0 105 965 248 48 123 105 0 124 6 450 84 27 96 124 0首 先 由 搬 运 量 fij及 单 位 距 离 搬 运 成 本 Cij求 出单 位 距 离 物 料 搬 运 矩 阵 F， 如 下 表 ： 改 进 生 成 树 算 法 求 解 过 程步 骤 i * j* p* q * fi * j * /fp * q * 布 局 消 去 行/列1） 1 6 450 t 1 t62 ） 1 6 1 3 320 t3 t1 t6 13 ） 3 6 3 2 144 t2t3 t1 t6 34 ） 2 6 6 5 124 t2t3 t1 t6t5 65 ） 5 5 5 4 105 t2t3 t1 t6t5t4 5利 用 单 位 距 离 物 料 搬 运 矩 阵 F， 经 过 数 次 布置 ， 得 出 机 床 排 列 次 序 ， 如 下 图 ： fp* q * =maxfi *k ， fj*l 1 63 优 先 生 长至 3， 划去 第 一 个点 2划 去 第三 个 点 5划 去 第 六 个 点4生 成 树 示 意 图 图 论 法 （ 构 造 型 算 法 ） 图 论 法 （ 构 造 型 算 法 ）1、 邻 接 值 不 代 表 距 离 ， 也 不 代 表 除 邻 接 部 门 间 和 其 他 部 门 间 的 关 系 2、 不 考 虑 部 门 的 尺 寸 数 据 ， 邻 接 部 门 间 公 共 边 界 的 长 度 也 不 予 考 虑3、 弧 不 能 相 交 ， 图 的 这 种 属 性 称 为 “ 平 面 性 planarity”4、 相 关 图 所 赋 数 值 权 重 对 总 评 分 影 响 很 大 图 论 法 （ 例 子 ）n 第 一 步 ， 选 择 作 业 单 位 对 中 权 重 最 大 的 ， 它 们 与其 他 部 门 有 联 系 也 不 考 虑在 上 例 中 ， 容 易 判 断 作 业 单 位 对 3-4首 先 进 入 邻 接 图n 第 二 步 ， 选 择 第 三 个 要 进 入 的 部 门 ， 按 照 与 前 两个 部 门 权 重 的 总 和 来 选 取 图 论 法 （ 例 子 ）n 第 三 步 ， 选 择 第 四 个 进 入 的 部 门 ， 仍 然 按照 总 权 重 的 值 来 选 取 ， 将 选 取 的 部 门 作 为一 个 结 点 加 入 前 面 形 成 的 邻 接 图 的 面 图 论 法 （ 例 子 ）n 第 四 步 ， 选 择 部 门 5要 插 入 哪 一 个 面 中 ， 可供 选 择 的 有 1-2-3， 1-2-4， 1-3-4和 2-3-4n 将 部 门 5插 入 1-2-4和 2-3-4都 得 到 同 样 的 最大 权 重 9， 故 两 者 均 可 选 图 论 法 （ 例 子 ）n 第 五 步 ， 确 定 了 邻 接 图 后 ， 最 后 一 步 是 构 建 一 个 对 应 的 块状 布 置 图 ， 可 能 需 要 对 原 来 的 部 门 有 较 大 的 调 整 ， 以 满 足邻 接 图 的 要 求 （ 实 际 中 可 能 不 能 做 这 么 大 的 调 整 ， 如 形 状 ） 设 施 布 置 问 题 CORELAP程 序lCORELAP程 序 实 际 上 就 是 计 算 机 化 的 SLP。步 骤 ：l1） 基 本 要 素 分 析 ；l2） 相 互 关 系 分 析 ；l3) 计 算 综 合 接 近 程 度 TCRij ；l4) 作 业 单 位 排 序 ；l5) 位 置 布 置 ， 计 算 各 位 置 分 数 ， 将 作 业 单位 布 置 在 位 置 分 数 最 高 的 位 置 上 。 这 种 算 法 的 出 发 点 是 部 门 之 间 的 关 系 表 ， 布 置 的 目 标 是 实 现 部 门 之 间最 大 的 密 切 度 。 CORELAP计 算 综 合 接 近 程 度 TCRn 首 先 将 关 系 图 中 的 每 一 个 关 系 代 码 ， 按 照 下 表所 示 的 对 应 关 系 数 值 化 ， 再 对 每 个 部 门 所 有 关系 值 求 和 ， 即 得 到 关 系 总 和 TCR关 系 码 A E I O U X数 值 6 5 4 3 2 1n 生 成 了 布 置 矢 量 后 ， 开 始 向 布 置 图 中 放 置 。 放 置原 则 是 保 证 进 入 布 置 图 的 部 门 与 前 面 进 入 的 相 邻部 门 的 关 系 值 的 和 NCR (Neighbor Closeness Rating)最 大 。 CORELAP作 业 单 位 排 序n 选 择 TCR最 大 的 部 门 作 为 最 先 进 入 布 置 的 部 门 。n 若 最 大 的 TCR值 有 多 个 部 门 ， 即 出 现 “ 结 ” ， 则选 择 面 积 最 大 的 部 门 解 “ 结 ” ； 若 依 然 解 不 开 ，则 随 机 选 取 。n 第 二 个 部 门 选 择 与 第 一 个 部 门 具 有 最 高 级 别 关 系(A级 )的 部 门 ， 依 次 选 择 E级 、 I级 ， 如 果 在 同 一关 系 级 别 中 出 现 多 个 部 门 (“结 ” )， 选 择 这 些 部 门中 TCR最 大 的 部 门 先 布 置 (解 “ 结 ” )。 n 在 布 置 中 ， 部 门 的 形 状 尽 可 能 设 计 成 正 方 形 。 n 在 上 图 中 部 门 1有 3种 放 置 方 法 。放 置 在 位 置 1a， 则 与 3、 4相 邻 ， NCR1a=CR13+CR14、NCR1b=CR14、 NCR1c CR13，所 以 应 该 选 择 位 置 1a进 入 布 置 图 。n 对 布 置 图 的 评 估 方 法 为 ： 任 意 两 部 门 间 的 关 系 值 该 两 部 门 间 的 最 短 直 线 距 离 的 总 和 。 根 据 该 和值 可 以 比 较 不 同 方 案 的 优 劣 ， 得 分 越 小 越 优 。 CORELAP例 题 ：已 知 部 门 关 系 图 TCR表 根 据 各 部 门 与 其 他 部 门 关 系 总 和 及相 互 关 系 确 定 布 置 顺 序n 部 门 2的 总 和 最 高 ， 所 以 首 先 布 置 该 部 门 ；n 其 他 部 门 中 ， 部 门 1与 2具 有 A级 关 系 ， 所 以 随 后布 置 部 门 1；n 部 门 4、 部 门 5与 部 门 2同 属 I级 关 系 且 TCR值 相等 ， 但 部 门 4的 面 积 大 ， 所 以 先 4后 5；n 最 后 布 置 与 部 门 2具 有 O级 关 系 的 3部 门 。 这 样 ，布 置 顺 序 矢 量 为 2-1-4-5-3。 根 据 各 部 门 面 积 确 定 最 终 布 置CORELAP布 置 过 程 面 积 已 知 评 估 布 置 方 案 其 中 2个 单 元 间 的 距 离 为 到 达 公 共 边 最 少 需 要 的 直 线 距 离不 同 方 案 的 比 较 ， 总 得 分 越 小 的 方 案 越 优 。 BLOCPLAN（ 构 造 或 者 改 进 型 算 法 ）n 可 以 用 相 关 表 或 者 从 至 表 作 为 “ 流 动 ” 的 输 入 数据n 评 价 布 置 “ 成 本 ” 可 以 按 照 基 于 距 离 目 标 或 者 基于 相 邻 性 的 目 标n “ 带 数 ” 是 由 程 序 确 定 ， 只 能 为 2或 者 3， 而 “ 带宽 ” 可 变 （ 带 内 建 筑 的 面 积 和 除 以 建 筑 物 的 长 度 ）n 每 个 部 门 限 定 一 个 “ 带 ” 中 ， 部 门 形 状 为 矩 形n 采 用 连 续 式 布 置 方 式 BLOCPLAN（ 构 造 或 者 改 进 型 算 法 ）n 例 子 ： AA序号 部 门 名 称 面 积ft2 方 格数 物 流 量A B C D E F G H1 A收 货 12000 30 0 45 15 25 10 5 0 02 B铣 削 8000 20 0 0 0 30 25 15 0 03 C冲 压 6000 15 0 0 0 0 5 10 0 04 D攻 丝 12000 30 0 20 0 0 35 0 0 05 E装 配 8000 20 0 0 0 0 0 65 35 06 F盖 板 12000 30 0 5 0 0 25 0 65 07 G发 货 12000 30 0 0 0 0 0 0 0 08 H虚 部 门 2000 5 0 0 0 0 0 0 0 0虚 部 门 ： 填 补 建 筑 物 的 不 规 则 之 处 ； 设 施 内 的 障 碍 或 者 不 能 用 的 区 域 （ 如 楼 梯 ） ； 代 表 厂 房的 额 外 空 间 ； 在 最 终 布 置 中 用 于 帮 助 通 道 位 置 的 确 定 BLOCPLAN（ 构 造 或 者 改 进 型 算 法 ） 初 始 方 案 ， 3个 带 ， 带 宽 由 各 部 门 面 积 和 除 以 建 筑 物 长 度 确 定 。 基 于 距 离 的 目标 函 数 z=61061.70 带宽 BLOCPLAN（ 构 造 或 者 改 进 型 算 法 ） 最 终 方 案 ： 两 两 交 换 位 置 。 基 于 距 离 的 目 标 函 数 z=58133.34基 于 相 邻 性 的 目 标 函 数 z=235（ 将 上 图 所 有 相 邻 部 门 单 位 对 的 fij值 相 加 ） 带宽 BLOCPLAN（ 构 造 或 者 改 进 型 算 法 ）n 如 果 输 入 数 据 要 求 是 相 关 表将 作 业 单 位 对 的 fij和 fji相 加 ， 形 成 合 并 物 流 量 从至 表按 照 5级 （ 如 果 考 虑 X级 则 为 6级 ） 将 物 流 量 的绝 对 值 转 换 为 密 切 程 度 等 级 ， 得 到 相 关 表按 照 密 切 程 度 等 级 的 默 认 数 值 ， 即 A=10、 E=5、I=2、 O=1、 U=0、 X=-10， 计 算 布 置 方 案 的 相邻 值 BLOCPLAN（ 构 造 或 者 改 进 型 算 法 ）n 转 化 过 程 如 下 表 所 示 ， 由 于 最 大 物 流 量 为90， 将 此 值 除 以 5得 到 18n 则 73-90为 A， 55-72为 E， 37-54为 I， 19-36为 O， 0-18为 U 上 下 三 角 阵 的 数 值 相 加 绝 对 值 转 换 为 5级 密 切 程 度 等 级 设 施 布 置 问 题 面 向 改 进 型 系统 布 置 程 序 CRAFTlCRAFT， 计 算 机 辅 助 设 施 相 对 定 位 技 术 （ 在原 有 布 置 方 案 上 求 得 改 进 布 置 ， 得 到 一 个 以降 低 系 统 物 流 搬 运 成 本 的 布 置 方 案 ） 。 步 骤 ：l1） 给 定 物 料 搬 运 结 果 矩 阵 ， 给 定 初 始 布 置 方 案 ，计 算 物 料 搬 运 费 用 ；l2） 位 置 交 换 、 费 用 比 较 、 选 择 优 化 方 案 ；l3)重 复 上 述 步 骤 ， 直 至 物 料 搬 运 费 用 不 再 减 小 。 这 种 交 换 通 常 是 以 两 两 交 换 的 方 式 进 行 ， 选 择 具 有 公 共 边 或 相 等 面 积 的 部 门进 行 交 换 ， 其 他 无 公 共 边 或 面 积 不 相 等 的 部 门 不 能 交 换Computerized Relative Allocation of Facilities Techinque CRAFT举 例 1l举 例 ： 等 面 积 设 备 布 置 问 题 。 如 图 有 A、B、 C、 D四 个 地 点 ， 分 别 用 P1 , P2 , P3 , P4 ， 表 示 ， 在 四 个 地 点 布 置 四 台 机 床 ，分 别 用 t1 , t2 , t3 , t4表 示 。 假 设 四 台 机 床的 占 地 面 积 相 等 ， 可 以 布 置 在 任 一 地 点上 。 A B CD A B CD加 工 工 艺 从 至 表 0123P4 1012P3 2101P2 3210P1 P4P3P2P1从 至地 点 对 之 间 的 物 料 搬 运 距 离07010100P 4 7003020P3 1030050P2 10020500P1 P4P3P2P1从 至地 点 对 之 间 的 物 料 搬 运 量 距 离 的 计 算 采 用 部 门 中 心 间的 折 线 距 离 CRAFT计 算 过 程 1l成 对 地 交 换 设 备 的 布 置 地 点 ， 来 改 善初 始 布 置 方 案 。迭 代次 数 i j 布 置 方 案 搬 运费 用 优 选 方案1 1 2 t2 t1 t3 t4 4303 t3 t2 t1 t4 4504 t4 t2 t3 t1 6002 3 t1 t3 t2 t4 6004 t 1 t4 t3 t2 4103 4 t1 t2 t4 t3 450 1分 别 与 2、3、 4交 换位 置 CRAFT计 算 过 程 2迭 代次 数 i j 布 置 方 案 搬 运费 用 优 选方 案2 1=(t1) 2=(t4) t4 t1 t3 t2 4203 =(t3) t3 t4 t1 t2 3704=(t2) t2 t4 t3 t1 5102 3 t1 t3 t4 t2 5104 t1 t2 t3 t4 5103 4 t 1 t4 t2 t3 440 在 上 一 次 的 优 化 结 果 上 ， 继 续 重 复 整 个 过 程 t1-t4-t3-t2 CRAFT计 算 过 程 3迭 代次 数 i j 布 置 方 案 搬 运费 用 优 选 方案3 1 2 t4t3 t2 t1 4303 t4t3t1t2 4104 t2 t4 t1 t3 4602 3 t3 t1 t4 t2 4604 t3 t2 t1 t4 4503 4 t 3 t4 t2t1 450 CRAFT举 例 2 FromTo 1 2 3 4 5 1 90 15 0 0 2 0 0 50 65 3 0 15 0 0 4 0 0 0 50 5 0 0 0 0 From To 1 2 3 4 5 1 1.5 1.5 3 3 2 1.5 2 1.5 1.5 3 1.5 2 2.5 1.5 4 3 1.5 2.5 2 5 3 1.5 1.5 2从 至 表 距 离 表部 门 中 心 间 的 折 线 距 离 1-2的 距 离 示 例 From To 1 2 3 4 5 合 计 1 135 22.5 0 0 157.5 2 0 0 75 97.5 172.5 3 0 30 0 0 30 4 0 0 0 100 100 5 0 0 0 0 0搬 运 费 用 表 =从 至 表 相 应 元 素 距 离 表 相 应 元 素总 费 用 =460 交 换n 首 先 选 择 可 以 进 行 交 换 的 部 门 分 别 是 12， 13，15， 23， 24， 25， 35， 45。 交 换12， 则 布 置 图 、 距 离 表 、 搬 运 费 用 表 变 为 FromTo 1 2 3 4 5 1 1.5 1.5 1 1 2 2 2.5 2.5 3 2 2.5 1.5 4 2 5 1-2互 换 的 布 置 图 From To 1 2 3 4 5 合 计 1 135 22.5 0 0 157.5 2 0 0 75 162.5 237.5 3 0 30 0 0 30 4 0 0 0 50 50 5 0 0 0 0 0 n 总 的 搬 运 费 用 变 为 475； 费 用 增 加 15， 故 取 消 该布 置 ， 继 续 下 一 个 交 换 ， 13交 换 ， 直 至 找 到 最小 搬 运 费 用 的 一 种 布 置 ， 结 束 本 轮 交 换 。n 第 一 轮 交 换 结 束 后 ， 确 定 出 首 轮 布 置 图 。 针 对 这一 布 置 图 、 再 次 进 行 具 有 公 共 边 及 面 积 相 等 的 部门 的 交 换 ， 直 至 搬 运 费 用 不 再 降 低 为 止 。n CRAFT是 应 用 较 为 广 泛 的 一 种 设 施 规 划 方 法 ， 因此 ， 得 到 了 不 断 地 完 善 、 改 进 。 CRAFT： 例 子 AA 假 设 的 初 始 方 案 如 同 所 示 ， 每 个 部 门 的 中 心 位 置 也 标 注 在 图 中 ， 例 如 部门 A和 B的 中 心 间 折 线 距 离 为 6格 ， 而 物 流 量 为 45 ， 则 成 本 为 45 6总 成 本 为 2974单 位 （ 假 设 A和 G的 位 置 固 定 进 行 迭 代 ）虚 部 门 CRAFT： 例 子 AAn 交 换 部 门 E和 F： CRAFT先 将 大 的 部 门 F最 左 列 开始 ， 将 前 面 20个 方 格 标 为 E， 并 将 原 来 的 E的 部 门标 为 F 总 成 本 为 2953单 位 CRAFT： 例 子 AAn 下 一 次 迭 代 ， B和 C的 交 换 ， 最 终 方 案 总 成 本 为 2833.50单 位设 计 人 员 必 须 打 磨 布 置 ， 一 般 不 采 用 网 格 ， 而 采 用 连 续 式 表 现 方 式 ， 这 样 可 以 平 滑 部门 边 界 并 修 改 部 门 的 面 积 和 取 向 。 打 磨 后 一 般 不 需 要 计 算 机 算 法 评 价 CRAFT： 例 子 AAn 最 终 打 磨 的 布 置 方 案 其 他 的 构 建 型 计 算 机 化 布 置 方 法 ALDEP (Automated Layout Design Procedure)n 其 布 置 基 础 是 关 系 图 ;n 第 一 个 布 置 部 门 的 选 择 方 法 是 随 机 选 取 的 ;n 随 后 选 择 方 法 是 根 据 与 第 一 个 部 门 的 关 系 进 行 排 队 ， 直 到排 到 设 定 的 最 低 关 系 密 切 度 TCR (Threshold Closeness Rating)； TCR是 指 一 个 预 先 设 定 的 关 系 代 码 ， 对 于 相 同 的 关 系 ， 则 随 机 选择 进 入 。 n 放 置 方 法 是 将 选 定 布 置 顺 序 的 各 部 门 ， 按 照 其 单 位 面 积 数 ，以 设 定 的 宽 度 ， 从 布 置 图 的 左 上 角 向 下 ， 蛇 行 婉 蜒 ， 直 至布 置 完 所 有 的 部 门 ALDEP的 评 估n 由 于 初 始 布 置 部 门 是 随 机 选 择 的 ， 评 估 非 常 重 要 。n 评 估 是 寻 求 相 邻 部 门 的 关 系 总 和 最 大 的 布 置 为 最 后 布 置方 案 。n 首 先 需 要 将 关 系 代 码 按 照 下 表 所 示 的 对 应 关 系 数 值 化 、然 后 计 算 所 有 相 邻 部 门 的 关 系 值 ， 并 求 和 。 关 系 码 A E I O U X 数 值 64 16 4 1 0 -1024 例 题 ： ALDEP的 应 用n 设 TCR I， “ 扫 描 ” 宽 度 为 1。n 随 机 选 取 第 一 个 部 门 ， 比 如 说 部 门 3。 寻求 与 部 门 3具 有 A关 系 的 ， 没 有 ； E关 系 的 ，没 有 ； I关 系 的 ， 没 有 ； 结 束 寻 找 。n 再 随 机 选 择 第 二 个 部 门 ， 比 如 说 选 到 4，则 寻 求 与 部 门 4具 有 A关 系 的 ， 没 有 ； E关系 的 ， 没 有 ； I关 系 的 ， 有 部 门 2、 部 门 5，随 机 选 取 ； n 若 选 到 2， 则 在 未 分 配 部 门 中 ， 寻 求 与 己布 置 部 门 具 有 A关 系 的 部 门 ， 这 里 选 到 部门 1。n 最 后 获 得 布 置 顺 序 矢 量 为 34215。 生 成 34215布 置 图 的 过 程 如 图 所 示 对 该 布 置 图 按 照 相 邻 部 门 原 则 进 行 评 估 ， 如表 所 示 。 多 次 循 环 进 行 （ 随 机 选 择 起 始 点 ，再 次 进 行 整 个 过 程 ） ， 选 择 总 分 值 最 大 的 一个 方 案 。 相 邻 部 门 关 系 分 值 相 邻 部 门 关 系 分 值 1-2 A 64 4-1 U 0 1-4 U 0 4-2 I 4 1-5 U 0 4-3 U 0 2-1 A 64 4-5 I 4 2-3 O 1 5-1 U 0 2-4 I 4 5-4 I 4 3-2 O 1 总 计 146 3-4 U 0 其 他 的 改 善 型 计 算 机 化 布 置 方 法 MultiPLE (Muti-floor Plant Layout Evaluation)n 是 类 似 于 Craft的 一 种 改 善 型 软 件 ， 输 入 数 据 为 从至 表 ， 目 标 函 数 为 基 于 距 离 的 目 标 函 数 ， 距 离 计算 采 用 中 心 点 直 线 距 离 ；n 部 门 间 的 交 换 采 用 2部 门 交 换 。 在 每 次 迭 代 中 选择 布 置 成 本 下 降 最 大 的 方 案 ；n 与 Craft的 区 别 在 于 MultiPLE的 交 换 可 以 不 局 限于 两 相 邻 部 门 间 。 这 一 点 的 实 现 主 要 是 通 过 空 间填 充 曲 线 SFC (Space Filling Curve)来 实 现 的 。 SFC是 指 填 充 一 定 空 间 的 一 条 折 线 n 对 于 图 中 的 64个 单 元 ，该 曲 线 对 每 个 单 元 只访 问 一 次 ， 恰 能 游 历整 个 64个 单 元 。 这 样在 布 置 顺 序 矢 量 一 定后 ， 各 部 门 就 根 据 自己 的 面 积 ， 沿 着 SFC进 行 放 置 ， 直 至 整 个布 置 n 例 ： 6个 部 门 的 面 积分 别 为 16、 8、 4、16、 8、 12个 单 位 面积 ， 布 置 矢 量 (布 置顺 序 )为 1 23456。 则 根 据SFC的 布 置 如 图 所 示 。对 于 一 个 问 题 ， 任 意 生 成 一 个 初 始 布 置 顺 序 矢 量 ， 并 根 据 SFC生 成 初 始 布 置 ； 任 意 部 门 的 交 换 ， 生 成 新 的 布 置 矢 量 ， 根 据 SFC生 成 布 置 ， 并 计 算 各 部 门 中 心间 的 直 线 距 离 ；循 环 往 复 ， 寻 找 到 最 低 物 流 费 用 的 布 置 方 案 。 MIP（ Mixed Integer Programming）n 一 般 情 况 下 ， 基 于 数 学 规 划 的 模 型 是 一 种 构 造 型模 型 ， 也 可 以 用 于 改 进 布 置n 采 用 连 续 式 的 表 现 方 式 ， 而 且 所 有 部 门 均 为 矩 形n 对 于 矩 形 的 部 门 ， 需 要 中 心 和 部 门 的 长 宽 ， 即 可确 定 其 位 置 和 形 状 （ 中 心 的 坐 标 ， 左 上 角 和 右 下角 的 坐 标 ）n 采 用 基 于 距 离 的 目 标 函 数n 可 以 看 做 是 “ 二 维 背 包 问 题 ” MIPn 首 先 需 要 的 参 数 ：n 决 策 变 量x yli iu l i iuiB x B yA i L iL i W iW i M： 厂 房 长 度 （ 方 向 ） ： 厂 房 宽 度 （ 方 向 ）： 部 门 的 面 积 ： 部 门 的 长 度 的 下 限： 部 门 的 长 度 的 上 限 ： 部 门 的 宽 度 的 下 限： 部 门 的 宽 度 的 上 限 ： 很 大 的 正 数1 01 0i ii i i ix xij ijy yij iji x i yx i x x i xy i y y i yz i j zz i j z ： 部 门 中 心 的 坐 标 ： 部 门 中 心 的 坐 标： 部 门 左 边 （ 西 边 ） 的 坐 标 ： 部 门 右 边 （ 东 边 ） 的 坐 标： 部 门 底 边 （ 南 边 ） 的 坐 标 ： 部 门 上 边 （ 北 边 ） 的 坐 标， 部 门 严 格 限 定 在 部 门 的 东 边 ； 否 则， 部 门 严 格 限 定 在 部 门 的 北 边 ； 否 则j i j ix x i jy y i jx y 当 且 仅 当 时 ， 部 门 严 格 限 定 在 部 门 的 东 边 ；或 者 ， 当 且 仅 当 时 ， 部 门 严 格 限 定 在 部 门 的 北 边 。两 个 部 门 只 有 在 轴 方 向 分 开 ， 或 者 沿 轴 分 开 才 能 保 证 两 个 部 门 不 交 叠 MIP min. . 0 , 00.5 0.5 , 0.5 0.5 , (1ij ij i j i ji jl ui i i il ui i i ii i i i ii i x i i yi i i i i ij iz f cst L x x L for all iW y y W for all ix x y y A for all ix x B y y B for all ix x y y for all i and j i jx x M z ) ,(1 ) ,1 , 0 , , , 0, 1 0 ,xijyj i ijx x y xij ji ij jii i i i i ix yij ij for all i and j i jy y M z for all i and j i jz z z z for all i and j i jx x y y for all iz z or for all i and j i j 基 于 距 离 的 目 标 函 数 （ 非 线 性 ）每 个 部 门 的 长 度 和 宽度 不 超 过 制 定 边 界每 个 部 门 所 需 的 面 积保 证 每 个 部 门 各 边 的 正 确 定 义 ， 位 于 厂 房 总 坐 标 内每 个 部 门 的 中 心 的 坐 标1xij j iz x x 时 ， 保 证与 上 一 个 约 束 目 的 相 同 ， 但 是 在 y方 向在 x方 向 或 y方 向 保 证 两 个 部 门 不 交 叠非 负 条 件0、 1变 量 LOGICn 给 定 从 至 表 作 为 物 流 量 的 输 入 数 据n 成 本 由 基 于 距 离 的 目 标 函 数 来 衡 量n 厂 房 为 矩 形 时 ， 由 LOGIC得 到 的 部 门 也 为 矩 形 ， 布 置 为 连 续 表现 方 式n 首 先 是 一 种 构 造 型 算 法 ， 也 可 以 作 为 改 进 型 算 法n 执 行 一 系 列 的 横 割 或 竖 割 ， 每 次 的 切 割 都 有 适 当 的 部 门 被 分 配到 割 线 的 东 西 或 者 南 北n 采 用 树 形 割 集 ， 并 假 设 每 次 切 割 和 部 门 分 配 都 是 随 机 的 n 需 要 计 算 割 线 的 精 确 坐 标n 可 以 替 代 BLOCPLAN， 因 为 所 有 的 BLOCPLAN布 局 方 案 都 是LOGIC布 局 方 案n 方 案 的 改 进 采 用 两 两 交 换 ， 或 者 模 拟 退 火 算 法 LOGIC： 例 子 AA形 成 方 案 假 设 第 一 次 为 竖 割 ， 部 门 分 配 如 图 所 示 ， 因 为 D、 F和 G的 面 积 已 知 ，因 此 可 以 精 确 计 算 分 割 线 的 x坐 标 LOGIC： 例 子 AA 形 成 方 案接 下 来 ， 将 上 述 每 一 部 分 厂 房 再 看 成 一 个 完 整 的 厂 房 ， 重 复 切 割 过 程 ， 直 到 每 一 块 厂 房 只 有 一 个 部 门 ， 并 计 算 割 线 的 坐 标（ 上 图 中 是 y坐 标 ） LOGIC： 例 子 AA 形 成 方 案 LOGIC： 例 子 AA 形 成 方 案 LOGIC： 例 子 AA 形 成 方 案 切 割 树 ： u表 示 竖 割 ； h表 示 横 割 LOGIC： 例 子 AA改 进 交 换 D和 E的 位 置 ， 保 持 切 割 树 不 变 ， 重 新 计 算 相 关 割 的 x或 者 y坐 标 LOGIC： 例 子 AA LOGIC可 以 用 于 非 矩 形 厂 房 ， 但 是 需 要 采 用 搜 索 算 法 ， 精确 计 算 割 线 的 位 置 下 次 课 内 容 1.物 料 搬 运 系 统