基于设备工序紧凑的综合调度算法的研究

论文摘要

由于传统车间调度算法是以工件为单位,解决的是纯加工或纯装配问题,这些方法比较适于解决品种单一、批量较大的产品调度。随着社会的进步和发展,人们的需求越来越多元化,即多品种小批量产品的生产越来越盛行,再运用传统的调度算法必然会导致资源(人力资源和设备资源等)分配的困难等,从而增加总加工时间,降低产品的生产效率,使传统方法失去其优势,因此,研究多品种小批量产品的生产,即复杂产品的综合调度问题,更具有理论价值和实际意义。复杂产品综合调度是以产品为单位,同时进行产品的加工和装配,以提高产品的生产效率。以往的复杂多产品综合调度算法,严格按产品工艺次序调度,即先调度儿子结点工序再调度父结点工序,是多对一的关系,如果先调度父结点工序再调度其儿子结点工序,则对应关系是一对多,因此本文首先提出了基于设备工序紧凑的逆序动态关键路径综合调度算法,该算法将逆序思想与综合调度相结合,在充分考虑了长路径影响产品总加工时间的同时,利用设备工序紧凑法减少设备空闲时间。又由于以往的复杂产品综合调度算法只考虑了当前需调度产品以及在调度过程中又有新产品到达的情况,忽略了各产品的开始时间和交货期都已知的情况,因此本文又提出了基于交货期紧迫度的综合调度算法,该算法根据时间紧迫度确定各产品的调度次序,并利用长路径和短用时策略提高工序加工的并行程度,理论分析和实例表明,该算法可在二次复杂度内给出开始时间与交货期都不相同的多品种小批量复杂产品较合理的综合调度方案。最后针对不同产品在并行时间段内争夺设备资源的情况,提出了按交货期由前到后确定产品调度次序的综合调度算法。该算法综合了层优先、长路径、短用时调度策略和设备工序紧凑法的优点,并用实例进行了验证。本文对复杂产品综合调度问题中的单产品和多产品(开始时间与交货期都已知)提出了相应的算法,通过理论分析和实例证明,算法复杂度都是二次的,且近优效果好,因此,具有一定的理论和现实意义。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究的背景
• 1.2 调度问题在国内外的研究现状及分析
• 1.3 课题研究的意义
• 1.4 课题来源及本文主要内容
• 1.4.1 课题来源
• 1.4.2 本文研究的主要内容
• 第2章 复杂产品综合调度问题综述
• 2.1 复杂产品综合调度问题描述
• 2.2 复杂产品综合调度问题中的概念与模型
• 2.2.1 复杂产品综合调度问题中的基本概念
• 2.2.2 复杂产品加工模型
• 2.3 复杂产品综合调度的求解方法
• 2.4 复杂产品综合调度中存在的问题与发展趋势
• 2.5 本章小结
• 第3章 基于设备工序紧凑的逆序动态关键路径综合调度算法
• 3.1 引言
• 3.2 问题描述
• 3.3 动态关键路径策略的描述
• 3.4 复杂单产品逆序调度与分析
• 3.4.1 逆序
• 3.4.2 工序调度策略设计与分析
• 3.5 逆序调度选择工序策略
• 3.5.1 逆序调度动态关键路径策略
• 3.5.2 逆序调度短用时策略
• 3.6 采用设备工序紧凑法确定工序开始时间策略
• 3.7 算法分析
• 3.8 复杂度分析
• 3.9 实例验证与分析
• 3.10 本章小结
• 第4章 基于交货期紧迫度的综合调度算法
• 4.1 引言
• 4.2 问题描述
• 4.3 有时间限制的多品种小批量产品调度设计与分析
• 4.3.1 调度策略
• 4.3.2 优先级策略
• 4.3.3 长路径策略
• 4.3.4 短用时策略
• 4.3.5 采用设备工序紧凑法确定工序开始时间
• 4.4 算法设计
• 4.5 复杂度分析
• 4.6 实例分析
• 4.7 本章小结
• 第5章 基于可并行时间段的有交货期综合调度算法
• 5.1 引言
• 5.2 调度设计与分析
• 5.2.1 调度策略
• 5.2.2 确定有时间限制的多品种小批量产品的调度顺序的策略分析
• 5.2.3 层优先策略
• 5.2.4 层优先长路径策略
• 5.2.5 层优先短用时策略
• 5.3 算法分析
• 5.4 复杂度分析
• 5.5 实例分析
• 5.6 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间所发表的学术论文
• 致谢