A MORPH-BASED SIMULATED ANNEALING HEURISTIC FOR A MODIFIED BIN-PACKING PROBLEM

This paper presents a local-search heuristic, based on the simulated a nnealing (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 bin s) from the target bin workload is minimized. This problem has a numbe r of practical applications which include the assignment of computer j obs to processors, the assignment of projects to work teams, and infin ite-loading machine scheduling problems. The SA-based heuristic we dev eloped uses a morph-based search procedure when looking for better all ocations. In a large computational study we evaluated 12 versions of t his new heuristic, as well as two versions of a previously published S A-based heuristic that used a completely random search. The primary pe rformance measure for this evaluation was the mean percent above the b est known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SE heuristic was more than 290 times larger than that of the best version of the morph-based SA heuri stic, we conclude that the morphing process is a significant enhanceme nt to SA algorithms for these problems.