一个可拒绝分批排序的NP-困难性及其FPTAS算法

摘要

一直以来,排序理论都是组合优化领域的一个热门方向,有着坚实的理论背景和深刻的实际意义,它产生的主要背景是机器制造,后来被广泛应用于计算机科学、管理科学、工农业生产、交通运输等许多领域。从普通的生产部门的计划安排、人员调度,学校课程表的制定,到宇宙飞船的复杂庞大的飞行计划,都要用到排序的理论和算法。从50年代起,人们就一直努力于排序问题理论与实践的研究,已经取得了许多有意义的成果。可拒绝排序和分批排序都是比较新颖的现代排序模型,本文主要讨论了这两个模型,做了以下一些工作。
　　论文共分三章。
　　第一章首先介绍了排序问题的应用背景及表示形式,接着给出了必要的预备知识,简单介绍了本文涉及的基本定义和定理,最后概述了本文研究的主要问题以及研究成果。
　　第二章主要考虑了工件带有拒绝费用的排序问题:可拒绝的排序问题是近年来出现的一类新型排序问题,为了满足现实需要,在加工时需要进行更高的决策,拒绝某些工件的加工,并支付一定的拒绝费用。在这一章中我们首次考虑了目标函数为极小化最大延误(最大延迟)与被拒绝工件的惩罚费用之和的单机无界平行批排序问题,利用二划分问题证明了问题1|B≥n,rej|Tmax+TCP为NP-困难的。
　　第三章继续讨论问题1|B≥n,rej|Tmax+TCP,给出了一个基于动态规划的O(n2∑Wj)时间的伪多项式时间算法,接着给出了2-近似算法和FPTAS。最后在本文证明的基础上,对目标函数是Lmax的情况进行了简单的讨论。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

第二章 一个可拒绝分批排序的NP-困难性的证明

第三章 一个可拒绝分批排序的动态规划算法和近似算法

参考文献

致谢