D. Bertsimas et J. Nino-mora, Optimization of multiclass queueing networks with changeover times via theachievable region approach: Part II, the multi-station case, MATH OPER R, 24(2), 1999, pp. 331-361
We address the problem of scheduling a multi-station multiclass queueing ne
twork (MQNET) with server changeover times to minimize steady-state mean jo
b holding costs. We present new lower bounds on the best achievable cost th
at emerge as the values of mathematical programming problems (linear, semid
efinite, and convex) over relaxed formulations of the system's achievable p
erformance region. The constraints on achievable performance defining these
formulations are obtained by formulating system's equilibrium relations. O
ur 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 (li
near, convex, and semidefinite) on the performance region of first and seco
nd 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 policie
s: a priority-index policy, and a policy extracted from the solution of a l
inear programming relaxation.