基于改进广义粒子群优化的开放式车间调度方法研究【精品】.pdf

华中科技大学
硕士学位论文
基于改进广义粒子群优化的开放式车间调度方法研究
姓名:何铁芳
申请学位级别:硕士
专业:工业工程
指导教师:高亮
20090515
华中科技大学硕士学位论文
摘要
合理的车间调度可以提高企业生产效率,在竞争日益激烈的环境下,高效的车间
调度对生产制造企业显得越来越重要, 是影响企业竞争力的关键因素。开放式车间调度
问题(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 今后的研究进行了展望。


关键词: 广义粒子群优化、开放式车间调度、准备时间、禁忌搜索
I
华中科技大学硕士学位论文
Abstract
Proper and effective shop scheduling can help the enterprises to improve the production
efficiency. With the upgrading of petitiveness, efficient shop scheduling
es more and more important for the panies. 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-binatorial 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 bining with TS.
Firstly, a systematic overview of OSSP and OSSP with setup time was given. And then,