A Morph-Based Simulated Annealing Heuristic for a Modified Bin-Packing Problem

dc.contributor.authorBrusco, Michael J.
dc.contributor.authorThompson, Gary
dc.contributor.authorJacobs, Larry W.
dc.description.abstractThis 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.
dc.description.legacydownloadsThompson38_A_morph_based.pdf: 57 downloads, before Aug. 1, 2020.
dc.rightsRequired Publisher Statement: © Taylor & Francis. Final version published as: Brusco, M. J., Thompson, G. M., & Jacobs, L. W. (1997) A morph-based simulated annealing heuristic for a modified bin-packing problem. Journal of the Operational Research Society, 48(4), 433-439. doi: 10.1057/palgrave.jors.2600356 Reprinted with permission. All rights reserved.
dc.subjectbin packing
dc.subjectsimulated annealing
dc.titleA Morph-Based Simulated Annealing Heuristic for a Modified Bin-Packing Problem
local.authorAffiliationBrusco, Michael J.: Florida State University
local.authorAffiliationThompson, Gary: gmt1@cornell.edu Cornell University School of Hotel Administration
local.authorAffiliationJacobs, Larry W.: Northern Illinois University
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
215.51 KB
Adobe Portable Document Format