工件具有学习与恶化效应的现代排序问题研究

摘要

排序问题是一类重要的组合优化问题，是运筹学的一个重要分支。经典的排序问题中，工件的加工时间一般被认为是常数。然而由于一些实际因素的影响，被加工的工件的实际加工时间是可变的。这样的因素很多，如:工件的加工位置、开工时间等。由此，产生了具有学习效应与恶化效应的现代排序问题。由于诸多因素的影响，所以这些问题大多情况下比经典排序问题更难于解决，很多都属于NP-难问题。处理NP-难问题，本文给出了基于某些特殊情下该类问题算法的最坏情况界并提出它们的有效算法。某些带有学习效应与恶化效应的现代排序问题是存在多项式算法的，研究这类问题也是非常有价值的。若该类问题存在多项式算法不但可以解决该类问题，也为与其相似的NP-难问题提供近似算法。对于工件具有学习效应与恶化效应的现代排序问题，本文做了如下的几个的面的工作:
　　1.在学习效应的环境下的现代排序问题。
　　(1)学习效应与工件在加工中所处的位置相关的排序问题，在单机情况下，讨论了三个不同的目标函数分别为:加权完工时间和、最大延迟和误工数。并且针对这三个问题的一些特殊情况，证明了它们是多项式时间可解的，也给出了三个最坏情况界。
　　(2)学习效应与工件位置相关并且带有松弛工期的单机排序问题，研究了极小化提前成本、延迟成本和工期的松弛的加权和，将此问题转化成为了指派问题，同时给出多项式时间最优算法。
　　(3)学习效应与工件的加工时间和相关的排序模型，解决了0＜α＜1（α为学习效应）时极小化完工时间问题是多项式时间可解的，最优排序可以按照工件正常加工时间从大到小排列得到。对于该模型的完工时间和问题，给出了最优解具有V-型性质。
　　(4)学习效应与工件正常加工时间的对数和相关的单机成组排序问题，给出了当目标函数为极小化最大完工时间时的多项式时间算法。
　　2.工件具有恶化效应的现代排序问题。
　　(1)具有依赖时间恶化的单机排序模型，对于该问题的极小化最大完成时间证明了该问题是多项式时间可解的，极小化完工时间和问题证明了最优排序中工件排列存在V-型性质。
　　(2)具有恶化效应的单机成组排序模型中，证明了目标函数为极小化最大完工时间的最优排序存在多项式时间算法。
　　(3)变速机排序问题中带有恶化维护情况下，证明了n个工件，m台带有恶化维护的变速机的极小化完工时间和问题的计算复杂性为:O(nm+3)。
　　3.同时具有学习效应与恶化效应的现代排序问题。
　　(1)工件具有恶化效应和与工件的加工位置相关的学习效应的排序问题，给出了目标函数为加权完工时间和与最大延迟的最坏情况界，用数值算例说明了最坏情况界的有效性。
　　(2)工件具有恶化效应和指数学习效应的排序问题，给出了目标函数为加权完工时间和与最大延迟的最坏情况界，用数值算例说明了最坏情况界的有效性。
　　(3)讨论了与工件的加工时间的和相关的学习效应同时还与开工时间相关的恶化效应的单机排序问题，解决了该问题的极小化最大完工时间问题。