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

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

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

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

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

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

单台机器有使用限制的排序问题

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.     

多纤波分复用链网与环网中的利润极大化问题

考虑多纤波分复用链网与环网中的利润极大化问题, 分别给出了多项式时间精确算法和2 近似算法. 对于环上各边光纤数目相同的均匀模式, 给出了1.582 近似算法. 这些结果也适用于有向链网与环网.     

用模拟退火算法求解无向排列的反转排序问题

分子生物学中基因元方向的反转基因组重排问题在数学上已被证明是一个NP-难问题。目前，较好的算法是Christie(2001)的3／2-近似算法，本文给出一种适合于计算基因元方向的反转基因组重排问题的模拟退火算法，定义了解的邻域结构，数据实验的结果表明该算法性能优于3／2-近似算法。     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

针对不确定执行时间任务的实时调度方案

为了解决在实时调度系统中,任务执行时间不确定性所带来的问题,提出了基于时间预测的调度方案。该方案设计了VSM(vectorspacemodel)模型、Markov模型和MVSM(Markovvectorspacemodel)模型。对这3种模型的比较表明:基于MVSM模型的调度方案可以很好地保证实时系统的效率和稳定性,即使在处理器超载的情况下,也能自动调节,超过99%的作业可以在时间期限之前完成。采用时间预测的方法,可以较好地解决任务执行时间不确定性所带来的影响,为不确定环境下的实时调度系统提供一种很好的参考解决方案。     

Local times of N-parameter Gaussian processes

An N-parameter Gaussian stationary process X = { X ( t ): t ∈ RN+ } is introduced and the existence and joint continuity of its local times is presented. And the moments of local times are estimated. Furthermore moduli of continuity and large increment results for the local times are established.     

互联网信息组织中一个模型的对偶求解

讨论了互联网信息组织和规划的一个新问题：带拒绝装箱问题，利用原始对偶互补松弛条件给出此问题的一个最优值的下界，利用下界值对应解的性质得到带拒绝装箱问题的一个近似算法．     

装箱问题的一种新的近似算法

 研究了一维装箱问题(Bin Packing Problem),给出了一个新的近似算法:交叉装填算法(简称CF算法).证明了CF算法达到装箱问题的最好的近似值3/2;并且当这些物件的大小按非增性质预先排序后,CF算法的时间复杂度是线性的.     

Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times

Theproblemconsideredinthispapercanbestatedasfollows:AsetofnjobsJ={1,2,…,n}aregiventobeprocessedwithoutinterruptiononasetofmunrelatedparallelmachinesM={1,2,…,m},suchthateachjobonlyneedstobeprocessedbyoneofthemachines.Eachjobj∈Jisassignedagivenweightwj,denotingitsrelativeimportance;anormalprocessingtimepi,jandareleasetimeri,jdenotetheearliestpointintimewhenjobjcanbeprocessedonmachinei∈M.Theprocessingtimesofjobsarecontrollableinthefollowingmanner[1,2,6]:Thenormalprocessingtimepi,jofjobjcanb…     

具有相关调整时间的排序问题

讨论任务具有相关调整时间的排序问题 .首先把 [2 ]中关于LPT算法的结论推广到一般算法 ,然后又进一步将新的结论推广到处理机为恒速机的情况 .     

考虑时空相关随机行驶时间的车辆路径问题模型与算法

本文对一类在真实道路网络中考虑时空相关的随机行驶时间的车辆路径问题进行了研究. 首先我们建立了该问题的两阶段随机规划模型. 然后我们将用于候选解寻优的智能优化算法与用于产生评价解的随机场景的情景生成技术相结合,提出一种智能随机优化方法求解该问题. 为了有效地进行解的寻优,本文结合可变邻域下降算法提出了一种混合粒子群优化算法.最后通过一系列基于北京市区道路网络的算例实验,我们验证了所提出的混合粒子群优化算法的有效性.实验结果还表明,考虑实际交通环境中道路网络上车辆行驶时间的时空相关性,会影响最优车辆路径决策方案.     

一种确定IFSP中迭代次数下限的算法

提出了一种求解带概率的迭代函数系统（IFSP）中迭代次数下限的自动算法，该算法基于一个基本假定，从给定的多个压缩仿射变换矩阵的谱半径入手，先分别求出每一个压缩仿射变换收敛到其对应的不动点时的迭代次数，然后根据每一个压缩仿射变换使用的概率即可计算出IFSP中迭代次数的下限．理论分析和实验计算结果表明，提出的算法能有效地确定IFSP中迭代次数的下限，且在保证分形图质量的同时避免了不必要的计算开销，为快速生成高质量的分形图提供了一种有效的方法．     

Correlations for the ignition delay times of hydrogen/air mixtures

Correlations for the ignition delay times of hydrogen/air mixtures were developed using the method of High Dimensional Model Representation (HDMR).The hydrogen/air ignition delay times for initial conditions over a wide range of temperatures from 800 to 1600 K,pressures from 0.1 to 100 atm,and equivalence ratios from 0.2 to 10 were first calculated utilizing the full chemical mechanism.Correlations were then developed based on these ignition delay times.Two forms of correlations were constructed:the first one is an overall general model covering the whole range of the initial conditions;while the second one is a piecewise correlation model valid for initial conditions within different sub-domains.The performance of these correlations was studied through comparison with results from the full chemical mechanism as well as experimental data.It was shown that these correlations work well over the whole range of initial conditions and that the accuracy can be significantly improved by using different piecewise correlations for different sub-domains.Therefore,piecewise correlations can be used as an effective replacement for the full mechanism when the prediction of chemical time scale is needed in certain combustion modeling.     

基于免疫算法的无向排列的反转排序问题

提出一种基于免疫算法的无向排列的反转排序的方法，将一种免疫算子加入到遗传算法的框架中，通过对个体接种疫苗来进一步提升个体的存活能力。数据实验的结果表明，该算法性能优于Christe提出的3/2-近似算法。     

工件尺寸不同的并行机批调度问题

考虑并行批加工机上不同尺寸工件的调度问题；目标是极小化最大完工时间.给出了一个(2+ε)-近似算法，ε＞0可以任意小.     

加权总完工时间有限的资源约束单机排序问题

讨论工件加工时间依赖于分配给它的一类资源，且加权总完工时间有限，目标函数为极小化资源总量的单机排序问题，对问题1，给出了一个有关最优解中最优资源使用的重要性质并利用该性质，对于bj=b，wj=w,aj=a这种特殊情况给出了最优算法．     

具有切换时延的光交换机抢占式调度技术研究

提出了一种新颖的2-近似启发式算法，对具有切换时延的光交换机进行调度．算法主要包含两步操作：匹配选择和权重判决．匹配选择通过贪心算法实现，它决定了交换机内核的配置情况；权重判决确定了交换内核配置的持续时间，其实现机理为：对于给定的匹配，所选择的权重要使得剩余业务矩阵的估计成本为最优．该算法的时间复杂度为O(N^2logN)．相对于最优调度算法来说，此算法理论上可保证2近似，即性能至多比最优调度恶化2倍．仿真结果表明：此文算法几乎可以逼近最优调度，比Adjust和Double算法更能自适应于各种变化的业务方式。