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

Welcome to the UPF Digital Repository

Niño-Mora, José. Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs. 2000
http://hdl.handle.net/10230/388
To cite or link this document: http://hdl.handle.net/10230/388
dc.contributor.author Niño-Mora, José
dc.contributor.other Universitat Pompeu Fabra. Departament d'Economia i Empresa
dc.date.issued 2000-11-01
dc.identifier.uri http://hdl.handle.net/10230/388
dc.description.abstract 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.
dc.language.iso eng
dc.relation.ispartofseries Economics and Business Working Papers Series; 514
dc.rights L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.title Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs
dc.type info:eu-repo/semantics/workingPaper
dc.date.modified 2014-06-03T07:14:03Z
dc.subject.keyword Operations Management
dc.subject.keyword stochastic scheduling
dc.subject.keyword dynamic index rule
dc.subject.keyword decomposition
dc.subject.keyword convex holding costs
dc.subject.keyword conservation laws
dc.subject.keyword achievable region
dc.subject.keyword linear programming relaxation
dc.subject.keyword polyhedral methods
dc.rights.accessRights info:eu-repo/semantics/openAccess


See full text
This document is licensed under a Creative Commons license:

Search


Advanced Search

Browse

My Account

Statistics