基于遗传算法的车间调度管理问题研究与应用

VIP免费
3.0 牛悦 2024-11-19 4 4 2.22MB 71 页 15积分
侵权投诉
摘 要
车间调度管理是企业根据生产资源对生产任务进行作业排序，并对生产过程
进行有效管理，调度结果的合理与否是企业能否按时完成生产任务的关键。在现
有研究成果的基础上，针对上海精智实业有限公司的生产情况，本文利用VB6.0、
SQL数据库和Access2007数据库作为工具，为企业研究并开发了车间调度管理系
统，该系统主要包括生产调度、车间通信、刀具管理等功能。
车间调度管理是企业管理的重要环节，合理的作业排序、有效的生产管理，
能够保证生产任务的按时完成，提高资源利用率和企业的经济效益。在实际生产
中，刀具是有限的资源，刀具分配是制约生产排序的关键问题。刀具管理是利用
有限的刀具完成最佳的生产分配，辅助完成生产任务调度，即刀具的动态分配。
本文所研究的车间调度和刀具管理功能相互配合，紧密联系。本文所编写的软件
系统主要利用遗传算法作为研究车间调度的核心理论，设计了算法结构，编写了
调度的核心算法程序。
本文根据企业的实际生产情况进行算法设计，所编写的算法使任务调度与刀
具管理相互结合，在生产中得到实际运用。本算法实现了生产任务在设备上的加
工分配，并根据刀具的使用情况，当多台机床争用同一把刀具时，根据实际约束
条件解决刀具分配的问题。在生产过程中还对刀具进行使用计时，记录并保存了
刀具的累积使用时间，为刀具的检修和报废提供了依据。
为了提高生产管理环节与企业管理其他环节联系的实时性，本文研究的车间
调度管理系统设计了车间通信功能，采用了触摸屏设备系统，为其编写了人机交
互界面，使得车间操作人员能够及时将加工完成情况及时反馈给调度管理中心，
便于企业相关部门实时了解生产情况。
最后，本文所设计的车间调度管理系统在上海精智实业有限公司进行了实际
调试运用，对比了企业原有调度方式和本系统调度方式，调度结果的比较结果验
证了本系统的有效性。
关键词：车间调度 遗传算法 刀具管理 车间通信
ABSTRACT
Job shop scheduling is the production task scheduling made by the enterprise
based on the production resources, and production process of effective management,
the scheduling result is reasonable or not is the key to fulfill production task on time
for the enterprise. In the existing research results, this paper used VB6.0, SQL database
and Access2007 database as a tool, research and develop a shop scheduling
management system, including production scheduling, shop floor communication, tool
management functions, etc..
Job shop scheduling is an important part of enterprise management. Reasonable
job shop sequencing, efficient production management, which ensures the production
task would be finished in time, improves the production resource utilization rate and
economic benefits of enterprises. In practical production, the tool is a limited resource;
tool allocation is the key problem of the production scheduling. Tool management is
used limited tools to complete the best distributed issue, which supports the production
scheduling. The production scheduling and management function is close with each
other in this paper; the genetic algorithm is the core theory for the system.
Based on the actual production for algorithm design, the system is used in actual
production. The system could complete the production scheduling and cutting tools
distribution according to the manufacturing task and task rank. In the production
process the system also records and stores the tool's cumulative time which could
provides a basis for the tool repair and scrapped.
Finally, the scheduling management system is used in Shanghai Jing Zhi
Industrial Co., Ltd. for the actual debugging use, Compared the original enterprise
scheduling and the scheduling, scheduling results have verified the effectiveness of this
system.
Key Words: job shop scheduling, genetic algorithm, tool management,
shop floor communication
目 录
中文摘要
ABSTRACT
第一章 绪论 ................................................................................................................. 1
§1.1 课题研究的背景及意义 ................................................................................ 1
§1.2 国内外研究现状及存在问题 ........................................................................ 2
§1.2.1 国内外研究现状...................................................................................... 2
§1.2.2 存在问题.................................................................................................. 3
§1.3 车间调度问题发展趋势 ................................................................................ 3
§1.4 本文研究内容及结构 .................................................................................... 4
§1.4.1 本文研究内容.......................................................................................... 4
§1.4.2 本文结构.................................................................................................. 4
§1.5 本章小结 ........................................................................................................ 5
第二章 车间调度问题概述 ......................................................................................... 6
§2.1 车间调度 ........................................................................................................ 6
§2.1.1 车间调度定义.......................................................................................... 6
§2.1.2 车间调度的数学模型.............................................................................. 6
§2.1.3 车间调度的分类...................................................................................... 7
§2.1.4 车间调度的特点...................................................................................... 9
§2.1.5 车间调度问题的研究方法.................................................................... 10
§ 2.2 本文需要解决的调度问题 ........................................................................ 12
§2.2.1 公司生产情况介绍............................................................................... 12
§2.2.2 算法设计问题....................................................................................... 13
§2.2.3 约束条件设定问题................................................................................ 14
§2.2.4 刀具分配和刀具管理问题.................................................................... 14
§2.2.5 任务优先级设定问题........................................................................... 15
§2.2.6 调度结果显示与车间通信问题............................................................ 16
§2.3 本章小结 ...................................................................................................... 16
第三章 基于遗传算法的车间调度问题算法设计 ................................................... 17
§3.1 遗传算法简介 .............................................................................................. 17
§3.1.1 遗传算法基本概念................................................................................ 17
§3.1.2 遗传算法的基本流程............................................................................ 18
§3.1.3 算法参数的选取.................................................................................... 19
§3.1.4 遗传算法的优缺点................................................................................ 20
§3.2 编码设计 ...................................................................................................... 21
§3.2.1 遗传算法编码........................................................................................ 21
§3.2.2 编码过程................................................................................................ 22
§3.3 生成初始种群 .............................................................................................. 23
§3.4 选择操作 ...................................................................................................... 23
§3.5 适应度函数 .................................................................................................. 24
§3.6 交叉 .............................................................................................................. 26
§3.6.1 交叉方法概述........................................................................................ 26
§3.6.2 交叉运算................................................................................................ 27
§3.7 变异 .............................................................................................................. 28
§3.8 本章小结 ...................................................................................................... 29
第四章 调度过程相关问题研究 ............................................................................... 30
§4.1 约束条件的数学描述 ................................................................................. 30
§4.2 刀具管理 ...................................................................................................... 31
§4.2.1 刀具编码................................................................................................ 31
§4.2.2 刀具管理与监控.................................................................................... 33
§4.3 刀具分配 ...................................................................................................... 34
§4.4 调度结果显示 .............................................................................................. 37
§4.5 车间通信 ...................................................................................................... 39
§4.6 本章小结 ...................................................................................................... 40
第五章 软件开发与应用 ........................................................................................... 41
§5.1 车间调度管理系统设计 .............................................................................. 41
§5.1.1 系统设计的目标和关键........................................................................ 41
§5.2 系统框架 ...................................................................................................... 42
§5.3 系统主要功能介绍 ...................................................................................... 43
§5.3.1 任务调度................................................................................................ 44
§5.3.2 刀具管理................................................................................................ 50
§5.4 其他功能 ...................................................................................................... 51
§ 5.5 加工任务介绍 ............................................................................................. 52
§ 5.6 调度结果比较 ............................................................................................. 53
§ 5.6.1 人工调度............................................................................................... 53
§5.6.2 系统调度................................................................................................ 54
§ 5.6.3 结果比较............................................................................................... 57
§ 5.7 其他功能验证 ............................................................................................. 58
§ 5.8 本章小结 ..................................................................................................... 60
第六章 总结与展望 ................................................................................................... 61
§6.1 总结 ............................................................................................................. 61
§6.2 展望 ............................................................................................................. 62
参考文献 ..................................................................................................................... 63
在读期间公开发表的论文和承担科研项目及取得成果 ......................................... 67
致 谢......................................................................................................................... 68
第一章 绪论
1
第一章 绪论
§1.1 课题研究的背景及意义
科学技术的发展，尤其是信息技术、自动化技术、网络技术的迅速发展，使
得加工制造行业呈现市场响应快速化、产品多元化的趋势。小批量、多品种的生
产方式日益重要，生产的复杂行越来越高，因此对企业的生产管理提出了更高的
要求。生产有序、管理高效是企业获取最大经济效益的关键途径，以前简单的、
人工排序的作业排序方式以及传统的车间管理方式，已经不能满足现代生产的需
求。加工制造企业的管理者面临以下问题：
1. 如何根据产品需求的变化及时改变生产计划和组织生产，也就是车间生产
如何实时调度的问题。
2. 如何实现各种资源的合理配置，减少固定资产的闲置，提高设备利用率。
随着科技的迅速发展，固定资产尤其是机器设备有加速折旧的趋向，提高
设备利用率就是提升经济效益。
3. 生产部门和其他有关部门缺乏有效沟通，生产完成情况不能实时反馈给管
理者以及相关人员。
制造业是我国国民经济的支柱产业，在产业布局中占有中心地位。中国已成
为世界制造业的中心，如何提高企业的核心竞争力，关键就在于加快企业的信息
化进程。我国制造业信息化的重点普遍放在建设 ERP 管理系统等方面，ERP 管理
软件能有效提高企业运作的规范化，但市场响应越来越快速化对企业生产调度和
组织提出挑战，这是 ERP 系统无法完成的问题，车间生产调度管理的重要性就凸
现出来。
对车间生产作业调度管理问题进行探讨，寻找新的调度算法，具有很大的现
实意义和经济意义，主要有以下几点：
1. 为企业及时提供合理的生产作业排序方案，使企业制定出合适的生产计
划，提高生产的响应速度，保证生产有序进行。
2. 使用先进的调度算法，能够合理配置企业资源，提高设备利用率和生产效
率，最终提高企业经济效益。
3. 合理的车间调度管理，能够有效解决生产与管理等其他环节的沟通问题，
提升企业的管理能力，提高企业的综合竞争力。
基于遗传算法的车间调度管理问题研究与应用
2
§1.2 国内外研究现状及存在问题
§1.2.1 国内外研究现状
车间生产调度是系统优化问题当中一个经典的问题，也是一个难题，对这项
问题的研究始于 20 世纪 50 年代。Johnson 教授在 1954 年对两台机床的 Flow-
Shop 型调度问题进行了研究，并提出了相关算法，代表调度理论研究的开始。
60-70 年代研究者们建立了调度理论的框架核心（也就是现在的经典调度理论）
并调度问题的复杂性进行了重点研究。
从七十年代开始，复杂性理论的研究进入一个新的阶段，NP 完全问题(NP-
complete) (N 指问题解决的时间复杂度，P问题指问题可以找到一个能在多项式时
间里解决的算法)的研究也开始兴起，研究者们开始注意并重视对作业调度的复杂
性进行研究，许多调度问题被证明是 NP 的难题(NP-hard)，即使是简单的 Job–
Shop 或Flow-Shop 问题也是 NP-hard 的，多项式求解方法对于这种问题是无效的，
因此研究者们开始探索有效的启发式方法解决这类问题。在这个时期内研究者们
对调度问题进行了深入的研究，七十年代末期，经典调度理论趋向成熟。
很多学者将遗传算法(Genetic Algorithm，遗传算法)用于解决调度问题，Davis
是最早的之一[1]，他使用遗传算法解决车间作业调度问题，并获得了近似最优解。
Davis 在1985 年发表了利用遗传算法解决车间调度问题的论文，介绍了相关成功
运用情况，充分验证了在解决车间调度问题中的遗传算法具有的卓越性能。此后，
很多学者在车间作业调度问题上，利用遗传算法进行了深入的研究和探索，发表
了很多有高质量的论文，使车间作业调度这个问题的解又向前迈出一步。
最近，遗传算法(Genetic Algorithm，GA)等优化算法理论引起了研究者们极
大兴趣，并广泛运用在车间作业调度问题上。Chen H[2]用GA 解决车间作业调度
的生产周期最短的问题，并利用图论的解决了编码问题。Najidn.M[3]综合模拟退
火算法用以求解生产过程中资源竞争的作业车间调度问题。
Kaceml[4,5]首先采用局部优化算法解决调度过程中的资源竞争问题，产生作业
分配计划，然后根据起始的分配集构造初始种群，再使用遗传算法来优化解。单
目标和多目标车间作业调度问题被这些学者利用遗传算法得以解决。又有学者对
遗传算法的早熟收敛现象提出了一种有效的基于遗传算法和禁忌搜索的优化调度
算法，HON.B[6]认为求解车间作业调度问题的遗传算法中的染色体需要特殊设计，
并给出评估染色体的性能的两个判定标准。L.De Giovanni[7]提出了一种改进遗传
算法求解分布式车间作业调度问题。Guohui Zhang[8]提出用全局选择和局部选择
产生高质量的初始种群，交叉和变异算子都采用不同的策略，并用实例论证了该
第一章 绪论
3
方法的有效性。
国内对车间作业调度问题的研究起步较晚，大多是进行理论上的研究。随着
国际上遗传算法在车间作业调度问题上的广泛应用，国内也掀起了应用遗传算法
解决优化问题的热潮，研究车间调度是重要的一个方向。相关研究者主要集中在
清华大学的 CIMS 国家重点实验室、上海交通大学、西安交通大学和北京机械工
业自动化研究所等，这些研究机构开发出了一些系统，但大多还是试运行阶段，
还不能够进行实际运用，因此各研究机构还在投入大量的资源进行该项工作的研
究，尤其是针对车间作业调度相关算法的研究，目前还处于实验研究或仿真阶段。
§1.2.2 存在问题
由于在实际生产过程中会有诸多约束性因素，从目前文献的研究来看，针对
加工过程中计划排序和资源分配没有给出实际可用的方案，大多是对问题进行假
设，按照理想条件进行处理。
大多数车间生产调度问题的研究，还集中在经典调度算法理论的设计和优化
方面，或者是调度算法的建模仿真，这与实际问题有一定的差别。在经典调度理
论算法或建模仿真，是对实际问题的理想化，这与车间生产的实际情况有很大的
差异。
在多数文献中，对于生产过程的约束条件仅仅局限于生产周期、交货期等时
间指标，而忽略了资源竞争、排序优先级设定等条件。在生产调度管理中，不仅
仅有调度排序的问题，而且还有生产管理的问题，如何将生产排序情况与其他部
门及时沟通也是需要考虑的问题。
§1.3 车间调度问题发展趋势
虽然对车间作业调度问题的研究已有半个多世纪的历史，但大多数研究没有
从实际问题出发，建模时对实际生产过程进行了大量简化处理，离实际的生产应
用还有很大的距离。
针对目前存在的情况以及车间调度问题的日益复杂的趋向，目前车间调度问
题的研究具有下列发展趋势。
1. 算法的混合使用，过去研究者大多是使用单一的搜索法，算法具有一定的
缺陷，算法的混合使用能避免这些缺陷，很多学者将遗传算法与神经网
络算法混合、遗传算法[9]与蚁群算法混合等，出现了很多将两种或多种
算法混合的解决方法。
摘要：

摘要车间调度管理是企业根据生产资源对生产任务进行作业排序，并对生产过程进行有效管理，调度结果的合理与否是企业能否按时完成生产任务的关键。在现有研究成果的基础上，针对上海精智实业有限公司的生产情况，本文利用VB6.0、SQL数据库和Access2007数据库作为工具，为企业研究并开发了车间调度管理系统，该系统主要包括生产调度、车间通信、刀具管理等功能。车间调度管理是企业管理的重要环节，合理的作业排序、有效的生产管理，能够保证生产任务的按时完成，提高资源利用率和企业的经济效益。在实际生产中，刀具是有限的资源，刀具分配是制约生产排序的关键问题。刀具管理是利用有限的刀具完成最佳的生产分配，辅助完成生产...

展开>> 收起<<
基于遗传算法的车间调度管理问题研究与应用.pdf

共71页,预览8页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：牛悦 分类：高等教育资料 价格：15积分 属性：71 页 大小：2.22MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 71
评分 收藏
分享
立即下载 VIP免费下载
客服
关注