A morph-based simulated annealing heuristic for a modified bin-packing problem
- PDF / 200,117 Bytes
- 7 Pages / 595 x 842 pts (A4) Page_size
- 31 Downloads / 183 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
A morph-based simulated annealing heuristic for a modi®ed bin-packing problem MJ Brusco1, GM Thompson2 and LW Jacobs3 1
College of Business, Tallahassee, USA; 2Cornell University, USA; and 3Northern Illinois University, USA
This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modi®ed binpacking problem (MBPP). The objective of the MBPP is to assign items of various sizes to a ®xed 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 in®nite-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 signi®cant enhancement to SA algorithms for these problems. Keywords: bin packing; heuristics; simulated annealing
INTRODUCTION The classic bin-packing problem (CBPP) in one dimension can be described using notation consistent with that of Hall et al.1, as follows: Min
n P j1
Yj
1
Subject to n P i1
ti Xij 4 CYj
j 1; . . . ; n
2
i 1; . . . ; n
3
Xij 2 f0; 1g
i 1; . . . ; n and j 1; . . . ; n
4
Yj 2 f0; 1g
j 1; . . . ; n
5
n P j1
where
Xij 1
Yj 1 if bin j is used; 0 otherwise; Xij 1 if item i is assigned to bin j; 0 otherwise; n the number of items; ti the size of item i; and C the capacity of each bin
C 5 max14i4n fti g:
The objective of the CBPP is to pack n items of size ti
1 4 i 4 n into bins of ®xed capacity C, while using as few bins as possible. The objective function (1) is to minimize the number of bins that are used to pack items. Correspondence: MJ Brusco, Information and Management Science Department, College of Business, Tallahassee, FL 32306-1042, USA
Constraints (2) ensure that the capacity of each bin is not exceeded. Constraints (3) require that each item is assigned to exactly one bin. Constraints (4) and (5) place binary restrictions on the items assignment and bin usage variables, respectively. It is well-known that the CBPP is NPcomplete2,3 and, therefore, a substantial research effort has been devoted to the development of heuristic procedures that can ®nd good, but not necessarily optimal, solutions. Coffman et al.4 provide an excellent survey of some of the most prominent heuristic methods
Data Loading...
