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

We address the performance optimization problem in a single-station multicl ass queueing network with changeover times by means of the achievable regio n 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, co nvex, nonconvex and positive semidefinite constraints) of this region are d eveloped 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 conservati on interpretation of the constraints previously derived by the potential fu nction method; (3) new positive semidefinite constraints; (4) new work deco mposition laws for single-station multiclass queueing networks, which yield new convex constraints; (5) a unified buffer occupancy method of performan ce analysis obtained from the constraints; (6) heuristic scheduling policie s from the solution of the relaxations.