最坏情况界

作品数：27被引量：27H指数：3
导出分析报告
相关领域：理学更多>>
相关作者：陈永张安蒋义伟陈光亭周萍更多>>
相关机构：浙江理工大学杭州电子科技大学浙江大学浙江商业职业技术学院更多>>
相关期刊：《系统科学与数学》《高校应用数学学报（A辑）》《系统工程理论与实践》《科学技术与工程》更多>>
相关基金：国家自然科学基金浙江省自然科学基金高等学校优秀青年教师教学科研奖励计划中国博士后科学基金更多>>
-
在结果中检索

检索结果分析

结果分析中...
共 条 记 录，以下是1-10
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
二部许可图下{2;3}问题的近似算法
《杭州电子科技大学学报（自然科学版）》2023年第5期78-83,共6页王佳音 张亮 张安 陈永 陈光亭 
国家自然科学基金资助项目(11771114,11971139);浙江省自然科学基金(LY21A010014)。
研究了二部许可图下的两台平行机排序问题,针对加工时间仅取2,3且目标函数为最小化最大完工时间这一特殊情形,设计了基于匹配方法的近似算法,证明了算法的最坏情况界为5/4。
关键词：平行机排序 许可图 匹配 近似算法 最坏情况界 
许可图约束下带释放时间的两机排序算法
《杭州电子科技大学学报（自然科学版）》2022年第6期90-94,共5页童昕 张亮 张安 陈永 陈光亭 
国家自然科学基金资助项目(11971139,11771114);浙江省自然科学基金资助项目(LY21A010014)。
研究一类许可图约束下的2台平行机排序问题,目标是最小化时间表长。针对许可图为二部图,在加工时间为1的工件仅在0时刻释放而加工时间为2的工件在0时刻或r时刻释放的强NP-难情形下,设计了基于最大权匹配方法的近似算法,证明了算法的最...
关键词：平行机排序 许可图 匹配 近似算法 最坏情况界 
极大化提前完工总量平行机排序问题的LPT算法
《运筹学学报》2022年第3期151-156,共6页周萍 季敏 蒋义伟 
浙江省教育厅高校国内访问学者“教师专业发展项目”(No.FX2020093);国家自然科学基金(Nos.11971434,11871327)。
研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断,目标是极大化所有工件的提前完工量,即在交货期前所加工工件(或部分)的总加工时长。由于该问题是NP-难问题,本文应用经典LPT算法来解决该问题。我们证明了LPT算法...
关键词：平行机排序 LPT算法 最坏情况界 提前完工总量 
边着色图上最大弱适当树问题近似算法
《杭州电子科技大学学报（自然科学版）》2021年第4期88-91,102,共5页金世豪 陈光亭 陈永 张安 
国家自然科学基金资助项目(11971139,11771114)。
边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了...
关键词：边着色图 近似算法 最坏情况界 树 
4-正则图上的最小连通顶点覆盖问题被引量：1
《杭州电子科技大学学报（自然科学版）》2020年第5期83-87,97,共6页许梦宇 张安 陈永 陈光亭 
国家自然科学基金资助项目(11771114,11571252)。
任给一个4-正则图,研究如何寻找4-正则图顶点数目最少的顶点覆盖问题,使其导出子图是一个连通图。已研究证明该问题是NP-难的且存在最坏情况界不超过4/3+O(1/n)的近似算法,其中n为4-正则图的顶点数。在此基础上,提出该算法的一个改进分...
关键词：顶点覆盖 正则图 割点 块图 最坏情况界 
顶点赋权图中的连通子图划分问题
《杭州电子科技大学学报（自然科学版）》2020年第4期91-94,共4页李彤 陈永 张安 陈光亭 
国家自然科学基金资助项目(11571252,11771114)。
基于局部搜索技术,针对k=2时的连通子图划分问题,设计了多项式时间近似算法,理论上证明了算法的最坏情况界为4/3,并给出了紧例。
关键词：图划分 连通子图 近似算法 最坏情况界 
MapReduce系统中的两阶段混合流水作业调度算法被引量：2
《系统工程理论与实践》2020年第5期1255-1265,共11页魏麒 吴用 蒋义伟 赵云 
浙江省哲社规划课题成果(19NDJC093YB);国家自然科学基金(11571013,11871327);宁波市自然科学基金(2019A610048,2019A610095)。
以极小化最大完工时间为目标,研究MapReduce系统中的两阶段混合流水作业调度问题.每个工件都包含两个任务集,即map任务集和reduce任务集.所有map任务必须在第一阶段的m1台平行机上加工,而reduce任务则必须在第二阶段的m2台平行机上加工...
关键词：MAPREDUCE 混合流水作业 近似算法 最坏情况界 
带有装卸服务器的两台平行机调度问题的LS和LPT算法
《系统科学与数学》2019年第8期1276-1286,共11页蒋义伟 周萍 马春磊 
国家自然科学基金项目(11571013)资助课题
研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章...
关键词：调度 服务器 MAKESPAN 算法 最坏情况界 
带有装卸服务器的三台平行机排序问题的LS算法
《浙江理工大学学报（自然科学版）》2019年第1期122-126,共5页马春磊 胡觉亮 蒋义伟 
国家自然科学基金项目(11471286,11571013)
针对一个装载服务器和一个卸载服务器的情形,研究三台平行机上的排序问题。每个工件在加工前需要由装载服务器安装到机器上,加工结束后由卸载服务器进行卸载。装载和卸载时间均为单位时间,目标是极小化最大完工时间。该问题是NP-难问题...
关键词：平行机排序 服务器 最坏情况界 MAKESPAN LS算法 
二部图中的完美匹配子集权的极小化问题
《杭州电子科技大学学报（自然科学版）》2017年第5期97-99,共3页李伟娟 陈光亭 陈永 张安 
国家自然科学基金资助项目(11571252;11401149);浙江省自然科学基金资助项目(LY16A010015)
主要研究了二部图中的完美匹配子集权的极小化问题,针对完美匹配两个子集权的极小化问题,证明了最小权重优先算法SWF的最坏情况界为3/2,并应用一一互换思想,设计了最坏情况界至多为4/3的改进算法.
关键词：二部图 完美匹配 近似算法 最坏情况界 
全选清除导出
共3页<123>
检索报告 对象比较 聚类工具 使用帮助 返回顶部