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

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

可控排序问题的凸二次规划松弛近似算法

用凸二次规划松弛方法,研究工件加工时间可控的,使加工时间压缩费用与加权总完工时间之和为最小的排序问题,得到界为3/2的多项式时间近似算法.     

整凸二次规划

本文给出了一种求解整凸二次规划的分枝定界法，该算法把松弛问题转化为线性互补问题，由于求解线性互补问题时，充分地利用了前一分枝点所对应的线性互补问题解的信息，从而地减少了计算量。     

加工时间离散可控的分批排序问题

分批排序和可控排序是两类重要的现代排序模型,该文中把这两类排序模型相结合,讨论加工时间离散可控的单机分批排序问题:对于所有工件具有相同的可控加工时间和控制费用这一情形,分别考虑机器容量有限及无限两种情况下,分别使最大完工时间和总完工时间加上加工时间可控所需费用的总和为最小作为优化的目标,讨论了这四个问题的最优解的性质,并在此基础上提出了相应的多项式时间最优算法.     

工件加工时间的可控排序问题

讨论离散加工时间可控的排序问题P｜dis_cpt,pmtn｜ n∑j=1Cjtj＋Cmax,应用线性规划松弛方法得到其性能比为e/e-1（≈1.583）多项式时间近似算法.     

微分代数方法求解凸二次规划问题

用微分代数方法求解凸二次规划问题,先把凸二次规划转化为带障碍项的凸规划,然后用微分代数方法求解,结果表明微分代数方法求解凸二次规划是切实可行的.     

带权的排序问题和二次规划

把带权的排序问题1‖∑ωjCj表示成一个二次规划,证明这个二次规划最优解的充分必要条件是成立WSPT规则,从而也证明WSPT规则是带权排序问题的充分必要条件。同时还证明了1‖∑ωjCj问题目标函数的最小值是∑i=1^n∑j=1^upπ（j)ωπ（i),为用二次规划研究其他带权的排序问题打下基础。     

凸二次参数规划的逆问题及其应用

考虑了凸二次参数规划和凸二次同参规划组的逆问题，首先给出凸二次参数规划的逆规划，然后考虑了凸二次同参规划组的逆问题，最后给出了凸二次参数规划的逆问题的经济背景．     

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的多项式时间近似算法．     

平行机上一种带拒绝费用的排序问题研究

主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP一难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。     

单机可控排序问题的神经网络模型

本文建立了1｜rj｜cmax的可控排序问题的数学规划模型,利用投影算子与变分不等式的关系,构造了求解数学规划模型的神经网络动力系统,运用Lyapunov方法,证明了该系统全局稳定,且系统的平衡点就是所求问题的最优解。     

一类特殊规划的求解算法

二次规划问题是一类重要的优化问题,是NP困难的.通过对已有算法的理解与分析,在假设原问题的Hessian矩阵正定的条件下,作者给出了求解二次规划问题的一种新算法,并讨论了算法的收敛性.     

非线性规划问题的函数逼近算法与收敛性

对于一般的非线性规划问题,利用Lagrange函数进行拟合,建立一种算法。在算法的每次迭代中,通过解构造的二次规划问题获得一个可行方向。并证明了该算法的收敛性。