Paper #302

Títol:

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

Autors:

Dimitris Bertsimas i José Niño-Mora

Data:

Juliol 1996

Resum:

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.

Paraules clau:

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

Codis JEL:

C61, C63

Àrea de Recerca:

Gestió de la Producció i de les Operacions

Publicat a:

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

Descarregar el paper en format PDF