Stabilizing Queueing Networks with Setups

For multiclass queueing networks, dispatch policies govern the assignment of servers to the jobs they process. Production policies perform the analogous task for queueing networks whose servers are subject to switch-over delays or setups, a model we refer to as setup networks. It is well known that a poorly chosen dispatch policy may lead to instability of a multiclass queueing network, even when the traffic intensity at each station is less than one and the policy is nonidling. Not surprisingly, setup networks and production policies inherit these instability concerns. With this in mind, we define a family of “sensible” production policies that are adaptations of dispatch policies and restrict the frequency of setup performance.

We provide a framework for proving the stability of a setup network operating under a sensible production policy. Central to this framework is the artificial fluid model of a setup network. The artificial fluid models presented are generalizations of standard fluid models of multiclass queueing networks; see, for example, Dai (1995). Unlike their standard fluid model counterparts, artificial fluid models do not arise directly from a limiting procedure on some discrete network process; hence the “artificial” qualifier. Nevertheless, stability of the artificial fluid model implies stability of the associated setup network, a connection paralleling the main result of Dai (1995).

As an exercise in using the artificial fluid model framework for proving stability of setup networks, we investigate several production policies adapted from dispatch policies. One production policy of particular interest involves a modification of the first-in-first-out dispatch policy.