使带权总完工时间为最小的自由作业排序问题
- 格式：pdf
- 大小：261.69 KB
- 文档页数：9
Ｏｐ ＝ ， ｕｒ ｃ，０ １ ｔｅ 巧 １ 。ｔｅ ｊ ２ ＝ ， ｒ Ｉ ｔｅ ∑ Ｉ Ｉ ｐ ｅ ∑ ， ｌ
ｊ ｌ ＝ ｊ ＝ｌ
Ｏ ｊ １ ｍＰ ＝ ， １ ｉ
０ｐ ＝ １ Ｉ Ｉ ∑
ｊ ＝１
可以看 出，这些结论大都是在单位加工时 间的假设条件下得 到的。本文将 在一般 情形下研究 问
基金项目：国家 自然科学基金重大国际 （ 地区） 合作研究 （０３ １０１） ７７ １６ ０５；江苏省教育厅 （ ６３ ） 江苏省 “ ｙ ０７ ｗ０ 青
篮 ”工 程 ．
第４ 期
陈荣军，唐国春 ：使带权总完工时间为最小的 自由作业排序 问题
６１ ３
均极小 ＮＰ困难 ；而下面几个 问题为极大 多项式 时间可解 ，即这些 问题本身是多项式时间可解 的，但略微一般 的情况都不是多项式时间可解 的【６。 ４】 —
ｊ ＝１
其 中 ， Ｍｉ 别 表 示 工 件 歹 Ｃ 分 和 的 完 工 时 间 ，ｗ ， ｊ ＷＭｉ 工 件 和 机 器 的 权 ，Ｊ 示 工 为 表
件，ｉ 表示机器。 与 自由作业相关 的大部分 问题 是 Ｎ Ｐ困难 的，只有少数情形是 多项式时 间可解 的 。当机器 数为两 台时 ，Ａｃｕ ｂ ｅ Ｃ ｉ［ 证 明 ｈ ｇ ｕ ｈｎ ］ 。
总完 工 时 间 为最 小 的 两类 问题 ，本 文 用 组 合方 法 或 者 数 学规 划 方 法 分 别给 出 了稠 密 时 间表 的算 法 或 者 置 换排 序 的算 法 ， 并分 析 算 法 的 性 能 比 。此 方法 在 理 论 和应 用 两 方 面 都 是 有 意义 的 。
关键词：排序 ； 自由作业 ；带权总完工时间；性能 比
题ｏ ｌ ｎ ｊ 的多项式时间近似算法。另外，在 日 ａ 一 ｒ Ｉ Ｗ 常生活中，人们也常常希望机器尽早 ∑
完成加工 ，以减 少机器租金等 ，这样产 生了研 究使机器 带权 总完工 时间为最小 的 自由作业 问 题，即０ｍＩ ｉ Ｍｉ ，对这类 问题 ， 目前文献少有研究 。 一 Ｉ ｍ Ｗ ＣＭｔ 对 自由作业 问题 的任一 可行 时间表 Ｓ ，如果机 器 在 时间区 间Ｑ ＝ ｆ Ｃ） Ｂ， 内空 闲 （ 即机 器 尬 在这 个时间区间 Ｑ ＝ 『 Ｃ） Ｂ， 上不加工任何工件 ，这个时间区间可 以称 为机器 的空闲 区间） ，在 时刻 之后 在机器 上加 工 的所有 工件在 Ｑ中的任何 时刻 ｔ 在其它 的机器上 加 都 工，那么 这个空 闲区间称 为是合理 的 。这表 示在机 器 的空 闲区间 以后 加工 的工 件不可 能 直接提 前到在这个 空闲区 间上加 工，而不 改变 其它机器在 该时间区 间的加 工情况 。如果 Ｓ中 的一切 空 闲 区 间都是 合 理 的 ，则称 Ｓ是 一个 稠 密 时 间表 。稠 密 时间表 的概念 最 早 由Ａ ｎ ｎａ Ｒ ｃｍａ ｙ７在 １８ 年提 出，关于它的性质研究可 以参考 文献 『， 。 ａｚ ｎ ［ Ｊ ９２ ８９ １
上加工一次。在任何时刻，一台机器至多加工一个工件 ，一个工件至多被一 台机器加工 ，不限 制工件被机 器加工 的次序 ，亦不限制机器加 工工件 的次序 。我们 要寻找满足 这些条件 的时间
表（ 称为可行时间表） ，使得工件或机器带权总完工时间最小，用三参数法记为
∑ｗ ｊ ｏ ｌ ｊ ｍｌ ｃ
是极小 ＮＰ困难 的 ，即问题本 身是 ＮＰ困难 的 ，但 略微特 殊一 点的情 况都是 多项 式时 间可解 的；Ｔｍｋｖｋ ［ 在 １９ 年证明 ｉ ｏｓｙ。 】 ９８
０ ｉ １ ２ｊ ， Ｉ ＝ Ｐ
∑ ，０ ｊ １ ３ｉ ， Ｉ ＝ ｐ
ｊ １ ＝
∑
ｊ ＝ｌ
收稿 日期： ０ ８０ － １ 作者简介 ：陈荣军 （９ １ 月生） ２ ０ —４２ ． １ ７ 年３ ，男，博士，副教授． 研究方 向：排序理论及应用．
第２卷 第 期 ７ ４
２ １ 年Ｏ 月 ０Ｏ ８
工
程
数
学
学
报
Ｖ １２ ｏ ４ ｏ ７ ． ． Ｎ
Ａｕ ．２ １ ｇ ００
ＣＨＩ ＮＥＳ Ｊ Ｅ ＯＵＲＮＡＬ ＯＦ ＥＮＧＩ ＮＥＥＲＩ ＮＧ ＭＡＴＨＥＭＡＴＩ ＣＳ
文 章编￣： ０—０５２１）４ ６２ ９ １ ５ ８（ ００— １— ０ ３ ０ ０ ０
分类号： ＡＭ Ｓ２０ ） ０ ３ ；０ ２ （００ ９Ｂ ５ ９Ｃ ７
中图分类号 ： ２４ ０ ２
文献标识码： Ａ
１ 引言
ｍ叫 ∑
Ｍ
Ｍ） 在 自由作 业【 问题 中，有 ｍ 台机器 Ｍ１Ｍ２… ， ，要加 工 几个工件｛，， ， ，在机 ］ ， ， ‰ １２… 札
器 上工件 Ｊ 的操作 （ 工序） 及其加工 时间分别 记为 Ｏ ｊ￣Ｐ 。所有 的工件 都要在 每一台机器 ｉ－ ｉ ｊ
本文余下部分是这样 安排 的：第 ２ 节用组合方法研究 问题
∑ ｗｉ ＭＣ ， Ｍ
ｉ １ ＝
∑
Ｊ １ ＝
的稠密时 间表 性能比，得到定理 １ 和定理 ２ 第 ３ ； 节用数 学规 划方法研究这两类 问题 ，同时假
设工件 带有 到达 时间，提 出置换排序 算法 ，并分 析算法 的性 能 比，即定理 ３ 定理 ４ 和 ；最 后
使 带权总完工 时间为最小 的 自由作 业排序 问题木
陈荣军 唐国春０ ，
（ 常 州 工 学 院数 学 系 ， 常 州 ２ ３ ０ ； ２ 海第 二工 业 大 学 管理 工 程 研 究 所 ，上 海 ２ １０ １ １ １ ０ ２ ．上 ０ ２ ９
摘
ห้องสมุดไป่ตู้
要： 本文研究多工序排序中的一类 自由作业模式。对于使机器带权总完工时间为最小或者使工件带权
第 ４ 总 结全 文 。 节
２ （ ｝ ＭＣ ｉ 《 Ｉ ＝ Ｗ ｉＭ 和 ＝ ） ∑ ｍｌ ＂ ） ∑ ｍｌ
