论文部分内容阅读
排序作为组合优化领域的一个重要分支，正被越来越广泛地应用于生产与制造领域。其中，带有库存约束的排序和含有服务器的排序是两类新型排序模型。前者是建立在车辆调度与仓库管理这一实际背景下的排序模型，而后者则在网络计算、纺织行业、钢铁工业等方面有着重要的应用。本文主要研究这两类排序问题，核心工作是建立它们的数学模型、设计算法并分析算法的性能。全文共分为五章。 第一章首先介绍排序、计算复杂性、近似算法等基本概念，接着简要综述经典排序研究的理论与算法，最后阐述本文拟研究的排序模型。 第二章，我们研究了单台机器带有库存约束的排序问题。这一章主要包括两个部分。第一部分考虑的是负工件个数只有一个的问题1｜inv,｜n-｜=1｜∑w1c1。我们首先给出了问题复杂性的证明，紧接着给出了贪婪算法，尽管算法的最坏情况界是无穷大，但随机试验表明算法的平均性能十分优越。第二部分，我们对负工件个数为任意多个的问题1｜inv,｜n1｜∑C1(n1≧1,n1∈Z+)进行了研究，给出了解决问题的0-1整数规划模型，同时设计了贪婪-合并算法，并采用随机试验说明算法的平均性能同样是非常优越的。 第三章，我们对含有一个服务器的m台平行机器排序问题进行了研究。在每个工件加工之前必须由一台公共的服务器将它们安装到机器上然后才能在机器上开始加工。每个工件在机器上的加工时间相同。这一章主要分为两个部分。首先，我们研究了问题p,s1｜s1,p1=p1｜Cmax证明了SPT算法的最坏情况界不超过2-1/m，且是紧的。紧接着，我们证明了对于问题p,s1｜s1,p1=p｜∑C1,SPT算法的最坏情况界不超过3/2。 第四章进一步讨论了当机器数量较少时含有单个服务器的排序问题，目标函数是极小化工件的完工时间总和。对于2台机和3台机的情形，我们分别证明了SPT算法的最坏情况界不超过2和6-1。 第五章，我们对本文进行了归纳与总结，并对未来的相关研究工作作了展望。