An Analytical Study of Multiprocessor Scheduling Using Metaheuristic Approach | SN Computer Science Skip to main content
Springer Nature Link
Log in

An Analytical Study of Multiprocessor Scheduling Using Metaheuristic Approach

  • Review Article
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

The process scheduling in the distributed and heterogeneous environment is the principal concern which can influence the execution performance of the application. The multiprocessor scheduling concept in grid environment incepts from 1980. After a decade in 1992 heuristic and evolutionary approaches started to solve these issues followed by nature inspired metaheuristic algorithms which started in the twentieth century. This paper provides a taxonomy of scheduling techniques which defines characteristics of each technique and gives some prominent algorithms as an example. Many research works have been done for minimizing execution cost and makespan as the influencing parameters for the scheduling of the dependent processes but few researchers have considered energy utilization, memory utilization and miss rate. This paper describes different types of algorithms starting from traditional algorithms from the year 1984 and consequently, metaheuristic algorithms including nature-inspired, bio-inspired, swarm intelligence-based techniques used for multiprocessor scheduling optimization purposes in different real-time applications up to 2019. It also defines available simulation tool for simulating scheduling algorithms. This paper will empower the beginners to select appropriate techniques according to their requirements and especially it will be a great help for getting a road map for different scheduling techniques and its applications.

