论文摘要
排序论,也可被称为时间表理论。它作为运筹学的一个重要部分,是一门应用性很强的科学,它有着很深的现实背景和广阔的应用前景.本文主要研究了两类可拒绝和一类半在线的排序问题。经典的排序模型中,人们往往假定机器必须加工所有的工件且它们的加工时间都是给定的。然而在许多现实应用中,如果某个工件加工时间或加工费用很大,我们就会考虑是否要加工该工件。我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。目标函数不再是传统的极小化最大完工时间,总完工时间,最大延迟等,而是同时考虑时间与费用.我们称这种排序为可拒绝排序.在大多经典排序理论中,排序问题被划分成离线和在线两种.如果工件的所有信息被提前告知,我们称它为离线的。相比之下,如果工件信息没有被提前告知,而是逐个到达,且要求该工件一旦到达便马上排序,然后下一个工件的信息才被释放,我们称这种排序为在线排序。最近几年,因为生产生活的需求,半在线（semi on-line）模型逐渐得到人们的重视。半在线排序是指早已安排好的工件不准再移动,但是在排序前早已经知道后面工件的些许信息,例如已知工件的最大加工时间等等.论文共分为三章.第一章是本文的绪论部分,主要介绍排序问题的由来、研究现状及一些必需的预备知识,并且介绍了本文的主要研究成果.第二章考虑的是两种带拒绝费用的排序问题,目标函数是在不超过总拒绝费用阀值的前提下使总完工时间和最大完工时间最小.首先,我们证明了问题都是NP-难的。然后我们针对这两个问题设计出了两个伪多项式时间的动态规划算法和FPTAS.第三章考虑的是带机器准备时间的两台同类机已知工件最大加工时间的半在线排序问题,讨论了极小化最大工件完工时间这个目标函数,并给出了一个竞争比为分段函数的近似算法.