无延迟加工约束下在线LPT算法关于平行机在线排序问题的性能

李文杰

首页> 中文期刊> 《应用数学进展》 >无延迟加工约束下在线LPT算法关于平行机在线排序问题的性能

无延迟加工约束下在线LPT算法关于平行机在线排序问题的性能

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

本文在无延迟加工约束下研究最小化最大完工时间m台平行机在线排序问题。这里的“无延迟加工”是指当工件到达时,如果有机器空闲则必须选择工件加工,即工件不能被延迟加工。当m ≥ 2时,证明无延迟加工约束下在线LPT算法是3/2–竞争的最好可能在线算法。如果所有工件都具有友好到达时间,首先给出无延迟加工约束下排序问题的下界分别为5/4 (当m = 2时)和4/3 (当m ≥ 3时),其次证明在线LPT算法是5/4–竞争的最好可能在线算法对两台平行机情形。

著录项

来源
《应用数学进展》 |2022年第3期|991-995|共5页
作者
李文杰;
展开▼
作者单位

洛阳师范学院洛阳;

展开▼
原文格式 PDF
正文语种 chi
中图分类计算技术、计算机技术;
关键词
在线排序; 在线算法; 无延迟加工; 最大完工时间;

相似文献

中文文献
外文文献
专利

1. 平行机在线(半在线)排序问题近似算法研究 [J] . 高丽娟 ,闵啸 . 嘉兴学院学报 . 2006,第0z1期
2. 三台可拒绝平行机在线排序问题的近似算法 [J] . 荣建华1 侯丽英2 . 石家庄铁道大学学报：自然科学版 . 2017,第002期
3. 三台可拒绝平行机在线排序问题的近似算法 [J] . 荣建华 ,侯丽英 . 石家庄铁道大学学报（自然科学版） . 2017,第002期
4. 单位工件的平行机并行分批在线排序问题的算法 [J] . 胡丹 ,农庆琴 ,方奇志 . 运筹与管理 . 2015,第001期
5. 三台平行机排序的一个复合半在线问题的算法 [J] . 华荣伟 ,胡觉亮 ,卢璐 . 管理工程学报 . 2006,第003期
6. 具有树和路约束的平行机排序问题 [C] . CHENG Jia-le ,程佳乐 ,LI Wei-dong . 2018年全国理论计算机科学学术年会 . -1
7. 工件带有优先约束的平行机在线排序问题 [A] . 吴丰金 . 2008

无延迟加工约束下在线LPT算法关于平行机在线排序问题的性能

摘要

著录项

相似文献

相关主题

期刊订阅