带有不可用区间中断可恢复的平行机排序问题

讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε0为误差精度。     

带有拒绝工件和机器具有不可用区间的单机排序问题

本文考虑带有拒绝工件和机器具有不可用区间的单机排序问题。目标是最小化被接受工件的特定加权总完工时间与被拒绝工件总费用的和。工件有不同的释放时间和权,权等于它们的加工时间。这个问题是一般NP-难的。为了能在较少的运行时间内得到该问题较好的近似解,利用削减状态空间的方法得到了一个全多项式时间近似方案(FPTAS),该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n3/ε2),其中n为输入工件的个数,ε是误差界。     

带有拒绝工件和机器维修区间的单机排序问题 (运筹学与控制论)

考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和。这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解。为了能在较少的运行时间内得到该问题的较好的近似解,利用削减状态空间方法得到了一个全多项式时间近似方案(FPTAS)。该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n2/ε2),其中n为输入工件的个数,ε>0为任意小的实数。     

带有退化、拒绝和不可用区间的单机排序问题

【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个NP-难问题,在不可用区间前、后,工件按照基本加工时间a_j的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。     

具有到达时间和禁用区间的单机平行批排序

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.     

退化工件2台机器异序车间作业排序问题

：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同。此外,每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工,也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的;然后对每个工件最多只有2个工序的问题给出了多项式算法;最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。     

带有分段线性递减加工时间和拒绝工件的单机排序问题

讨论了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标函数是极小化被接受工件的最大完工时间和被拒绝工件的总惩罚之和。这一问题是NP-难的。基于对问题的分析,给出了一个全多项式近似策略。全多项式近似策略的计算复杂性为O(n4 L4/ε3)。     

带有分段线性递减加工时间和拒绝工件的单机排序问题

讨论了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标函数是极小化被接受工件的最大完工时间和被拒绝工件的总惩罚之和。这一问题是NP-难的。基于对问题的分析,给出了一个全多项式近似策略。全多项式近似策略的计算复杂性为 O(n4L4/ε3)。
     

极小化加权总完工时间的可拒绝单机排序问题

在经典的排序问题中,工件的加工时间是固定不变的。然而,在实际生产中,工件的实际加工时间会发生变化。同时,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,即机器的不可用区间。研究带有到达时间、退化效应和拒绝工件,及机器带有不可用区间的单机排序问题。在这一模型中,工件的开始加工时间越晚,其实际加工时间越大,实际加工时间是与其开始加工时间有关的函数。该问题中工件允许被拒绝。如果工件被拒绝,那么需要支付拒绝惩罚。讨论的目标函数是接受工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先说明该问题是一般意义NP-难的,进而利用划分程序的方法给出了一个全多项式近似方案,最后分析了该近似方案的时间复杂性。     

一种工件可拒绝的有界批量分批排序问题研究

研究了一类极小化加权总完工时间的可拒绝分批排序问题.首先证明了该问题是NP-难的,然后对于所有工件的加工时间相同的情况,给出了时间复杂性为O（n2）的动态规划算法,在此基础上,对于工件有两种到达时间的情况给出了多项式时间算法.