A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniforn Processors

Author

Agrawala, Ashok K. ; Coffman, Edward G., Jr. ; Garey, Michael R. ; Tripathi, Satish K.

Author_Institution

Department of Computer Science, University of Maryland

Issue

4

fYear

1984

fDate

4/1/1984 12:00:00 AM

Firstpage

351

Lastpage

356

Keywords

Consider a set of processors P1,..., Pm differing only in speed, and a set of jobs with exponentially distributed execution times. The rate parameter for the ith processor is given by μi, 1 ≤i ≤ m, where we assume the processors are ordered so that μ1 ≥ μ2 ≥ ... ≥ μm. The problem is to sequence the jobs nonpreemptively so as to minimize expected total flow time (sum of finishing times). We define a threshold ru; Mean flow time minimization; routing problems; stochastic optimization; stochastic scheduling; uniform processor systems; Computer science; Delay effects; Finishing; Processor scheduling; Random variables; Routing; Stochastic processes; Stochastic systems; Consider a set of processors P1,..., Pm differing only in speed, and a set of jobs with exponentially distributed execution times. The rate parameter for the ith processor is given by μi, 1 ≤i ≤ m, where we assume the processors are ordered so that μ1 ≥ μ2 ≥ ... ≥ μm. The problem is to sequence the jobs nonpreemptively so as to minimize expected total flow time (sum of finishing times). We define a threshold ru; Mean flow time minimization; routing problems; stochastic optimization; stochastic scheduling; uniform processor systems;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.1984.1676440

Filename

1676440