A Morph-Based Simulated Annealing Heuristic for a Modified Bin-Packing Problem
Loading...
No Access Until
Permanent Link(s)
Collections
Other Titles
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.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
1997-01-01
Publisher
Keywords
bin packing; heuristics; simulated annealing
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Required 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.
Rights URI
Types
article