The sequence with nth term defined by left bracket (n plus 1)p right bracket - (np) is an extremal zero-one valued sequence of asymptotic mean p in the following sense (for example): if a fraction p of customers from a point process with iid interarrival times is sent to an exponential server queue according to a prespecified splitting sequence, then the long-term average queue size is minimized when the above sequence is used. The proof involves consideration of the lower convex envelope J (which is a function on R**m) of a function J on Z**m. An explicit representation is given for J in terms of J, for J in a broad class of functions, which we call 'multimodular'. The expected queue size just before an arrival, considered as a function of the zero-one splitting sequence, is shown to belong to this class.
ASJC Scopus subject areas
- Computer Science Applications
- Management Science and Operations Research