Stochastic resource allocation problems in networks and image formation systems.

Resource allocation and scheduling problems arise in several important technological fields such as computer and communication networks, manufacturing systems, image formation systems, as well as in economic systems. The fundamental issue in resource allocation problems is the following. There is a large number of tasks (jobs, messages, etc) to be processed; each task has its own processing characteristics and its own Quality of Service (QoS) requirements (e.g. deadlines, delay, percentage of packet losses, etc). There is a limited amount of resources to process the tasks. The resources must be allocated in such a way so as to optimize a performance criterion that accounts for the tasks' priorities and QoS requirements. An issue dual to the above is the following. Given: (i) the statistical description of the number of tasks that must be processed; (ii) the statistical description of the tasks' processing times; and (iii) the tasks' QoS requirements, determine the minimum expected amount of resources required to process the tasks and satisfy their QoS requirements. Both classes of allocation problems described above are important because they address important issues that are distinctly different from each other, in fact complementary to each other. In this dissertation we formulate and analyze problems addressing both of the aforementioned issues. In the situation where the amount of resources is fixed and the goal is to determine an optimal allocation strategy according to a specific performance criterion we consider two problems: (i) we analyze a makespan minimization problem in two interconnected queues and establish conditions on the queues' service times and the interconnection process, sufficient to guarantee the optimality of a specific priority scheduling policy; and (ii) we study a search problem with multiple sensors and determine search strategies that maximize the total probability of successful search in finite time. In the situation where the goal is to determine the minimum expected amount of resources so as to process a certain number of tasks and meet their QoS requirements, we formulate a stochastic machine minimization problem with hard deadlines, and determine qualitative properties of an allocation policy that achieves the objective.PhDApplied SciencesElectrical engineeringIndustrial engineeringOperations researchUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/131794/2/9929958.pd