学海网

考虑加工成本的双目标平行机批调度问题的启发式算法研究（硕士学位论文），共51页。
【摘要】 生产调度问题作为一个在生产制造领域中有着很强应用背景的组合优化问题,它是指在一定时间内对生产任务进行规划和分配以达到某项或某几项指标的过程。合理并且有针对性的调度方案在提高企业的生产效益,促进有限资源的合理利用等方面起到了巨大的推动作用。然而由于实际的生产调度问题往往具有约束条件多、目标问题种类多以及随机不确定性等特点,导致了不少调度问题都未能得到妥善合理地解决。其中很多问题已被证明属于NP难问题,因此如何针对复杂的生产调度环境设计简单高效的求解算法始终是批调度问题研究的侧重点。本文从调度问题的基础概念出发,介绍了关于描述一个具体的调度问题时所通用的表示方法、调度问题按不同研究角度形成的分类及其主要研究方法。其次,介绍了构成构成经典调度问题的四个必要条件。经典调度问题的假设之一,即任何机器无论在任何时刻至多只能加工一个工件。但在实际的工业生产环境中,为了缩短加工时间,提高生产效率,有的机器可以同时加工多个工件,这种类型的现代调度问题即为批调度问题。最后介绍了本文所要研究的批调度问题的一个分支：差异工件批调度,即待加工的工件集中各工件在尺寸上存在差异,而且需要满足属于同一批中的工件,其尺寸之和不能超过机器容量的条件。差异工件批调度问题相较于经典调度和工件尺寸均一致的传统批调度来说,其问题复杂程度要高出很多,更能适应现代复杂多变的生产环境需求。本文探讨了考虑工件自身加工成本的双目标平行机批调度问题,当前关于平行机环境下的研究主要集中于如何提高生产效率,即优化的目标函数主要是关于时间的函数(例如最大完工时间Cmax、总完工时间∑Cj),然而随着绿色制造理念的提出,生产中的能源效率问题也日益突出。在现有涉及到成本目标的批调度问题的研究中,主要考虑的是批的交货成本(即客户对每个批所要求的交货时间),而忽视了工件作为独立对象被分配加工时所产生的成本。针对考虑工件加工成本的双目标平行机批调度问题,本文提出了一个启发式优化算法。对于双目标的优化本文基于分级法思想,以最小化总完工时间为第一目标,以最小化机器总加工成本MOC为第二目标。对批调度过程中的两个阶段：分批以及批排序,分别利用启发式算法BFLPS和rank-s予以解决。通过仿真实验将本文设计的启发式算法与遗传算法及文献中现有的启发式算法进行性能比较并给出了性能分析,实验结果验证了本文算法对于优化双目标平行机批调度问题的有效性。
【关键词】 平行机； 双目标； 差异工件批调度； 分级法思想； 启发式算法；

目录
m ^ I
Abstract Ill
第一章弓|言 1
1.1调度问题概述 1
1.1.1调度问题的三参数表示法 1
1.1. 2调度问题的分类 5
1.1. 3调度问题的研究方法 6
1.2调度问题的研究现状 12
1. 2.1经典调度问题 12
1.2.2批调度问题 13
1. 2. 3差异工件批调度问题 14
1. 3论文的主要研究内容与结构安排 16
1. 3.1论文的研究内容 16
1.3. 2论文的结构安排 17
第二章多目标批调度问题 19
2.1多目标优化理论和方法 19
2.2多目标批调度问题的研究现状 20
2.2.1基于客户满意度的多目标批处理机调度问题 20
2. 2. 2考虑成本的多目标批处理机调度问题 22
2.2.3现有研究存在的问题 23
第三章启发式算法在考虑成本的多目标多机批调度问题中的应用 26
3.1考虑成本的多目标多机批调度问题 26
3. 3.1数学模型 26
3. 3. 2问题下界 28
3. 2启发式求解算法 28
3. 2.1算法整体流程描述 : 28
3. 2. 2分批阶段的启发式算法BFLPS 29
3.2.3批分配阶段的启发式算法rank-s 29
第四章仿真实验与结果分析 31
4.1实验设计 31
4. 2参数设置 31
4. 3实验结果及分析 32
第五章总结及展望 36
参考文献 37