Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
E. G. Coffman, Jr., G. S. Lueker, A. H. G. Rinnooy Kan
Management Science · 1988 · Volume 34 · Issue 3
Abstract
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.
Keywords
programming: integer algorithms, heuristic
Enable JavaScript for citation tools and additional paper interactions.