工件加工时间非恒定的排序模型研究

论文摘要

排序问题是运筹学中一类重要的组合优化问题。在经典排序问题中，通常假设工件的加工时间是恒定的。但是在诸多有实际背景的问题中，工件的实际加工时间由于加工机器设备，工件本身以及加工顺序(位置)等因素的影响而不可能始终是恒定的。此产生一类重要的新型排序问题—工件加工时间非恒定的排序问题。一般来说，这类排序问题比经典排序问题更为复杂，绝大多数均为NP—hard问题。而对于NP—hard问题的研究，一般是研究它的多项式时间近似算法，并分析该近似算法的最坏情况界。然而由于生产实践的需要，研究某NP—hard问题一些特例的多项式时间算法是很有必要的。它一方面可以为求出该NP—hard问题一些特例的最优解提供方法，另一方面也可以为解决原NP—hard问题提供近似算法，从而使排序理论更好地服务于生产实践。本文主要对工件加工时间非恒定的排序模型进行了研究。并在以下几个方面做了一些探讨： 1．本文介绍了有关排序问题，计算复杂性，近似算法以及最坏情况界等基本概念，并对近年来出现的各种工件加工时间非恒定的排序模型及其有关结果作了简要的归纳。 2．对工件加工时间是其正常加工时间和开始加工时间的线性函数的排序模型。 (1) 对目标函数为加工全程的单机排序问题，给出了相应的最优算法；对于加权总完工时间的单机排序问题证明了其为NP—hard的 (2) 对机器具有某种优势关系的流水作业排序问题进行了研究，取目标函数分别为加工全程和完工时间之和，对它们分别给出了最优算法。 3．对工件加工时间是其开始加工时间的线性函数的排序模型。 (1) 对工件间有调整时间和没有调整时间的单机排序问题，以加工全程，加权完工时间之和以及最大延误等为目标函数作了研究，并给出了相应问题的最优算法或者证明了其计算复杂性。 (2) 对目标函数为极小化最大完工时间和极大化最小机器完工时间的平行机排序问题进行了探讨，分别给出了近似算法并分析了相应的性能比。 (3) 证明了工件具有调整时间的两台机器的流水作业排序问题是NP—hard的，讨论了机器具有一定优势关系下的一些特殊情况，对目标函数为极小化最大完工时间的情形给出了最优算法。 4．对具有学习效应的排序模型。 (1) 提出了一种新的具有学习效应的单机排序模型，并对目标函数为极小化最大完工时间，完工时间之和，超前迟后，多目标函数以及一些经典的目标函数的情况进行了研究。并分别给出了最优算法。 (2) 针对流水作业排序问题，首先研究了目标函数为最大完工时间和完工时间之和的情况，给出了相应问题的近似算法并分析了其性能比。其次对机器具有某种优势关系的情形进行了探讨，对目标函数为最大完工时间问题给出了最优算法。同时还讨论了工件具有线性学习效应的流水作业问题。

论文目录

• 摘要,关键词
• Abstract,Keywords
• 第一章 绪论
• 第二章 工件加工时间是其正常加工时间及开始加工时间的线性函数的排序模型
• §2.1 前言
• §2.2 工件具有相同正常加工时间的二类单机排序问题
• §2.3 工件具有相同正常加工时间的流水作业排序问题
• §2.4 工件具有相同退化率的流水作业排序问题
• 第三章 工件加工时间为其开始加工时间的线性函数的排序模型
• §3.1 前言
• §3.2 工件成组加工时的单机排序问题
• §3.3 工件间具有调整时间的单机排序问题
• §3.4 平行机排序问题
• §3.5 机器具有优势关系的流水作业问题
• 第四章 具有学习效应的若干排序模型
• §4.1 前言
• §4.2 具有共同学习效应的单机排序问题
• §4.3 学习效应与工件相关的单机排序问题
• §4.4 工件同时具有退化和学习效应的单机排序问题
• §4.5 工件具有学习效应的流水作业排序问题
• §4.6 工件具有线性学习效应的流水作业排序问题
• 第五章 工件具有线性退化加工时间的半在线排序模型
• §5.1 前言
• §5.2 具有相同的机器准备时间的半在线排序模型
• 第六章 结论与展望
• 参考文献
• 作者在攻读博士学位期间公开发表的论文