Paper #302

Título:

Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case

Autores:

Dimitris Bertsimas y José Niño-Mora

Data:

Julio 1996

Resumen:

We address the performance optimization problem in a single-station multiclass queueing network with changeover times by means of the achievable region approach. This approach seeks to obtain performance bounds and scheduling policies from the solution of a mathematical program over a relaxation of the system's performance region. Relaxed formulations (including linear, convex, nonconvex and positive semidefinite constraints) of this region are developed by formulating equilibrium relations satisfied by the system, with the help of Palm calculus. Our contributions include: (1) new constraints formulating equilibrium relations on server dynamics; (2) a flow conservation interpretation of the constraints previously derived by the potential function method; (3) new positive semidefinite constraints; (4) new work decomposition laws for single-station multiclass queueing networks, which yield new convex constraints; (5) a unified buffer occupancy method of performance analysis obtained from the constraints; (6) heuristic scheduling policies from the solution of the relaxations.

Palabras clave:

Multiclass queueing networks, optimal scheduling, achievable region, changeover times, polling systems, stochastic scheduling

Códigos JEL:

C61, C63

Área de investigación:

Gestión de la Producción y de las Operaciones

Publicado en:

Mathematics of Operations Research, 24, (1999), pp. 306-330

Descargar el paper en formato PDF