Paper Info
Title
Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem
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.
Year
DOI
Venue
2011
10.1016/j.ejor.2010.11.004
European Journal of Operational Research
Keywords
Field
DocType
Packing,Heuristics,Bin-packing,Bin-oriented heuristics,Reductions
Mathematical optimization,Heuristic,Bin,Heuristics,Body weight,Constructive heuristic,Operations management,Bin packing problem,Mathematics,Computation
Journal
Volume
Issue
ISSN
210
2
0377-2217
Citations 
PageRank 
References 
13
0.58
20
Authors
2
Name
Order
Citations
PageRank
Krzysztof Fleszar136825.38
Christoforos Charalambous2504.35