车间调度中瓶颈问题的研究

论文摘要

车间作业调度问题（Job-Shop Scheduling Problem,JSSP）是最一般的,最复杂的和最具难度的生产调度问题。一般的车间作业调度中,设备资源约束是每台加工设备只有一台;因而在实际的加工调度中往往会存在对整个产品加工时间影响较大的瓶颈,对于这种情况,一般的求解方法也往往采用确定各个工序中工件的加工次序。解决瓶颈问题的一种简便方法是增加瓶颈设备,现在无论在学术界还是实际生产中对瓶颈的概念还没有很好的理解,也没有很完善的定义瓶颈的方法;但解决车间作业调度瓶颈问题的关键不仅是找出瓶颈设备,而且要确定是通过增加相同设备可最大幅度提高加工效率的可增加瓶颈设备,而判断可增加瓶颈设备的方法主要是通过判断设备是否有最长加工时间的并行工序。通过对并行工序的研究,首先提出了一种较快速准确地判断并行工序的方法。第一步是确定加工工艺图中每一条从树叶到树根的路线,为每个工序标记它所在的路线号。第二步进行判断,若两个工序存在相同的路线号,则这两个工序不可以并行加工,不是并行工序;若两个工序的路线号全不相同,则它们可以并行加工,为并行工序。然后提出了基于并行工序确定可增加瓶颈设备的算法,得到每台加工设备上的并行工序的个数和并行工序加工总时间,并行工序加工总时间最大的设备即为可增加瓶颈设备。此外在一个相互紧密联系的调度系统中,设备的等待和阻塞是相互的;所以一台设备如果处在加工状态,持续加工的时间越长,该台设备造成其它加工设备等待或阻塞的可能性越大,因为正在加工的工序很可能就是其它设备上将要加工工序的紧前工序,所以又提出了将紧前工序作为考虑因素来判断可增加瓶颈设备的方法。最后分析研究了在动态Job-Shop调度中确定可增加瓶颈设备的问题。本文提出的方法为解决Job-Shop调度的瓶颈问题提供了新的研究思路,具有理论和现实双重意义。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题的背景
• 1.2 JOB-SHOP 调度问题概述
• 1.2.1 Job-Shop 调度问题的含义
• 1.2.2 Job-Shop 调度问题的特点
• 1.2.3 车间调度的分类
• 1.3 JOB-SHOP 调度问题的算法
• 1.3.1 Job-Shop 调度问题的求解算法
• 1.3.2 典型智能优化算法
• 1.4 JOB-SHOP 调度瓶颈研究现状及发展
• 1.4.1 Job-Shop 调度瓶颈研究现状
• 1.4.2 Job-Shop 调度瓶颈问题的发展趋势
• 1.5 本文研究的意义和主要内容
• 1.5.1 课题来源
• 1.5.2 本文研究的意义
• 1.5.3 本文研究的主要内容
• 1.6 论文结构
• 第2章 并行工序及其判断
• 2.1 引言
• 2.2 加工工艺图
• 2.3 相关和独立工序调度的数学描述
• 2.4 并行工序定义及判断
• 2.4.1 并行工序的定义
• 2.4.2 并行工序的判断
• 2.4.3 实例
• 2.5 本章小结
• 第3章 基于并行工序确定可增加瓶颈设备的方法
• 3.1 引言
• 3.2 单作业JOB-SHOP 问题描述
• 3.3 设备
• 3.3.1 瓶颈设备
• 3.3.2 可增加瓶颈设备
• 3.4 算法描述及复杂度分析
• 3.4.1 算法描述
• 3.4.2 复杂度分析
• 3.5 调度实例
• 3.6 本章小结
• 第4章 基于紧前工序确定可增加瓶颈设备的方法
• 4.1 引言
• 4.2 多作业JOB-SHOP 调度问题描述
• 4.3 紧前工序的分析
• 4.4 算法描述及复杂度分析
• 4.4.1 算法描述
• 4.4.2 复杂度分析
• 4.5 调度实例
• 4.6 本章小结
• 第5章 动态JOB-SHOP 调度中确定可增加瓶颈设备的研究
• 5.1 引言
• 5.2 瓶颈设备算法
• 5.2.1 瓶颈机床的识别算法
• 5.2.2 活跃期方法
• 5.3 动态调度分析
• 5.4 在动态JOB-SHOP 调度中确定可增加瓶颈设备算法
• 5.4.1 算法描述
• 5.4.2 算法复杂度分析
• 5.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间所发表的学术论文
• 致谢