Job-Shop调度问题的Chance-Makespan方法.pdf

Job．Shop调度问题的Chance．Makespan方法 口 张一平 口 陈 进 江南大学机械工程学院 江苏无锡 214122 摘 要：提 出的算法考虑 了固定的完工时间及可能发生的完工时间，且其评价函数是用来推论 出更多的平行加：r-TL 更少的中断，并证明了为缩短完工时间而调整加工顺序的一个有效的步骤。Chance—Makespan算法建立了一个可行域的 加工路线顺序，评估了在这个域内加工可能的剩余加工时间的任务，并提出具有调整性的迭代计算规则的方法。 关键词：Job-Shop调度 问题 运算规则 算法研究 中图分类号：F273；0224 文献标识码：A 文章编号：1000—4998(2oo9)o6—0060—03 Job—Shop调 度 问题 是 著 名 的组合 优 化 问题 ，是 调 启发式算法 的调度方法是切 实可行且有潜力 的。因此 度 问题 中的典 型难 题 ，常被 用来 验 证智 能算法 的有效 本文致 力 于 JmIICmax的 Job—Shop，开发 一个 简单 的算 性 。既有重 要 的科 研价 值 ，又有 重大 的实 际212程 意义 。 法 ，名 为 Chance—Makespan算 法 ，其 中有 简 单 的评 价 函 Job—Shop调度 问题是讨论无 中间策 略 的约束和 n任务 数 、迭代程序 和接近最优 目标等 ，该算 法继承 了分析 在 m机 器 上 加 工 的情 况 ，该 调 度 问题 的 目标 是 如何 和启发式方法 的一些优 点 ，甚至有 时可实现手工计算 。 选择 加工顺 序 以使 总 的制造 周期 (Makespan)最短 。 1 Chance—Makespan算法 根据调度 的建模方法分类 ，主要 的调度建模方法 可被 归类为分析 、启发式和人工智能 (AI)等方法 。分析 1．1 问题描述及算法步骤 法 是 以技术 为 基础 的 ，如 线性 规 划 、队列理 论 、分 支定 Job—Shop调 度 问题 可 描述 为 ：在 m 台机器 上安排 界算法 及 动态 规划 等 ，这 种方 法 可得 出精确 解 。然 而 ， n 个任务进 行加工 。由于任务加工工艺 的要求 ，给定每 很 明显 ，该 方法 是不 能有效解决 复杂调 度 问题 的。原 因 个 任务 的加 工路 线 以及 每道 工序 所花 费 的时 间 ，而且 ： 是 由于调度 问题 的性质 ，即除 了一些特殊情况，其调度 1)每个机器在 同一 时刻 只能加工一个任务 ；2)不 同任 算法应是非 多项式 (N—P)的。此外 ，分析 的方法应用 务 的工序之 间没有顺序 约束 ；3)操作一旦开始就不能 到动态 的 Job—Shop是不切 合 实际 。启 发 式方 法 分 析 了 中途停 止 。调度 的 目的是 安排 每 台机 器 上 的工件加 工 计算程序 ，并可得到更好 的解 。如果有相关 的 比较大 的 顺序，并满足约束条件 ，使得制造 系统某种性 能指标得 问题且 Job—Shop的环境是动态 的，启发式算法可 以在 到最大 限度优化 。因此基本建模及算法步骤如下 ： 有效 时 间 内产 生接 近最优 甚 至最优 的解 ，其 中包括 各 i：机器编 号 ，i=1，2，… ，m。 种分 派规 则 、优 先规 则 、调 度规 则 、甚 至 先进 的最优 化 ：任务 编号 ，J=1，2，… ，n。 技术 ，如一些邻近搜 索和禁忌有哪些信誉好的足球投注网站方法 。人工智能方法 P ：J任务在 i机器上 的加工时 间，P=[P]… 。 可分 为4种 ：专 家 系统 、人 212神 经 网络 、其 他人32智能方 ：根据加工路线 任务在 i机器上加工 的顺序 ， 法和混合 方法 。 R= [ 】… 。 目前在 有 关 JobShop调度 问题 的文 献 中 ，现 有 的 e：在加工路线上顺序为 g