考虑维护时间的机器调度问题研究

摘要

传统的机器调度问题通常假定在整个调度期内机器一直可用。然而，在实际生产过程中，为了减少因机器失效或机器故障而导致的产品质量下降、维护成本增加和生产效率降低等问题，企业一般都会在调度期之前预先安排机器维护，因此在调度问题中考虑这种预防维护时间更具现实意义。
　　 本文首先较为详尽的研究了考虑维护时间的单机调度问题，包括维护时段固定且加工时间恒定、维护时段固定且加工时间可变、维护时段可调且加工时间恒定以及维护时段可调且加工时间可变等四类问题。对于多机调度问题，重点研究了维护时段固定且加工时间恒定的问题，以此说明了把单机调度问题的求解方法拓展到相应多机调度问题的思路，其他三类问题均可按照这种思路进行求解。受维护时段的影响，工件在加工过程中可能会被中断，基于实际生产过程中的不同情况，本文分别考虑了被中断工件可续、不可续和部分可续三种情形。
　　 上述问题的目标函数假定为与生产效率有关的最大完工时间及（加权）完工时间和。根据问题的复杂性不同，本文给出了不同的求解方法：对于NP-难问题，本文一方面致力于设计能求解尽可能大规模问题的精确算法，另一方面，鉴于精确算法在时间和空间性能上的不足，本文也致力于构造高效的启发式算法，从而能够在合理的时间内求得大规模问题高质量的满意解；另外，在某些特殊情形下，有些问题是多项式可解的，对于这些问题，本文通过证明某种多项式时间算法能够为其提供最优解来说明其多项式可解性。
　　 具体而言，本文的主要研究内容和创新点如下：
　　 （1）对于维护时段固定且加工时间恒定的单机调度问题，研究了部分可续情形下的两种目标函数。对于最大完工时间最小化问题，简单说明了此问题的NP-难性，给出了最大加工时间优先（Longest processing time first，LPT）规则的最坏情况相对误差界，进而提出了两个基于LPT 规则的启发式算法：LPT-PI和MLPT，其中LPT-PI以LPT 规则作为初始解，并结合基于成对交换技术的邻域搜索对解进行改进，而MLPT 通过改进LPT 算法执行过程中的某一类特殊情况来得到更优的启发式解。另外，还证明了MLPT的最坏情况相对误差界，并通过大规模实验对算法性能进行了对比分析。对于加权完工时间和最小化问题，简单说明了问题的NP-难性，提出了最优解的性质，并在此基础上构造了动态规划和分枝定界两种精确算法。
　　 大量随机数据的实验结果表明这两种算法都是有效的，且不论从能解问题规模，还是从寻得最优解所需时间方面，分枝定界算法都要优于动态规划算法。
　　 （2）对于维护时段固定且加工时间可变的单机调度问题，研究了最大完工时间及完工时间和两种目标函数。证明了这两种目标函数下加工时间线性增加和线性减少时的几种可续情形是多项式可解的。对于不可续情形，重点研究了加工时间线性增加时的完工时间和问题。
　　 对于该问题，简单说明了其NP-难性，证明了最优解的性质，在此基础上构造了一种动态规划算法，鉴于此算法应用上的局限性，给出了SNPT(Shortest normal processing time）规则的最坏情况相对误差界，进而提出了一种基于SNPT 规则和交换技术的启发式算法。大量算例的实验结果显示不仅算法的运行时间很少，相对误差也很小（平均相对误差和最大相对误差分别为0.082％和3.448％），并且将近有一半的算例能得到最优解，因此该启发式算法能够很高效的解决此类问题。而对于其他目标函数和加工时间函数下的不可续情形，通过分析与上述问题求解方法上的相似性，给出了其求解思路。
　　 （3）对于维护时段可调的单机调度问题，重点研究了加工时间恒定的问题，考虑了完工时间和这个目标函数。对于可续情形，给出了最优解的几个性质，提出了一种SPT 算法，并证明了其最优性；对于不可续情形，简单说明了其NP-难性，提出了几个与可续情形类似的最优解的性质和SPT 算法，给出了该算法最优的条件，并证明了其最坏情况相对误差界。在最优解性质的基础上，构造了一种动态规划算法和一种分枝定界算法，其中分枝定界算法的初始解是在SPT 算法的基础上利用两条性质对维护时段之前的末工件和维护时段之后的工件进行交换所得，而提出的几个下界是基于维护时段固定的相应问题。实验证明了动态规划和分枝定界这两种算法的有效性及互补性。对于加工时间可变的调度问题，首先证明了其可续情形是多项式可解的，并对此问题与相应加工时间恒定问题在求解方法上的相似性进行了总结，进而给出了不可续情形的求解思路。
　　 （4）对于多机调度问题，重点研究了维护时段固定且加工时间恒定的问题，考虑了部分可续情形下的两种目标函数。对于最大完工时间最小化问题，说明了问题的NP-难性，建立了整数规划模型，并提出了两台机器上工件互换的四条性质，进而提出了一种启发式算法，该算法首先把所有工件按LPT 算法进行分配，得到一个可行解，然后再重复把最大完工时间最大和最小两台机器上的工件进行互换以提高解的质量。该启发式算法和LPT 算法的对比实验结果验证了此算法的有效性；对于加权完工时间和最小化问题，说明了问题的NP-难性，给出了最优解的性质，进而提出了一种动态规划算法来求得中小规模问题的最优解，另外还提出了一种基于WSPT(Weighted shortest processing time）规则和交换技术的启发式算法来解决大规模问题，实验结果表明启发式算法的平均相对误差为0.463％，最大相对误差也仅为5.094％，该算法因此不失为一种比较有效的启发式算法。在此基础上，通过比较这两个问题与相应单机问题求解方法上的异同，给出了如何把单机问题的求解方法推广到相应多机问题的思路，按照这种思路，其他的三类多机问题即可得到解决。

目录

文摘

英文文摘

论文说明：图表目录

声明

第一章绪论

第二章文献综述

第三章维护时段固定且加工时间恒定的单机调度问题

第四章维护时段固定且加工时间可变的单机调度问题

第五章维护时段可调的单机调度问题

第六章带维护时段的多机调度问题

第七章总结与展望

附录A 定理5.4 的证明

参考文献

攻读学位期间的主要研究成果及发表论文

致谢