An index policy for a stochastic scheduling model with improving/deteriorating jobs

We consider stochastic scheduling models which have the natural character that jobs improve while being processed, but deteriorate (and may possibly leave the system altogether) while processing is diverted elsewhere. Such restless bandit problems are shown to be indexable in the sense of Whittle. A numerical study which elucidates the strong performance of the resulting index policy is complemented by a theoretical study which demonstrates the optimality of the index policy under given conditions and which develops performance guarantees for the index heuristic more generally. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 706–721, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10036     

The effect of correlated exponential service times on single server tandem queues

An investigation via simulation of system performance of two stage queues in series (single server, first-come, first-served) under the assumption of correlated exponential service times indicates that the system's behavior is quite sensitive to departures from the traditional assumption of mutually independent service times, especially at higher utilizations. That service times at the various stages of a tandem queueing system for a given customer should be correlated is intuitively appealing and apparently not at all atypical. Since tandem queues occur frequently, e.g. production lines and the logistics therewith associated, it is incumbent on both the practitioner and the theoretician that they be aware of the marked effects that may be induced by correlated service times. For the case of infinite interstage storage, system performance is improved by positive correlation and impaired by negative correlation. This change in system performance is reversed however for zero interstage storage and depends on the value of the utilization rate for the case where interstage storage equals unity. The effect due to correlation is shown to be statistically significant using spectral analytic techniques. For correlation equal unity and infinite interstage storage, results are provided for two through twenty-five stages in series to suggest how adding stages affects system performance for ρ>0. In this extreme case of correlation, adding stages has an effect on system performance which depends markedly on the utilization rate. Recursive formulae for the waiting time per customer for the cases of zero, one, and infinite interstage storage are derived.