基于蚁群算法的分层生产调度模型研究与设计

论文摘要

生产调度是企业在生产管理中关注的核心问题之一,它是解决如何按时间先后分配资源使预定目标最优化的问题。组车间调度问题（Group Shop Scheduling Problem, GSP）是许多实际生产调度问题的简化模型,是一个典型的NP-hard问题,已被证明在多项式时间内得不到最优解。蚁群算法是用于解决组合优化问题的一种新兴启发式算法,因其具有良好的解发现能力、较强的鲁棒性、并行性本质等特点,而逐渐成为研究热点。论文描述了GSP的数学模型和析取图模型,分析了GSP的特点,研究了基本蚁群算法的原理、理论框架及其改进思路,重点研究了一种改进蚁群算法——最大最小蚂蚁系统（MAX-MIN Ant System, MMAS）的算法思想,并深入分析了其在GSP求解中的应用——MMAS-HC-GSP。本文的研究以国家863项目“基于RFID的通用汽油机生产执行监控系统”为研究背景,总结和分析了背景项目的研究成果和对生产调度的需求,提出了求解GSP的分层生产调度模型（HJSM）。HJSM由车间层调度和工位层调度组成。车间层调度将生产任务划分为若干子集,并保证了这些子集对应析取图的连通性,为工位层调度创造了条件;工位层调度在车间层调度的基础上,实现了在较短生产周期约束条件下对生产任务的优化调度。在车间层调度的设计中,通过对生产任务所需资源相互关联程度的分析,提出了“相关任务集”这一新概念,并给出了求解相关任务集的算法和数据结构设计。在工位层调度的设计中,分析了GSP析取图模型的特点,提出了一种析取图的生成算法及其相应数据结构设计;以MMAS- HC-GSP作为核心调度算法,给出其关键步骤的算法及相应数据结构的具体设计。本文结合背景项目设计了测试用例,测试的结果表明,模型的设计达到了预期目标,能够为生产调度提供较好的决策支持。HJSM的提出对背景项目MES系统的功能扩展具有一定实际意义,为生产调度问题的研究提供了一种新思路,对后续生产调度研究和生产调度系统的实现具有一定借鉴意义。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 选题背景及研究意义
• 1.2 国内外研究现状
• 1.2.1 制造型企业生产经营模式的转变
• 1.2.2 生产调度问题的研究现状
• 1.2.3 小结
• 1.3 主要研究内容及预期目标
• 1.4 论文的章节安排
• 2 生产调度相关技术研究
• 2.1 生产调度概述
• 2.1.1 生产调度简介
• 2.1.2 生产调度问题的评价指标
• 2.1.3 生产调度问题的主要类别
• 2.1.4 GSP 的代表性
• 2.1.5 GSP 的数学模型
• 2.1.6 GSP 的析取图模型
• 2.2 蚁群优化算法
• 2.2.1 蚁群算法的思想起源
• 2.2.2 蚁群算法的理论模型
• 2.2.3 基本蚁群算法的不足及后续改进算法
• 2.2.4 MMAS 的原理
• 2.2.5 MMAS 在GSP 中的应用：MMAS-HC-GSP
• 2.3 本章小结
• 3 背景项目研究
• 3.1 背景项目概述
• 3.2 背景项目为模型设计创造的条件
• 3.2.1 ERP 生产计划的管理
• 3.2.2 现场生产数据的采集
• 3.2.3 现场生产设备的管理
• 3.3 背景项目对生产调度的需求
• 3.4 本章小结
• 4 分层生产调度模型的设计
• 4.1 模型的总体设计
• 4.1.1 模型的设计目标
• 4.1.2 模型的假定条件
• 4.1.3 模型与ERP、MES 的联系
• 4.1.4 模型的体系结构
• 4.2 车间层调度模型设计
• 4.2.1 车间层调度的总体目标
• 4.2.2 车间层调度的输入和输出
• 4.2.3 生产设备的分配
• 4.2.4 生产任务的设备相关性及相关任务集
• 4.2.5 相关任务集的求解
• 4.3 工位层调度模型设计
• 4.3.1 工位层调度的总体目标
• 4.3.2 工位层调度的输入和输出
• 4.3.3 GSP 析取图的建立
• 4.3.4 MMAS-HC-GSP 的实现
• 4.4 实例分析
• 4.5 本章小结
• 5 论文总结
• 5.1 论文工作
• 5.2 成果总结与展望
• 致谢
• 参考文献
• 附录