Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumed the linearity of job holding costs, which is arguably not appropriate in some applications. This motivates our study of a model for scheduling $n$ classes of stochastic jobs on a single machine, with the objective of minimizing the total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable, nondecreasing and convex on the number of jobs in each class. We formulate the problem as a linear program over a certain greedoid polytope, and establish that it is solved optimally by a dynamic (priority) index rule,which extends the classical Smith's rule (1956) for the linear case. Unlike Smith's indices, defined for each class, our new indices are defined for each extended class, consisting of a class and a number of jobs in that class, and yield an optimal dynamic index rule: work at each time on a job whose current extended class has larger index. We further show that the indices possess a decomposition property, as they are computed separately for each class, and interpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time. We establish the results by deploying a methodology recently introduced by us [J. Niño-Mora (1999). "Restless bandits, partial conservation laws, and indexability. "Forthcoming in Advances in Applied Probability Vol. 33 No. 1, 2001], based on the satisfaction by performance measures of partial conservation laws (PCL) (which extend the generalized conservation laws of Bertsimas and Niño-Mora (1996)): PCL provide a polyhedral framework for establishing the optimality of index policies with special structure in scheduling problems under admissible objectives, which we apply to the model of concern.