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

Simple item page
dc.contributor.authorBrusco, Michael J.
dc.contributor.authorThompson, Gary
dc.contributor.authorJacobs, Larry W.
dc.date.accessioned2020-09-12T21:14:30Z
dc.date.available2020-09-12T21:14:30Z
dc.date.issued1997-01-01
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.identifier.other12282397
dc.identifier.urihttps://hdl.handle.net/1813/72472
dc.language.isoen_US
dc.relation.doihttps://doi.org/10.1057/palgrave.jors.2600356
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.subjectheuristics
dc.subjectsimulated annealing
dc.titleA Morph-Based Simulated Annealing Heuristic for a Modified Bin-Packing Problem
dc.typearticle
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
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Thompson38_A_morph_based.pdf
Size:
215.51 KB
Format:
Adobe Portable Document Format
Download
Collections
SHA Articles and Chapters