Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case

Dimitris Bertsimas and José Niño-Mora

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

Abstract: We address the problem of scheduling a multi-station multiclass queueing network (MQNET) with server changeover times to minimize steady-state mean job holding costs. We present new lower bounds on the best achievable cost that emerge as the values of mathematical programming problems (linear, semidefinite, and convex) over relaxed formulations of the system's achievable performance region. The constraints on achievable performance defining these formulations are obtained by formulating system's equilibrium relations. Our contributions include: (1) a flow conservation interpretation and closed formulae for the constraints previously derived by the potential function method; (2) new work decomposition laws for MQNETs; (3) new constraints (linear, convex, and semidefinite) on the performance region of first and second moments of queue lengths for MQNETs; (4) a fast bound for a MQNET with N customer classes computed in N steps; (5) two heuristic scheduling policies: a priority-index policy, and a policy extracted from the solution of a linear programming relaxation.

Keywords: Multiclass queueing network; changeover times; optimal scheduling; performance region; linear programming relaxation; semidefinite programming; convex programming (search for similar items in EconPapers)
JEL-codes: C61 C63 (search for similar items in EconPapers)
Date: 1996-09, Revised 1998-08
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://econ-papers.upf.edu/papers/314.pdf Whole Paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:upf:upfgen:314

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by ( this e-mail address is bad, please contact ).