Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem |
| |
Authors: | Krzysztof Fleszar Christoforos Charalambous |
| |
Affiliation: | 1. Olayan School of Business, American University of Beirut (AUB), P.O. Box 11-0236, Riad El Solh, Beirut 1107 2020, Lebanon;2. Department of Computer Science, Frederick University, P.O. Box 24729, 1303 Nicosia, Cyprus |
| |
Abstract: | Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time. |
| |
Keywords: | Packing Heuristics Bin-packing Bin-oriented heuristics Reductions |
本文献已被 ScienceDirect 等数据库收录! |
|