A morph-based simulated annealing heuristic for a modified bin-packing problem

A morph-based simulated annealing heuristic for a modified bin-packing problem

0.00 Avg rating0 Votes
Article ID: iaor19981864
Country: United Kingdom
Volume: 48
Issue: 4
Start Page Number: 433
End Page Number: 439
Publication Date: Apr 1997
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: bin packing
Abstract:

This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modified bin-packing problem (MBPP). The objective of the MBPP is to assign items of various sizes to a fixed number of bins, such that the sum-of-squared deviation (across all bins) from the target bin workload is minimized. This problem has a number of practical applications which include the assignment of computer jobs to processors, the assignment of projects to work teams, and infinite-loading machine scheduling problems. The SA-based heuristic we developed uses a morph-based search procedure when looking for better allocations. In a large computational study we evaluated 12 versions of this new heuristic, as well as two versions of a previously published SA-based heuristic that used a completely random search. The primary performance measure for this evaluation was the mean percent above the best known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SA heuristic was more than 290 times larger than that of the best version of the morph-based SA heuristic, we conclude that the morphing process is a significant enhancement to SA algorithms for these problems.

Reviews

Required fields are marked *. Your email address will not be published.