IBM研究报告（pdf 21页)(英文)

1 Introduction
2 Mathematical Analysis
3 Numerical Example
4 Conclusions

 

1 Introduction
We consider a class of stochastic processes that model the problem of stochastic online bin packing in which
fractions of a single resource are allocated among multiple streams of requests with different resource requirements
such that the allocation never exceeds the total capacity of the resource. The system operates
in discrete units of time, where the allocation of resource capacity at each time epoch is governed by a
specific scheduling policy under which unallocated requests form queues. This fundamental problem was
introduced by Coffman and Stolyar [5] and its analysis is known to be very difficult. In particular, a number
of important issues of interest remain open for general instances of the problem, including stability conditions
and stationary distributions for stable processes. Our focus in this paper is on the long-run dynamics of
the request queues primarily under the Best Fit scheduling policy, a simple rule according to which requests
with the largest resource requirements are allocated first, requests with the second largest requirements are
allocated next, and so on. Our results also can be applied to other scheduling policies, as we discuss later in
the paper.

..............................