论文部分内容阅读
排序问题的大部分文献都假设机器总是一直可用的.然而在实际生产过程中并非如此.本学位论文考虑的是机器并非是一直可用的,即机器具有一个不可用区间.这里的不可用区间分两种模型:一是机器具有一个可变的维护区间;另一个是机器具有一个操作员不可用区间.在可变的维护区间内,工件是不允许加工的,且该维护区间的开始时间是提前知道且固定的,维护工期(维护区间的长度)是关于维护活动开始之前机器装载量的非负不减的函数.与机器的不可用区间相比,操作员不可用区间允许加工工件,但在该区间内,工件不能开工或者完工.另外,工件可拒绝指的是每个工件可能被接收并在机器上进行加工,也可能被拒绝并支付相应的拒绝费用.本文综合考虑了以上因素,我们首先研究机器具有可变的维护区间和工件可拒绝的两个单机排序问题,接着又研究了机器具有操作员不可用区间和工件可拒绝的单机排序问题.本文研究的内容主要分为三部分.第一部分研究机器具有可变的维护区间和工件可拒绝且具有相同的到达时间的排序模型.第二部分研究机器具有可变的维护区间和工件可拒绝且具有不同的到达时间的排序模型.第三部分研究机器具有操作员不可用区间和工件可拒绝且具有相同的到达时间的排序模型.我们用h1表示机器具有一个可变的维护区间,用ona(1)表示机器具有一个操作员不可用区间,用wldmt表示维护工期与机器的装载量有关,用reject表示工件允许被拒绝.在第二章,我们所研究的排序问题:工件具有相同的到达时间最小化接收工件的最大完工时间与拒绝工件的总费用之和的单机排序问题:1,h1,wldmt|reject|Cmax(A)+ W(R).针对上述问题,在第2.2节,我们给出了一个动态规划算法.在第2.3节,我们给出了一个近似算法并证明了该算法的近似比为2.在第2.4节,我们给出了特殊情形下的一个全多项式时间近似方案.在第三章,我们所研究的排序问题:工件具有不同的到达时间最小化接收工件的最大完工时间与拒绝工件的总费用之和的单机排序问题:1,h1,wldmt|rj,reject|Cmax(A)+W(R).针对上述问题,在第3.2节,我们给出了一个动态规划算法.在第3.3节,我们给出了一个近似算法并分析了该算法的近似比为3.在第四章,我们所研究的排序问题:机器具有操作员不可用区间且工件具有相同的到达时间最小化接收工件的最大完工时间与拒绝工件的总费用之和的单机排序问题:1|ona(1),reject|Cmax(A)+W(R).针对上述问题,在第4.2节,我们给出了一个近似算法且证明了该算法的近似比为2.