Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T03:44:07.425Z Has data issue: false hasContentIssue false

On the optimality of static priority policies in stochastic scheduling on parallel machines

Published online by Cambridge University Press:  14 July 2016

Thomas Kämpke*
Affiliation:
Universität Passau
*
∗ Postal address: Lehrstuhl für Informatik und Operations Research, Universität Passau, Postfach 2540, 8390 Passau, W. Germany.

Abstract

n jobs are to be preemptively scheduled for processing on n machines. The machines may have differing speeds and the jobs have processing requirements which are distributed as independent exponential random variables with different means. Holding cost g(U) is incurred per unit time that the set of uncompleted jobs is U and it is desired to minimize the total expected holding cost which is incurred until all jobs are complete. We show that if g satisfies certain simple conditions then the optimal policy is one which takes the jobs in the order 1, 2, ···, n and assigns each uncompleted job in turn to the fastest available machine. In the special case in which the objective is to minimize the expected weighted flowtime, where there is a holding cost of wi while job i is incomplete, the sufficient condition is simply w1 ≧ … ≧ wn and λ1 w1 ≧ … ≧ λn wn .

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1987 

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.)

Article purchase

Temporarily unavailable