华中科技大学 硕士学位论文 基于改进广义粒子群优化的开放式车间调度方法研究 姓名：何铁芳 申请学位级别：硕士 专业：工业工程 指导教师：高亮 20090515 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 I 摘摘 要要 合理的车间调度可以提高企业生产效率，在竞争日益激烈的环境下，高效的车间 调度对生产制造企业显得越来越重要, 是影响企业竞争力的关键因素。开放式车间调度 问题（Open-Shop Scheduling Problem, OSSP）是众多生产调度问题中的一种，广泛存 在于检测和服务行业如汽车保养中心。OSSP 拥有很大的搜索空间，并且是一个 NP 完 全的组合优化问题，对于大规模问题，目前的算法很难求解到最优解。 广义粒子群优化算法（General Particle Swarm Optimization）是求解组合优化问题 的高效智能算法，而禁忌搜索（Tabu Search，TS）是目前求解车间调度问题最有效的 局部搜索算法之一。本文通过改进广义粒子群优化算法并结合禁忌搜索来求解 OSSP 及其扩展问题带准备时间的 OSSP。 系统地概述了 OSSP 和带准备时间的 OSSP 的研究现况，并总结了 PSO 算法在求 解 OSSP 方面的进展及不足。 介绍了 OSSP 和带准备时间的 OSSP 的定义和特点，建立了相关的整数规划模型和 析取图模型，并对各自的邻域结构做了详细的数学分析。 通过分析 GPSO 算法的基本思想，引入全局和个体极值记忆库改进 GPSO 算法的 信息共享模式，并开发了相应的软件系统 GPSO-OSSP，并用 OSSP 的三个标准测试集 来测试算法的有效性，测试结果大多都达到了最优解。其中，最难的问题实例 GP-10 系列中 60%的问题都已求到目前最好解。 根据带准备时间 OSSP 的特点，设计了 LTRPOM-SST 启发式规则。应用改进后的 GPSO 算法求解带准备时间的 OSSP，测试了随机实例和来自标准测试集的实例，测试 结果普遍求到了较好解。 对全文进行了总结，并对 GPSO 算法及 OSSP 今后的研究进行了展望。 关键词关键词： 广义粒子群优化、开放式车间调度、准备时间、禁忌搜索 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 II Abstract Proper and effective shop scheduling can help the enterprises to improve the production efficiency. With the upgrading of marketing competitiveness, efficient shop scheduling becomes more and more important for the manufacturing companies. Open Shop Scheduling Problem (OSSP) as one of various scheduling problems, can be encountered widely in diagnostic tests and service industry such as vehicle maintenance center. OSSP which has large search space is one of hard NP-hard combinatorial optimization problems, and it is hard for the algorithms proposed so far to get optimal solution. General Particle Swarm Optimization (GPSO) is an efficient intelligent algorithm for combinatorial optimization problem, and tabu search (TS) is one of the most efficient local search algorithms for OSSP. In this paper, firstly we improved the GPSO algorithm, and then applied the GPSO to solve the OSSP and the OSSP with setup time by combining with TS. Firstly, a systematic overview of OSSP and OSSP with setup time was given. And then, we summed up the success and deficiency of algorithms in solving OSSP. Secondly, a systematic introduction to the definition and characteristics of OSSP and OSSP with setup time was given. And then we established the integer programming model and the disjunctive graph model and gave a detailed mathematical analysis of their neighborhood structure. Thirdly, through analyzing the basic idea of GPSO algorithm, we improved the information sharing model through introducing two memory bases and developed a system GPSO-OSSP based on the idea. And we applied the proposed algorithm to solve three classes of benchmark instances, the test results show that almost instances can be solved to optimal, and 60% of the most difficulty instance series GP-10-* were solve to new best results. Fourthly, based on the characteristics of OSSP with setup time, we designed a heuristic rules LTRPOM-SST, applied improved GPSO to solve the problem and tested the random and benchmark instance. The test results show that the GPSO is an efficient algorithm to OSSP with setup time. Finally, a conclusion is given and the further research directions of GPSO algorithm and OSSP are anticipated. 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 III Keywords: General Particle Swarm Optimization, Open Shop Scheduling Problem, Setup time, Tabu Search 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本论文属于 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 保密，在 年解密后适用本授权书。 不保密。 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪论绪论 本章首先概述课题的来源、目的、意义，然后对开放式车间调度问题和带准备时 间的开放式车间调度问题的研究现状进行系统综述和探讨，最后阐述了本文的结构和 主要研究工作。 1.1 课题来源、目的及意义课题来源、目的及意义 1.1.1 课题的来源课题的来源 本课题来源于两个国家高技术研究发展计划(863 计划)： “基于复杂性科学的车间 动态调度理论与方法研究”和“复杂制造系统中与工艺规划集成的车间调度” ，项目编 号分别为 2006AA04Z131 和 2007AA04Z107。 1.1.2 课题的目的课题的目的 本课题的主要研究目的是通过对广义粒子群优化算法（General Particle Swarm Optimization，GPSO）核心思想的研究，对 GPSO 进行一定的扩展与改进，并应用于 求解开放式车间调度问题（Open Shop Scheduling Problem，OSSP）和带准备时间 （Setup time）的 OSSP，并用标准测试集实例和随机实例测试算法的有效性。 1.1.3 课题的意义课题的意义 车间调度是在给定的时间内将稀有资源分配给任务的决策过程，在当前竞争日益 激烈的环境下，高效的车间调度对生产制造企业显得越来越重要，它在降低成本、提 高生产效率的同时大大增强了企业的竞争优势1。 经典调度问题主要分为单机调度、多机调度，而多机调度主要分为作业车间调度 （Job Shop Scheduling Problem，JSSP） 、流水作业车间调度问题(Flow Shop Scheduling Problem，FSSP)、开放式车间调度问题(Open Shop Scheduling Problem，OSSP)，它们 都属于组合优化问题中的 NP 完全问题。 OSSP 广泛存在于半导体行业中的检测和诊断车间2，教师排班（Teacher-Class assignment）和考试安排（Examination scheduling）也是 OSSP 问题3。同时相比 JSSP、FSSP 问题而言，对它的研究相对来说还十分有限4。 OSSP 问题拥有非常庞大的搜索空间，对其的求解也显得更加困难，如对于一个 10 10的 OSSP 问题(10 个工件，每个工件有 10 道工序)，相应就有(10!)104.81019种 可行调度。如果要在解空间中通过穷举法找出最优调度，若以 CPU 主频为 2G 的计算 华 中 科 技 大 学 硕 士 学 位 论 文华 中