多项式时间

作品数：245被引量：298H指数：7
导出分析报告
相关领域：理学自动化与计算机技术更多>>
相关作者：李曙光张少强冯琪李国君徐健腾更多>>
相关机构：曲阜师范大学山东大学郑州大学云南大学更多>>
相关期刊：更多>>
相关基金：国家自然科学基金山东省自然科学基金国家教育部博士点基金国家重点基础研究发展计划更多>>
-
在结果中检索

检索结果分析

结果分析中...
共 条 记 录，以下是1-10
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
带恶化效应的极小化总加权延误工件个数的单机双代理调度问题
《沈阳大学学报(自然科学版)》2025年第1期34-43,共10页谢谢 杨新茹 
国家自然科学基金资助项目(71672117)。
针对钢铁企业的热轧实际生产流程,提出一类随工件加工位置呈一般线性恶化且工件正常加工时长为单位时间的单机双代理调度问题。在该问题中,热轧阶段进入冷轧厂进行冷轧的工件看作A代理商,直接销售给顾客的工件看作B代理商。A代理商的目...
关键词：双代理调度 最大完工时间 延误 工件 恶化效应 完全多项式时间近似方案 
单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题
《运筹学学报(中英文)》2024年第4期66-74,共9页葛晴 录岭法 原晋江 张利弄 
国家自然科学基金(Nos.12271491,12471305,12071442,12371318)。
本文我们考虑单机上工件可拒绝的ND双代理排序问题。在该问题中,假设有两个代理A和B他们的工件集合分别记为J^(A)和J^(B)。在经典的CO双代理排序模型中,总是假设两个代理之间是竞争的,即J^(A)∩J^(B)=Ф。而在ND双代理排序问题中,我们...
关键词：排序 ND双代理 拒绝费用 拟多项式时间算法 全多项式时间近似方案 
一类单机排序问题的新伪多项式时间精确算法
《工业工程与管理》2024年第5期74-84,共11页魏汉英 原梦迪 苏志雄 
国家自然科学基金资助项目(71961020);江西省教育厅科学技术项目(GJJ201920);江西省研究生创新专项资金资助项目(YC2023-S986)。
本文以最小化所有工件的最大延误时间为目标,研究了带有工件释放时间和交付时间的单机排序问题。该问题是机器排序的经典基础性问题,是NP-hard问题。首先,从该问题的结构特征入手,通过揭示工件单机排序结构(各工件的排序位置)与工件最...
关键词：单机排序 最大延误 混合0-1线性规划 伪多项式时间精确算法 Dantzig-Wolfe分解 
次指数过程上确界的多项式时间逼近算法
《理论数学》2024年第8期105-111,共7页龙新雨 
本文提出了一个用于逼近一类次指数过程上确界的算法,具体来说,给定一个有限的向量集合V⊆ℝd,对于集合上密度函数对称单峰的次指数过程X,我们能够在多项式时间内确定性地计算出其上确界的期望,即E[ supv∈V| 〈 v,X 〉 | ]的(1+ε)阶的近似...
关键词：次指数过程上确界 多项式时间逼近算法 Slepian引理 Kanter引理 
有向网络中最大容量支撑树形图扩容问题
《运筹学学报（中英文）》2024年第2期151-158,共8页杨子兰 朱娟萍 杨宇 
国家自然科学基金(No.11126355);云南省教育厅科学基金(No.2022J1217);云南省地方本科高校基础研究联合专项资金(No.202301BA070001-092);丽江文化旅游学院校级中青年学术和技术后备人才(No.2023xshb10)。
针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树...
关键词：最大容量树形图 扩容 NP-困难 启发式算法 多项式时间算法 
带有公共交货期窗口问询和退化工件的单机排序问题
《运筹与管理》2024年第5期48-54,共7页岳青 万国华 
上海高校青年教师培训项目(ZZSUIBE16025)。
为了研究考虑公共交货期窗口问询的退化工件排序问题,构建了极小化因提前时间、延误时间以及交货期窗口问询产生的总成本的单机排序调度决策模型。模型假定所有工件的交货期窗口一致,且窗口的开始时间、窗口大小为决策变量;工件具有差...
关键词：单机排序 公共交货期窗口 退化因子 多项式时间算法 
时间约束下最优时变后向超路近似算法设计
《山西大学学报（自然科学版）》2024年第1期112-121,共10页邢治乐 张淑蓉 
山西省自然科学基金(202103021224058)。
时变最短路径设计是网络优化的一类重要问题。特别是针对结构复杂的网络,通常采用时变超图作为网络拓扑结构,所以在时变超图中研究路径优化问题受到广泛关注。时变后向超图(TVBH)是一类特殊的时变超图。文章主要是研究了在TVBH中构建满...
关键词：时变后向超图 时间约束下的最优超路 近似算法 伪多项式时间算法 时间离散 
多共同工期分配调度问题算法研究
《重庆师范大学学报（自然科学版）》2024年第1期8-13,共6页包晗 吕丹阳 王吉波 
国家自然科学基金(No.71471120);辽宁省“兴辽英才计划”项目资助(No.XLYC2002017)。
为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该...
关键词：调度 提前/延误惩罚 多项式时间算法 单机 多共同工期 
共享制造环境下的同类机排序问题
《曲阜师范大学学报（自然科学版）》2023年第4期15-23,共9页宋嘉欣 孔凡雨 霍雨佳 苗翠霞 赵韵杰 
国家自然科学基金(12271295,12001313);山东省自然科学基金(ZR2022MA019);山东省大学生创新创业训练计划项目(S202210446018)。
考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件Jj都有一个可以加工的机器集Mj,Jj可以被分别给Mj的某一台机器加工,也可以一定服务成本分配给其他剩余机器进行加工.该文的目标是最小化工件的最大完工时间加总服务成本...
关键词：排序 共享制造 同类机 全多项式时间近似方案 
求解单位L_(∞)范数下带值约束的最大权完美匹配逆问题的算法
《数学的实践与认识》2023年第11期114-119,共6页周泽聿 于成成 张斌武 
国家自然科学基金(11471073);中央高校业务费(2018B44014);国家级大学生创新创业训练项目(201810294084)。
通过研究单位L_(∞)范数下的带值约束的最大权完美匹配逆问题的性质,将单位L_(∞)范数下最大权完美匹配逆问题转化为求解最大平均交替圈问题,给出一个求解该类问题的一个强多项式时间算法,其时间复杂度为O(n^(4)).并通过一个算例,验证...
关键词：最大权完美匹配 单位L_(∞)范数 强多项式时间 值约束 
全选清除导出
共25页<12345678910>
检索报告 对象比较 聚类工具 使用帮助 返回顶部