期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

局内装箱算法综述 被引量：2

A Survey of Online Bin Packing Algorithms
下载PDF
导出
摘要 系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。 Online bin packing problem is introduced. Developments in online bin packing problem such as analysis of items distribution, dividing and optimizing of bins are reviewed. Then, it has been successfully applied to much engineering: job scheduling and allocating resource etc. At last, a brief conclusion and further research direction are given.
作者 杨鼎强 王晨
机构地区 湖南大学软件学院 中国湖南国际经济技术合作公司
出处 《计算机与现代化》 2005年第5期7-11,共5页 Computer and Modernization
关键词 装箱问题 局内 近似算法 最坏情况渐近性能比 bin packing online approximation algorithms asymptotic worst-case performance ratio
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献20

  • 1Johnson D S. Fast algorithms for bin packing[J].Journal of Computer and System Sciences,1974,8: 272-314.
  • 2D S Johnson,A Demers,J D llman,M R Garey,R L Graham.Worst-case performance bounds for simple one-dimensional packing algorithms[J]. SIAM Journal on Computing,1974,3(4): 299-325.
  • 3Yao A C C.New algorithms for bin packing[J]. Journal of the ACM, 1980, 27:207-227.
  • 4Brown D J.A Lower Bound for On-line One-dimensional Bin Packing Algorithms[R]. Tech. Rep. R-864, Coordinated Sci. Lab., University of Illinois at Urbana-Champaign, 1979.
  • 5Liang F M.A lower bound for online bin packing[J].Information Processing Letters,1980,10:76-79.
  • 6Van Vliet A.An improved lower bound for online bin packing algorithms[J].Information Processing Letters,1992,43(5):277-284.
  • 7Lee C,Lee D.A simple on-line bin-packing algorithm[J]. Journal of the ACM,1985,32(3):562-572.
  • 8Ramanan P,Brown D,Lee C,Lee D.On-line bin packing in linear time[J]. Journal of Algorithms,1989,10(3):305-326.
  • 9Steven S Seiden,Rob Van Stee, Leah Epstein. New bounds for variable-sized online bin packing[J]. SIAM Journal on Computing,2002,32(2):455-469.
  • 10P Manyem. Bin packing and covering with longest items at the bottom[J]. ANZIAM Journal,2002,43(E): 186-232.

同被引文献11

  • 1孙春玲,陈智斌,李建平.装箱问题的一种新的近似算法[J].云南大学学报（自然科学版）,2004,26(5):392-396. 被引量：24
  • 2Jaeek Blazewicz, Klaus H Ecker, Erwin Pesch,et al Handbook on Scheduling: From Theory to Appliea tions[M]. New York.. Springer-Verlag Berlin Heidel berg, 2007.
  • 3William Leinberger, George Karypis, Vipin Kumar. Multi-capacity Bin Packing Algorithms with Appli- cations to Job Scheduling under Multiple Con- straints[R]. Minnesota.. Department of Computer Sci- ence and Engineering, University of Minnesota, 1999.
  • 4Devavrat Shah, John N Tsitsiklis. Bin Packing with Queues [EB/OL]. http..//www, mit. edu/~ de- vavrat/binpack, pdf, 2006-12-04.
  • 5Duin C W, Van Sluis E. ()n the Complexity of Ad- jacent Resource Scheduling[J]. Journal of Schedu- ling, 2006, 9(1): 49-62.
  • 6Jacob Jan Paulus, Johann Hurink. Adjacent-resource Scheduling: Why Spatial Resources are so Hard to Incorporate[J]. Electronic Notes in Discrete Mathe- matics, 2006, 25: 113-116.
  • 7Hurink J L, Paulus J J. Online Algorithms for Par- allel Job Scheduling and Strip Packing[A]. Pro- ceeding of the 5th International Workshop on Ap- proximation and Online Algorithms [C]. Eilat, 2008..67 74.
  • 8Ranjan Vargheset, Duck Young YoorL Dynamic Spatial Block Arrangement Scheduling in Shipbuilding Industry Using Genetic Algorithm[A]. Proceedings of the 3rd IEEE International Conference on Industrial Informatics [C]. Perth, 2005 : 444-449.
  • 9Piyush Raj, Rajiv K Srivastava. Analytical and Heuris- tic Approaches for Solving the Spatial Scheduling Prob- lem[A]. Proceedings of the 2007 IEEE IEEM[C]. Singapore, 2007:1 093-1 097.
  • 10Lueker G S. Bin Packing with Items Uniformly Dis- tributed Over Intervals [a, b] [A]. 24th Annual Symposiumon Foundations of Computer Science [C]. Tucson, 1983:289-297.

引证文献2

二级引证文献2

计算机与现代化
2005年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部