Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-04T19:39:03.969Z Has data issue: false hasContentIssue false
  • English
  • Français

On permutation policies for the scheduling of deteriorating stochastic jobs on a single machine

Part of: Operations research and management science

Published online by Cambridge University Press:  14 July 2016

K. D. Glazebrook
K. D. Glazebrook*
Affiliation:
University of Newcastle upon Tyne
*
∗ Postal address: Department of Mathematics and Statistics, University of Newcastle upon Tyne, NE1 7RU, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

A single machine is available to process a collection of stochastic jobs. Processing is preemptive and so (for example) the machine is allowed to switch away from a job before completion, should that prove advantageous. The jobs are deteriorating in the sense that their processing requirements grow (at job-specific rates) as they await processing. This phenomenon might be expected to enhance the status of non-preemptive policies. The primary objective of the paper is to find conditions which are sufficient to ensure the existence of a permutation policy to minimise the expected makespan. We also derive results for a weighted flowtime criterion. Applications of such models to the control of queues and to communication systems have been cited by other authors.

Keywords

COMPLETION (OR HAZARD) RATEMAKESPANMEAN RESIDUAL LIFETIMEPERMUTATION POLICYSTOCHASTIC SCHEDULING

MSC classification

Primary: 90C40: Markov and semi-Markov decision processes
Secondary: 90B35: Scheduling theory, deterministic 90C39: Dynamic programming
Type
Research Papers
Information
Journal of Applied Probability , Volume 30 , Issue 1 , March 1993 , pp. 184 - 193
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bertsekas, D. P. (1976) Dynamic Programming and Stochastic Control. Academic Press, New York.Google Scholar
Browne, S. and Yechiali, U. (1990) Scheduling deteriorating jobs on a single processor. Operat. Res. 38, 495–498.Google Scholar
Gittins, J. C. (1989) Multi-armed Bandit Allocation Indices. Wiley, New York.Google Scholar
Glazebrook, K. D. (1984) Scheduling stochastic jobs on a single machine subject to breakdowns. Naval. Res. Logist. Quart. 31, 251–264.Google Scholar
Glazebrook, K. D. (1987) Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval. Res. Logist. 34, 319–335.Google Scholar
Glazebrook, K. D. (1991) On nonpreemptive policies for stochastic single-machine scheduling with breakdowns. Prob. Eng. Inf. Sci. 5, 77–87.Google Scholar
Glazebrook, K. D. (1992) Single machine scheduling of stochastic jobs subject to deterioration or delay. Naval Res. Logist. 39, 613–633.3.0.CO;2-P>CrossRefGoogle Scholar
Glazebrook, K. D. and Whitaker, L. R. (1992) Single-machine stochastic scheduling with dependent processing times. Adv. Appl. Prob. 24, 635–652.Google Scholar
Hardy, G., Littlewood, J. E. and Pólya, G. (1934) Inequalities. Cambridge University Press.Google Scholar
Lawless, J. F. (1982) Statistical Models and Methods for Lifetime Data. Wiley, New York.Google Scholar
Pinedo, M. (1982) On the computational complexity of stochastic scheduling problems. In Deterministic and Stochastic Scheduling (ed. Dempster, M. A. H., Lenstra, J. K. and Rinnooy Kan, A. H.), pp. 355–365, Reidel, Dordrecht.Google Scholar
Righter, R. and Shanthikumar, J. G. (1989) Scheduling multiclass single server queueing systems to stochastically maximise the number of successful departures. Prob. Eng. Inf. Sci. 3, 323–333.CrossRefGoogle Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
Weber, R. R. (1982) Scheduling jobs with stochastic processing requirement on parallel machines to minimise makespan or flowtime. J. Appl. Prob. 19, 167–182.CrossRefGoogle Scholar
Weiss, G. (1982) Multiserver stochastic scheduling. In Deterministic and Stochastic Scheduling (ed. Dempster, M. A. H., Lenstra, J. K. and Rinnooy Kan, A. H.), pp. 157–179, Reidel, Dordrecht.Google Scholar