处理时间恶化的单机调度问题研究

论文摘要

调度问题是制造业和服务业中不可或缺的关键问题,而单机调度问题几乎是所有调度问题的核心部分。单机调度的深入研究对提高企业的运作效率、降低资源浪费、提高客户满意度以及更好地使资源得到优化配置,都具有极为重要的意义。传统的调度问题中工件的处理时间常被假设为常量。然而,人们在实际的调度中发现,工件的处理时间由于受外界环境或自身特性的影响,导致后面被加工工件的处理时间都将延长,这种现象称之为处理时间恶化的现象。为此,本文研究了处理时间恶化的单机调度问题。本文综述了单机调度问题产生的背景、特点、分类和目前的研究现状,同时综述了分枝定界算法、嵌套分割方法以及两者在调度问题中的应用。在此基础上,本文针对处理时间不同恶化模式,研究了处理时间依赖开始时间恶化的单机调度问题、处理时间依赖等待时间恶化的单机调度问题、处理时间依赖累积处理时间恶化的单机调度问题和处理时间依赖累积处理时间恶化的交货期安排问题。针对处理时间依赖开始时间恶化的单机调度问题,分恶化率相同和不同两种情况进行了研究。（1）针对恶化率相同的情况,以最小化最大完工时间为目标,研究了工件具有不同释放时间和相同恶化率的单机调度问题。建立了该问题的混合整数规划模型,采用ILOG软件包对模型进行了求解,与已有文献提出的分枝定界算法和启发式算法进行了对比,验证了模型的有效性。（2）针对恶化率不同的情况,以最小化最大完工时间为目标,研究了工件具有不同释放时间和不同恶化率的单机调度问题。首先,建立了该问题的混合整数规划模型,并采用ILOG软件包求解了该模型；其次,提出了基于优先支配性质和下界的分枝定界算法,获得了问题的最优解,并验证了该算法时间优于ILOG;由于分枝定界算法对大规模问题的局限性,进而提出了规则引导的嵌套分割方法并获得了问题的近优解；最后,对所提的算法进行了对比分析,结果表明所提出的模型和算法是有效的。针对处理时间依赖等待时间恶化的单机调度问题,分工件处理时间依赖等待时间线性恶化和分段线性恶化两种情况分别进行了研究。（1）针对处理时间依赖等待时间线性恶化的情况,以最小化最大完工时间为目标展开研究。首先,提出了工件处理时间依赖等待时间线性恶化的数学模型；其次,提出了基于优先支配性质和下界的分枝定界算法,并获得问题的最优解；为弥补分枝定界算法的局限性,提出了规则引导的嵌套分割方法并获得了问题的近优解；最后,对所提的模型和算法进行了对比分析,结果表明所提出的模型和算法是有效的。（2）针对工件处理时间依赖等待时间分段线性恶化的情况,以最小化最大完工时间为目标展开研究。首先,提出了工件的处理时间依赖等待时间分段线性恶化的模型；其次,提出了基于优先支配性质和下界的分枝定界算法,并获得问题的最优解；进一步地,提出了规则引导的嵌套分割方法并获得了问题的近优解；最后,对所提的算法进行了对比分析,结果验证了所提算法的有效性。针对处理时间依赖累积处理时间恶化的单机调度问题,分在调度序列中安排多个恢复时间和考虑恢复函数两种情况进行了研究。（1）针对处理时间依赖累积处理时间非线性恶化的情况下安排多个恢复时间的单机调度问题,以最小化最大完工时间为目标展开了研究。首先,根据问题特点,提出了问题优先支配性质和下界；其次,提出了基于性质和下界的分枝定界算法以及基于性质的启发式算法,通过实验验证了所提算法的有效性；最后,针对问题的两个特例,证明了在多项式时间内可获得最优解。（2）针对处理时间依赖累积处理时间非线性恶化的情况下考虑恢复函数的单机调度问题,分别以最小化最大完工时间和最小化总的完工时间为目标展开了研究。首先,根据工人体力恢复依赖时间的特点,提出了基于时间的恢复函数；其次,基于该问题的特点,提出了相关的性质和定理；进而,基于上述特性,针对两个目标函数不同的问题,分别给出了问题的多项式算法；最后,通过算例验证了所提模型和算法的有效性。针对处理时间依赖累积处理时间恶化的交货期安排问题,分别对允许工件提前和在调度过程中安排多个机器维护阶段（Rate-modifying activities, RMAs）的两类问题进行了研究。（1）针对允许工件提前的交货期安排问题,以最小化总的拖期惩罚为目标展开了研究。证明了该问题在多项式时间内是可解的,并给出了问题的多项式算法以及算例。（2）针对在调度过程中安排多个机器维护阶段的问题,以最小化总的提前和拖期惩罚为目标,研究了处理时间非线性恶化和带有多个RMAs交货期安排的单机调度问题。首先,根据问题的特点,将其分为几种不同的情况进行了分析,提出了相关的性质和定理；其次,给出了最优的松弛时间；最后,证明了该问题在多项式时间内是可解的。最后给出了全文的结论和未来研究方向上的一些建议。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究目的及意义
• 1.3 本文的研究思路
• 1.4 本文的主要工作
• 第二章 相关理论综述
• 2.1 单机调度问题综述
• 2.1.1 单机调度问题的定义
• 2.1.2 单机调度问题的特点
• 2.1.3 单机调度问题的研究现状
• 2.1.3.1 处理时间不变的单机调度问题
• 2.1.3.2 处理时间变化的单机调度问题
• 2.2 处理时间变化的单机调度问题综述
• 2.2.1 处理时间变化的单机调度问题分类及特点
• 2.2.2 处理时间变化的单机调度问题的研究现状
• 2.3 相关算法综述
• 2.3.1 精确算法综述
• 2.3.1.1 分枝定界算法
• 2.3.2 近似算法综述
• 2.3.2.1 启发式规则简述
• 2.3.2.2 嵌套分割方法综述
• 2.4 本章小结
• 第三章 处理时间依赖开始时间恶化的单机调度问题
• 3.1 基于相同恶化率的单机调度问题
• 3.1.1 问题描述
• 3.1.2 数学模型
• 3.1.3 模型求解
• 3.1.4 结果对比分析
• 3.2 基于不同恶化率的单机调度问题
• 3.2.1 问题描述
• 3.2.2 数学模型
• 3.2.3 支配性质
• 3.2.4 下界
• 3.2.5 分枝定界算法
• 3.2.6 规则引导的嵌套分割方法
• 3.2.7 结果对比分析
• 3.3 本章小结
• 第四章 处理时间依赖等待时间恶化的单机调度问题
• 4.1 依赖等待时间线性恶化的单机调度问题
• 4.1.1 问题描述
• 4.1.2 支配性质
• 4.1.3 下界
• 4.1.4 分枝定界算法
• 4.1.5 规则引导的嵌套分割方法
• 4.1.6 结果对比分析
• 4.2 依赖等待时间分段线性恶化的单机调度问题
• 4.2.1 问题描述
• 4.2.2 支配性质
• 4.2.3 下界
• 4.2.4 分枝定界算法
• 4.2.5 规则引导的嵌套分割方法
• 4.2.6 最小完成时间启发式算法
• 4.2.7 结果对比分析
• 4.3 本章小结
• 第五章 处理时间依赖累积处理时间恶化的单机调度问题
• 5.1 考虑不同RMAs的单机调度问题
• 5.1.1 考虑一个RMA的单机调度问题
• 5.1.1.1 问题描述
• 5.1.1.2 支配性质
• 5.1.1.3 下界
• 5.1.1.4 分枝定界算法
• 5.1.1.5 启发式算法
• jr,rm,a_j=a|C_max'>5.1.1.6 特例1|p_jr,rm,a_j=a|C_max
• 5.1.1.7 结果对比分析
• 5.1.2 考虑多个RMAs的单机调度问题
• 5.1.2.1 问题描述
• 5.1.2.2 支配性质
• 5.1.2.3 下界
• 5.1.2.4 分枝定界算法
• 5.1.2.5 启发式算法
• jr,mrm,a_j=a|C_max'>5.1.2.6 特例1|p_jr,mrm,a_j=a|C_max
• 5.1.2.7 结果对比分析
• 5.2 考虑恢复函数的单机调度问题
• 5.2.1 最小化最大完工时间的单机调度问题
• 5.2.1.1 问题描述
• 5.2.1.2 恢复函数
• 5.2.1.3 支配性质
• 5.2.1.4 多项式算法
• 5.2.2 最小化总完工时间的单机调度问题
• 5.2.2.1 问题描述
• 5.2.2.2 恢复函数
• 5.2.2.3 支配性质
• 5.2.2.4 多项式算法
• 5.2.3 结果对比分析
• 5.3 本章小结
• 第六章 处理时间依赖累积处理时间恶化的交货期安排问题
• 6.1 允许工件提前的单机调度问题
• 6.1.1 问题描述
• 6.1.2 支配性质
• 6.1.3 多项式算法
• 6.2 考虑多个RMAs的交货期安排问题
• 6.2.1 问题描述
• 6.2.2 问题性质
• 6.2.3 问题求解
• 6.3 本章小结
• 第七章 结束语
• 参考文献
• 致谢
• 攻读博士期间撰写的论文
• 作者简介