Hostname: page-component-848d4c4894-cjp7w Total loading time: 0 Render date: 2024-07-02T17:48:07.079Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastically Minimizing Total Delay of Jobs Subject to Random Deadlines

Published online by Cambridge University Press:  27 July 2009

Susan H. Xu
Susan H. Xu
Affiliation:
Department of Management Science College of Business Administration The Pennsylvania State University, University Park, Pennsylvania 16802
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper analyzes a scheduling system where a fixed number of nonpreemptive jobs is to be processed on multiple parallel processors with different processing speeds. Each processor has an exponential processing time distribution and the processors are ordered in ascending order of their mean processing times. Each job has its own deadline that is exponentially distributed with rate ß1, independent of the deadlines of other jobs and also independent of job processing times. A job departs the system as soon as either its processing completes or its deadline occurs. We show that there exists a simple threshold strategy that slochastically minimizes the total delay of all jobs. The policy depends on distributions of processing times and deadlines, but is independent of the rate of deadlines. When the rate of the deadline distribution is 0 (no deadlines), the total delay reduces to the flowtime (the sum of completion times of all jobs). If each job has its own probability of being correctly processed, then an extension of this policy stochastically maximizes the total number of correctly processed, nontardy jobs. We discuss possible generalizations and limitations of this result.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 5 , Issue 3 , July 1991 , pp. 333 - 348
Copyright
Copyright © Cambridge University Press 1991

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

REFERENCES

Agrawala, A.K., Coffman, E.G. Jr, Garey, M.R. & Tripathi, S.K. (1984). A stochastic optimization algorithm minimizing expected flowtime on uniform processors. IEEE Transactions on Computer C-33: 351–357.CrossRefGoogle Scholar
Coffman, E.G., Flatto, L., Garey, M.R. & Weber, R.R. (1987). Minimizing expected makespan on uniform processors systems. Advances in Applied Probability 19: 177–201.CrossRefGoogle Scholar
Kumar, P.R. & Walrand, J. (1985). Individually routing in parallel systems. Journal of Applied Probability 22: 989–995.CrossRefGoogle Scholar
Righter, R. (1988). Job scheduling to minimize expected weighted flowtime on uniform processors. Systems & Control Letters 10: 211–216.CrossRefGoogle Scholar
Righter, R. (1990). Stochastically maximizing the number of successes in a sequential assignment problem. Journal of Applied Probability 27: 351–364.CrossRefGoogle Scholar
Righter, R. & Xu, S.H. (1991a). Scheduling jobs on heterogeneous processors. Annals of Operations Research (to appear).CrossRefGoogle Scholar
Righter, R. & Xu, S.H. (1991b). Scheduling jobs on nonidentical IFR processors to minimize general cost functions. Advances in Applied Probability (to appear).CrossRefGoogle Scholar
Ross, S. (1983). Introduction to stochastic dynamic programming. New York: Academic Press.Google Scholar
Xu, S.H. (1991). Socially and individually optimal routing of stochastic jobs in parallel processors systems. Operations Research 39(4) (to appear).Google Scholar
Xu, S.H., Mirchandani, P.B., Kumar, S.P. & Weber, R.R. (1990). Stochastic dispatching of multi-priority jobs to heterogeneous processors. Journal of Applied Probability 27(4): 852–861.CrossRefGoogle Scholar
Xu, S.H. (1991). Minimizing expected makespans of multi-priority classes of jobs on uniform processors. Operations Research Letters 10(5) (to appear).CrossRefGoogle Scholar