Last two fit augmentation to the well-known construction heuristics for one-dimensional bin-packing problem: an empirical study
SCIE
SCOPUS
- Title
- Last two fit augmentation to the well-known construction heuristics for one-dimensional bin-packing problem: an empirical study
- Authors
- Kim, BI; Wy, J
- Date Issued
- 2010-10
- Publisher
- SPRINGER LONDON LTD
- Abstract
- The bin-packing problem is a combinatorial optimization problem that has been widely applied in many manufacturing and logistics industries. It requires packing a set of different-sized items into a minimum number of identical bins. This paper introduces the last two fit (L2F) augmentation to the well-known next fit decreasing, first fit decreasing, and best fit decreasing algorithms for the one-dimensional bin-packing problem. L2F checks whether an additional item can be packed into the bin when an item is packed; if it cannot be done, replacement of the item with a pair of two unpacked items whose combined size is larger than the item is pursued. The focus of this paper is on improving the well-known construction heuristics with L2F and comparing their performance to the original heuristics. Experiments with benchmark problem sets show the effectiveness of the L2F augmented algorithms.
- Keywords
- Bin packing; Heuristics; First fit decreasing; Last two fit; LOWER BOUNDS; ALGORITHM
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/25623
- DOI
- 10.1007/S00170-010-2572-Z
- ISSN
- 0268-3768
- Article Type
- Article
- Citation
- INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, vol. 50, no. 9-12, page. 1145 - 1152, 2010-10
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.