English, Article, Journal or magazine article edition: Beyond Smith's Rule: An Optimal Dynamic Index, Rule for Single Machine Stochastic Scheduling with Convex Holding Costs José Niño-Mora

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/155008
Physical Description
  • preprint
Language
  • English

Edition details

Title
  • Beyond Smith's Rule: An Optimal Dynamic Index, Rule for Single Machine Stochastic Scheduling with Convex Holding Costs
Author
  • José Niño-Mora
Physical Description
  • preprint
Notes
  • 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.
  • Stochastic scheduling, dynamic index rule, decomposition, convex holding costs, conservation laws, achievable region, linear programming relaxation, polyhedral methods
  • RePEc:upf:upfgen:514
Language
  • English
Contributed by
OAIster

Get this edition

Other links

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment