We consider a parallel-queue single-server system in which queues can be randomly connected to the server depending on an exogenous process. We study the effect that timing constraints over scheduling decisions have on the stability of the system. We consider three types of timing constraints:
I. the free setting, in which the server can switch the queue to which it is dedicated at any time;
II. the non-preemptive setting, where the server can only switch when a task is finished;
III. the server can only switch at $\gamma$-rate exponential times.
By explicitly describing the maximum stability region in each setting, we show that stability is severely affected by these timing constraints, a phenomenon that is known not to occur in the absence of random connectivities. In all these settings, the policy that at each decision epoch serves the longest connected queue is maximal stable.
To prove our results, we propose an apparently novel strategy, which we termed the test for fluid limits, that works as follows: if this test is passed by every fluid limit, then stability follows, the advantage being, of course, that this test is easy to verify in our examples.
This is a joint work with U. Ayesta (IRIT-CNRS), M. Jockheere (LAAS-CNRS) and I.M. Verloop (IRIT-CNRS).
