经典一维装箱问题近似算法的研究进展

A survey on approximation algorithms for one dimensional bin packing

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。

With the emergence of computational complexity theory,the study of approximation algorithms has gradually become an important field in combinatorial optimization since the 1970 s.As one of the classic combinatorial optimization problems,bin packing has attracted great attention.It can be widely found in various resource allocation problems with capacity constraints.Its more and more important applications including logistics loading and material cutting aside,any theoretical breakthrough of bin packing algorithms is related to the development of the whole combinatorial optimization.At present,the research on approximation algorithms of bin packing is still popular.This paper briefly introduces the process of some classic Fit algorithms,analyzes the main ideas of approximation schemes based on linear programming relaxation,reviews the state of the art,and provides some suggestions for future research.