单机工件运输排序问题上界的改进

A Note on the Upper-Bound of the Machine Scheduling with Transportation Consideration

下载PDF

导出

摘要在单机排序和工件运输问题的模型中,在2T1≥T3限制下,我们证明了最劣性能比可改进为27/14. In this paper we assume that 2T1≥T3. Under this restriction a worst-case performance ratio 27/14 is given.

作者汪松玉陈友军

机构地区河南农业大学信息管理学院华北水利水电学院数学与信息科学学院

出处《河南科学》 2008年第3期268-271,共4页 Henan Science

基金河南省自然科学基金(2007110013)

关键词启发式算法最劣性能比强NP困难 heuristic worst-case performance strongly NP-hard

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献1

1越民义.A SIMPLE PROOF OF THE INEQUALITY FFD (L)≤11/9 OPT(L)+1, ■L FOR THE FFD BIN-PACKING ALGORITHM[J].Acta Mathematicae Applicatae Sinica,1991,7(4):321-331. 被引量：6

共引文献5

1李荣珩,越民义.A TIGHTER BOUND FOR FFd ALGORITHM[J].Acta Mathematicae Applicatae Sinica,2000,16(4):337-347.
2录岭法,陈友军,原晋江.加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题(英文)[J].运筹学学报,2007,11(1):16-22. 被引量：2
3吴海双,张亮,李杰辉.IaaS环境中一种保证SLA的资源调度策略[J].计算机工程,2013,39(7):51-54. 被引量：5
4陈旭瑾,徐大川,张国川.组合优化若干经典问题新进展[J].运筹学学报,2014,18(1):149-158. 被引量：6
5陈婳,张国川.经典一维装箱问题近似算法的研究进展[J].运筹学学报,2022,26(1):69-84. 被引量：3

1杨晓光.具有交货期窗口满意数最大的排序问题算法复杂性[J].系统工程理论方法应用,2000,9(1):1-4. 被引量：5
2录岭法,陈友军,原晋江.加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题(英文)[J].运筹学学报,2007,11(1):16-22. 被引量：2
3杨晓光.异时排序问题的算法复杂性[J].应用数学与计算数学学报,1999,13(2):94-96.
4时凌,徐春.流水作业排序问题的启发式算法[J].华中科技大学学报（自然科学版）,2010,38(5):13-15. 被引量：1
5陈秀宏.一类三机器流水作业极小化加工全长问题[J].淮阴师范学院学报（自然科学版）,2002,1(2):1-5.
6成岗,鲁习文.含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性[J].运筹学学报,2003,7(4):86-96. 被引量：3
7刘其佳,冯琪.有界平行批处理机的在线排序问题[J].河南师范大学学报（自然科学版）,2015,43(5):8-11.
8徐平生.转盘上单机排序问题的可解情形[J].铁道师院学报,1998,15(1):7-10.
9农庆琴,原晋江.最小最大树划分的近似算法与最小和树划分的精确算法[J].运筹学学报,2006,10(4):115-121. 被引量：1
10臧西杰,李士生.两类极小化最大加权完工时间排序问题研究[J].佛山科学技术学院学报（自然科学版）,2014,32(3):18-20.

河南科学

2008年第3期

浏览历史

内容加载中请稍等...

单机工件运输排序问题上界的改进

参考文献1

共引文献5

相关作者

相关机构

相关主题

浏览历史