caa a22 4500 46577458X CHVBK 20180323111938.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02248591 doi (NATIONALLICENCE)springer-10.1007/BF02248591 Weiss Gideon School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332-0205, Atlanta, GA, USA aut Approximation results in parallel machnies stochastic scheduling [Elektronische Daten] [Gideon Weiss] We consider scheduling a batch of jobs with stochastic processing times on parallel machines. We derive various new formulae for the expected flowtime and weighted flowtime under general scheduling rules. Smith's Rule, which orders job starts by decreasing ratio of weight to expected processing time provides a natural heuristic for this problem. We obtain a bound on the worst case difference between the expected weighted flow time under Smith's Rule and under an optimal policy. For a wide class of processing time distributions, this bound is of oderO(1) and does not increase with the number of jobs. J.C. Baltzer AG, Scientific Publishing Company, 1990 Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 26/1(1990-12-01), 195-242 0254-5330 26:1<195 1990 26 10479 https://doi.org/10.1007/BF02248591 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02248591 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Weiss Gideon School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332-0205, Atlanta, GA, USA aut NATIONALLICENCE 773 0- Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 26/1(1990-12-01), 195-242 0254-5330 26:1<195 1990 26 10479 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer