Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

Recently there has been considerable interest in the average-case performance of heuristics. This paper pursues that interest, where it concerns sequencing and packing problems. In particular, we survey the methods that have been used to obtain formal probabilistic analyses of heuristics for makespan scheduling and one-dimensional bin packing. In so doing, we present many of the key results in these research areas.

MoreLess

Year of publication:	1988
Authors:	E. G. Coffman, Jr. ; Lueker, G. S. ; Kan, A. H. G. Rinnooy
Published in:	Management Science. - Institute for Operations Research and the Management Sciences - INFORMS, ISSN 0025-1909. - Vol. 34.1988, 3, p. 266-290
Publisher:	Institute for Operations Research and the Management Sciences - INFORMS
Subject:	programming: integer algorithms \| heuristic

More details

Extent:	application/pdf
Type of publication:	Article
Other identifiers:	10.1287/mnsc.34.3.266 [DOI]
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10009191667