基于关键路径法求解车间调度问题的研究

论文摘要

随着全球经济一体化和知识经济的到来,企业之间的竞争越来越激烈。如果一个企业不具备强有力的竞争力,那么就很难在这个社会的市场上有生存的空间。对于加工制造业而言,在最短的时间内以最低的成本制造出顾客满意的产品,无疑是企业增加竞争力的有力手段。因此,如何利用有限的资源,降低产品的生产成本,缩短产品的制造周期,保证按时交货,提高企业信誉,赢得更多客户,成为制造业在竞争中生存的重要条件之一。有效的利用现有资源,制定出一个合理的企业和车间之间的生产计划,以实现车间生产的高效率性和高可靠性将是企业生产的关键。通过分析车间调度的问题,并结合图论的技术,给出了基于图的车间调度的模型（G-JSHOP）。针对车间调度的复杂性,将求解车间调度的问题转化为求解图的关键路径的问题,即利用关键路径技术求解车间调度问题。将关键路径技术和遗传算法相结合求解车间调度问题。在编制车间调度计划的过程中,每个工件的加工的工艺路线、加工时间和加工成本是已知的,但是,每台机器加工的工件的顺序是可以调整的,而这个加工的顺序起到决策的作用。本论文就是从这个决策的路线开始着手,结合遗传算法,将每一条决策路线转化为决策矩阵,并将决策矩阵作为种群中的个体。由于每台机器内部加工的工件的个数和工序数是固定的,所以只允许机器内部的工序进行调整,即只能将所有的机器内部加工的最大的工件数k为一个基因组。利用选择算子、k位基因组的交叉和变异算子技术产生下一代,最后经过若干代的进化之后,最终得到一个次优解。本论文将关键路径技术应用到模具生产管理中,首先,介绍了模具生产管理中的车间作业计划;其次,分析了他的功能架构及其特点;最后,分析了车间级生产作业计划和厂级生产作业计划,并将这两级计划互相衔接构成二级调度的生产作业计划,并将该计划和关键路径法相结合解决模具的生产调度问题。通过分析试验,该算法在整体上缩短了模具的加工时间。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 选题的背景与意义
• 1.2 车间调度（JSHOP）问题的概述
• 1.2.1 JSHOP 的定义
• 1.2.2 JSHOP 国内外研究现状
• 1.2.3 JSHOP 研究存在的问题
• 1.3 论文的研究内容与结构
• 1.3.1 主要的研究内容
• 1.3.2 论文的结构
• 第二章 基于图的车间调度建模
• 2.1 车间调度建模方法的分类
• 2.1.1 数学分析的方法
• 2.1.2 图与网络的方法
• 2.2 经典的车间调度（JSHOP）问题
• 2.2.1 问题的描述
• 2.2.2 车间调度问题的特点和分类
• 2.2.3 局限性分析
• 2.3 基于图的JSHOP（G-JSHOP）模型
• 2.3.1 G-JSHOP 模型的提出
• 2.3.2 G-JSHOP 模型的约束条件
• 2.3.3 G-JSHOP 模型的数学描述
• 2.3.4 G-JSHOP 模型的研究用例描述
• 2.4 求解G-JSHOP 问题的算法选择
• 2.4.1 经典算法优缺点概括与比较
• 2.4.2 基于关键路径法解决G-JSHOP 问题的优势
• 2.5 小结
• 第三章 基于k 位基因组编码的遗传进化调度算法
• 3.1 遗传进化调度算法的编码设计方案
• 3.1.1 基于普通的适应度函数的编码设计
• 3.1.2 G-JSHOP 模型的k 位基因组编码设计
• 3.1.3 G-JSHOP 模型的条件与约束的处理策略
• 3.1.4 G-JSHOP 模型的处理流程
• 3.2 选择算子设计
• 3.2.1 局部最优调度选择
• 3.2.2 环调度的淘汰
• 3.2.3 最差调度的淘汰算法
• 3.3 k 位基因组的交叉
• 3.3.1 k 位基因组的两点交叉
• 3.3.2 k 位基因组两点交叉的处理流程
• 3.4 k 位基因组的变异
• 3.4.1 k 位基因组的逆序变异
• 3.4.2 k 位基因组的逆序变异的处理流程
• 3.5 小结
• 第四章 基于关键路径法的适应度函数的设计
• 4.1 基于关键路径法的单目标适应度函数设计
• 4.1.1 工件加工调度图生成
• 4.1.2 工件加工调度图的拓扑排序
• 4.1.3 工件加工工序的关键路径
• 4.1.4 基于关键路径的单目标适应度函数的设计思路
• 4.2 基于关键路径法的双目标适应度函数设计
• 4.2.2 基于关键路径法的双目标适应度函数设计
• 4.2.3 基于关键路径法的双目标适应度函数设计的改进
• 4.3 小结
• 第五章 关键路径法在模具生产管理中的应用
• 5.1 模具生产管理的车间作业计划的概述
• 5.2 模具生产管理的车间作业计划的系统功能架构
• 5.2.1 模具生产管理的车间作业计划的特点
• 5.2.2 模具生产管理的车间作业计划的系统功能结构
• 5.2.3 模具生产管理的车间作业计划的架构说明
• 5.3 基于关键路径法的二级调度策略
• 5.3.1 车间级生产作业计划的调度策略
• 5.3.2 厂级生产作业计划的调度策略
• 5.3.3 二级生产作业计划的调度衔接策略
• 5.4 基于关键路径法的二级调度策略在模具生产管理中的应用
• 5.4.1 二级生产作业计划中的关键路径
• 5.4.2 二级生产作业计划在模具生产管理中的应用
• 5.5 试验分析
• 第六章 总结与展望
• 6.1 结论
• 6.2 进一步的研究方向
• 参考文献
• 发表论文和科研情况说明
• 致谢