《基于粒子群优化的多目标车间调度算法》由会员分享，可在线阅读，更多相关《基于粒子群优化的多目标车间调度算法（66页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 基于粒子群优化的多目标车间调度算法 姓名：丁英娟 申请学位级别：硕士 专业：工业工程 指导教师：高亮 20070528 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 I 摘摘 要要 当前，多目标调度成为车间调度的研究热点。粒子群优化算法是一种简单有效的 仿生算法。多点并行搜索的特性，使粒子群优化算法也适用于多目标优化问题的求 解。本文主要研究了三种基于粒子群优化的多目标车间调度算法。 首先，阐述了多目标车间调度的三种求解方法，系统地介绍了粒子群优化算法， 归纳了其发展过程及基本应用，并概述了多目标粒子群优化算法的研究现
2、状。 其次，研究了基于粒子群优化的多目标流水车间调度，构造了适合求解多目标流 水车间调度问题的粒子群优化算法。在算法的求解过程中，采用 PMX 交叉算子实现粒 子的更新；采用基于调度问题的邻域结构(关键路径)实现粒子的局部搜索；采用插入变 异算子实现粒子的随机搜索。实验结果表明了算法的有效性和优越性。 然后，在解决多目标流水车间调度问题的基础上，研究了更为复杂的基于粒子群 优化的多目标作业车间调度，构造了适合求解多目标作业车间调度问题的粒子群优化 算法。在算法的求解过程中，利用基于工件的交叉算子作为粒子的更新方式；采用禁 忌搜索作为粒子的局部搜索策略；采用交换位置变异算子实现粒子的随机搜索。基
3、于 标准测试问题的实验结果验证了该算法的有效性和优越性。 随后，在解决多目标作业车间调度问题的基础上，研究了更为复杂的基于粒子群 优化的多目标柔性作业车间调度。针对多目标柔性作业车间调度的特点，设计了基于 工序顺序和基于机器分配相融合的编码方案，利用基于工序顺序和基于机器分配的交 叉算子和变异算子作为粒子的更新策略及随机搜索策略，采用禁忌搜索作为粒子的局 部搜索策略，构造出了适合求解多目标柔性作业车间调度问题的粒子群优化算法。实 验结果也验证了该算法的有效性和优越性。 最后，对全文进行了总结，并对多目标粒子群优化以及多目标车间调度的研究方 向进行了展望。 关键词关键词：流水车间调度 作业车间调
4、度 柔性作业车间调度 多目标粒子群优化 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 II Abstract Recently, multi-objective scheduling is becoming a hot research topic of shop scheduling. Particle Swarm Optimization (PSO) algorithm is a simple and effective method, which simulates the activities of biologic colony. PS
5、O algorithms speciality of multi-point parallel search makes it be applicable to multi-objective optimization problems solving. This work concentrates on three multi-objective shop schedulings based on PSO algorithm. Firstly, the three kinds of solving methods about multi-objective shop scheduling a
6、re introduced. The PSO algorithm is also introduced and its development are reviewed. The basic application of PSO algorithm and the research actuality of multi-objective PSO algorithm are summarized. Secondly, multi-objective Flow-shop Scheduling Problem (FSP) based on PSO is researched and PSO alg
7、orithm which competently solve multi-objective FSP is constructed. In the algorithm, PMX crossover operator is used to realize particles renewal, vicinage framework (key path) based on scheduling problem is used to realize particles local search, and inserting mutation operator is used to realize pa
8、rticles random search. The algorithms efficiency and superiority are indicated through experimental results. Thirdly, basing on multi-objective FSP has been solved, more complicated multi- objective Job-shop Scheduling Problem (JSP) based on PSO is researched and PSO algorithm that can solve multi-o
9、bjective JSP is constructed. In the algorithm, crossover operator based on workpiece is used to realize particles renewal, Tabu Search (TS) is used to realize particles local search, and changing position mutation operator is used to realize particles random search. This algorithms feasibility and s
10、uperiority are also validated through the experimental results based on normal testing problem. Fourthly, according to the experience of solving multi-objective JSP successfully, more complicated multi-objective Flexible Job-shop Scheduling Problem (FJSP) based on PSO is researched. Basing on the ch
11、aracteristic of multi-objective FJSP, Coding precept based on both working procedure sequence and machine assigning is designed. Crossover operator and mutation operator based on both working procedure sequence and machine assigning is also used as particles renewal strategy and random search strate
12、gy. And TS is also used as particles local search. So, the PSO algorithm which competently solves multi-objective FJSP is constructed. And its efficiency and advantage are also proved through experimental results. Finally, conclusion is drawn and the future research focus about multi-objective PSO a
13、nd multi-objective shop scheduling is pointed out. Keywords: Flow-shop Scheduling，Job-shop Scheduling, Flexible Job-shop Scheduling， multi-objective Particle Swarm Optimization 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标
14、明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本论文属于 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 保密，在 年解密后适用本授权书。 不保密。 华 中 科 技 大 学 硕 士 学 位 论 文
15、华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪绪 论论 1.1 课题来源、目的及意义课题来源、目的及意义 1.1.1 课题来源课题来源 1. 国家自然科学基金项目： “群体智能理论与粒子群优化算法在作业车间调度中的 应用研究” ，项目编号：50305008。 2. 863 项目“基于复杂性科学的车间动态调度理论与方法研究” ，项目编号： 2006AA04Z131。 1.1.2 课题目的课题目的 以粒子群优化算法为核心，分别研究多目标流水车间、多目标作业车间和多目标 柔性作业车间这三种车间调度问题，将粒子群优化算法的应用拓展到多目标优化调度 领域。课题的主要目的是在用粒子群优化算法求
16、解多目标车间调度问题上有较大的理 论突破，产生了原创性的成果。 1.1.3 课题意义课题意义 全球性的竞争给制造业提出了新的挑战。企业要想在激烈的竞争中立于不败之 地，必须以最快的速度、最好的质量、最低的成本和最优的服务来响应市场。调度是 决定企业生产能力的关键因素。在制造环境中调度就是对加工过程进行作业计划，采 用高效的调度可以“缩短工期、减少库存、按时交货、提高信誉 ” 。随着客户需求的个 性化，制造系统的调度问题愈来愈受到重视。此外，在企业的生产调度中，多目标问 题普遍存在。比如，生产者不仅要考虑满足用户的需求，还要考虑自身企业的经济效 益；既要应付突如其来的紧急任务，又要有计划地完成合同订货任务；既要缩短空闲 时间和用户等待时间，又要缩短生产周期；既要减少因为延误时间造成的未完工时 费，还要防止因为提前带来的存储费用等一系列相互联系、相互矛盾的问题。因此， 研究多目标车间调度问题，对促进企业生产管理的现代化，建立现代企业制度，提高 我国企业入世后的竞争力和市场应变能力，迅速打开走向世界的
