1988 | OriginalPaper | Buchkapitel
Stochastic Scheduling on Parallel Processors and Minimization of Concave Functions of Completion Times
verfasst von : Richard R. Weber
Erschienen in: Stochastic Differential Systems, Stochastic Control Theory and Applications
Verlag: Springer New York
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider a stochastic scheduling problem in which n jobs are to be scheduled on m identical processors which operate in parallel. The processing times of the jobs are not known in advance but they have known distributions with hazard rates ρ1, (t), …, ρ n (t). It is desired to minimize the expected value of к(C), where C i is the time at which job i is completed C = (C1, …, C n ), and к(C) is increasing and concave in C. Suppose processor i first becomes available at time τ i . We prove that if there is a single static list priority policy which is optimal for every τ = (τ1, …, τ m ), then the minimal expected cost must be increasing and concave in τ. Moreover, if к(C) is supermodular in C then this cost is also supermodular in τ. This result is used to prove that processing jobs according to the static list priority order (1,2,…,n) minimizes the expected value of ∑w i h(C i ), when h(·) is a nondecreasing, concave function, w 1 ≥ … ≥ w n , and ρ1 (t1)w1 ≥ … ≥ ρ n (t n )w n for all t1, …, t n .