Ellis Horowitz
Sartaj Sahni
Abstract
Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to m processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on m-processors an algorithm is given whose complexity is O(n log mn).
- 1 BRUNO, J., COFFMAN, E.G. JR., AND SETHI, R. Scheduling independent tasks to reduce mean finishing-time. Comm. ACM 17, 7 (july 1974), 382-387. Google Scholar
- 2 BRUNO, J., COrFMAN, E.G. JR., ANY SET~I, R. Algorithms for minimizing mean flow time Proc. IFIP Congr. 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 504-510.Google Scholar
- 3 COFFMAN, E.G., AND SETHI, R. Algorithms minimizing mean flow time: Schedule length properties. Comput. Scl. Dep., Pennsylvania State U., University Park, Pa., 1974Google Scholar
- 4 CONWAY, R.W., MAXWELL, W.L., ASD MILLER, L.W Theory of Scheduling. Addison-Wesley, Reading, Mass., 1967.Google Scholar
- 5 GRAHAM, R.L. Bounds on multiprocessing time anomalies. SIAM J. Appl. Math. 17, 2 (March 1969), 416-429.Google Scholar
- 6 HOROWITZ, E., AND SAHNI, S Computing partitions with applications to the knapsack problem. J. ACM 21, 2 (April 1974), 277-292. Google Scholar
- 7 IBARRA, O H., AN}) KI~, C E. Fast approximation algorithms for the knapsack and sum of subset problems. Comput Sci. Tech Rep #74-13, U. of Minnesota, Minneapolis, Minn., 1974.Google Scholar
- 8 KARP, R.M. Reducibility among combinatorml problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-103.Google Scholar
- 9 KNUTH, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-{ Wesley, Reading, Mass., 1973 Google Scholar
- 10 KOHLER, W.H., ANn STEIGLITZ, K. Characterization and theoretical comparison of branchand-bound algorithms for permutation problems. J. ACM 21,1 (Jan 1974), 140-156. Google Scholar
- 11 LIu, J.W.S., AND LIU, C L. Bounds on scheduling algorithms for heterogeneous computing systems. Proc. IFIP Congr. 74, North-Holland Pub Co., Amsterdam, 1974, pp. 349-353.Google Scholar
- 12 SAHNI, S. Algorithms for scheduling independent tasks. J. ACM 2S, 1 (Jan. 1976), 116-127. Google Scholar
- 13 SAHNI, S. Computationally related problems. SIAMJ. Comput. 8,4 (Dec 1974),262-279.Google Scholar
- 14 ULLMAN, J.D. Polynomial complete scheduling algorithms. 4th Symposium on Operating Systems Principles, Oct. 1973, Yorktown Heights, New York, pp. 96-101; also in J Comput. Syst. Scis. 10, 3 (June 1975), 384-393. Google Scholar
Index Terms
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
Recommendations
Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a finishing ...
Exact and approximate algorithms for high-multiplicity parallel machine scheduling
In many scheduling applications, a large number of jobs are grouped into a comparatively small number of lots made of identical items. It is then sufficient to give, for each lot, the number of jobs it involves plus the description of one single job. ...
Comments