若干带拒绝费用的分批排序问题研究

首次考虑了工件可拒绝的单机串行分批排序问题.对于问题1,s｜s-batch,rej｜Cmax＋Σ j∈ ej,均给出了最优算法;对于问题1,s｜s-batch,rej｜Σ j∈s Cj＋Σj∈ ej,通过动态规划算法给出了多项式时间的精确算法.研究了问题1｜B〈n,rej｜Σj∈s wjCj＋Σj∈ ej中工件加工时间均相等的特殊情况.     

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

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

工件可拒绝排序问题的研究

用凸二次规划松弛方法研究工件具有就绪时间，目标函数为工件总拒绝费用与接受工件的带权总完工时间之和的工件可拒绝排序问题，得到界为2的多项式时间近似算法．     

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

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

三台平行机上四个约束链的排序问题

考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.     

工件可拒绝平行机排序

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

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

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

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题，资源约束是指每个机器最多加工κ个工件．首先对一般情况下的同型机的PLPT排序进行了讨论；并首次对同类机排序进行了研究，给出了一个FLPT近似算法，同时对m=2时证明了PLPT排序的最坏情况紧界是2．     

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

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

同型号平行机器排序问题中近似解的一种改进方法

利用首先完工准则关于初始加工时间的数学性质，讨论一种对同型号平行机器的排序问题中的近似解进行改进的方法．一些实例的计算结果表明，这一方法能有效的提高近似解的精度．     

二机流水作业带不可用区间、工件可拒绝的调度问题

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.     

凸二次规划松弛方法研究离散加工时间可控排序问题

离散加工时间可控的排序问题,得到界为3/2的多项式时间近似算法。     

混合量子衍生进化规划算法及其在并行机拖期调度中的应用

针对并行机调度问题的求解,提出一种新的混合量子衍生进化规划算法(Hybrid Quan-tum-Inspired Evolutionary Programming,HQEP)。目标函数是最小化所有工件的拖期总和。HQEP将量子进化算法中的量子位、线性叠加态和量子旋转门的概念引入到进化规划算法中。定义了新的用于调度问题的量子旋转角,使个体向更好的解靠近。此外,针对并行机问题本身,改进了个体的编码方式和新的变异方法。为了验证算法的有效性和收敛性,将HQEP算法应用于同等并行机调度拖期问题的求解并加以不同规模的算例进行仿真实验。结果显示,即使在小种群情况下,所得解均优于进化规划求得的解。     

三台平行同型机的一个半在线排序算法

本文研究三台平行同型机的一个半在线排序算法，我们假设工作的最大加工时间预先知道，我们将给出一个竞争比为（1＋√73)/6≈1.5907的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是√2.     

凸二次规划松驰方法研究离散加工时间可控排序问题

用凸二次规划松弛方法研究离散加工时间可控的排序问题,得到界为3/2的多项式时间近似算法。     

并行多机成组工件调度的启发式算法

N个成组工件将在M台并行一致的机器上加工,当一个工件接在不同组的工件之后时需要装设,而接在同组工件之后时不需要重新装设,目标函数是使总的通过时间最小·利用最优解的必要条件,将单个工件组成基本运行,在研究基本运行组合规则的基础上,提出了一个基于基本运行的并行多机成组工件调度的启发式算法·在中、小规模水平问题上,将启发式算法的结果与最优解的结果进行了比较·效果令人满意·实验证明该启发式算法能够有效地解决成组工件调度的实际问题,具有解决中大规模实际问题的潜力·