### Abstract

In Stolyar (Queueing Systems 50 (2005) 401-457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several "commodities.") Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401-457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples.

Original language | English (US) |
---|---|

Pages (from-to) | 203-220 |

Number of pages | 18 |

Journal | Queueing Systems |

Volume | 54 |

Issue number | 3 |

DOIs | |

State | Published - Nov 1 2006 |

Externally published | Yes |

### Fingerprint

### Keywords

- Convex optimization
- Dynamic scheduling
- Greedy primal-dual algorithm
- Non-linear constraints
- Queueing networks
- Resource allocation

### ASJC Scopus subject areas

- Statistics and Probability
- Computer Science Applications
- Management Science and Operations Research
- Computational Theory and Mathematics