第３ ０卷 第 ８期 ２ １ ３年 ８月
计 算 机 应 用 研 究
Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ ｏ ｆ Ｃｏ ｍｐ ｕ ｔ ｅ ｒ ｓ
Ｖｏ Ｉ ． ３ ０ Ｎｏ ． ８
Ａｕ ｇ ． ２ ０ １ ３
一
种 求解 典 型 Ｊ Ｓ Ｐ的 改进 离 散粒 子 群优 化 算 法
ｔ ｙ ｐ ｉ ｃ ａ ｌ Ｊ ｏ ｂ － Ｓ ｈ ｏ ｐ ｓ ｃ ｈ ｅ ｄ ｕ ｌ ｉ ｎ ｇ ｐ ｒ ｏ ｂ ｌ ｅ ｍ
ＷＵ Ｚ ｈ ｅ ｎ ｇ — ｊ ｉ ａ ，Ｌ Ｕ Ｏ Ｙ ｕ ｅ — ｓ ｈ ｅ ｎ ｇ ， Ｚ ＨＯ Ｕ Ｙ ｕ — ｑ ｉ ｏ ｎ ｇ ， ＨＵ Ａ Ｎ Ｇ Ｓ ｈ ａ ｏ — ｘ ｉ ｏ ｎ ｇ
（ Ｃ ｏ ｌ ｌ ｅ ｇ ｅ ｏ ｆ Ｍｅ ｃ ｈ ａ ｎ ｉ ｃ ａ ｌ ＆ Ｍａ ｔ ｅ ｒ ｉ ａ ｌ Ｅ ｎ ｇ ｉ ｎ ｅ ｅ ｒ ｉ ｎ ｇ ，Ｃ ｈ ｉ ｎ ａ Ｔ ｈ ｒ ｅ ｅ Ｇ ｏ ｒ ｇ ｅ ｓ Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ，Ｙ ｃ ｉ ｈ ａ ｎ ｇ Ｈｕ ｂ ｅ ｉ ４ ４ ３ ０ ０ ２ ，Ｃ ｈ ｉ ｎ ａ ）
ａ ｌ ｇ ｏ ｉ ｒ ｔ ｈ ｍ ｗ ｅ ｌ １ ．Ｔ ｏ ｓ ｏ ｌ ｖ ｅ ｔ ｙ ｐ ｉ ｃ ａ ｌ Ｊ Ｓ Ｐ ｔ ｈ ｒ ｏ ｕ ｇ ｈ ｕ ｓ ｉ ｎ ｇ ｔ ｈ ｅ ｉ ｍｐ ｒ ｏ ｖ ｅ ｄ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ａ ｎ ｄ ｓ ｔ ａ ｎ ｄ ａ ｒ ｄ ｐ ａ ｔｉ ｒ ｃ ｌ ｅ ｓ ｗａ ｒ ｍ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ，
ｄ ｏ ｉ ： １ ０ ． ３ ９ ６ ９ ／ ｊ ． ｉ ｓ ｓ ｎ ． １ ０ ０ ｌ 一 ３ ６ ９ ５ ． ２ ０ １ ３ ． ０ ８ ． ０ ４ １
Ｉ ｍｐ ｒ ｏ ｖ ｅ ｄ ｄ ｉ ｓ ｃ ｒ ｅ ｔ ｅ ｐ ａ ｒ ｔ ｉ ｃ ｌ ｅ ｓ ｗａ ｒ ｍ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｆ ｏ ｒ
行局 部搜 索， 很好 地 防止 了算法 出现早 熟收 敛 。通 过将 该算 法和标 准粒 子群优 化算 法 用于求解 典型 Ｊ Ｓ Ｐ ， 计算 结 果 对比表 明 ， 改进 的算 法具有 很 强的全 局寻优 能 力 ； 就综合 解 的质 量和 计 算效率 而言 ， 改进 算 法优 于标 准粒 子群
吴 正佳 ， 罗月胜 ， 周玉琼 ， 黄绍雄
（ 三峡 大 学 机械 与材料 学院 ， 湖北 宜 昌 ４ ４ ３ ０ ０ ２ ）
摘
要 ：针 对 Ｎ Ｐ ・ ｈ ａ ｒ ｄ性 质 的作业 车 间调 度 问题 ， 设计 了一 种改进 的 离散 粒 子群优 化 算 法 。引入 遗传 算 法 交叉
算子和变异算子来实现粒子的更新 ， 并将变异思想和模拟退火算法思想融入该算法中对全局最优粒子的邻域进
Ａｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ａｃ ｃ ｏ ｒ ｄ ｉ ｎ ｇ ｔ ｏ ｔ ｈ ｅ Ｊ ｏ ｂ ・ Ｓ ｈ ｏ ｐ ｓ ｃ ｈ ｅ ｄ ｕ ｌ ｉ ｎ ｇ ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｗ ｈ ｉ ｃ ｈ ｃ ｏ ｎ ｔ ａ ｉ ｎ ｅ ｄ Ｎ Ｐ — ｈ ａ ｒ ｄ ｆ ｅ ａ ｔ ｕ ｒ ｅ， ｔ ｈ ｉ ｓ ｐ ａ ｐ ｅ ｒ ｄ ｅ ｓ ｉ ｇ ｎ ｅ ｄ ａ ｋ ｉ ｎ ｄ ｏ ｆ ｉ ｍ—
ｐ ｒ ｏ ｖ ｅ ｄ ｄ ｉ ｓ ｃ ｒ ｅ ｔ ｅ ｐ ａ ｒ ｔ ｉ ｃ ｌ ｅ ｓ ｗ ａ ｒ ｍ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ａ ｌ ｇ ｏ ｉｔ ｒ ｈ ｍ．Ｉ ｔ ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｅ ｄ ｔ ｈ ｅ ｃ ｒ ｏ ｓ ｓ ｏ ｖ ｅ ｒ ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ａ ｎ ｄ ｔ ｈ ｅ ｍｕ ｔ ａ ｔ ｉ ｏ ｎ ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ｏ ｆ ｇ ｅ ｎ ｅ ｔ ｉ ｃ ａ ｌ ｇ ｏ ｉ ｒ ｔ ｈ ｍ ｔ ｏ ｒ ｅ ａ ｌ ｉ ｚ ｅ ｔ ｈ ｅ ｐ ａ ｒ ｔ ｉ ｃ ｌ ｅ ｕ ｐ ｄ ａ ｔ ｉ ｎ ｇ ．Ｉ ｔ ｅ ｍｂ ｏ ｄ ｉ ｅ ｄ ｔ ｈ ｅ ｔ ｈ ｏ ｕ ｇ ｈ ｔ ｏ ｆ ｔ ｈ ｅ ｖ ａ ｉａ ｒ ｔ ｉ ｏ ｎ ａ ｎ ｄ ｓ ｉ ｍｕ ｌ ａ ｔ ｅ ｄ ａ ｎ ｎ ｅ ａ ｌ ｉ ｎ ｇ ａ ｌ ｇ ｏ ｉｔ ｒ ｈ ｍ ｉ ｎ ｔ ｏ ｔ ｈ ｉ ｓ ａ ｌ ｇ ｏ ｉ ｒ ｔ ｈ ｍ ｔ ｏ ａ ｃ ｈ ｉ ｅ ｖ ｅ ｌ ｏ ｃ ａ ｌ ｓ ｅ ａ ｒ ｃ ｈ ｆ ｏ ｒ ｔ ｈ ｅ ｇ ｌ ｏ ｂ ａ ｌ ｏ ｐ ｔ ｉ ｍａ ｌ ｐ ａ ｔ ｒ ｉ ｃ ｌ ｅ ｎ ｅ ｉ ｇ ｈ ｂ ｏ ｒ ｈ ｏ ｏ ｄ ，ｗ ｈ ｉ ｃ ｈ ｐ ｒ ｅ ｖ ｅ ｎ ｔ ｅ ｄ ｐ ｒ ｅ ｍａ ｔ ｕ ｒ ｅ ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ｏ ｆ ｔ ｈ ｅ
优化算法。同时， 将该算法结果与文献 中其他相关算法结果进行比较 ， 验证 了该改进算法的有效性。该算法能
够有 效地 、 高质量 地解 决作 业车 间调度 问题 。 关 键 词 ：改进 离散粒 子群 ； 作 业 车间调度 ； 遗 传 算法 ； 模 拟退 火 ； 局 部搜 索 中图分 类号 ：Ｔ Ｐ １ ８ ； Ｔ Ｐ ３ ０ １ ． ６ 文献标 志码 ：Ａ 文章 编号 ：１ ０ ０ １ ． ３ ６ ９ ５ （ ２ ０ １ ３ ） ０ ８ — ２ ４ ０ ５ ． ０ ５