期刊文献+
共找到22篇文章
< 1 2 >
每页显示 20 50 100
带到达时间的加工时间离散可控的单机排序问题1|r_j,dm|C_(max)+TPC的FPTAS算法
1
作者 周瑞扬 曹志刚 张玉忠 《洛阳大学学报》 2006年第4期39-42,共4页
考虑工件加工时间离散可控的单机分批排序问题,目标函数是极小化最大完工时间与加工费用之和.对于工件不同时到达的情况,本文给出了FPTAS算法.
关键词 离散可控 到达时间 最大完工时间 fptas
下载PDF
离散加工时间的可控排序问题(英文) 被引量:4
2
作者 张树霞 曹志刚 张玉忠 《运筹学学报》 CSCD 北大核心 2007年第2期59-64,共6页
本文主要研究了离散加工时间的可控排序问题,目标函数是总压缩费用约束下极小化最大完工时间,对单机工件有不同到达时间以及同型机工件到达时间都相同这两个问题,我们设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法.
关键词 运筹学 排序 动态规划 离散可控 fptas算法
下载PDF
工件可转包加工的排序问题研究 被引量:4
3
作者 仲维亚 刘晓蕾 霍志明 《运筹学学报》 CSCD 北大核心 2012年第1期121-126,共6页
研究工件可以转包加工的单台机排序问题:有n个工件,在零时刻已经到达一个单台机处,每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工.如果工件被转包加工,那么其完工时间等于在自有机器上的加工时间,而产生的加工费用与... 研究工件可以转包加工的单台机排序问题:有n个工件,在零时刻已经到达一个单台机处,每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工.如果工件被转包加工,那么其完工时间等于在自有机器上的加工时间,而产生的加工费用与在自有机器上加工的费用不同.假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和.该问题已经被证明是NP-难的.最后给出该问题的伪多项式时间最优算法,并且提出一个完全多项式时间近似方案(FPTAS). 展开更多
关键词 排序 伪多项式时间最优算法 fptas
下载PDF
具有退化工件和老化效应的单机可拒绝排序问题 被引量:5
4
作者 刘春来 王建军 《运筹与管理》 CSSCI CSCD 北大核心 2017年第6期95-101,共7页
研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加... 研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(FPTAS)算法。 展开更多
关键词 单机排序 拒绝 维修活动 fptas
下载PDF
工件带简单线性恶化函数和共同交货期单机排序问题
5
作者 余英 舒彤 曾春花 《运筹与管理》 CSSCI CSCD 北大核心 2016年第1期154-157,共4页
本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何... 本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。 展开更多
关键词 单机排序 动态规划算法 近似算法(fptas) 几何舍入技巧
下载PDF
最小化加权误工工件数的多代理平行分批排序(英文)
6
作者 原晋江 何程 林诒勋 《运筹学学报》 CSCD 2009年第4期1-13,共13页
考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,... 考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法. 展开更多
关键词 运筹学 多目标排序 平行分批 误工工件数 fptas
下载PDF
工件加工可拒绝的无界批量分批排序问题的几点探讨(英文) 被引量:1
7
作者 张咸昭 蔡增霞 任剑锋 《运筹学学报》 CSCD 2009年第3期23-30,共8页
本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑w_jT_j+TP和1|B≥n,rej|∑w_jU_j+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.
关键词 运筹学 可拒绝 NP-困难 伪多项式时间 fptas
下载PDF
仿生物态模拟型硬件理论与关键技术研究 被引量:8
8
作者 王友仁 崔坚 +1 位作者 朱开阳 姚睿 《南京航空航天大学学报》 EI CAS CSCD 北大核心 2004年第5期595-599,共5页
阐述了模拟型仿生硬件的概念、基本思想与技术瓶颈 ,分析了基于 FPTA( Field programmable transistorarray)的模拟型仿生硬件的结构与电子细胞电路工作原理。给出了模拟型仿生硬件的电路编码方案、个体电路测试评估方法和进化实现过程... 阐述了模拟型仿生硬件的概念、基本思想与技术瓶颈 ,分析了基于 FPTA( Field programmable transistorarray)的模拟型仿生硬件的结构与电子细胞电路工作原理。给出了模拟型仿生硬件的电路编码方案、个体电路测试评估方法和进化实现过程。提出了基于单染色体自适应变异进化机制的模拟型仿生硬件进化算法。以信号放大器、半波整流器、异或门数字电路作为典型应用实例 ,来验证模拟型仿生硬件的进化特性 ,并讨论了进化算法的参数选取、染色体适应度评估问题。仿真结果表明 :所提出硬件进化算法的进化速度快、成功率高 ,所设计的FPTA细胞阵列可以实现模拟信号放大。 展开更多
关键词 仿生硬件 FPTA 电子细胞阵列 模拟电路 进化算法 外部进化方式
下载PDF
工件可拒绝排序问题综述 被引量:7
9
作者 张玉忠 《运筹学学报》 北大核心 2020年第2期111-130,共20页
可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类... 可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿. 展开更多
关键词 可拒绝排序 在线排序 离线排序 近似算法 复杂性 竞争比 NP-难 PTAS fptas
下载PDF
有使用限制的两台机器排序问题的近似算法
10
作者 李刚刚 李浩 《华中师范大学学报(自然科学版)》 CAS 北大核心 2015年第1期11-13,20,共4页
研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS(fully po... 研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS(fully polynomial-time approximation scheme). 展开更多
关键词 排序 使用限制 算法 fptas
下载PDF
Parallel-batch scheduling with deterioration and rejection on a single machine 被引量:3
11
作者 LI Da-wei LU Xi-wen 《Applied Mathematics(A Journal of Chinese Universities)》 SCIE CSCD 2020年第2期141-156,共16页
The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the mach... The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems. 展开更多
关键词 parallel-batch scheduling REJECTION DETERIORATION fptas NP-COMPLETE
下载PDF
模拟型演化硬件中可重构器件的比较研究 被引量:1
12
作者 周永彬 杨俊 王跃科 《电子器件》 CAS 2008年第4期1226-1231,共6页
演化硬件的研究者受困于满足可演化要求的灵活可重构硬件平台的匮乏。一方面,虽然现有商用可重构平台多数具有动态可局部重构能力,但是其设计目的不是用来研究演化硬件的。另外一方面,用户定制的面向演化硬件研究的芯片没有商用化,而且... 演化硬件的研究者受困于满足可演化要求的灵活可重构硬件平台的匮乏。一方面,虽然现有商用可重构平台多数具有动态可局部重构能力,但是其设计目的不是用来研究演化硬件的。另外一方面,用户定制的面向演化硬件研究的芯片没有商用化,而且也不太可能在最近走向商用市场。本文研究了两类用来进行模拟演化硬件研究的可重构器件:商用的现场可编程模拟阵列和用户定制的现场可编程三极管阵列。通过比较研究,作者认为在FPTA类定制用于演化的可重构平台商用化之前,在FPAA平台上开展EHW的研究是有意义的,因为FPAA已经具有充分灵活的重构接口和充足的可重配置资源。 展开更多
关键词 演化硬件 可重构器件 现场可编程模拟阵列FPAA 现场可编程三极管阵列FPTA 粒度
下载PDF
平行机上一种带拒绝费用的排序问题研究
13
作者 武光华 《青岛大学学报(自然科学版)》 CAS 2014年第2期14-16,共3页
主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP-难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。
关键词 近似算法 可拒绝排序 动态规划 fptas
下载PDF
一种带拒绝费用的排序问题研究
14
作者 武光华 丽苑华 《洛阳理工学院学报(自然科学版)》 2010年第1期61-64,共4页
主要研究了一种带拒绝费用的排序问题。目标函数是在不超过总拒绝费用阀值的前提下使最大完工时间最小。首先,证明了该问题是N P-难的;然后我们针对这个问题设计出了伪多项式时间的动态规划算法,并给出了FPTAS。
关键词 近似算法 可拒绝排序 动态规划 fptas
下载PDF
时间一致时极小化工件配送时间的近似算法
15
作者 唐庆晨 《济宁学院学报》 2008年第6期31-34,共4页
本文主要研究了平行机上时间一致时极小化工件配送时间的分批排序问题,该问题是传统的分批排序与当代的物流相结合而产生的一类新的问题.一般情况下当工件有不同的到达时间时该问题是强NP—难的,但对工件有有限个到达时间及机器台数有限... 本文主要研究了平行机上时间一致时极小化工件配送时间的分批排序问题,该问题是传统的分批排序与当代的物流相结合而产生的一类新的问题.一般情况下当工件有不同的到达时间时该问题是强NP—难的,但对工件有有限个到达时间及机器台数有限时,若所有的输入数据均为整数,本文给出了问题的伪多项式时间算法,从而说明了在这种情况下问题不是强NP—难的.当输入数据是有理数时,本文给出了问题的FPTAS算法.并给出了时间一致时一般情形的PTAS算法. 展开更多
关键词 配送时间 近似算法 fptas算法 PTAS算法 平行机
下载PDF
基于DSP的演化硬件独立演化系统设计
16
作者 李建明 石玉 《佳木斯大学学报(自然科学版)》 CAS 2009年第2期161-163,167,共4页
演化硬件由于具有自组织、自适应、自修复的特点而在航空航天等尖端领域有广泛的应用前景.国内对模拟型演化硬件的研究大多采用仿真研究,演化速度慢且不适合多细胞演化.本文设计了一种基于DSP的可扩展的独立演化系统,实现了演化硬件自... 演化硬件由于具有自组织、自适应、自修复的特点而在航空航天等尖端领域有广泛的应用前景.国内对模拟型演化硬件的研究大多采用仿真研究,演化速度慢且不适合多细胞演化.本文设计了一种基于DSP的可扩展的独立演化系统,实现了演化硬件自动、高速的内部演化. 展开更多
关键词 演化硬件 内部演化 DSP FPTA
下载PDF
三台平行机上四个约束链的排序问题
17
作者 栾文婕 《聊城大学学报(自然科学版)》 2011年第4期37-40,51,共5页
考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.
关键词 排序 约束链 动态规划 计算复杂性 fptas
下载PDF
Some Discussions on Parallel Bounded Batch Scheduling to Minimize the Sum of Squared Machine Loads
18
作者 Zengxia Cai Xianzhao Zhang 《Journal of Mathematics and System Science》 2016年第2期60-65,共6页
We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the long... We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) for this problem. 展开更多
关键词 SCHEDULING Parallel batch Polynomial time approximation scheme fptas
下载PDF
基于导频的OFDM系统信道估计算法研究及实现 被引量:2
19
作者 杨玉峰 黄炜 余波 《电视技术》 北大核心 2006年第9期8-10,共3页
介绍了基于导频的OFDM系统信道估计方法,对典型估计方法的算法复杂性进行了分析比较,并在此基础上给出了频域导频时域平均信道估计算法的硬件电路FPGA实现方案,对FPGA设计的主要模块进行了详细说明,以Altera的StratixII芯片为平台完成... 介绍了基于导频的OFDM系统信道估计方法,对典型估计方法的算法复杂性进行了分析比较,并在此基础上给出了频域导频时域平均信道估计算法的硬件电路FPGA实现方案,对FPGA设计的主要模块进行了详细说明,以Altera的StratixII芯片为平台完成仿真和综合。系统分析和FPGA电路综合结果表明:相比传统的频域信道估计算法,该算法节省资源,更利于硬件实现。 展开更多
关键词 正交频分复用 信道估计 FPTA算法 现场可编程门阵列
下载PDF
基于背包问题算法的中长期电力合同签约优化问题
20
作者 屈源 《电力设备管理》 2022年第19期301-303,共3页
根据中长期合同签约中的总量限制问题,建立有效的数学模型。引入背包问题的伪多项式时间复杂度算法,给出合理的解决方案,并从近似度、复杂度等方面对方案进行评估。
关键词 中长期合同 背包问题 算法 fptas 时间复杂度 近似度
下载PDF
上一页 1 2 下一页 到第
使用帮助 返回顶部