ASYMPTOTIC METHODS IN THE PROBABILISTIC ANALYSIS OF SEQUENCING AND PACKING HEURISTICS

被引:30
作者
COFFMAN, EG
LUEKER, GS
KAN, AHGR
机构
[1] UNIV CALIF IRVINE,INFORMAT & COMP SCI,IRVINE,CA 92717
[2] ERASMUS UNIV,INST ECONOMETR,3000 DR ROTTERDAM,NETHERLANDS
关键词
MATHEMATICAL PROGRAMMING - MATHEMATICAL TECHNIQUES - Combinatorial Mathematics;
D O I
10.1287/mnsc.34.3.266
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:266 / 290
页数:25
相关论文
共 68 条
  • [21] A PROBABILISTIC ANALYSIS OF THE NEXT FIT DECREASING BIN PACKING HEURISTIC
    CSIRIK, J
    GALAMBOS, G
    FRENK, JBG
    FRIEZE, AM
    KAN, AHGR
    [J]. OPERATIONS RESEARCH LETTERS, 1986, 5 (05) : 233 - 236
  • [22] CSIRIK J, 1986, UNPUB PROBABILISTIC
  • [23] Durbin J., 1973, DISTRIBUTION THEORY
  • [24] DYER ME, 1986, UNPUB NOTE GREEDY AL
  • [25] Erdos P., 1974, PROBABILISTIC METHOD
  • [26] Feller W., 2008, INTRO PROBABILITY TH
  • [27] Feller W., 1968, INTRO PROBABILITY IT, V1
  • [28] Floyd S., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P322, DOI 10.1109/SFCS.1986.18
  • [30] FRENK JBG, 1985, MATH OPER RES