Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T09:38:32.071Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling jobs on non-identical IFR processors to minimize general cost functions

Published online by Cambridge University Press:  01 July 2016

Rhonda Righter  and
Susan H. Xu
Rhonda Righter*
Affiliation:
Santa Clara University
Susan H. Xu*
Affiliation:
Pennsylvania State University
*
∗Postal address: Department of Decision and Information Sciences, Santa Clara University, Santa Clara, CA 95053, USA.
∗∗Postal address: Department of Management Science, College of Business Administration, The Pennsylvania State University, University Park, PA 16802, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of scheduling n jobs non-preemptively on m parallel, non-identical processors to minimize a weighted expected cost function of job completion times, where the weights are associated with the jobs. The cost function is assumed to be increasing and concave but otherwise arbitrary. Processing times are IFR with different distributions for different processors. Jobs may be processed on any processor and there are no precedences. We show that the optimal policy orders the jobs in decreasing order of their weights and then uses the individually optimal policy for each job. In other words, processors are offered to jobs in order, and each job considers its own expected cost function for its completion time to decide whether to accept or reject a processor. Therefore, the optimal policy does not depend on the weights of the jobs except through their order. Special cases of our objective function are weighted expected flowtime, weighted discounted expected flowtime, and weighted expected number of tardy jobs.

Keywords

STOCHASTIC SCHEDULINGMULTIPROCESSOR SCHEDULINGINCREASING FAILURERATESTOCHASTIC OPTIMIZATION
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 4 , December 1991 , pp. 909 - 924
Copyright
Copyright © Applied Probability Trust 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

Agrawala, A. K., Coffman, E. G. Jr., Garey, M. R. and Tripathi, S. K. (1984) A stochastic optimal algorithm minimizing exponential flow times on uniform processors. IEEE Trans. Computers 33, 351–356.Google Scholar
Barlow, R. E. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing. Holt, Rinehart and Winston, New York.Google Scholar
Coffman, E. G. Jr., Flatto, L., Garey, M. R. and Weber, R. R. (1987) Minimizing expected makespans on uniform processor systems. Adv. Appl. Prob. 19, 177–201.Google Scholar
Courcoubetis, C. A. and Reiman, M. I. (1988) Optimal dynamic allocation of heterogeneous servers under the condition of total overload: The discounted case. Preprint.Google Scholar
Derman, C., Lieberman, G. J. and Ross, S. M. (1980) On the optimal assignment of servers and a repairman. J. Appl. Prob. 17, 577–581.Google Scholar
Glazebrook, K. D. (1979) Scheduling tasks with exponential service times on parallel processors. J. Appl. Prob. 16, 685–689.Google Scholar
Hardy, G. H., Littlewood, J. E. and Pólya, G. (1934) Inequalities. Cambridge University Press.Google Scholar
Kämpke, T. (1987a) On the optimality of static priority policies in stochastic scheduling on parallel machines. J. Appl. Prob. 24, 430–448.Google Scholar
Kämpke, T. (1987b) Necessary optimality conditions for priority policies in stochastic weighted flowtime scheduling problems. Adv. Appl. Prob. 19, 749–750.Google Scholar
Kumar, P. and Walrand, J. (1985) Individually optimal routing on parallel systems J. Appl. Prob. 22, 989–995.Google Scholar
Larsen, R. L. and Agrawala, A. K. (1983) Control of a heterogeneous two-server exponential queueing system. IEEE Trans. Software Eng. 9, 522–526.Google Scholar
Lin, W. and Kumar, P. R. (1984) Optimal control of a queueing system with two heterogeneous servers. IEEE Trans. Autom. Control 29, 696–703.Google Scholar
Nelson, R. and Towsley, D. (1987) Approximating the meantime in system in a multiple-server queue that uses threshold scheduling. Operat. Res. 35, 419–427.Google Scholar
Pinedo, M. and Weiss, G. (1979) Scheduling of stochastic tasks on two parallel processors. Naval Res. Logist. Quart. 26, 527–535.Google Scholar
Righter, R. (1988) Job scheduling to minimize expected weighted flowtime on uniform processors. Syst. Control Lett. 10, 211–216.Google Scholar
Righter, R. (1990) Stochastically maximizing the number of successes in a sequential assignment problem. J. Appl. Prob. 27, 351–364.Google Scholar
Righter, R. and Xu, S. H. (1991) Scheduling jobs on heterogeneous processors Ann. Operat. Res. 29, 587–602.Google Scholar
Rosberg, Z. and Makowski, S. (1990) Optimal routing to parallel heterogeneous servers—small arrival rates. IEEE Trans. Autom. Control 35, 789–796.Google Scholar
Ross, S. (1983) Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
Viniotis, I. and Ephremides, A. (1988) Extension of the optimality of the threshold policy in heterogeneous multiserver queueing systems. IEEE Trans. Autom. Control 33, 104–109.Google Scholar
Walrand, J. (1984) A note on ‘Optimal control of a queueing system with two heterogeneous servers’. Syst. Control Lett. 4, 131–134.Google Scholar
Weber, R. R. (1982) Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime. J. Appl. Prob. 19, 167–182.Google Scholar
Weber, R., Varaiya, P. and Walrand, J. (1986) Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. J Appl. Prob. 23, 841–847.Google Scholar
Weiss, G. and Pinedo, M. (1980) Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Prob. 17, 187–202.Google Scholar
Xu, S. H. (1991a) Socially and individually optimal routing of stochastic jobs in parallel processors systems. Operat. Res. 39.Google Scholar
Xu, S. H. (1991b) Minimizing expected makespans of multi priority classes of jobs on uniform processors. Operat. Res. Lett. Google Scholar
Xu, S. H. (1991c) Stochastically minimizing total delay of jobs subject to random deadlines. Prob. Eng. Inf. Sci. To appear.Google Scholar