Graphical Abstract

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Casavant TL, Kuhl JG. Taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans Softw Eng. 1988;14:141–54. https://doi.org/10.1109/32.4634.

    Article  Google Scholar 

  2. Allen BT, Tucker BT. Computer Science Handbook. 2nd ed. London: Chapman & Hall/CRC Publishers; 2004.

    MATH  Google Scholar 

  3. Ranadive P, et al. Taxonomy of automotive real-time scheduling. No. 2016-01-0038. SAE Technical Paper, 2016. https://doi.org/10.4271/2016-01-0038.

  4. Topcuoglu H, Wu MY. Performance-effective and low complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Comput. 2002;13(3):260–74. https://doi.org/10.1109/71.993206.

    Article  Google Scholar 

  5. Kour R. Multiprocessor scheduling using task duplication-based scheduling algorithms: a review paper. Int J Appl Innov Eng Manag. 2013;2(4):311–7.

    Google Scholar 

  6. Kruatrachue B, Lewis TG. Duplication scheduling heuristic, a new precedence task scheduling for parallel system. Technical Report 87-60-3. Corvallis: Oregon State University; 1987.

  7. Hwang J-J, et al. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J Comput. 1989;18(2):244–57. https://doi.org/10.1137/0218016.

    Article  MathSciNet  MATH  Google Scholar 

  8. El-Rewini H, Lewis TG, Ali HH. Task scheduling in parallel and distributed systems. Hoboken: Prentice-Hall Inc; 1994.

    Google Scholar 

  9. Radulescu A, Van Gemund AJC. FLB: fast load balancing for distributed-memory machines. In: Proceedings of the 1999 International Conference on Parallel Processing. New York: IEEE; 1999. https://doi.org/10.1109/ICPP.1999.797442.

  10. Topcuoglu H, Hariri S, Min-you Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst. 2002;13(3):260–74. https://doi.org/10.1109/71.993206.

    Article  Google Scholar 

  11. Radulescu A, Van Gemund AJC. Fast and effective task scheduling in heterogeneous systems. In: Proceedings 9th heterogeneous computing workshop (HCW 2000) (Cat. No. PR00556). New York: IEEE; 2000. https://doi.org/10.1109/HCW.2000.843747.

  12. Acharya B, Panda S. Modified SSA for solving multiprocessor scheduling problems. In: 2021 5th international conference on intelligent computing and control systems (ICICCS). New York: IEEE; p. 1075–80. 2021. https://doi.org/10.1109/ICICCS51141.2021.9432367.

  13. Kirkpatrick S, Gelatt CD Jr, Vecchi MP. Optimization by simulated annealing. Science. 1983;220(4598):671–80. https://doi.org/10.1126/science.220.4598.671.

    Article  MathSciNet  MATH  Google Scholar 

  14. Devadas S, Newton AR. Algorithms for hardware allocation in data path synthesis. IEEE Trans Comput-Aided Des Integr Circuits Syst. 1989;8(7):768–81. https://doi.org/10.1109/43.31534.

    Article  Google Scholar 

  15. Orsila H, Salminen E, Hämäläinen TD. Parameterizing simulated annealing for distributing kahn process networks on multiprocessor socs. In: 2009 international symposium on system-on-chip. New York: IEEE; 2009. https://doi.org/10.1109/SOCC.2009.5335683.

  16. Maniezzo V, Carbonaro A. Ant colony optimization: an overview. In: Essays and surveys in metaheuristics. Operations research/computer science interfaces series, vol 15. Boston: Springer; 2002.

  17. Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput. 1997;1(1):53–66. https://doi.org/10.1109/4235.585892.

    Article  Google Scholar 

  18. Pierucci S, et al. An industrial application of an on-line data reconciliation and optimization problem. Comput Chem Eng. 1996;20:S1539–44. https://doi.org/10.1016/0098-1354(96)00262-1.

    Article  Google Scholar 

  19. den Besten M, Stützle T, Dorigo M, et al. Ant colony optimization for the total weighted tardiness problem. In: Schoenauer M, et al., editors. Parallel problem solving from nature PPSN VI. PPSN 2000. Lecture notes in computer science, vol. 1917. Berlin: Springer; 2000.

    Google Scholar 

  20. Gajpal Y, Rajendran C, Ziegler H. An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. Int J Adv Manuf Technol. 2006;30(5–6):416–24. https://doi.org/10.1007/s00170-005-0093-y.

    Article  Google Scholar 

  21. Rajendran C, Ziegler H. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res. 2004;155(2):426–38. https://doi.org/10.1016/S0377-2217(02)00908-6.

    Article  MATH  Google Scholar 

  22. Glover F, Laguna M. Tabu search Handbook of combinatorial optimization. Springer; 1998. p. 2093–229.

    Book  Google Scholar 

  23. Glover F, Taillard E. A user’s guide to tabu search. Ann Oper Res. 1993;41(1):1–28.

    Article  MATH  Google Scholar 

  24. Acharya B, Panda, S. GA–JAYA: a novel hybridization technique to solving job scheduling problems. In: Proceedings of data analytics and management. Singapore: Springer. 2022. p. 221–30. https://doi.org/10.1007/978-981-16-6289-8_19.

  25. Kwok Y-K, Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv. 1999;31(4):406–71. https://doi.org/10.1145/344588.344618.

    Article  Google Scholar 

  26. Grajcar M. Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system. In: Proceedings 1999 design automation conference (Cat. No. 99CH36361). New York: IEEE; 1999. https://doi.org/10.1109/DAC.1999.781326.

  27. Holland JH. Adaptation in natural and artificial systems, vol. 1. Ann Arbor: The University of Michigan Press; 1975. p. 975.

    Google Scholar 

  28. Gordberg DE. Genetic algorithm in search, optimization and machine learning. Reading: Addison-Wesley; 1989.

  29. Alba E, Dorronsoro B. Solving the vehicle routing problem by using cellular genetic algorithms. In: Gottlieb J, Raidl GR, editors. Evolutionary computation in combinatorial optimization. EvoCOP 2004. Lecture notes in computer science, vol. 3004. Berlin: Springer; 2004.

    Google Scholar 

  30. Dawkins R. The selfish gene. Oxford: Clarendon; 1976.

    Google Scholar 

  31. Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Caltech concurrent computation program, C3P Report 826 (1989). 1989.

  32. Kohler WH, Steiglitz K. Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems. J ACM. 1974;21(1):140–56. https://doi.org/10.1145/321796.321808.

    Article  MathSciNet  MATH  Google Scholar 

  33. Kasahara H, Narita S. Practical multiprocessor scheduling algorithms for efficient parallel processing. IEEE Trans Comput. 1984;11:1023–9. https://doi.org/10.1109/TC.1984.1676376.

    Article  Google Scholar 

  34. Fujita S, Masukawa M, Tagashira S. A fast branch-and-bound algorithm with an improved lower bound for solving the multiprocessor scheduling problem. In: Ninth international conference on parallel and distributed systems, 2002. proceedings. New York: IEEE; 2002. https://doi.org/10.1109/ICPADS.2002.1183469.

  35. Atamtürk A, Savelsbergh MW. Integer-programming software systems. Ann Oper Res. 2005;140(1):67–124. https://doi.org/10.1007/s10479-005-3968-2.

    Article  MathSciNet  MATH  Google Scholar 

  36. Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM. 1973;20(1):46–61. https://doi.org/10.1145/321738.321743.

    Article  MathSciNet  MATH  Google Scholar 

  37. Leung JYT, Whitehead J. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform Eval. 1982;2(4):237–50. https://doi.org/10.1016/0166-5316(82)90024-4.

    Article  MathSciNet  MATH  Google Scholar 

  38. Mok AK. Multiprocessor scheduling in a hard real-time environment. In: Proc. Seventh Texas Conf. Compt. Syst. 1978.

  39. Doulamis ND, et al. Fair scheduling algorithms in grids. IEEE Trans Parallel Distrib Syst. 2007;18(11):1630–48. https://doi.org/10.1109/TPDS.2007.1053.

    Article  Google Scholar 

  40. Cho H, Ravindran B, Jensen ED. An optimal real-time scheduling algorithm for multiprocessors. In: 2006 27th IEEE international real-time systems symposium (RTSS'06). New York: IEEE; 2006.https://doi.org/10.1109/RTSS.2006.10.

  41. Davis RI, Kato S. FPSL, FPCL and FPZL schedulability analysis. Real-Time Syst. 2012;48(6):750–88. https://doi.org/10.1007/s11241-012-9149-x.

    Article  MATH  Google Scholar 

  42. Baruah SK, et al. Proportionate progress: a notion of fairness in resource allocation. Algorithmica. 1996;15(6):600–25. https://doi.org/10.1007/BF01940883.

    Article  MathSciNet  MATH  Google Scholar 

  43. Baruah SK, Gehrke JE, Plaxton CG. Fast scheduling of periodic tasks on multiple resources. In: Proceedings of 9th international parallel processing symposium. New York: IEEE; 1995. https://doi.org/10.1109/IPPS.1995.395946.

  44. Anderson JH, Srinivasan A. Early-release fair scheduling. In: Proceedings 12th euromicro conference on real-time systems. Euromicro RTS 2000. New York: IEEE; 2000. https://doi.org/10.1109/EMRTS.2000.853990.

  45. Anderson J, Srinivasan A. Pfair scheduling of sporadic tasks. Unpublished manuscript.

  46. Aoun D, Déplanche AM. Pfair scheduling improvement to reduce interprocessor migrations. In: 16th international conference on real-time and network systems (RTNS 2008). 2008. https://hal.inria.fr/inria-00336513.

  47. Deubzer M, et al. Efficient scheduling of reliable automotive multi-core systems with PD2 by Weakening ERfair task system requirements. In: Proceedings of the automotive safety & security. 2010.

  48. Sarkar A, Ghose S, Chakrabarti PP. Sticky-ERfair: a task-processor affinity aware proportional fair scheduler. Real Time Syst. 2011;47(4):356–377. https://doi.org/10.1007/s11241-011-9120-2.

  49. Anderson JH, Block A, Srinivasan A. "Quick-release fair scheduling." RTSS 2003. In: 24th IEEE real-time systems symposium, 2003. New York: IEEE; 2003. https://doi.org/10.1109/REAL.2003.1253261.

  50. Block A, Anderson JH, Bishop G. Fine-grained task reweighting on multiprocessors. In: 11th IEEE international conference on embedded and real-time computing systems and applications (RTCSA'05). New York: IEEE; 2005. https://doi.org/10.1109/RTCSA.2005.53.

  51. Dudani A, Mueller F, Zhu Y. Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints. ACM SIGPLAN Notices. 2002;37(7):213–22. https://doi.org/10.1145/513829.513865.

    Article  Google Scholar 

  52. Li D, Wu J. Energy-aware scheduling on multiprocessor platforms. Berlin: Springer Science & Business Media; 2012.

    Google Scholar 

  53. Yang C-Y, et al. Energy reduction techniques for systems with non-DVS components. In: 2009 IEEE conference on emerging technologies & factory automation. New York: IEEE; 2009. https://doi.org/10.1109/ETFA.2009.5347153.

  54. Zakarya M, Ayaz U, Khan A. Power aware scheduling algorithm for real time task over multi processors. Middle-East J. Sci. Res. 15. 2013.

  55. Davis H, Goldschmidt SR, Hennessy JL. Tango: a multiprocessor simulation and tracing system. Stanford: Computer Systems Laboratory, Stanford University; 1990.

    Google Scholar 

  56. Chapin SJ. Scheduling support mechanisms for autonomous, heterogeneous, distributed systems (Ph. D. Thesis). 1993.

  57. Decotigny D, Puaut I. Artisst: an extensible framework for the simulation of real-time systems. Technical Report 1423. 2001.

  58. The original LITMUSRT paper: Calandrino J, Leontyev H, Block A, Devi U, Anderson J. LITMUSRT: a testbed for empirically comparing real-time multiprocessor schedulers. In: Proceedings of the 27th IEEE real-time systems symposium. 2006. p. 111–23. https://doi.org/10.1109/RTSS.2006.27.

  59. The description of the current version: B. Brandenburg. Scheduling and locking in multiprocessor real-time operating systems. PhD thesis, UNC Chapel Hill; 2011.

  60. Ahmad H, Badal N. CAPS: a tool for process scheduling in distributed environment. 2014.

  61. Kathiravelu P, Veiga L. Concurrent and distributed cloudsim simulations. In: 2014 IEEE 22nd international symposium on modelling, analysis & simulation of computer and telecommunication systems. New York: IEEE; 2014. https://doi.org/10.1109/MASCOTS.2014.70.

  62. Kurtin PS, Hausmans JP, Bekooij MJ. HAPI: an event-driven simulator for real-time multiprocessor systems. In: Proceedings of the 19th international workshop on software and compilers for embedded systems. New York: ACM; 2016. https://doi.org/10.1145/2906363.2906381.

  63. Kasahara H, Narita S. Parallel processing of robot-arm control computation on a multimicroprocessor system. IEEE J Robot Autom. 1985;1(2):104–13. https://doi.org/10.1109/JRA.1985.1087004.

    Article  Google Scholar 

  64. Chen CL, Lee CG, Hou ES. Efficient scheduling algorithms for robot inverse dynamics computation on a multiprocessor system. IEEE Trans Syst Man Cybern. 1988;18(5):729–43. https://doi.org/10.1109/21.21600.

    Article  Google Scholar 

  65. Chen C-L. Efficient mapping algorithms for scheduling autonomous vehicles and robotic computations. 1988.

  66. Al-Mouhamed M, Al-Maasarani A. Performance evaluation of scheduling precedence-constrained computations on message-passing systems. IEEE Trans Parallel Distrib Syst. 1994;5(12):1317–21. https://doi.org/10.1109/71.334905.

    Article  Google Scholar 

  67. Wang DJ, Hu YH. Multiprocessor implementation of real-time DSP algorithms. IEEE Trans Very Large-Scale Integr Syst. 1995;3(3):393–403. https://doi.org/10.1109/92.406997.

    Article  Google Scholar 

  68. Dell’Olmo P, Speranza MG, Tuza Z. Comparability graph augmentation for some multiprocessor scheduling problems. Discrete Appl Math. 1997;72(1–2):71–84. https://doi.org/10.1016/S0166-218X(96)00037-6.

    Article  MathSciNet  MATH  Google Scholar 

  69. Peng D-T, Shin KG, Abdelzaher TF. Assignment and scheduling communicating periodic tasks in distributed real-time systems. IEEE Trans Softw Eng. 1997;23(12):745–58. https://doi.org/10.1109/32.637388.

    Article  Google Scholar 

  70. Zhu D, Melhem R, Childers BR. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems. IEEE Trans Parallel Distrib Syst. 2003;14(7):686–700. https://doi.org/10.1109/TPDS.2003.1214320.

    Article  Google Scholar 

  71. Lam T-W, et al. Nonmigratory multiprocessor scheduling for response time and energy. IEEE Trans Parallel Distrib Syst. 2008;19(11):1527–39. https://doi.org/10.1109/TPDS.2008.115.

    Article  Google Scholar 

  72. Kahraman C, et al. Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach. Appl Soft Comput. 2010;10(4):1293–300. https://doi.org/10.1016/j.asoc.2010.03.008.

    Article  Google Scholar 

  73. Houshmand M, et al. Efficient scheduling of task graphs to multiprocessors using a combination of modified simulated annealing and list based scheduling. In: 2010 third international symposium on intelligent information technology and security informatics. New York: IEEE; 2010. https://doi.org/10.1109/IITSI.2010.137.

  74. Al-Daoud H, Al-Azzoni I, Down DG. Power-aware linear programming based scheduling for heterogeneous computer clusters. Futur Gener Comput Syst. 2012;28(5):745–54. https://doi.org/10.1016/j.future.2011.04.001.

    Article  Google Scholar 

  75. Hasan M, Goraya MS. Successive stage multi-round scheduling for cube based multi-processor systems. In: 2014 IEEE international conference on computational intelligence and computing research. New York: IEEE; 2014. https://doi.org/10.1109/ICCIC.2014.7238340.

  76. Wang G, Li W, Hei X. Energy-aware real-time scheduling on heterogeneous multi-processor. In: 2015 49th annual conference on information sciences and systems (CISS). New York: IEEE; 2015. https://doi.org/10.1109/CISS.2015.7086884.

  77. Grzonka D, et al. Artificial Neural Network support to monitoring of the evolutionary driven security aware scheduling in computational distributed environments. Future Gener Comput Syst. 2015;51:72–86. https://doi.org/10.1016/j.future.2014.10.031.

    Article  Google Scholar 

  78. Wu P, Majeed S, Ryu M. Two approaches towards EDZL scheduling for performance asymmetric multiprocessors. In: 2016 IEEE international conference on network infrastructure and digital content (IC-NIDC). New York: IEEE; 2016. https://doi.org/10.1109/ICNIDC.2016.7974548.

  79. Sharma K, Singh A, Singh B. Repository of arbitration cores (ROAC) for scheduling in various multi-processor SOCs. In: 2016 international conference on control, instrumentation, communication and computational technologies (ICCICCT). New York: IEEE; 2016. https://doi.org/10.1109/ICCICCT.2016.7987944.

  80. Yang S, Deyu Q. Study on static task scheduling based on heterogeneous multi-core processor. In: 2017 international conference on computer network, electronic and automation (ICCNEA). New York: IEEE; 2017. https://doi.org/10.1109/ICCNEA.2017.38.

  81. Zou X, Cheng AMK. Real-time multiprocessor scheduling algorithm based on information theory principles. IEEE Embedded Syst Lett. 2017;9(4):93–6. https://doi.org/10.1109/LES.2017.2761540.

    Article  Google Scholar 

  82. Belmabrouk M, Marrakchi M. Comparison of parallel scheduling for triangular system resolution on multi-core processors. In: 2017 4th international conference on control, decision and information technologies (CoDIT). New York: IEEE; 2017. https://doi.org/10.1109/CoDIT.2017.8102668.

  83. Jiang X, et al. Semi-federated scheduling of parallel real-time tasks on multiprocessors. In: 2017 IEEE real-time systems symposium (RTSS). New York: IEEE; 2017.https://doi.org/10.1109/RTSS.2017.00015.

  84. Afshar S, et al. An optimal spin-lock priority assignment algorithm for real-time multi-core systems. In: 2017 IEEE 23rd international conference on embedded and real-time computing systems and applications (RTCSA). New York: IEEE; 2017. https://doi.org/10.1109/RTCSA.2017.8046310.

  85. Zheng H, et al. Scheduling of non-preemptive strictly periodic tasks in multi-core systems. In: 2017 international conference on circuits, devices and systems (ICCDS). New York: IEEE; 2017. https://doi.org/10.1109/ICCDS.2017.8120477.

  86. Baek H, Lee J, Shin I. Multi-level contention-free policy for real-time multiprocessor scheduling. J Syst Softw. 2018;137:36–49. https://doi.org/10.1016/j.jss.2017.11.027.

    Article  Google Scholar 

  87. Ying K-C, Lin S-W. Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks. Expert Syst Appl. 2018;92:132–41. https://doi.org/10.1016/j.eswa.2017.09.032.

    Article  Google Scholar 

  88. Alhussia H, et al. Practical performance analysis of real-time multiprocessor scheduling algorithms. J Fundam Appl Sci. 2018;10(2S):60–73.

    Google Scholar 

  89. Severo R, et al. Design and test of the RT-NKE task scheduling algorithm for multicore architectures. In: 2018 IEEE 19th Latin-American test symposium (LATS). New York: IEEE; 2018. https://doi.org/10.1109/LATW.2018.8349682.

  90. Shin K, et al. Task scheduling algorithm using minimized duplications in homogeneous systems. J Parallel Distrib Comput. 2008;68(8):1146–56. https://doi.org/10.1016/j.jpdc.2008.04.001.

    Article  MATH  Google Scholar 

  91. Hou ES, Ansari N, Ren H. A genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst. 1994;5(2):113–20. https://doi.org/10.1109/71.265940.

    Article  Google Scholar 

  92. Wang L, et al. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J Parallel Distrib Comput. 1997;47(1):8–22. https://doi.org/10.1006/jpdc.1997.1392.

    Article  Google Scholar 

  93. Zomaya AY, Ward C, Macey B. Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Trans Parallel Distrib Syst. 1999;10(8):795–812. https://doi.org/10.1109/71.790598.

    Article  Google Scholar 

  94. Ercan MF, Oğuz C. Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks. Comput Electr Eng. 2005;31(8):537–55. https://doi.org/10.1016/j.compeleceng.2005.09.004.

    Article  MATH  Google Scholar 

  95. Engin O, Ceran G, Yilmaz MK. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Appl Soft Comput. 2011;11(3):3056–65. https://doi.org/10.1016/j.asoc.2010.12.006.

    Article  Google Scholar 

  96. Chen RM, Huang YM. Multiconstraint task scheduling in multi-processor system by neural network. In: Proceedings tenth IEEE international conference on tools with artificial intelligence (Cat. No. 98CH36294). New York: IEEE; 1998. https://doi.org/10.1109/TAI.1998.744856.

  97. Huang Y-M, Chen R-M. Scheduling multiprocessor job with resource and timing constraints using neural networks. IEEE Trans Syst Man Cybern Part B. 1999;29(4):490–502. https://doi.org/10.1109/3477.775265.

    Article  Google Scholar 

  98. Chandiramani V, et al. A neural network approach to process assignment in multiprocessor systems based on the execution time. In: Proceedings of international conference on intelligent sensing and information processing, 2004. New York: IEEE; 2004. https://doi.org/10.1109/ICISIP.2004.1287678.

  99. Damak N, et al. Differential evolution for solving multi-mode resource-constrained project scheduling problems. Comput Oper Res. 2009;36(9):2653–9. https://doi.org/10.1016/j.cor.2008.11.010.

    Article  MathSciNet  MATH  Google Scholar 

  100. Ebrahimi Moghaddam M, Bonyadi MR. An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem. Int J Parallel Program. 2012;40(2):225–57. https://doi.org/10.1007/s10766-011-0179-0.

    Article  Google Scholar 

  101. Kechadi M-T, Low KS, Goncalves G. Recurrent neural network approach for cyclic job shop scheduling problem. J Manuf Syst. 2013;32(4):689–99. https://doi.org/10.1016/j.jmsy.2013.02.001.

    Article  Google Scholar 

  102. Ahmad SG, et al. A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems. J Parallel Distrib Comput. 2016;87:80–90. https://doi.org/10.1016/j.jpdc.2015.10.001.

    Article  Google Scholar 

  103. Tsuchiya T, Osada T, Kikuno T. Genetics-based multiprocessor scheduling using task duplication. Microprocess Microsyst. 1998;22(3–4):197–207. https://doi.org/10.1016/S0141-9331(98)00079-9.

    Article  Google Scholar 

  104. Wu AS, et al. An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Trans Parallel Distrib Syst. 2004;15(9):824–34. https://doi.org/10.1109/TPDS.2004.38.

    Article  Google Scholar 

  105. Omara FA, Arafa MM. Genetic algorithms for task scheduling problem. In: Abraham A, Hassanien AE, Siarry P, Engelbrecht A, editors. Foundations of computational intelligence, vol. 3. Studies in computational intelligence, vol. 203. Berlin: Springer; 2009.

  106. Behnamian J, Ghomi SMTF. Multi-objective fuzzy multiprocessor flowshop scheduling. Appl Soft Comput. 2014;21:139–48. https://doi.org/10.1016/j.asoc.2014.03.031.

    Article  Google Scholar 

  107. Xu Y, et al. A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci. 2014;270:255–87. https://doi.org/10.1016/j.ins.2014.02.122.

    Article  MathSciNet  MATH  Google Scholar 

  108. Konar D, et al. An improved Hybrid Quantum-Inspired Genetic Algorithm (HQIGA) for scheduling of real-time task in multiprocessor system. Appl Soft Comput. 2017;53:296–307. https://doi.org/10.1016/j.asoc.2016.12.051.

    Article  Google Scholar 

  109. Nanda AK, DeGroot D, Stenger DL. Scheduling directed task graphs on multiprocessors using simulated annealing. In: Proceedings of the 12th international conference on distributed computing systems. New York: IEEE; 1992. https://doi.org/10.1109/ICDCS.1992.235059.

  110. Sivanandam SN, Visalakshi P, Bhuvaneswari A. Multiprocessor scheduling using hybrid particle swarm optimization with dynamically varying inertia. IJCSA. 2007;4(3):95–106.

    Google Scholar 

  111. Salleh S, Zomaya AY. Multiprocessor scheduling using mean-field annealing. Futur Gener Comput Syst. 1998;14(5–6):393–408. https://doi.org/10.1016/S0167-739X(98)00042-9.

    Article  Google Scholar 

  112. Liu Y, et al. A scheduling algorithm in the randomly heterogeneous multi-core processor. In: 2016 12th international conference on natural computation, fuzzy systems and knowledge discovery (ICNC-FSKD). New York: IEEE; 2016. https://doi.org/10.1109/FSKD.2016.7603512.

  113. Choudhury P, Kumar R, Chakrabarti PP. Hybrid scheduling of dynamic task graphs with selective duplication for multiprocessors under memory and time constraints. IEEE Trans Parallel Distrib Syst 19(7):967–80. 2008. https://doi.org/10.1109/TPDS.2007.70784.

    Article  Google Scholar 

  114. Choudhury P, Chakrabarti PP, Kumar R. Online scheduling of dynamic task graphs with communication and contention for multiprocessors. IEEE Trans Parallel Distrib Syst. 2012;23(1):126–33. https://doi.org/10.1109/TPDS.2011.104.

    Article  Google Scholar 

  115. Li J, et al. Machine learning based online performance prediction for runtime parallelization and task scheduling. In: 2009 IEEE international symposium on performance analysis of systems and software. New York: IEEE; 2009. https://doi.org/10.1109/ISPASS.2009.4919641.

  116. Tabba N, Entezari-Maleki R, Movaghar A. Reduced communications fault tolerant task scheduling algorithm for multiprocessor systems. Procedia Eng. 2012;29:3820–5. https://doi.org/10.1016/j.proeng.2012.01.577.

    Article  Google Scholar 

  117. Xu Y, et al. A DAG scheduling scheme on heterogeneous computing systems using double molecular structure-based chemical reaction optimization. J Parallel Distrib Comput. 2013;73(9):1306–22. https://doi.org/10.1016/j.jpdc.2013.05.005.

    Article  Google Scholar 

  118. Gomatheeshwari B, Selvakumar J. Token based energy aware scheduling algorithms for heterogeneous multi-core. In: 2017 international conference on nextgen electronic technologies: silicon to software (ICNETS2). New York: IEEE; 2017. https://doi.org/10.1109/ICNETS2.2017.8067887.

  119. Khan H, Bashir Q, Hashmi MU. Scheduling based energy optimization technique in multiprocessor embedded systems. In: 2018 international conference on engineering and emerging technologies (ICEET). New York: IEEE; 2018. https://doi.org/10.1109/ICEET1.2018.8338643.

  120. Yun D, Wu CQ, Gu Y. An integrated approach to workflow mapping and task scheduling for delay minimization in distributed environments. J Parallel Distrib Comput. 2015;84:51–64. https://doi.org/10.1016/j.jpdc.2015.07.004.

    Article  Google Scholar 

  121. Bonabeau E, et al. Swarm intelligence: from natural to artificial systems. No. 1. Oxford: Oxford University Press; 1999.

  122. Eberhart RC, Shi Y, Kennedy J. Swarm intelligence. Amsterdam: Elsevier; 2001.

    Google Scholar 

  123. Tan Y. Fundamentals of computational swarm intelligence. 2009. p. 17–8.

  124. Abdelhalim MB. Task assignment for heterogeneous multiprocessors using re-excited particle swarm optimization. In: 2008 international conference on computer and electrical engineering. New York: IEEE; 2008. https://doi.org/10.1109/ICCEE.2008.41.

  125. Josephson J, Ramesh R. A novel algorithm for real time task scheduling in multiprocessor environment. Cluster Comput. 2018. https://doi.org/10.1007/s10586-018-2083-5.

    Article  Google Scholar 

  126. Ziarati K, Akbari R, Zeighami V. On the performance of bee algorithms for resource-constrained project scheduling problem. Appl Soft Comput. 2011;11(4):3720–33. https://doi.org/10.1016/j.asoc.2011.02.002.

    Article  Google Scholar 

  127. Zhisheng Z. Quantum-behaved particle swarm optimization algorithm for economic load dispatch of power system. Expert Syst Appl. 2010;37(2):1800–3. https://doi.org/10.1016/j.eswa.2009.07.042.

    Article  Google Scholar 

  128. Sarangi A, et al. Swarm intelligence based techniques for digital filter design. Appl Soft Comput. 2014;25:530–4. https://doi.org/10.1016/j.asoc.2013.06.001.

    Article  Google Scholar 

  129. Lo S-T, et al. Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system. Expert Syst Appl. 2008;34(3):2071–81. https://doi.org/10.1016/j.eswa.2007.02.022.

    Article  MathSciNet  Google Scholar 

  130. Omkar SN, et al. Quantum behaved Particle Swarm Optimization (QPSO) for multi-objective design optimization of composite structures. Expert Syst Appl. 2009;36(8):11312–22. https://doi.org/10.1016/j.eswa.2009.03.006.

    Article  Google Scholar 

  131. Kiyarazm O, Moeinzadeh MH, Sharifian-R S. A new method for scheduling load balancing in multi-processor systems based on PSO. In: 2011 second international conference on intelligent systems, modelling and simulation. New York: IEEE; 2011. https://doi.org/10.1109/ISMS.2011.73.

  132. Thanushkodi K, Deeba K. On performance analysis of hybrid algorithm (improved PSO with simulated annealing) with GA, PSO for multiprocessor job scheduling. WSEAS Trans Comput. 2011;10(9):287–300.

    Google Scholar 

  133. Dasgupta D. An overview of artificial immune systems and their applications. In: Dasgupta D, editor. Artificial immune systems and their applications. Berlin: Springer; 1993.

    Chapter  Google Scholar 

  134. De Castro LN, Castro LN, Timmis J. An introduction to artificial immune systems: a new computational intelligence paradigm. 2002.

  135. De Castro LN, Von Zuben FJ. Learning and optimization using the clonal selection principle. IEEE Trans Evol Comput. 2002;6(3):239–51. https://doi.org/10.1109/TEVC.2002.1011539.

    Article  Google Scholar 

  136. Dasgupta D. Advances in artificial immune systems. IEEE Comput Intell Mag. 2006;1(4):40–9. https://doi.org/10.1109/MCI.2006.329705.

    Article  Google Scholar 

  137. Dasgupta D, Senhua Yu, Nino F. Recent advances in artificial immune systems: models and applications. Appl Soft Comput. 2011;11(2):1574–87. https://doi.org/10.1016/j.asoc.2010.08.024.

    Article  Google Scholar 

  138. Nanda SJ. Artificial immune systems: principle, algorithms and applications. Diss. 2009.

  139. Passino KM. Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Syst Mag. 2002;22(3):52–67. https://doi.org/10.1109/MCS.2002.1004010.

    Article  Google Scholar 

  140. Tang WJ, Wu QH, Saunders JR. Bacterial foraging algorithm for dynamic environments. In: 2006 IEEE international conference on evolutionary computation. New York: IEEE; 2006. https://doi.org/10.1109/CEC.2006.1688462.

  141. Mishra S. A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation. IEEE Trans Evol Comput. 2005;9(1):61–73. https://doi.org/10.1109/TEVC.2004.840144.

    Article  Google Scholar 

  142. Greensmith J, Aickelin U. The dendritic cell algorithm (Ph. D. thesis). University of Nottingham; 2007.

  143. Greensmith J, Aickelin U, Twycross J. Articulation and clarification of the dendritic cell algorithm. In: Bersini H, Carneiro J, editors. Artificial immune systems. ICARIS 2006. Lecture notes in computer science, vol. 4163. Berlin: Springer; 2006. https://doi.org/10.1007/11823940_31.

    Chapter  Google Scholar 

  144. Gandomi AH, Alavi AH. Krill herd: a new bio-inspired optimization algorithm. Commun Nonlinear Sci Numer Simul. 2012;17(12):4831–45. https://doi.org/10.1016/j.cnsns.2012.05.010.

    Article  MathSciNet  MATH  Google Scholar 

  145. Swiecicka A, Seredynski F, Zomaya AY. Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support. IEEE Trans Parallel Distrib Syst. 2006;17(3):253–62. https://doi.org/10.1109/TPDS.2006.38.

    Article  Google Scholar 

  146. Nayak SK, Padhy SK, Panigrahi SP. A novel algorithm for dynamic task scheduling. Future Gener Comput Syst. 2012;28(5):709–17. https://doi.org/10.1016/j.future.2011.12.001.

    Article  Google Scholar 

  147. Tripathy B, Dash S, Padhy SK. Multiprocessor scheduling and neural network training methods using shuffled frog-leaping algorithm. Comput Ind Eng. 2015;80:154–8. https://doi.org/10.1016/j.cie.2014.12.013.

    Article  Google Scholar 

  148. Marichelvam MK, Prabaharan T, Yang XS. Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan. Appl Soft Comput. 2014;19:93–101. https://doi.org/10.1016/j.asoc.2014.02.005.

    Article  Google Scholar 

  149. Nayak SK, Panda CS, Padhy SK. Efficient multiprocessor scheduling using water cycle algorithm. In: Ray K, Pant M, Bandyopadhyay A, editors. Soft computing applications. Studies in computational intelligence, vol. 761. Singapore: Springer; 2018.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Application, VSSUT, Burla, Odisha, India

    Biswaranjan Acharya & Sucheta Panda

  2. Bonfils Automation Technology Pvt. Ltd., Chennai, India

    Eashwar Sivakumar

Authors
  1. Biswaranjan Acharya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sucheta Panda
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eashwar Sivakumar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Biswaranjan Acharya.

Ethics declarations

Conflict of interest

On behalf of all authors, the corresponding author states that there is no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Intelligent Systems” guest edited by Geetha Ganesan, Lalit Garg, Renu Dhir, Vijay Kumar and Manik Sharma.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Acharya, B., Panda, S. & Sivakumar, E. An Analytical Study of Multiprocessor Scheduling Using Metaheuristic Approach. SN COMPUT. SCI. 3, 497 (2022). https://doi.org/10.1007/s42979-022-01398-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-022-01398-1

Keywords

Search

Navigation