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 assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe 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 eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Endogenous spillovers, increased competition and re-organization waves

We consider an entrepreneur that is the sole producer of a costreducing skill, but the entrepreneur that hires a team to usethe skill cannot prevent collusive trade for the innovation related knowledge between employees and competitors. We showthat there are two types of diffusion avoiding strategies forthe entrepreneur to preempt collusive communication i) settingup a large productive capacity (the traditional firm) and ii)keeping a small team (the lean firm). The traditional firm ischaracterized by its many "marginal" employees that work shortdays, receive flat wages and are incompletely informed about the innovation. The lean firm is small in number of employees,engages in complete information sharing among members, that are paid with stock option schemes. We find that the lean firm is superior to the traditional firm when technological entry costsare low and when the sector is immature.