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

带启动重量的脆度装箱问题

Fragile bin-packing problem with start-up weight
在线阅读 下载PDF
导出
摘要 讨论如下定义的带启动重量的脆度装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数(脆度和重量),若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小.该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配.本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果. A fragile bin-packing problem with start-up weight is discussed in this paper. Supposing there are many one-dimensional boxes with the same size and a list of objects which have two attributes-fragility and weight. The bin needs to be put some additional start-up weight if the bin is filled with objects for the first time. Make sure that the total weight of the every bin and the objects within the bins can not exceed the minimum fragility of the objects inside the bin. Using the fewest bins to arrange the objects is a new combina- torial optimization problem which comes from the channel allocation in CDMA cellular com- munication system. A linear off-line approximation algorithm C-NFI is offered to solve the problem. It proves that the C-NFI algorithm has an asymptotic worst case performance rati- o of 2 and the corresponding experimental results are given.
作者 杨鼎强 刘林浩 单树民
机构地区 长沙理工大学计算机与通信工程学院
出处 《长沙理工大学学报（自然科学版）》 CAS 2013年第2期69-74,共6页 Journal of Changsha University of Science and Technology:Natural Science
基金 湖南省科技厅科研计划资助项目(2011GK3120)
关键词 信道分配 装箱问题 脆度 最坏情况渐进性能比 channel assignment bin-packing problem fragile worst-case performance ratio
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献12

  • 1Parikh, Pratik J Scott, Rosalyn Barnes. A dual bin- packing approach to scheduling surgical cases at a publicly-funded hospital [J].European Journal of Operational Research, 2012,35 (8) : 78-88.
  • 2Hsiao Ping-Che. A VNS-based hyper-heuristic with adaptive computational budget of local searchI-A]. Congress on Evolutionary Computation[C]. Taipei:IEEE Press,2012:231-237.
  • 3Isabel Correiaa, Luis Gouveiab,Francisco Saldanha- da-Gamab. Solving the variable size bin-packing problem with discredited formulations[A]. The 7th Proceedings of the Latin America Transmission and Distribution Conference and Exposition[C]. Caracas : IEEE Press, 2006 : 156-166.
  • 4David Pisinger, Mikkel Sigurd. The two-dimensional bin-packing problem with variable bin sizes and costs [J]. Discrete Optimization,2009,18(2) :154-167.
  • 5Francois Clautiauxa,Jacques Carlierb, Aziz Moukrimb. A new exact method for the two-dimensional bin-pack- ing problem with fixed orientation[A]. The 8th In- ternational Symposium on Communication Systems, Networks and Digital Signal Pro-cessing[C]. Bourne- mouth:IEEE Press,2011 : 89-98.
  • 6Zong Rong-Fang,Lu Hong. Adaptive immune evolu- tionary algorithm for multi-objective function optimi- zation[J]. Journal of Convergence Information Tech- nology,2011,20(5) : 111-116.
  • 7Ali Khanafer, Francois Clautiaux, E1-Ghazali Talbi. Tree-decomposition based heuristics for the two-di- mensional bin-packing problem with conflicts [A]. The 2nd International Conference on Information Technology[C]. Hyderabad: IEEE Press, 2010: 83- 86.
  • 8Ping Gu,Qingsheng Zhu, Haibo Liu,et al. Hierarchi- cal model exploiting context and semantic relation- ship for document classification[J]. Journal of Con- vergence Information Technology, 2011,20 (8) : 275- 282.
  • 9Mehdi Nasiri,Leyla Sadat Taghavi,Behrouz Minaee. Multi-objective rule mining using simulated annea- ling algorithm[J]. Journal of Convergence Informa tion Technology, 2010,8 (5) : 60-68.
  • 10Zsolt Ddnyddi. A fuzzy bacterial evolutionary solu- tion for crisp three-dimensional bin-paeking prob- lems[A]. International Conference on Fuzzy Sys- tems[C]. Gyor :IEEE Press, 2012 : 1-5.
长沙理工大学学报（自然科学版）
2013年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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