考虑加工成本的双目标平行机批调度问题的启发式算法研究

摘要

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

目录

声明

摘要

第一章 引言

1．1 调度问题概述

1．1．1 调度问题的三参数表示法

1．1．2 调度问题的分类

1．1．3 调度问题的研究方法

1．2 调度问题的研究现状

1．2．1 经典调度问题

1．2．2 批调度问题

1．2．3 差异工件批调度问题

1．3 论文的主要研究内容与结构安排

1．3．1 论文的研究内容

1．3．2 论文的结构安排

第二章 多目标批调度问题

2．1 多目标优化理论和方法

2．2 多目标批调度问题的研究现状

2．2．1 基于客户满意度的多目标批处理机调度问题

2．2．2 考虑成本的多目标批处理机调度问题

2．2．3 现有研究存在的问题

第三章 启发式算法在考虑成本的多目标多机批调度问题中的应用

3．1 考虑成本的多目标多机批调度问题

3．3．1 数学模型

3．3．2 问题下界

3．2 启发式求解算法

3．2．1 算法整体流程描述

3．2．2 分批阶段的启发式算法BFLPS

3．2．3 批分配阶段的启发式算法rank-s

第四章 仿真实验与结果分析

4．1 实验设计

4．2 参数设置

4．3 实验结果及分析

第五章 总结及展望

参考文献

致谢