Fair Distribution Heuristics for Parallel Processors

Authors

  • Mohammad Mahmood Otoom Department of Computer Science and Information, College of Science at Zulfi, Majmaah University, Al-Majmaah 11952

DOI:

https://doi.org/10.26713/cma.v12i2.1494

Keywords:

Heuristics, Fair distribution, Parallel processors, Process scheduling

Abstract

This paper studies the machine covering problem to satisfy the fair distribution of several tasks with different execution times to be run on several parallel processors. My work deals with process scheduling on identical parallel processors and how to find the best solution to this problem. The goal is to maximize the finishing time for the processor with the least time regarding all other system processors. Some algorithms were proposed that can approximately solve the studied problem by minimizing the difference between the finishing time of all processors in the system.

Downloads

Download data is not yet available.

References

M. Alharbi and M. Jemmali, Algorithms for investment project distribution on regions, Computational Intelligence and Neuroscience 2020 (2020), Article ID 3607547, DOI: 10.1155/2020/3607547.

H. Alquhayz, M. Jemmali and M. M. Otoom, Dispatching-rule variants algorithms for used spaces of storage supports, Discrete Dynamics in Nature and Society 2020 (2020), Article ID 1072485, DOI: 10.1155/2020/1072485.

Y. Azar and L. Epstein, On-line machine covering, Journal of Scheduling 1 (1998), 67 – 77, DOI: 10.1002/(SICI)1099-1425(199808)1:2%3C67::AID-JOS6%3E3.0.CO;2-Y.

S.-Y. Cai, Semi-online machine covering, Asia-Pacific Journal of Operational Research 24 (2007), 373 – 382, DOI: 10.1142/S0217595907001255.

X. Chen, L. Epstein and Z. Tan, Semi-online machine covering for two uniform machines, Theoretical Computer Science 410 (2009), 5047 – 5062, DOI: 10.1016/j.tcs.2009.08.001.

B. L. Deuermeyer, D. K. Friesen and M. A. Langston, Scheduling to maximize the minimum processor finish time in a multiprocessor system, SIAM Journal on Algebraic Discrete Methods 3, 190 – 196, 1982, DOI: 10.1137/0603019.

T. Ebenlendr, J. Noga, J. Sgall and G. Woeginger, A note on semi-online machine covering, in International Workshop on Approximation and Online Algorithms (2005), pp. 110 – 118, DOI: 10.1007/11671411_9.

W. Gálvez, J. A. Soto and J. Verschae, Improved online algorithms for the machine covering problem with bounded migration, in: 12th Workshop on Models and Algorithms for Planning and Scheduling Problems, La Roche-en-Ardenne, Belgium, June 8–12, 2015, pp. 21 – 23, https://feb.kuleuven.be/mapsp2015/Proceedings%20MAPSP%202015.pdf.

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics 5 (1979), 287 – 326, DOI: 10.1016/S0167-5060(08)70356-X.

M. Haouari and M. Jemmali, Maximizing the minimum completion time on parallel machines, 4OR 6 (2008), 375 – 392, DOI: 10.1007/s10288-007-0053-5.

Y. Huang and Y. Wu, Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times, International Mathematical Forum 5 (2010), pp. 185 – 190, http://www.m-hikari.com/imf-2010/1-4-2010/wuyongIMF1-4-2010.pdf.

M. Jemmali, Approximate solutions for the projects revenues assignment problem, Communications in Mathematics and Applications 10 (2019), 653 – 658, DOI: 10.26713/cma.v10i3.1238.

M. Jemmali, Budgets balancing algorithms for the projects assignment, International Journal of Advanced Computer Science and Applications 10 (2019), 574 – 578, URL: https://thesai.org/Downloads/Volume10No11/Paper_77-Budgets_Balancing_Algorithms_for_the_Projects_Assignment.pdf.

M. Jemmali and H. Alquhayz, Equity Data Distribution Algorithms on Identical Routers, in Advances in Intelligent Systems and Computing book series (AISC, Vol. 1059) (2020), pp. 297 – 305, DOI: 10.1007/978-981-15-0324-5_26.

M. Jemmali, L. K. B. Melhim and M. Alharbi, Randomized-variants lower bounds for gas turbines aircraft engines, in Advances in Intelligent Systems and Computing book series (AISC, Vol. 991) (2019), pp. 949 – 956, DOI: 10.1007/978-3-030-21803-4_94.

M. Jemmali, L. K. B. Melhim, S. O. B. Alharbi and A. S. Bajahzar, Lower bounds for gas turbines aircraft engines, Communications in Mathematics and Applications 10 (2019), 637 – 642, DOI: 10.26713/cma.v10i3.1218.

M. Jemmali, M. M. Otoom and F. Al Fayez, Max-min probabilistic algorithms for parallel machines, in: Proceedings of the 2020 International Conference on Industrial Engineering and Industrial Management, 2020, pp. 19 – 24, DOI: 10.1145/3394941.3394945.

Pisinger, Dynamic programming on the word RAM, Algorithmica 35 (2003), 128 – 145, URL: https://link.springer.com/article/10.1007/s00453-002-0989-y.

Z. Tan, Y. He and L. Epstein, Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data, Information and Computation 196 (2005), 57 – 70, DOI: 10.1016/j.ic.2004.10.002.

Y. Wu, T. C. E. Cheng and M. Ji, Optimal algorithms for semi-online machine covering on two hierarchical machines, Theoretical Computer Science 531 (2014), 37 – 46, DOI: 10.1016/j.tcs.2014.02.015.

Y. Wu, Z. Tan and Q. Yang, Optimal semi-online scheduling algorithms on a small number of machines, in: International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science book series (LNCS, Vol. 4614) (2007), pp. 504 – 515, DOI: 10.1007/978-3-540-74450-4_45.

Downloads

Published

30-06-2021
CITATION

How to Cite

Otoom, M. M. (2021). Fair Distribution Heuristics for Parallel Processors. Communications in Mathematics and Applications, 12(2), 359–366. https://doi.org/10.26713/cma.v12i2.1494

Issue

Vol. 12 No. 2 (2021)

Section

Research Article

License

Creative Commons Licence 4.0 by  

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.