论文部分内容阅读
排序问题一直以来是经典组合优化问题之一，近几十年来，正被越来越广泛地应用于生产与制造领域。本论文研究了带有时间窗口约束的排序问题，可以被看作是一个新的资源约束模型，其在柔性制造系统和印刷电路板组件等方面具有潜在的应用。论文分为四章，重点研究了近似算法的设计与分析。 第一章主要简要介绍了排序问题的一些相关知识和国内外研究的现状，提供了几个经典排序问题的复杂性及其算法，同时也对启发式算法与近似算法进行了一些简单介绍。 第二章研究了带单位时间窗口约束的单机排序问题。要求任意单位时间内最多只允许B个工件进行加工，对B2与B3两种情况分别设计了近似算法，并证明当B=2时，算法目标值(此次公式省略)；当B=3,4时，（此次公式省略），当B≧5时，（此次公式省略）。 第三章在第二章的基础上，讨论了带单位时间窗口约束的两台平行机排序问题。要求任意单位时间内两台机器上最多允许B个工件进行加工。分析了LPT与LS两个经典算法的近似性能，当B=2时，对LS算法有（此次公式省略）；对LPT算法（此次公式省略）；而当B≧3时，对LS算法有（此次公式省略） 第四章研究了一类带外包选择的单机排序问题。假设仅有一台本地机器和一个外包承包商，每个工件既可以在本地机器上加工又可以外包商处加工。本地加工的费用为总误工工件数，外包加工的费用与外包工件有关。对于极小化总加工费用这一NP难问题，给出伪多项式时间动态规划算法。如果外包费用正比于外包工件的加工时间，设计出近似算法并给出最坏情况分析。 第五章，我们对本文进行了归纳与总结，并对未来的相关研究工作作了展望。