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: | Jacobs Larry W., Brusco Michael J., Thompson G.M. |
Keywords: | bin packing |
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