## Abstract

We consider a queueing system with multitype customers and flexible (multiskilled) servers that work in parallel. If Q _{i} is the queue length of type i customers, this queue incurs cost at the rate of C _{i}(Q _{i}), where C _{i}(·) is increasing and convex. We analyze the system in heavy traffic (Harrison and Lopez 1999) and show that a very simple generalized cμ-rule (Van Mieghem 1995) minimizes both instantaneous and cumulative queueing costs, asymptotically, over essentially all scheduling disciplines, preemptive or non-preemptive. This rule aims at myopically maximizing the rate of decrease of the instantaneous cost at all times, which translates into the following: when becoming free, server j chooses for service a type i customer such that i ε arg max _{i} C′ _{i}(Q _{i})μ _{ij}, where μ _{ij} is the average service rate of type i customers by server j. An analogous version of the generalized cμ-rule asymptotically minimizes delay costs. To this end, let the cost incurred by a type i customer be an increasing convex function C _{i}(D) of its sojourn time D. Then, server j always chooses for service a customer for which the value of C′ _{i}(D)μ _{ij} is maximal, where D and i are the customer's sojourn time and type, respectively.

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

Pages (from-to) | 836-855 |

Number of pages | 20 |

Journal | Operations Research |

Volume | 52 |

Issue number | 6 |

DOIs | |

State | Published - Nov 1 2004 |

Externally published | Yes |

## Keywords

- Networks: stochastic
- Production/scheduling: sequencing/stochastic
- Queues: diffusion models, networks, optimization

## ASJC Scopus subject areas

- Computer Science Applications
- Management Science and Operations Research