单机主次指标排序问题(英文)

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax.在同工期且准备时间和工期具有一致性的情形下,给出了该问题的允许中断抢先的多项式时间算法.     

加工时间和工期一致的单机主次指标排序问题1｜｜∑U｜Tmax

本研究了单机主次指标排序问题1||∑U|Tmax。在加工时间和工期具有一致性的情形下，给出了该问题的多项式时间算法。     

处理机具有准备时间的Qm,aj｜pj=1｜Cmax排序问题

讨论了处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题,通过这一问题的一个下界,给出了一个最优算法,算法的复杂性为O（m^2）。     

问题1|d_j=d|Σw_jT_j的一个全多项式近似方案

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充.     

加工时间依赖资源的流水作业资源分配问题

本研究加工时间受资源影响的流水作业时间表长问题。对问题F2|chain，∑（j=1，n）μj≤U|Cmax给出了问题求最优解的多项式时间算法。     

问题Pm|rj,B|∑Cj的多项式时间近似算法

本文针对同型机分批排序问题Pm|rj,B|∑Cj进行了研究,给出了该问题在批容量B及机器台数m为常数情况下的多项式时间近似算法(以下简称PTAS);在B为常数时设计出了问题1|rj,B|∑WjCj的计算时间更少的PTAS．     

几类任务到达时间受资源约束的单机排序问题

本研究了任务到达时间受资源影响的，与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法，对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法；还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。     

相容工件系统的最小化最大延迟与误工和的重新排序

在单机重新排序问题中,一个原始工件集已经排好顺序,使得给定的目标函数最小．当一个新的工件集到来时就会产生一些错位,决策者需要插入新工件到原来排序中而还不能过分打乱它们的顺序．该论文首先研究了当工件加工时间和工期相容时,在错位量限制的条件下最小化最大延迟问题;也研究了当工件加工时间相同或工件工期相同时,在错位量限制的条件下最小化误工和问题．对这些问题,给出了好的算法．     

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

成组加工中带可分配工期的最大延误问题

研究成组加工中带可分配工期的最大延误问题的排序与工期分配,对于成组加工中带可分配工期的最大延误问题的不同模型,或给出其最优序．或证明其是NP-难问题．     

Flow Shop排序问题Fm|prmu|∑w_jC_j的分枝定界法

本文讨论FlowShop排序问题Fm|prmu|∑ωjCj给出了求解该问题的一个分枝定界法．     

单机两组工件继列分批与平行分批混合排序

研究单机两组工件继列分批与平行分批混合排序.在问题中有两组工件J^A和JA和J^B.A-工件可以在平行批中进行加工,B-工件可以在继列批中进行加工.对若干正则目标函数给出了多项式时间算法.主要结果如下:·排序问题1|s-p-batch,s(B),(∞,∞)|L_(max)在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|∑C_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,p_j=1,s(B),(b(A),b(B))|∑w_jC_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|f_(max)可以在时间界为O(log(max_jf_j(M))×(nlogM+n_An_Bn))内可解.其中,M是工件完工时间的一个上界.     

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,rj,pmtn|∑j Uj.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n4+m log m),其中m和n分别是固定工件数和自由工件数.     

半线性摄动电报方程的渐近理论及应用

对二阶半线性摄动电报方程的初值问题.本交给出了一个渐近方法.证明了渐近理论及形式近似解的合理性都在时间变量无穷大时(即0≤t≤O(|ε|-1)成立.作为浙近理论的应用,我们对一个带初问题的特殊电报方程进行了研究,得到了两个|ε|-1阶渐近近似解.     

柔性工期下的资源受限项目调度双目标优化研究

在项目调度过程中,活动工期应根据项目截止工期以及资源供给情况进行合理设置,而在传统的资源受限项目调度问题(RCPSP)中,活动的工期往往是已知且固定的,这在一定程度上限制了项目调度的灵活性。多模式下的项目调度方式虽然弥补了这一缺点,但其提供的工期-资源组合种类固定且有限,并不一定能保证包含最优的工期-资源组合。本文将活动工期作为项目调度问题的决策变量,允许其在一定范围内取值。这种柔性工期调度方式虽然增加了项目调度难度,但提高了项目调度灵活性,同时可以起到压缩项目完工时间的作用。为验证柔性工期调度方式对项目工期和成本的影响,本文建立了工期-成本双目标权衡优化模型,设计了两阶段嵌套算法(NSGAⅡ-RS)对其求解,实验证明,柔性工期调度策略是一种鲁棒性较好的项目完工时间压缩策略。     

工件加工可拒绝的无界批量分批排序问题的几点探讨

本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑ωjTj+TP和1|B≥n,rej|∑ωj+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.     

MDD函数在单机总误工排序问题中的作用

本文把工件的修正工期（MDD：Modified Due Date）看成工件关于时间的函数，通过研究该函数在一定区间的性质建立了一个具有全局意义的定理，利用这个定理可以方便地导出有关单机总误工排序问题的一些重要结论．这些工作既能够很好地解释常用的MI）D规则的有效性，同时也说明MDD函数可以成为解决单机总误工排序问题的基本工具．     

一类四阶抛物型方程的解的渐近行为

本文考虑一维空间中四阶抛物型方程Cauchy问题{ut-(e)2xu+(e)4xu=(e)xf(u), x∈R,t＞0,u(x,0)=u0(x), x∈R,的整体解u=u(x,t)的大时间渐近行为和时间衰减速率,其中f(u)∈C1(R), |f(u)|≤C|u|q, q＞5/2.     

考虑运营期收益的项目建设期时间/费用交换问题(TCTP/R)研究

给出了考虑运营期收益的项目建设期时间/费用交换问题DTCTP/R的概念,讨论了项目工期/收益的函数关系,建立了优化的数学模型,并且将遗传算法应用于问题的求解.最后,结合一个案例说明了在对建设期优化时,应当考虑其对项目运营收入的影响,从全局的角度来进行时间/费用的优化,所得结果才准确与可靠.