多项式时间算法

作品数：148被引量：181H指数：5
导出分析报告
相关领域：理学更多>>
相关作者：徐健腾王浚岭王勤唐国春刘朝晖更多>>
相关机构：曲阜师范大学郑州大学云南大学山东大学更多>>
相关期刊：更多>>
相关基金：国家自然科学基金国家教育部博士点基金山东省自然科学基金河南省教育厅自然科学基金更多>>
-
在结果中检索

检索结果分析

结果分析中...
共 条 记 录，以下是1-10
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
有向网络中最大容量支撑树形图扩容问题
《运筹学学报（中英文）》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年第1期67-72,共6页吴兆蕊 陈智斌 王扬 
国家自然科学基金项目(11761042)。
研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设...
关键词：排序问题 服务等级 多项式时间算法 近似算法 
单位无穷范数下边权有界的最小支撑树逆最优值问题被引量：1
《运筹学学报》2022年第3期44-56,共13页张斌武 关秀翠 
国家自然科学基金(No.11471073)。
研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标...
关键词：最小支撑树 l_(∞)范数 逆最优值问题 强多项式时间算法 
从NP-Hard到多项式时间算法的大规模机组组合近似线性规划:双重凸包模型被引量：16
《中国电机工程学报》2022年第9期3261-3275,共15页曲明 丁涛 李立 迟方德 贺元康 陈天恩 王凤宇 
国家自然科学基金项目(51977166);陕西电力公司新能源消纳科技专项项目(SGSN0000TKJS2001711);陕西省重点研发计划国际合作项目(2020KW-022)。
机组组合优化是电力系统经济运行的核心模型之一,通常以成本最小为目标函数,满足电力系统运行的物理约束和安全约束。从数学模型上讲,机组组合为混合整数规划问题,其本质是一个NP-hard问题。随着系统规模的增加,整数变量随之增加,其计...
关键词：机组组合 凸包 混合整数规划 动态规划 
带有恶化效应的松弛工期窗口排序问题
《沈阳航空航天大学学报》2022年第1期85-90,共6页黄雪 骆思雯 王吉波 
国家自然科学基金(项目编号:71471120);辽宁省自然科学基金(项目编号:2020-MS-233);辽宁省“兴辽英才计划”(项目编号:XLYC2002017)。
研究单机带有恶化效应的松弛工期窗口排序问题,其中工件的加工时间是一般的线性恶化。对两类目标函数进行研究:一是提前惩罚、误工惩罚、窗口开始时间以及窗口长度的加权和;二是提前任务数、误工任务数、窗口开始时间以及窗口长度的加...
关键词：单机 恶化效应 松弛工期窗口 排序问题 多项式时间算法 
针对经典排序问题的一种新算法的近似比分析被引量：1
《计算机科学》2021年第4期37-42,共6页高吉吉 岳雪蓉 陈智斌 
国家自然科学基金(11761042,11461081)。
给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。...
关键词：经典排序 近似算法 多项式时间算法 紧例子 一维装箱问题 
具有共同窗口指派的单机成组排序问题被引量：1
《沈阳航空航天大学学报》2020年第5期90-95,共6页胡杨 于文汐 霍旭 赵妍楠 张斯雯 王怡丹 王吉波 
辽宁省自然科学基金项目(项目编号:2020-MS-233);校大学生创新创业训练计划项目(项目编号:201810143262)。
研究具有共同交货期窗口指派的单机成组排序问题,其中每组都需要确定一个共同的窗口,工件在窗口内完工不受到惩罚,否则受到提前或延误惩罚。目标是确定工件的排列顺序(包括同组内工件的加工顺序和各组之间的加工顺序),每组的共同交货期...
关键词：排序 单机 窗口指派 成组技术 多项式时间算法 
全选清除导出
共15页<12345678910>
检索报告 对象比较 聚类工具 使用帮助 返回顶部