检索结果-内蒙古大学图书馆

中国科学:数学 2025年第2期55卷 221-236页

作者：成夏炎赵聪聪马丽娜李荣珩湖南第一师范学院数学与统计学院长沙410205 湖南师范大学数学与统计学院长沙410081 湖南省沅陵县第一中学怀化419600 云南财经大学统计与数学学院昆明650221 湖南师范大学数学与统计学院计算与随机数学教育部重点实验室复杂系统的控制与优化湖南省高校重点实验室长沙410081

本文研究同类平行机环境下的在线排序问题,其中工件具有任意到达时间,目标为最小化最大完工时间.所讨论机器的速度,除了最后一台为s(s>1)外,其余m−1台机器的速度均为1.本文分析了列表(list scheduling,LS)算法的性能,得到了机器数m=2... 详细信息

本文研究同类平行机环境下的在线排序问题,其中工件具有任意到达时间,目标为最小化最大完工时间.所讨论机器的速度,除了最后一台为s(s>1)外,其余m−1台机器的速度均为1.本文分析了列表(list scheduling,LS)算法的性能,得到了机器数m=2及m≥3时LS算法的竞争比分别为2/3+√5和4−4/m+1,并在一般情形下设计了一个竞争比不超过3.8626的更好的算法—改良列表(modified list scheduling,MLS)算法.

关键词：在线排序同类平行机到达时间算法竞争比

来源：评论

学校读者我要写书评

暂无评论

同类机半在线排序问题及其近似算法

引用

系统工程理论与实践 2001年第2期21卷 53-57页

作者：谈之奕何勇浙江大学数学系浙江杭州310027

研究两台同类机系统两个半在线排序问题 .第一个为总加工时间已知 ,第二个为最大工件加工时间已知 .对这两个问题 ,文章给出了各自的近似算法 ,证明了它们的最坏情况界分别为 3和3/2 .

关键词：在线排序近似算法最坏情况分析组合最优化

来源：评论

学校读者我要写书评

暂无评论

在线排序与博弈排序研究

在线排序与博弈排序研究

引用

作者：成夏炎湖南师范大学

学位级别：博士

排序问题是组合优化的一个重要分支,它在理论上大都是NP-H问题.排序问题不仅具有组合数学的典型特点,同时与相关领域的一些热点问题密切相关,其问题的解决涉及许多学科的交叉领域,具有重要的理论价值.伴随着计算机科学的发展,在该领域... 详细信息

排序问题是组合优化的一个重要分支,它在理论上大都是NP-H问题.排序问题不仅具有组合数学的典型特点,同时与相关领域的一些热点问题密切相关,其问题的解决涉及许多学科的交叉领域,具有重要的理论价值.伴随着计算机科学的发展,在该领域出现了许多新的模型和研究方法.作为现代排序中的在线排序和博弈排序,也取得了相当丰富的成果.本文研究了在平行机环境下的这两类排序问题.全文分为三章.第一章简要介绍了组合优化以及排序问题,特别是在线排序和博弈排序的相关内容作了较为系统简洁地阐述,同时综述了在线排序和博弈排序的有关研究成果.另外,对我们取得的主要研究成果进行了梳理.第二章讨论了同类平行机环境下工件有到达时间,目标函数为极小化最大完工时间的在线排序问题Qm|online,rj|Cmax(m≥2),分析了LS算法的竞争比.得到了机器环境为2台和不少于3台同类平行机时竞争比的紧界,分别是(?).另外给出了比LS算法的竞争比要好的算法MLS算法,并分析了其竞争比.第三章主要研究的是相同平行机环境下机器和工件均具有自私性的二元平衡博弈排序问题Pm‖Cmax(m≥2).此模型中,工件和机器因自私性,均为各自的目标函数而相互进行博弈.当博弈形成一种稳定的平衡状态时,均不会使工件和机器各自的决策发生改变,这种平衡状态被称为二元平衡状态,简写成DE.本章采用权函数的方法,通过对比DE状态下和最优状态下的工件排序情况确定最大完工时间来分析PoA.首先讨论了2台机器的情况,得到了8/7这个PoA的紧界,并给出了以工件长度相似系数r为参数的PoA结果,是一个关于r的分段函数.接着,讨论了机器数3 ≤ m ≤ 9时,4/3为DE状态PoA的一个上界,且是紧界.当m ≥ 10时,得到7/5-9/5(5m-3)为PoA的一个上界.这比此前该模型仅有的结果7/5要好.

关键词：在线排序博弈排序算法竞争比 PoA

来源：评论

学校读者我要写书评

暂无评论

同类机随机在线排序模型及算法分析

引用

华东理工大学学报（自然科学版） 2009年第6期35卷 942-946页

作者：顾满占鲁习文华东理工大学理学院数学系上海200237

考虑同类机随机在线排序问题。假设有m台同类机,工件在线到达,问题的目标是使总加权完工时间的期望值最小。考察该随机在线问题,首先利用线性规划松弛的方法,得到问题最优解的一个下界;然后给出解决该问题的一个在线算法,并分析了该算... 详细信息

考虑同类机随机在线排序问题。假设有m台同类机,工件在线到达,问题的目标是使总加权完工时间的期望值最小。考察该随机在线问题,首先利用线性规划松弛的方法,得到问题最优解的一个下界;然后给出解决该问题的一个在线算法,并分析了该算法的竞争比。

关键词：在线排序随机排序同类机竞争比

