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 条
[21]   A PROBABILISTIC ANALYSIS OF THE NEXT FIT DECREASING BIN PACKING HEURISTIC [J].
CSIRIK, J ;
GALAMBOS, G ;
FRENK, JBG ;
FRIEZE, AM ;
KAN, AHGR .
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
[29]   PROBABILISTIC ANALYSIS FOR SIMPLE ONE-DIMENSIONAL AND TWO-DIMENSIONAL BIN PACKING ALGORITHMS [J].
FREDERICKSON, GN .
INFORMATION PROCESSING LETTERS, 1980, 11 (4-5) :156-161
[30]  
FRENK JBG, 1985, MATH OPER RES
1234567