A new average case analysis for completion time scheduling

Abstract

We present a new average case analysis for the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. Our goal is to use the concept of competitive ratio---which is a typical worst case notion---also within an average case analysis. We show that the classic SEPT scheduling strategy with Ω(n) worst-case competitive ratio achieves an average of O(1) under several natural distributions, among them the exponential distribution. Our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. Thus, our result bridges the gap between worst case and average case performance guarantee.

References

1. Abramowitz, M., and Stegun, I. A., Eds. 1970. Handbook of Mathematical Functions. Dover Publications, New York.
2. Alon, N., and Spencer, J. H. 2000. The Probabilistic Method, 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York.
3. Bollobás, B. 2001. Random Graphs, 2nd ed. Cambridge University Press, Cambridge, MA.
4. Borodin, A., and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, MA.
5. Bruno, J., Downey, P., and Frederickson, G. N. 1981. Sequencing tasks with exponential service times to minimize the expected flow time or makespan. J. ACM 28, 100--113.
6. Bruno, Jr., E. C., and Sethi, R. 1974. Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17, 382--387.
7. Coffman, Jr., E. G., Garey, M. R., and Johnson, D. S. 1997. Approximation algorithms for bin packing: A survey. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, Ed. 46--93.
8. Coffmann, Jr., E. and Gilbert, E. N. 1985. Expected relative performance of list scheduling rules. Oper. Res. 33, 548--561.
9. Coffmann, Jr., E. G., Sao, K., Hofri, M., and Yao, A. C. 1980. A stochastic model of bin-packing. Inf. Cont. 44, 105--115.
10. Conway, R. W., Maxwell, W. L., and Miller, L. W. 1967. Theory of Scheduling. Addison--Wesley, Reading, MA.
11. Eastman, W. L., Even, S., and Isaacs, I. M. 1964. Bounds for the optimal scheduling of n jobs on m processors. Manage. Sci. 11, 268--279.
12. Garey, M. R., and Johnson, D. S. 1998. Computers and Intractability. W. H. Freeman and Company.
13. Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnoy Kan, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5, 287--326.
14. Hall, L. A., Schulz, A. S., Shmoys, D. B., and Wein, J. 1997. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22, 513--544.
15. Janson, S., Luczak, T., and Ruciński, A. 2000. Random Graphs. Wiley-Interscience, New York.
16. Kämpke, T. 1987. On the optimality of static priority policies in stochastic scheduling on parallel machines. J. Appl. Prob. 24, 430--448.
17. Karmakar, N. 1982. Probabilistic analysis of some bin--packing algorithms. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 107--111.
18. Kawaguchi, T., and Kyan, S. 1986. Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput. 15, 4, 1119--1129.
19. Koutsoupias, E., and Papadimitriou, C. 1994. Beyond competitive analysis. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS '94). IEEE Computer Society Press, Los Alamitos, CA, 394--400.
20. Lageweg, B. J., and Lenstra, J. K. 1977. manuscript. unpublished. (See Garey and Johnson {1998}.)
21. McNaughton, R. 1959. Scheduling with deadlines and loss functions. Manage. Sci. 6, 1--12.
22. Möhring, R. H., Radermacher, F. J., and Weiss, G. 1984. Stochastic scheduling problems I: General strategies. Z. Oper. Res. Ser. A. 28, 193--260.
23. Möhring, R. H., Schulz, A., and Uetz, M. 1999. Approximation in stochastic scheduling: The power of LP--based priority policies. J. ACM 46, 924--942.
24. Phillips, C., Stein, C., and Wein, J. 1998. Minimizing average completion time in the presence of release dates. Math. Prog. 82, 199--223.
25. Pinedo, M. 1995. Scheduling---Theory, Algorithms, and Systems. Prentice--Hall, Englewood Cliffs, NJ.
26. Port, S. C. 1994. Theoretical Probability for Applications. Wiley, New York.
27. Rothkopf, M. H. 1966. Scheduling with random service times. Manage. Sci. 12, 703--713.
28. Sahni, S. K. 1976. Algorithms for scheduling independent tasks. J. ACM 23, 116--127.
29. Schulz, A. S. 1996. Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 1084. Springer Verlag, Berlin, Germany, 301--315.
30. Skutella, M. 2001. Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM 48, 206--242.
31. Skutella, M., and Woeginger, G. J. 2000. A PTAS for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res. 25, 63--75.
32. Smith, W. E. 1956. Various optimizers for single-stage production. Naval Res. Log. Quatl. 3, 59--66.
33. Souza, A., and Steger, A. 2006. The expected competitive ratio for weighted completion time scheduling. Theory Comput. Syst., 39, 1 (Feb.), 121--136.
34. Weber, R. 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.
35. 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.

Index Terms

• Theory of computation

  • Design and analysis of algorithms