来源：评论

学校读者我要写书评

暂无评论

两台可拒绝同类机在线排序问题近似算法的参数性能比

引用

高校应用数学学报（A辑） 2000年第3期15A卷 326-332页

作者：闵啸何勇浙江经济高等专科学校数学教研室浙江嘉兴314000 浙江大学应用数学系杭州310027

讨论两台可拒绝同类机在线排序问题的近似算法 .设两台机器的速度之比为 s(≥ 1) .工件逐个到位 ,可以被加工 ,也可以被拒绝 ,但要付出相应的罚值pj.并且只有在安排完当前工件之后 ,下一个工件才到达 .目标函数要求被加工工件集的最迟... 详细信息

讨论两台可拒绝同类机在线排序问题的近似算法 .设两台机器的速度之比为 s(≥ 1) .工件逐个到位 ,可以被加工 ,也可以被拒绝 ,但要付出相应的罚值pj.并且只有在安排完当前工件之后 ,下一个工件才到达 .目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小 .文中设计出线性时间的 RL S(α)算法 ,并证明了其关于 s的参数紧界 ,这个界于 s=1以及 s≥(5 +1) / 2均是不可改进的 .

关键词：在线排序近似算法参数性能比同类机

来源：评论

学校读者我要写书评

暂无评论

加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究

引用

运筹学学报(中英文) 2024年第4期28卷 18-28页

作者：李文杰杜智慧苏孟龙洛阳师范学院数学科学学院河南洛阳471934

本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时,则空闲机器必须立刻选择工件加工,即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型,即若工... 详细信息

本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时,则空闲机器必须立刻选择工件加工,即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型,即若工件Ji和Jj的加工时间满足pi≥pj,则其运输时间满足qi≥qj。我们首先给出NDP约束下该排序问题的下界为4/3,其次设计出一个竞争比是1.382的在线算法。

关键词：在线排序在线算法 NDP约束一致性运输完工时间

来源：评论

学校读者我要写书评

暂无评论

具有前瞻区间的两个工件组单机在线排序问题

引用

运筹学学报 2012年第2期16卷 115-120页

作者：杨素芳李文华郑州大学数学系郑州450001

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在无界平行分批排序中,一台容量无限制机器可将多个工件形成一批同时加工,每一批的加工时间等于该批中最长工件... 详细信息

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在无界平行分批排序中,一台容量无限制机器可将多个工件形成一批同时加工,每一批的加工时间等于该批中最长工件的加工时间.具有前瞻区间是指在时刻t,在线算法能预见到时间区间（t,t＋β）内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为1＋α的最好可能的在线算法,其中α是方程2α~2＋（β＋1）α＋β-2=0的一个正根,这里0≤β〈1.

关键词：在线排序平行分批不相容工件组最大完工时间竞争比

来源：评论

学校读者我要写书评

暂无评论

具有服务等级的两台同型机实时在线排序

引用

运筹学学报 2016年第2期20卷 49-58页

作者：侯丽英南京农业大学理学院南京210095

考虑具有服务等级的两台同型机在线排序问题,其中工件带有到达时间,目标为最小化最大完工时间,设计了竞争比为7/4的在线算法.

关键词：在线排序服务等级到达时间竞争比

来源：评论

学校读者我要写书评

暂无评论

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

引用

运筹学学报 2022年第2期26卷 55-63页

作者：李文杰李钰晶刘海玲洛阳师范学院数学科学学院河南洛阳471934 河南工程学院理学院河南郑州451191

工件的释放时间和加工时间具有一致性,是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间,即若r_(i)≥r_(j),则p_(i)≥p_(j)。本文在该一致性约束下,研究最小化最大加权完工时间单机在线排序问题,和最小化总加权完工时... 详细信息

工件的释放时间和加工时间具有一致性,是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间,即若r_(i)≥r_(j),则p_(i)≥p_(j)。本文在该一致性约束下,研究最小化最大加权完工时间单机在线排序问题,和最小化总加权完工时间单机在线排序问题,并分别设计出√5+2/2—竞争的最好可能在线算法。

关键词：在线排序在线算法一致性加权完工时间

来源：评论

学校读者我要写书评

暂无评论

工件权重带限制的最小化最大加权完工时间的单机在线排序问题

引用

运筹学学报（中英文） 2024年第2期28卷 71-80页

作者：徐娟年马冉韩雯雯张玉忠青岛理工大学管理工程学院山东青岛266525 曲阜师范大学管理学院、运筹学研究院山东日照276826

本文考虑了最小化最大加权完工时间的单机在线排序问题,要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性,即apj≤wj≤bpj(a≥(√5−1/2)b,b≥a)且若wi>wj则pi≥pj,如果wi=wj则pi=pj。工件以时间在线... 详细信息

本文考虑了最小化最大加权完工时间的单机在线排序问题,要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性,即apj≤wj≤bpj(a≥(√5−1/2)b,b≥a)且若wi>wj则pi≥pj,如果wi=wj则pi=pj。工件以时间在线的方式到达,只有工件Jj在达到释放时间rj后,决策者才知晓工件的基本信息,如加工时间pj和权重wj。对于此问题,首先利用对手法证明了其下界为1+b/(b+a),随后给出了竞争比为1+b/(b+a)的最好可能的在线算法。特别地,当a=(√5−1/2)b时,该算法的竞争比为(5√+1)/2。

关键词：单机在线排序在线算法加权完工时间

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：