Fair Distribution Heuristics for Parallel Processors

Mohammad Mahmood Otoom

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.


Keywords


Heuristics; Fair distribution, Parallel processors; Process scheduling

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.26713%2Fcma.v12i2.1494

Refbacks

  • There are currently no refbacks.


eISSN 0975-8607; pISSN 0976-5905