article

Free access

Exact and Approximate Algorithms for Scheduling Nonidentical Processors

Authors:

Ellis Horowitz,

Sartaj SahniAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 2

Pages 317 - 327

https://doi.org/10.1145/321941.321951

Published: 01 April 1976 Publication History

PDF eReader

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).

References

[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.

Crossref

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., 1974

Google 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.

Crossref

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

Crossref

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.

Crossref

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.

Crossref

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.

Crossref

Google Scholar

Cited By

View all

Bamatraf KGharbi A(2024)Variable Neighborhood Search for Minimizing the Makespan in a Uniform Parallel Machine SchedulingSystems10.3390/systems1206022112:6(221)Online publication date: 20-Jun-2024
https://doi.org/10.3390/systems12060221
Li ZJian XWang YShao YChen L(2024)DAHA: Accelerating GNN Training with Data and Hardware Aware Execution PlanningProceedings of the VLDB Endowment10.14778/3648160.364817617:6(1364-1376)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648176
Coletti KRomeo RDavis R(2024)Bayesian backcalculation of pavement properties using parallel transitional Markov chain Monte CarloComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1312339:13(1911-1927)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1111/mice.13123
Show More Cited By

Index Terms

Exact and Approximate Algorithms for Scheduling Nonidentical Processors
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

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. ...
Parallel job scheduling algorithms

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 23, Issue 2

April 1976

176 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321941

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1976

Published in JACM Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

375
Total Citations
View Citations
3,314
Total Downloads

Downloads (Last 12 months)370
Downloads (Last 6 weeks)35

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bamatraf KGharbi A(2024)Variable Neighborhood Search for Minimizing the Makespan in a Uniform Parallel Machine SchedulingSystems10.3390/systems1206022112:6(221)Online publication date: 20-Jun-2024
https://doi.org/10.3390/systems12060221
Li ZJian XWang YShao YChen L(2024)DAHA: Accelerating GNN Training with Data and Hardware Aware Execution PlanningProceedings of the VLDB Endowment10.14778/3648160.364817617:6(1364-1376)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648176
Coletti KRomeo RDavis R(2024)Bayesian backcalculation of pavement properties using parallel transitional Markov chain Monte CarloComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1312339:13(1911-1927)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1111/mice.13123
Kenne MDate PEguchi RHu ZRousseau JVenkatasubramanian N(2024)iFair: Achieving Fairness in the Allocation of Scarce Resources for Senior Health Care2024 IEEE International Conference on Smart Computing (SMARTCOMP)10.1109/SMARTCOMP61445.2024.00025(22-30)Online publication date: 29-Jun-2024
https://doi.org/10.1109/SMARTCOMP61445.2024.00025
Zhang YLi GYuan B(2024)Toward Efficient Co- Design of CNN Quantization and HW Architecture on FPGA Hybrid-Accelerator2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617620(678-683)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617620
Landeta-López PGuevara-Vega C(2024)Computational Experiments in Computer Science Research: A Literature SurveyIEEE Access10.1109/ACCESS.2024.345880812(132254-132270)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3458808
Furmańczyk HPikies TSokołowska ITurowski K(2024)Approximation algorithms for job scheduling with block-type conflict graphsComputers and Operations Research10.1016/j.cor.2024.106606166:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106606
Zouitine MBerjaoui ALagnoux APellegrini CRachelson E(2024)Learning Heuristics for Combinatorial Optimization Problems on K-Partite HypergraphsIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-60599-4_21(304-314)Online publication date: 28-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60599-4_21
Nguyen TRothe JElkind E(2023)Complexity results and exact algorithms for fair division of indivisible itemsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/754(6732-6740)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/754
Esin MKorepanova ASabrekov A(2023)Automation of the System of Efficient Packaging of Cargoes by Containers Using Heuristic Algorithms2023 XXVI International Conference on Soft Computing and Measurements (SCM)10.1109/SCM58628.2023.10159120(183-187)Online publication date: 24-May-2023
https://doi.org/10.1109/SCM58628.2023.10159120
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors

Exact and approximate algorithms for high-multiplicity parallel machine scheduling

Parallel job scheduling algorithms

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations