一个可中断三台可拒绝平行机半在线排序问题

研究了工件带有拒绝费用的3台平行机半在线算法。工件逐个到达，当工件到达时可以被接收加工，消耗一定的加工时间，也可以被拒绝，但此时要付出一定的拒绝费用。进一步假定工件的加工时间与拒绝费用事先成固定比例α(α≥=0)。目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小。针对工件加工可中断情形，设计出半在线算法ARH，并证明算法ARH的竞争比为关于参数α的分段函数，且为紧界。
     

特殊情形下的两台可拒绝同类机在线排序问题

研究了工件带有拒绝费用的两台同类机在线算法,两台机器的速度分别为1和s,s∈[1,+∞),工件逐个到达,当工件到达时,可以选择被分配到机器上进行加工并花费一定的加工时间;也可以被拒绝,但此时需付出一定的拒绝费用。进一步假定每个工件的加工时间与拒绝费用成固定比例α(α≥0),即p_j=αt_j。目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小,工件的加工不可中断。本研究设计一种在线算法URLS,并证明该算法的竞争比和下界均为关于参数α的分段函数,且当α∈[0,(s+1)~(1/2)/s+1)∪[1,+∞)时上下界相吻合,算法达到最优。     

特殊情形下的两台可拒绝同类机在线排序问题

研究了工件带有拒绝费用的两台同类机在线算法,两台机器的速度分别为 1 和 s ,s ∈ [ 1 , +∞ ),工件逐个到达,当工件到达时,可以选择被分配到机器上进行加工并花费一定的加工时间;也可以被拒绝,但此时需付出一定的拒绝费用。进一步假定每个工件的加工时间与拒绝费用成固定比例 α ( α ≥0 ),即 pj =αtj 。目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小,工件的加工不可中断。本研究设计一种在线算法 URLS ,并证明该算法的竞争比和下界均为关于参数 α 的分段函数,且当 * 时上下界相吻合,算法达到最优。(注：*处代表公式)
     

两台具有服务等级的可拒绝平行机排序问题

研究了工件具有服务等级且可拒绝的平行机排序问题.设有两台平行机,加工速度相同;n个工件分别按列表在线到达,每个工件含有三个参数:加工长度,拒绝费用以及服务等级g_j=1,2.当且仅当g(Mi)≤gj时,工件J_j可由机器M_i加工,且加工不允许中断.进一步,当工件到达时,可以选择被加工,花费一定的加工时间;也可以被拒绝,此时要付出相应的罚值.目标为使被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.文中设计出在线算法H,并证明算法的竞争比为1+(2~(1/2)/2)≈1.707,下界为5/3≈1.667,上下界大约相差0.04.     

工件有工期并且可拒绝单机最小化最大提前时间的排序问题

研究工件有工期并且可拒绝的单机最小化最大提前时间的排序问题.若工件被拒绝,则需支付一定的惩罚费用;若工件被接受,则将该工件安排在机器上加工.目标函数是最小化被接收工件的最大提前完工时间与被拒绝工件的惩罚费用之和.通过对该排序问题的Pareto最优点的分析,得到该问题的多项式算法.     

工件可拒绝的在线同类机排序

针对带有惩罚费用的工件在同类平行机上的在线排序问题,目标函数为极小化被接收工件的最大完工时间加上被拒收工件的总拒绝费用,给出了一在线算法,证明了该算法的竞赛比不超过,有Z^on/Z^OPT≤1＋ρ。     

工件可拒绝的分批配送问题研究

考虑工件可拒绝的分批配送问题:一个制造商为一个客户加工n个工件,每个工件既可以被接受加工,也可以被拒绝加工(但要支付拒绝费用),工件加工完之后要安排车辆运送给客户,完工时间为工件送达客户的时间.目标函数为被接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,文中对处理机为单机的情形给出了多项式时间算法,且证明了两台平行机的情形下该问题是NP-完备的,并给出了伪多项式时间算法.     

工件可拒绝平行机排序

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.     

极小化加权总完工时间的工件可拒绝排序 (运筹学与控制论)

经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝,并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中,目标函数是有限的总惩罚费用(总惩罚费用约束下)极小化加权总完工时间,工件到达时间都相同的同型机问题,设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法。     

带有恶化率的可拒绝单机排序及批配送

首次考虑了加工时间带有线性恶化率的可拒绝单机排序及其批配送的问题.如果工件被拒绝,则要付出一定的拒绝费用;如果工件被接受,则要安排加工并配送.目标函数是极小化接受工件的加权总完工时间或最大延误时间,配送费用与拒绝工件的拒绝费用这三部分的和,我们不仅证明了这些问题都是NP-hard的,而且还提出了基于动态规划的伪多项式时间算法.     

带有准备时间的可拒绝供应链排序

考虑可拒绝排序中生产与配送的集成问题.有一个制造商和多个客户,不同的客户订购不同种类的工件.机器在加工不同种类的工件前要有一个准备时间.对于客户的工件制造商可以选择接受或拒绝加工,但当工件被拒绝时制造商需要支付相应的拒绝费用.每个工件有自己的工期并且生产完成后需要配送到相应的客户处,每一批配送需要花费一定的时间和费用.该文研究了排序理论中几个主要的目标函数,给出了相应的动态规划算法并分析了算法的复杂性.     

带有学习效应和退化效应的可拒绝排序问题

讨论了具有学习效应和退化效应的多窗口的可拒绝单机排序问题。工件的实际加工时间与开始加工时间和所排位置有关。工件集分为接受工件集和拒绝工件集,对于被拒绝加工的工件而言,它的费用只与工件有关,目标是确定接受工件集的最优加工顺序和拒绝费用,从而极小化2个费用函数。考虑2个问题,第1个问题的目标函数是与提前、延误、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,第2个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,并且针对这2个问题分别给出了多项式时间算法。     

极小化最大完工时间及拒绝费用的单机可拒绝分批排序

首次考虑了工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划算法给出了多项式时间的精确算法,借助于数据结构中的堆排序,我们将算法复杂性降低为O(n2logB).     

带有不可用区间的单机排序问题

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。一个工件或者被拒绝加工,或者被接受。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。在张丽琦工作的基础上增加了一个不可用区间,机器在此区间内不能加工工件,并且在同一时刻至多加工一个工件。目标函数是最小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出一个动态规划算法,然后通过构造输入,将拒绝惩罚进行取整运算,再通过动态规划算法,得到拒绝惩罚取整后的一个最优排序,按照这个工件排序得到原问题的一个可行排序,最后借助一个3—因子算法得到一个全多项式时间近似方案。     

带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究)

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε)     

具有指数学习效应和恶化效应的可拒绝单机排序问题

讨论了带有工期窗口的单机排序问题。规定每个被接受的工件都有1个待定的交货期窗口,且所有工件的交货期窗口大小相同。工件的实际加工时间为与其开始时间和位置有关的指数函数。1个工件或者被拒绝,或者被接受。被拒绝就要支付拒绝的费用;被接受就会产生相应的提前、延误惩罚以及最大加工时间的惩罚。研究了2个问题,都需要确定工件的最优排序和窗口的开始时间,第1个问题的目标函数是与窗口的开始时间、窗口的大小、提前时间、延误时间、最大完工时间以及拒绝费用有关的函数。第2个问题的目标函数是与窗口的开始时间、窗口的大小、提前和延误的工件数、最大完工时间以及拒绝费用有关的函数。该问题在多项式时间可解,给出了问题的多项式时间算法。     

带有不可用区间及拒绝的最大完工时间单机排序问题

研究带有退化效应、拒绝工件及不可用区间的单机排序问题。该问题中,工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。加工工件的开始加工时间越晚,则工件的实际加工时间越大。机器带有不可用区间,在此区间内任何工件都不能被加工。目标函数为所有拒绝工件的拒绝惩罚与接受工件的最大完工时间之和。首先给出了拟多项式时间的动态规划算法,最后得到了一个全多项式近似方案。     

带有不可用区间及拒绝的最大完工时间单机排序问题

研究带有退化效应、拒绝工件及不可用区间的单机排序问题。该问题中,工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。加工工件的开始加工时间越晚,则工件的实际加工时间越大。机器带有不可用区间,在此区间内任何工件都不能被加工。目标函数为所有拒绝工件的拒绝惩罚与接受工件的最大完工时间之和。首先给出了拟多项式时间的动态规划算法,最后得到了一个全多项式近似方案。
     

运筹学与控制论两台平行机环境下加工时间退化的可拒绝排序问题

研究两台平行机环境下加工时间线性退化的可拒绝排序问题，工件的实际加工时间是关于该工件开始加工时间的线性函数，每个工件都有一个独立的截止工期，在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝，如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合，找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此 NP 难问题可以通过动态规划方法求得最优解，并通过动态规划运用简化执行空间的方法给出了复杂度为o(n5D2/ε2)的全多项式近似策略（FPTAS），其中 n 表示工件的数量，ε 是允许误差界。
     

带有退化工件和拒绝的不同类型机排序问题

在工业生产过程中,由于一些特殊的原因,工件可以被拒绝加工但要付出相应的费用,即拒绝惩罚。为了节约处理成本,加工时间长的工件或者加工所需的费用高的工件,可以支付一定的费用来进行外加工或购买。将退化和拒绝结合起来考虑,讨论带有退化工件和拒绝的不同类型机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数,其中工件的退化率只与机器有关,与工件本身无关。目标函数是极小化接受工件的排序指标与拒绝工件总惩罚之和。排序指标分别为总时间表长和总完工时间。目的是找到拒绝工件集和接受工件集,并安排接受工件的加工顺序,使所求问题的目标函数值最小。通过将2个问题的目标函数转化为指派问题,证明了他们都是多项式可解的。