期刊文献+
共找到69篇文章
< 1 2 4 >
每页显示 20 50 100
具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案 被引量:3
1
作者 金苗苗 吴蒙洁 罗文昌 《运筹与管理》 CSSCI CSCD 北大核心 2021年第8期87-92,共6页
本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个... 本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。 展开更多
关键词 重新排序 不可用区间 拒绝 最大延误 近似方案
下载PDF
Bound States of the Klein-Gordon for Exponential-Type Potentials in D-Dimensions
2
作者 Sameer M. Ikhdair 《Journal of Quantum Information Science》 2011年第2期73-86,共14页
The approximate analytic bound state solutions of the Klein-Gordon equation with equal scalar and vector exponential-type potentials including the centrifugal potential term are obtained for any arbitrary orbital quan... The approximate analytic bound state solutions of the Klein-Gordon equation with equal scalar and vector exponential-type potentials including the centrifugal potential term are obtained for any arbitrary orbital quantum number l and dimensional space D. The relativistic/non-relativistic energy spectrum formula and the corresponding un-normalized radial wave functions, expressed in terms of the Jacobi polynomials and or the generalized hypergeometric functions have been obtained. A short-cut of the Nikiforov-Uvarov (NU) method is used in the solution. A unified treatment of the Eckart, Rosen-Morse, Hulthén and Woods-Saxon potential models can be easily derived from our general solution. The present calculations are found to be identical with those ones appearing in the literature. Further, based on the PT-symmetry, the bound state solutions of the trigonometric Rosen-Morse potential can be easily obtained. 展开更多
关键词 approximation scheme Eckart-Type POTENTIALS Rosen-Morse-Type POTENTIALS Trigonometric Rosen-Morse POTENTIAL Hulthén POTENTIAL and Woods-Saxon POTENTIAL KLEIN-GORDON Equation NU Method
下载PDF
Approximation Schemes for the 3-Partitioning Problems
3
作者 Jianbo Li Honglin Ding 《Communications and Network》 2013年第1期90-95,共6页
The 3-partitioning problem is to decide whether a given multiset of nonnegative integers can be partitioned into triples that all have the same sum. It is considerably used to prove the strong NP-hardness of many sche... The 3-partitioning problem is to decide whether a given multiset of nonnegative integers can be partitioned into triples that all have the same sum. It is considerably used to prove the strong NP-hardness of many scheduling problems. In this paper, we consider four optimization versions of the 3-partitioning problem, and then present four polynomial time approximation schemes for these problems. 展开更多
关键词 3-partitioning PROBLEM approximation scheme
下载PDF
最大一致流问题的一个逼近算法 被引量:1
4
作者 郭海旭 程丛电 吴亚坤 《辽宁大学学报(自然科学版)》 CAS 2009年第1期35-39,共5页
通过建构辅助网络,以Korte和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索,给出了一个新的求解最大一致流问题的逼近算法.然后,进行算法分析,说明了所建立的算法是拟多项式算法,... 通过建构辅助网络,以Korte和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索,给出了一个新的求解最大一致流问题的逼近算法.然后,进行算法分析,说明了所建立的算法是拟多项式算法,并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系.该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的,并且为研究网络流问题提供了一种新的方法. 展开更多
关键词 多物资网络流 逼近 算法 复杂性
下载PDF
工件可拒绝的两个代理排序问题的全多项式时间近似方案 被引量:1
5
作者 冯琪 杨丽华 狄帅 《工程数学学报》 CSCD 北大核心 2021年第3期369-376,共8页
本文研究单处理机上工件可拒绝的两个代理的排序问题.在此问题中,有两个代理A和B,分别有各自的工件集和费用函数.代理A的工件可以被接收,也可以被拒绝,但要支付一定的拒绝费用.代理B的工件要全部接收.代理A的费用函数是他的接收工件的... 本文研究单处理机上工件可拒绝的两个代理的排序问题.在此问题中,有两个代理A和B,分别有各自的工件集和费用函数.代理A的工件可以被接收,也可以被拒绝,但要支付一定的拒绝费用.代理B的工件要全部接收.代理A的费用函数是他的接收工件的最大完工时间与拒绝工件的拒绝费用之和,代理B的费用函数是他的工件的最大延迟.排序问题的目标是在满足代理B的费用函数不超过一定数量的前提下,使得代理A的费用函数达到最小.对于该问题给出了一个全多项式时间近似方案. 展开更多
关键词 排序 代理 拒绝 近似方案
下载PDF
线性分式多乘积问题的ε-近似算法
6
作者 申子慧 陈玉松 申培萍 《应用数学》 CSCD 北大核心 2021年第4期877-884,共8页
本文针对线性分式多乘积问题提出一个近似算法;该算法主要通过非均匀搜索网格结点,将等价问题转化为多项式个与结点参量相关的线性子问题,通过求解这些子问题获得原问题的全局近似最优解.本文不仅从理论上证明了算法的收敛性,且通过算... 本文针对线性分式多乘积问题提出一个近似算法;该算法主要通过非均匀搜索网格结点,将等价问题转化为多项式个与结点参量相关的线性子问题,通过求解这些子问题获得原问题的全局近似最优解.本文不仅从理论上证明了算法的收敛性,且通过算例验证算法的可行性与有效性,最终给出算法的计算复杂度. 展开更多
关键词 分式多乘积 全局优化 近似算法 计算复杂度
下载PDF
求解2-D Strip Packing问题的u-分组优化算法
7
作者 黄海 李松斌 《计算机科学》 CSCD 北大核心 2017年第5期290-293,303,共5页
2-D strip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的... 2-D strip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的数据结构,最后对不同类别矩形基于箱子X轴的u等分点进行填充,使其装入的物品价值最大。文中的主要贡献在于:提出了一种有效的分组构造函数;计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法;特别地,在期望目标ε、多项式时间复杂度和至少装入(1-ε)OPT价值物品的情况下,可将所需箱体宽度从1+ε减小到1,而高度保持不变。 展开更多
关键词 u-分组 二维装箱 近似算法 NP难度 启发式
下载PDF
一种新的高效的有限体积法
8
作者 罗跃生 张见升 《价值工程》 2012年第9期268-269,共2页
有限体积法是一种新的流体力学数值计算方法,其对于数值求解流体力学中常常遇到的偏微分方程十分有效。这篇文章采用有限体积法离散得到数值逼近格式,由原来的九点格式变成现在的五点格式,减少了节点的使用个数,且系数矩阵的条件数比较... 有限体积法是一种新的流体力学数值计算方法,其对于数值求解流体力学中常常遇到的偏微分方程十分有效。这篇文章采用有限体积法离散得到数值逼近格式,由原来的九点格式变成现在的五点格式,减少了节点的使用个数,且系数矩阵的条件数比较小,能保证离散的方程组有唯一解,且有较高的精度,并用提出的数值解方法求解二维的Laplace方程。数值计算结果与精确解作比较,吻合良好,且降低了计算机计算时所需要的时间。 展开更多
关键词 有限体积法 逼近格式 流体力学
下载PDF
工件延误和可拒绝下的单机重新排序问题的近似方案
9
作者 余山杉 金苗苗 罗文昌 《运筹学学报》 CSCD 北大核心 2021年第2期104-114,共11页
研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题。在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已... 研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题。在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定。然而,在工件正式开始加工时,工件集中的部分工件由于延误不能按时到达,这对初始排序的执行产生了干扰,所以需要对初始排序进行调整,即重新排序。为了保证服务水平,允许对延误工件拒绝加工,但需支付相应的拒绝费用。调整后的重新排序的目标是在保证接受工件集中工件的最大延误不超过给定的上界的约束下,使得接受工件集的赋权完工时间和,拒绝工件集的拒绝费用和以及接受工件集中工件的最大延误的赋权惩罚费用之和达到极小。对该问题,设计了一个伪多项式时间动态规划精确算法,并利用稀疏技术得到了一个完全多项式时间近似方案。 展开更多
关键词 重新排序 工件拒绝 工件延误 动态规划 近似方案
下载PDF
线性比式和优化问题的完全多项式时间近似算法
10
作者 申子慧 申培萍 《应用数学》 CSCD 北大核心 2019年第1期176-182,共7页
本文针对线性比式和优化问题提出一个完全多项式时间近似算法,该算法主要利用原问题的等价问题及网格结点参数获得有限个与结点参数相关的线性规划问题,通过求解这些线性规划问题获得原问题的近似最优解.最终证明算法的收敛性,并给出了... 本文针对线性比式和优化问题提出一个完全多项式时间近似算法,该算法主要利用原问题的等价问题及网格结点参数获得有限个与结点参数相关的线性规划问题,通过求解这些线性规划问题获得原问题的近似最优解.最终证明算法的收敛性,并给出了算法的计算复杂度,通过计算结果呈现算法的有效性与可行性. 展开更多
关键词 比式和 全局优化 近似算法 计算复杂性
下载PDF
工件带安装时间的单机排序问题的列生成算法
11
作者 樊保强 唐国春 《运筹学学报》 CSCD 北大核心 2007年第3期65-74,94,共11页
在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松... 在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的. 展开更多
关键词 运筹学 近似算法 幺模矩阵 分支定界 列生成算法 NP-困难
下载PDF
工件带简单线性恶化函数和共同交货期单机排序问题
12
作者 余英 舒彤 曾春花 《运筹与管理》 CSSCI CSCD 北大核心 2016年第1期154-157,共4页
本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何... 本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。 展开更多
关键词 单机排序 动态规划算法 近似算法(FPTAS) 几何舍入技巧
下载PDF
基于四阶非线性偏微分方程的图像去噪算法 被引量:17
13
作者 吴登辉 周先春 陈铭 《电子测量与仪器学报》 CSCD 北大核心 2017年第6期839-843,共5页
为了更好的实现图像模糊消除和有效地去除斑点噪声,提出了一种新的基于偏微分方程的图像去噪方法,它是基于非线性四阶扩散模型。首先提出了该非线性偏微分方程的方案,然后对微分模型进行数学处理,研究它的适定性,最后证明了此模型在一... 为了更好的实现图像模糊消除和有效地去除斑点噪声,提出了一种新的基于偏微分方程的图像去噪方法,它是基于非线性四阶扩散模型。首先提出了该非线性偏微分方程的方案,然后对微分模型进行数学处理,研究它的适定性,最后证明了此模型在一定条件下是适定的,并且存在了弱解,所得到的弱解近似于基于有限差分数值离散格式。实验结果表明,新模型在图像去噪和保边缘等细节信息方面都达到较好的效果,峰值信噪比有了大幅提高,去噪性能较经典模型更具优越性。 展开更多
关键词 图像去噪 偏微分方程 非线性扩散 弱解 数值逼近法
下载PDF
无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案(英文) 被引量:4
14
作者 李曙光 李国君 赵浩 《运筹学学报》 CSCD 北大核心 2004年第4期27-32,共6页
本文考虑n个工件的无限批量机器调度问题.一台机器可以同时加工B≥n个工件.每个工件具有一个正权因子、一个释放时间和一个加工时间.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时... 本文考虑n个工件的无限批量机器调度问题.一台机器可以同时加工B≥n个工件.每个工件具有一个正权因子、一个释放时间和一个加工时间.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.对于最小化加权完工时间和问题,本文给出了第一个多项式时间近似方案(PTAS).对任意给定精度,该算法的运行时间为线性的. 展开更多
关键词 完工时间 近似 线性 加工时间 加权 调度问题 多项式时间 批次 最小化 批量
下载PDF
欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现 被引量:3
15
作者 赵卫中 冯好娣 朱大铭 《计算机研究与发展》 EI CSCD 北大核心 2007年第10期1790-1795,共6页
货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究... 货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的"补丁引理"结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析. 展开更多
关键词 货郎担问题 近似算法 多项式时间近似方案 计算复杂性 动态规划
下载PDF
二维非定常对流扩散方程的隐式多重网格方法 被引量:4
16
作者 田瑞雪 葛永斌 吴文权 《西南师范大学学报(自然科学版)》 CAS CSCD 北大核心 2003年第4期507-512,共6页
提出了数值求解二维非定常对流扩散方程的一种新的加权平均隐格式,利用Fourier分析方法证明了该格式是无条件稳定的.利用多重网格加速技术,提出了基于时间修正的多重网格的全近似格式(FAS),从而克服了传统迭代法在求解隐格式时收敛速度... 提出了数值求解二维非定常对流扩散方程的一种新的加权平均隐格式,利用Fourier分析方法证明了该格式是无条件稳定的.利用多重网格加速技术,提出了基于时间修正的多重网格的全近似格式(FAS),从而克服了传统迭代法在求解隐格式时收敛速度慢的缺陷,大大加快了迭代收敛速度,提高了问题的求解效率.数值计算结果表明,修正的多重网格FAS格式较传统的多重网格粗网格校正格式(CS)具有更好的收敛效率.并且随着σ和s的增大,它可以将传统迭代法的收敛速度提高几十倍,甚至几百倍. 展开更多
关键词 二维非定常对流扩散方程 隐式多重网格方法 加权平均隐格式 FOURIER分析 多重网格全近似格式
下载PDF
限制性的带核元划分问题 被引量:2
17
作者 李伟东 葛瑜 +1 位作者 张同全 李建平 《云南大学学报(自然科学版)》 CAS CSCD 北大核心 2010年第1期6-11,共6页
考虑了限制性的带核元划分问题,即将一个整数集合划分为2个子集,使得2个核元分别在不同的子集里且每个子集至多包含k个元素,这里n/2+1≤k≤n+1,目标使2个子集中元素之和的最小者达尽可能大.对一般的k,给出了全多项式时间近似方案(FPTAS)... 考虑了限制性的带核元划分问题,即将一个整数集合划分为2个子集,使得2个核元分别在不同的子集里且每个子集至多包含k个元素,这里n/2+1≤k≤n+1,目标使2个子集中元素之和的最小者达尽可能大.对一般的k,给出了全多项式时间近似方案(FPTAS).当k=n+1时,给出了线性时间内的多项式时间近似方案(PTAS)和全多项式时间近似方案(FPTAS). 展开更多
关键词 带核元划分 近似算法 多项式时间近似方案 全多项式时间近似方案
原文传递
极小化完工时间和的有界批调度问题(英文) 被引量:3
18
作者 李曙光 李国君 赵洪銮 《应用数学》 CSCD 北大核心 2006年第2期446-454,共9页
考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.
关键词 近似算法 多项式时间近似方案 调度 批加工 完工时间和
下载PDF
极小化加权完工时间和的无界批量机器并行调度问题(英文) 被引量:3
19
作者 李曙光 李国君 王秀红 《软件学报》 EI CSCD 北大核心 2006年第10期2063-2068,共6页
考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间... 考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS). 展开更多
关键词 多项式时间近似方案 调度 无界批量并行机 加权完工时间和 释放时间
下载PDF
线性张力腿模型与非线性模型的比较研究 被引量:3
20
作者 徐万海 曾晓辉 吴应湘 《振动与冲击》 EI CSCD 北大核心 2008年第5期134-138,共5页
平台运动对张力腿的非线性动力响应具有显著的影响。提出了新的更加符合实际的边界条件,分别采用线性的Euler-Bernoulli梁和非线性梁模型,分析了在不同的张力腿长度和平台激励条件下,线性张力腿模型与非线性模型在预测其动力响应时所得... 平台运动对张力腿的非线性动力响应具有显著的影响。提出了新的更加符合实际的边界条件,分别采用线性的Euler-Bernoulli梁和非线性梁模型,分析了在不同的张力腿长度和平台激励条件下,线性张力腿模型与非线性模型在预测其动力响应时所得结果的差异。为了保证数值计算的正确性和可靠性,运用了两种不同的计算方法;Galerkin法,有限差分法进行数值求解。结果表明:非线性模型所得的张力腿流向响应幅值要比线性模型的小,且随着张力腿长度以及平台纵荡幅值的增加,非线性模型与线性模型的预测结果之间的差异会变得越来越显著。 展开更多
关键词 Euler—Bernoulli梁 有限差分法 GALERKIN法 参数振动 受迫振动
下载PDF
上一页 1 2 4 下一页 到第
使用帮助 返回顶部