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
来源：
MANAGEMENT SCIENCE | 1988年 / 34卷 / 03期
关键词：
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 条
  • [1] ON OPTIMAL MATCHINGS
    AJTAI, M
    KOMLOS, J
    TUSNADY, G
    [J]. COMBINATORICA, 1984, 4 (04) : 259 - 264
  • [2] [Anonymous], 1969, SIAM J APPL MATH
  • [3] BENTLEY J, 1980, COMMUNICATION
  • [4] BENTLEY JL, 1983, 21ST P ANN ALL C COM, P51
  • [5] BENTLEY JL, 1984, 16TH P ANN ACM S THE, P279
  • [6] BILLARD P, 1965, ANN SCI ECOLE NORM S, V82, P131
  • [7] Boxma O. J., 1984, PERFORMANCE '84: Models of Computer System Performance. Proceedings of the Tenth International Symposium, P475
  • [8] BOXMA OJ, 1985, STOCH MODELS, V1, P209
  • [9] BRUNO JL, 1985, ACTA INFORM, V22, P333, DOI 10.1007/BF00265685
  • [10] PROBABILISTIC BOUNDS ON THE PERFORMANCE OF LIST SCHEDULING
    BRUNO, JL
    DOWNEY, PJ
    [J]. SIAM JOURNAL ON COMPUTING, 1986, 15 (02) : 409 - 417
1234567