检索结果-南通市图书馆

同方期刊数据库

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

平行机上带有前瞻区间的不相容工件组在线排序问题

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2015年第4期19卷 121-126页

作者：李文华柴幸袁航杨素芳郑州大学数学与统计学院郑州450001 浙江大学经济学院杭州310027

研究当不相容工件组的个数与机器数相等时，具有前瞻区间的单位工件平行机无界平行分批在线排序问题工件按时在线到达，目标是最小化最大完工时间．具有前瞻区间是指在时刻t，在线算法能预见到时间区间（t，t＋β[]内到达的所有工件的... 详细信息

研究当不相容工件组的个数与机器数相等时，具有前瞻区间的单位工件平行机无界平行分批在线排序问题工件按时在线到达，目标是最小化最大完工时间．具有前瞻区间是指在时刻t，在线算法能预见到时间区间（t，t＋β[]内到达的所有工件的信息．不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工．当β≥1时，提供了一个最优的在线算法；当0≤p〈1时，提供了一个竞争比为1＋α的最好可能的在线算法，其中＆是方程OL0＋（1＋β）α＋β-1=0的一个正根．最后，给出了当β=0时稠密算法竞争比的下界，并提供了达到该下界的最好可能的稠密算法．

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

在线全文

学校读者我要写书评

暂无评论

带机器准备时间的平行机在线与半在线排序

系统科学与数学 2002年第4期22卷 414-421页

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

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的... 详细信息

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。

关键词：机器准备时间平行机半在线排序在线排序近似算法最坏情况分析

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

在线全文

学校读者我要写书评

暂无评论

运筹学学报（中英文） 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。

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

加工时间与运输时间具有一致性的单机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.

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

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

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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