ON OPTIMAL PACKING OF RANDOMLY ARRIVING OBJECTS

被引:6
作者
COURCOUBETIS, C
ROTHBLUM, UG
机构
[1] TECHNION ISRAEL INST TECHNOL,FAC IND ENGN & MANAGEMENT,IL-32000 HAIFA,ISRAEL
[2] RUTGERS STATE UNIV,HILL CTR MATH SCI,RUTGERS CTR OPERAT RES,NEW BRUNSWICK,NJ 08903
关键词
OPTIMAL BIN PACKING; POISSON ARRIVALS; QUEUE SIZE;
D O I
10.1287/moor.16.1.176
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
Objects of finitely many types arrive at a facility according to independent stationary Poisson processes. The objects are to be placed in boxes as they arrive. There are finitely many types of boxes and each box type has its own packing configuration. There is an unlimited supply of boxes of each type and once an object is placed in a box it cannot be moved to another box in the future. When a box is completely filled it produces a reward which depends on its configuration. The objective is to select a rule for placing the arriving objects in boxes so as to maximize expected reward. We show how to construct optimal and epsilon-optimal policies under which the expected number of partially packed boxes does not explode.
引用
收藏
页码:176 / 194
页数:19
相关论文
共 8 条
[1]   NECESSARY AND SUFFICIENT CONDITIONS FOR STABILITY OF A BIN-PACKING SYSTEM [J].
COURCOUBETIS, C ;
WEBER, RR .
JOURNAL OF APPLIED PROBABILITY, 1986, 23 (04) :989-999
[2]  
COURCOUBETIS C, 1986, 25TH P IEEE CDC ATH
[3]  
EAVES BC, 1990, LINEAR ALGEBRA APPL, V132, P1
[4]   A DISCRETE-TIME AVERAGE COST FLEXIBLE MANUFACTURING AND OPERATOR SCHEDULING MODEL SOLVED BY DECONVEXIFICATION OVER TIME [J].
EAVES, BC ;
ROTHBLUM, UG .
OPERATIONS RESEARCH, 1988, 36 (02) :242-257
[5]  
EAVES BC, 1989, LINEAR ALGEBRA APPL, V114, P417
[6]  
FELLER W, 1968, INTRO THEORY PROBABL, V1
[8]  
Keilson, 1979, MARKOV CHAIN MODELS