【摘 要】
：
排序问题一直是组合优化领域的一个热门方向，有着坚实的应用背景和深刻的理论意义．带尺寸的分批排序、可拒绝排序都是比较新的排序模型，本文就这两个模型做了以下一些工作： 1．
论文部分内容阅读
排序问题一直是组合优化领域的一个热门方向，有着坚实的应用背景和深刻的理论意义．带尺寸的分批排序、可拒绝排序都是比较新的排序模型，本文就这两个模型做了以下一些工作：
1．本文主要对带尺寸的分批排序极小化完工时间和的问题进行了研究．对于问题1｜B，s<,j>=1｜∑C<,j>，运用拆分的技巧首次给出了近似比是常数的三个近似算法，近似比分别是4，2，和3/2．此外我们还给出例子表明后两个算法所给的界是紧的．接下来针对问题1｜B，s<,j>｜∑C<,j>，对已有的几个算法进行了分析，说明这几个算法的最差性能比是无穷大．
2．首次对可拒绝的分批排序问题1｜B≥n，rej｜∑ω<,j>T<,j>+TP和1｜B≥n，rej｜∑ω<,j>U<,j>+TP进行了研究，在已知它们是NP-困难的基础上，我们给出厂伪多项式时间精确算法以及FPTAS算法．这是最好的精确算法和近似算法；因为对于NP-困难问题，最好的精确算法就是伪多项式时间算法，而最好的近似算法也只能是FPTAS算法．
其他文献
本文基于Berm dez-Moreno广义对偶方法提出了用于求解变分不等式的具最优参数的Berm dez-Moreno对偶径向基函数伪谱方法,简称BM-RBF方法,即利用B-M算法将原问题转化为迭代格
算子代数间的局部映射问题主要是研究算子代数间的映射在每一点的局部性质(如局部导子，局部自同构，局部等距等)能否决定该映射的某种整体性质，这已成为算子代数理论的一个研究热
一块挪威的冰鲜三文鱼，从加工出厂到最后配送到消费者手上需要经过繁复的周转腾挪。如何确保新鲜成了生鲜电商发展面临的最大技术门槛之一。 全程冷链是生鲜电商食品保鲜的最重要保障，建设、维系冷链则需要巨大资金投入。为弥补冷链短板，“泡沫箱加冰袋“组合成为目前配送生鲜产品“最后一公里”的主流模式。可这种生鲜包裹往往混迹在普通快递中，遇上天气炎热或者配送超时，就会有冰袋化冻，生鲜变质的风险。 对于目前的生
本文介绍了径向基配点法(RBF)、伪谱方法(PS)与几种非重叠型区域分解方法(DDM),并给出了三种非重叠型径向基配点区域分解法(RBF-DDM)和伪谱区域分解方法(PS-DDM)的算法框架,
本文分别对一些图类的泛圈性质，最长圈，和可靠性参数进行了研究。 全文分为三部分，分别介绍了有关图的泛圈性质，最长圈和网络可靠性参数的一些研究结果。 第一部分只含第一
矩阵半群理论是矩阵理论的重要分支之一，许多专家学者对其进行了深入的系统研究．本文主要研究了(0，∞)-矩阵半群和有限链K上的矩阵半群． 第一章，我们对矩阵理论的研究背景、现