批处理机调度问题的模型与优化方法研究

论文摘要

批处理机调度是调度问题的一个重要分支。不同于经典调度问题,在批处理机调度问题中,一台机器可以同时加工多个工件。由于这类调度问题不仅需要将工件指派到机器上,还包含将工件分批的决策问题,因此比经典调度问题更为复杂,很多已知的批调度问题均是NP难解问题。批处理机调度在现实生产环境中有着广泛的应用,包括半导体芯片生产,钢铁制造,货物运输等。合理的调度方案可以大幅提高生产效率,节省生产成本,因此对批处理机调度问题的研究有着重要的现实意义。尽管当前已有不少文献对批处理机调度问题进行研究,但这些研究仍然有着不足之处。一是研究的问题主要侧重于工件具有相同尺寸的较简单情形,较少涉及不同尺寸工件情况。二是求解方法多是设计精确求解算法解决小规模问题或是用简单启发式算法获得近似解,对于复杂的构造式方法较少有人研究。三是研究的目标集中在以makespan为代表的生产效率型目标,而对于调度问题中的能源效率则鲜有关注。针对当前研究中存在的问题,本研究主要做了以下工作:（1）从聚类视角下研究了不同尺寸工件批处理机调度问题。论证了差异工件单机环境下的批调度问题实质为一种广义聚类问题,为求解该问题提供了一个新的途径。提出了批的空间浪费比的概念,将最小化C max的目标函数变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明。此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法CACB,并通过实验验证了算法的有效性。（2）将不同尺寸工件的批处理机调度问题推广到工件动态到达的并行机环境,提出并证明了该问题的两个不同下界。在此基础上设计了两种智能优化算法。一是基于工件序列编码的遗传算法,通过工件序列和Best-Fit规则生成分批,并设计了一个ERT-LPT算法来安排批在机器上的加工。另外一种是基于构造式分批的蚁群算法,算法同时考虑工件在尺寸和加工维度的特点作为启发式信息,指导蚂蚁不断寻找适合的工件加入当前批,直到所有分批构造完毕。对两种算法的性能及偏好,通过大量仿真实验进行了比较。（3）将能源效率问题融入调度领域的研究中。构建了在分时电价条件下,以最小化电力成本和makespan为目标的柔性流水车间批调度问题的模型。设计了三种不同的多目标优化算法来求解该问题:即偏好向量蚁群系统PVACS,基于NSGA-II和基于SPEA2的进化算法,并比较了三种算法在不同评价指标下的性能。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 调度问题的基本描述与求解方法
• 1.2.1 调度问题的基本描述
• 1.2.2 调度问题的求解方法
• 1.3 批处理机调度问题的研究现状
• 1.3.1 单机环境批处理机调度问题
• 1.3.2 并行机环境批处理机调度问题
• 1.3.3 车间环境批处理机调度问题
• 1.3.4 现有研究的特点及存在的问题
• 1.4 本文的主要研究工作与结构
• 1.4.1 主要研究工作
• 1.4.2 结构与内容安排
• 第2章 聚类视角下不同尺寸工件批调度问题研究
• 2.1 不同尺寸工件批调度问题的基本描述
• 2.2 分批问题与聚类问题的比较
• 2.3 批的空间浪费比的概念
• 2.4 分批约束凝聚聚类算法（CACB）
• 2.5 仿真实验
• 2.5.1 实验设计
• 2.5.2 算法参数设置
• 2.5.3 实验结果与讨论
• 2.6 本章小结
• 第3章 工件动态到达批调度问题的遗传算法研究
• 3.1 工件动态到达批调度问题的基本描述
• 3.1.1 单机环境下的模型
• 3.1.2 并行机环境下的模型
• 3.2 工件动态到达问题的两个下界
• 3.3 遗传算法及其在调度问题中的应用
• 3.4 基于工件序列的遗传算法
• 3.4.1 安排批加工的ERT-LPT 规则
• 3.4.2 种群初始化
• 3.4.3 选择操作
• 3.4.4 交叉操作
• 3.4.5 变异操作
• 3.5 本章小结
• 第4章 工件动态到达批调度问题的蚁群算法研究
• 4.1 蚁群算法介绍
• 4.2 构造分批的蚁群算法
• 4.2.1 算法初始化
• 4.2.2 解的构造过程
• 4.2.3 信息素更新
• 4.3 仿真实验
• 4.3.1 实验设计
• 4.3.2 两个下界的测试
• 4.3.3 算法的参数设置
• 4.3.4 实验结果与讨论
• 4.4 本章小结
• 第5章 考虑电力成本的多目标柔性流水车间批调度问题研究
• 5.1 能源效率问题产生的背景
• 5.2 问题描述及数学模型
• 5.3 多目标优化的基本概念
• 5.4 PVACS 算法
• 5.4.1 解的编码和解码
• 5.4.2 信息素表示
• 5.4.3 启发式信息
• 5.4.4 解的构造过程
• 5.4.5 减少EPC 的Right-Shift 过程
• 5.4.6 信息素更新
• 5.5 基于NSGA-II 的优化算法
• 5.5.1 NSGA-II 介绍
• 5.5.2 边界集的构造
• 5.5.3 聚集距离的计算
• 5.5.4 选择，交叉和变异操作
• 5.6 基于SPEA2 的优化算法
• 5.6.1 SPEA2 介绍
• 5.6.2 适应度分配
• 5.6.3 环境选择
• 5.7 仿真实验
• 5.7.1 实验设计
• 5.7.2 算法评价指标
• 5.7.3 算法参数设置
• 5.7.4 实验结果与讨论
• 5.8 本章小结
• 第6章 总结与研究展望
• 6.1 全文总结
• 6.2 研究展望
• 参考文献
• 致谢