Engineering topics

Towsley, Don

Publications and source records attributed to Towsley, Don.

3 records

NASA NTRS1992

Static assignment of complex stochastic tasks using stochastic majorization

We consider the problem of statically assigning many tasks to a (smaller) system of homogeneous processors, where a task's structure is modeled as a branching process, and all tasks are assumed to have identical behavior. We show how the theory of majorization can be used to obtain a partial order among possible task assignments. Our results show that if the vector of numbers of tasks assigned to each processor under one mapping is majorized by that of another mapping, then the former mapping is better than the latter with respect to a large number of objective functions. In particular, we show how measurements of finishing time, resource utilization, and reliability are all captured by the theory. We also show how the theory may be applied to the problem of partitioning a pool of processors for distribution among parallelizable tasks.

Nicol, David↗

NASA NTRS1992

Optimal routing and buffer allocation for a class of finite capacity queueing systems

The problem of routing jobs to K parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Routing decisions are taken by a controller which has buffering space available to it and may delay routing of a customer to a queue. Using ideas from weak majorization, it is shown that the shorter nonfull queue delayed (SNQD) policy minimizes both the total number of customers in the system at any time and the number of customers that are rejected by that time. The SNQD policy always delays routing decisions as long as all servers are busy. Only when all the buffers at the controller are occupied is a customer routed to the queue with the shortest queue length that is not at capacity. Moreover, it is shown that, if a fixed number of buffers is to be distributed among the K queues, then the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.

Towsley, Don↗

NASA NTRS1990

Stochastic ordering properties and optimal routing control for a class of finite capacity queueing systems

The problem of routing jobs to parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Stochastic ordering and weak majorization properties on critical performance measures are established by means of event-driven inductions. In particular, it is shown that the intuitive 'join the shortest non-full queue' (SNQ) policy is optimal with respect to an overall function that accounts for holding and blocking costs. Moreover, the buffer allocation problem is solved by proving the intuitive result that, for a fixed total buffer capacity, the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.

Towsley, Don↗