Resource Allocation under Uncertainty
Applications in Mobile
PhD Thesis, Uppsala University,
Sept. 2004, 221 pp.
Dissertation in Signal Processing to be publicly examined
in room K23, Magistern, Dag Hammarskjölds väg 31,
Uppsala on October 8, 2004 at 10.15 a.m.
Professor Vikram Krishnamurthy,
The University of British Columbia, Canada,
The thesis available in
Paper copies of the thesis can be obtained from
Signals and Systems Group, Uppsala University,
Box 534, SE-75121 Uppsala, Sweden.
See also the thesis homepage
at the Uppsala University database for Ph.D. theses.
This material is presented to ensure timely dissemination
of scholarly and technical work. Copyright and all rights
therein are retained by authors.
All persons copying this information are expected to
adhere to the terms and constraints invoked by each authors
copyright. This work may not be reposted
without the explicit permission of the copyright holders.
In this thesis we consider a number of problems
with the common feature that they all require
decisions on how to allocate resources among
different tasks under uncertainty concerning
the demand and potentially also the supply of
We first study a model problem from
the manufacturing industry in which a plant
manager has a number of production units
which are used to produce different sorts of widgets.
The manager's aim is to meet the order
intake, but the task is complicated by uncertainty
concerning the future order intakes as
well as possibly uncertain production capacities.
We then consider the customer
perspective in an auctioning situation.
With only limited information concerning
other customers' bids, what amount should
an individual customer bid? The answer
obviously depends on what the expected
benefit of the customer will be from winning,
and we therefore investigate a few different
Based on the general ideas that
we formulate in connection to these two
problems, we then consider a number of
specific problems which are of current interest
in digital mobile cellular communications.
The objective is to increase the resource
efficiency, or to maximize the useful work
performed by the resources, over a given
time horizon and thereby achieve a more
cost-efficient cellular network.
This thesis is concerned with scheduling the use of
resources, or allocating resources, so as to meet future demands
for the entities produced by the resources. We consider
applications in mobile communications such as scheduling users'
transmissions so that the amount of transmitted information is
maximized, and scenarios in the manufacturing industry where the
task is to distribute work among production units so as to
minimize the number of missed orders.
The allocation decisions are complicated by a lack of information
concerning the future demand and possibly also about the
capacities of the available resources. We therefore resort to
using probability theory and the maximum entropy principle as a
means for making rational decisions under uncertainty.
By using probabilities interpreted as a reasonable degree of
belief, we find optimum decision rules for the manufacturing
problem, bidding under uncertainty in a certain type of auctions,
scheduling users in communications with uncertain channel
qualities and uncertain arrival rates, quantization of channel
information, partitioning bandwidth between interfering and
non-interfering areas in cellular networks, hand-overs and
admission control. Moreover, a new method for making optimum
approximate Bayesian inference is introduced.
We further discuss reasonable optimization criteria for the
mentioned applications, and provide an introduction to the topic
of probability theory as an extension to two-valued logic. It is
argued that this view unifies a wide range of resource-allocation
problems, and we discuss various directions for further research.
Resource allocation, uncertainty, probability theory as
logic, scheduling, mulytiuser diversity,
Jaynes, maximum entropy,
Bayesian probability theory.
Table of Contents:
- Probability Theory as Logic
- Controlling Production Resources to Meet Customer Demands
- Bidding under Uncertainty in a Certain Type of Auctions
- Scheduling for Maximum Througput under Uncertainty
- Implications of Limited Feedback for Scheduling and
Adaptive Modulation - Througput, Sensitivity, Fairness
and A Way Out
- Inter-Cell Scheduling, Access Control and Hand-Overs
- A New Method for Adaptive Approximation of
Non-Stationary Posterior Distributions and Expectations.
IEEE Trans. VT 2008 on
dynamic reuse partitioning within cells based on local
channel and arrival rate fluctuations.
IEEE Trans. IT 2005 on
Resource allocation under unceratinty using the Maximum Entropy
IEEE SP Letters 2007 on
Bayesian model selection for Markov, Hidden Markov,
and Multinomial models.
approximate Bayesian inference by adaptive quantization
of the hypothesis space.
Diversity-Enhanced Equal Access.
on benefits of multiuser diversity with limited feedback.
on multiuser diversity and maximum entropy scheduling.
on probabilistic resource allocation and scheduling.