A Novel ACO-Based Static Task Scheduling Approach for Multiprocessor Environments

References

• Chretienne P, et al. Scheduling Theory and Its Application. New York: Wiley; 1995.
   Google Scholar
• Kwok Y, Ahmad I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. Final report. Hong Kong Research Grants Council, Hong Kong; 1998. Report No.: HKUST 734/96E and HKUST 6076/97E.
   Google Scholar
• Ahmad I and Kwok Y. On Parallelizing the Multiprocessor Scheduling Problem. IEEE Trans. Parallel Distrib. Syst. 1999 Aug; 10(8):795–18. doi: 10.1109/71.790598
   Web of Science ®Google Scholar
• Papadimitriou CH and Yannakakis M. Scheduling Interval-Ordered Tasks. SIAM J.Computing. 1979; 8: 405–5. doi: 10.1137/0208031
   Web of Science ®Google Scholar
• Kruatrachue B and Lewis TG. Duplication Scheduling Heuristics (DSH): A New Precedence Task Scheduler for Parallel Processor Systems. Final report. Oregon State University, Corvallis; 1987. Report No.: OR 97331.
   Google Scholar
• Colin JY and Chretienne P. C.P.M. Scheduling with Small Computation Delays and Task Duplication. Operations Research. 1991: 680–5. doi: 10.1287/opre.39.4.680
   Web of Science ®Google Scholar
• Chung YC and Ranka S. Application and Performance Analysis of a Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed-Memory Multiprocessors. In: proceeding of the Supercomputing’92; 1992 Nov: p. 512–10. doi: 10.1109/SUPERC.1992.236653
   Google Scholar
• Chen H Shirazi B and Marquis J. Performance Evaluation of A Novel Scheduling Method: Linear Clustering with Task Duplication. In: Proceeding of the Int’l Conf. Parallel and Distributed Systems; 1993 Dec: p. 270–6.
   Google Scholar
• Ahmad I and Kwok YK. On Exploiting Task Duplication in Parallel Program Scheduling. IEEE Trans. Parallel and Distributed Systems. 1998 Sept; 9(9): 872–21. doi: 10.1109/71.722221
   Web of Science ®Google Scholar
• Palis MA Liou JC and. Wei DSL. Task Clustering and Scheduling for Distributed Memory Parallel Architectures. IEEE Trans. Parallel and Distributed Systems. 1996 Jan; 7(1): 46–10. doi: 10.1109/71.481597
   Web of Science ®Google Scholar
• Park GL Shirazi B and Marquis J. DFRN: A New Approach for Duplication Based Scheduling for Distributed Memory Multiprocessor Systems. In: Proceeding of the 11th Int’l Parallel Processing Symposium; 1997 Apr: p. 157–10. doi: 10.1109/IPPS.1997.580875
   Google Scholar
• Kim SJ and Browne JC. A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures. In: Proceeding of the 1988 Int’l Conference on Parallel Processing; 1988 Aug; 2: p. 1–8.
   Google Scholar
• Sarkar V. Partitioning and Scheduling Parallel Programs for Multiprocessors. Cambridge (MA): MIT Press; 1989.
   Google Scholar
• Wu MY and Gajski DD. Hypertool: A Programming Aid for Message-Passing Systems. IEEE Trans. Parallel and Distributed Systems. 1990 Jul; 1(3): 330–14. doi: 10.1109/71.80160
   Google Scholar
• Yang T and Gerasoulis A. List Scheduling with and without Communication Delays. Parallel Computing. 1993; 19: 1321–24. doi: 10.1016/0167-8191(93)90079-Z
   Web of Science ®Google Scholar
• Kwok YK and Ahmad I. Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors. IEEE Trans. Parallel and Distributed Systems. 1996 May; 7(5): 506–16. doi: 10.1109/71.503776
   Web of Science ®Google Scholar
• Adam TL, Chandy KM and Dickson J. A Comparison of List Scheduling for Parallel Processing Systems. Comm. ACM. 1974 Dec; 17(12): 685–16. doi: 10.1145/361604.361619
   Web of Science ®Google Scholar
• McCreary C and Gill H. Automatic Determination of Grain Size for Efficient Parallel Processing. Comm. ACM. 1989 Sep; 32: 1073–6. doi: 10.1145/66451.66454
   Web of Science ®Google Scholar
• Baxter J. and Patel JH. The LAST Algorithm: A Heuristic-Based Static Task Allocation Algorithm. In: Proceeding of the 1989 Int’l Conf. Parallel Processing; 1989 Aug; II: p. 217–6.
   Google Scholar
• Hwang JJ, Chow YC, Anger FD and Lee CY. Scheduling Precedence Graphs in Systems with Interprocessor Communication Times. SIAM J. Computing. 1989 Apr; 18(2): pp. 244–14. doi: 10.1137/0218016
   Web of Science ®Google Scholar
• Sih GC and Lee EA. A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures. IEEE Trans. Parallel and Distributed Systems. 1993 Feb; 4(2): 75–13. doi: 10.1109/71.207593
   Web of Science ®Google Scholar
• Parsa S, Lotfi Sh and Lotfi N. The approach based on evolutional processing for task graph scheduling in multiprocessor architecture. In: Proceeding of the 11th Iranian Int. CSI Computer Conf.; 2006; Tehran: p. 627–8.
   Google Scholar
• Salmani M, Zali M and Moghimi M. Task Scheduling in Multi-Processor Systems Using Genetic Algorithm and Reinforcement Learning. In: Proceeding of the 12th Iranian Int. CSI Computer Conf.; 2007; Tehran: p. 1948–4.
   Google Scholar
• Abdeyazdan M and Rahmani A. Task scheduling in multiprocessor systems using a new genetic alghorithm priority based on number of offspring. In Proceeding of the 13th Iranian Int. CSI Computer Conf.; 2008; Kish.
   Google Scholar
• Hou E, Ansari N and Ren H. A Genetic Algorithm for Multiprocessor Scheduling. IEEE Trans. Parallel Distrib. Syst. 1994 Feb; 5(2): 113–8. doi: 10.1109/71.265940
   Web of Science ®Google Scholar
• Salmani M, Fakhraie S, Montazeri F, Fakhraie SM and Nili M. A Representation for Genetic-Algorithm-Based Multiprocessor Task Scheduling. In: Proceeding of the IEEE Congr. On Evolutionary Computation; 2006; Vancouver: p. 340–8.
   Google Scholar
• Correa R, Ferreira A and Rebreyend P. Scheduling Multiprocessor Tasks with Genetic Algorithms. IEEE Trans. Parallel Distrib. Syst. 1999 Aug; 10(8): 825–13. doi: 10.1109/71.790600
   Web of Science ®Google Scholar
• Zomaya A, Wards C and Macey B. Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance Issues. IEEE Trans. Parallel Distrib. Syst. 1999 Aug; 10(8), 795–18. doi: 10.1109/71.790598
   Web of Science ®Google Scholar
• Dehodhi M, Ahmad I and Ahmad I. A Multiprocessor Scheduling Scheme Using Problem-Space Genetic Algorithms. In: Proceeding of the IEEE International Conference on Evolutionary Computation; 1995 Nov 29Dec 1; Perth (WA): 214–6.
   Google Scholar
• Wu A, Yu H, Jin S, Lin K, and Schiavone G. An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling. IEEE Trans. Parallel Distrib. Syst. 2004 Sep; 15(9): 824–11. doi: 10.1109/TPDS.2004.38
   Web of Science ®Google Scholar
• Hou E, Hong R and Ansari N. Efficient Multiprocessor scheduling Based on Genetic Algorithms. In: Proceeding of the 16th Annual Conference of IEEE of Industrial Electronics Society; IECON '90; 1990 Nov 27–30; Pacific Grove (CA): p. 1239–5.
   Google Scholar
• Hwang R, Gen M and Katayama H.A comparison of multiprocessor task scheduling algorithms with communication costs. Computer & Operations Research. 2008; 35: 976–18. doi: 10.1016/j.cor.2006.05.013
   Web of Science ®Google Scholar
• Shroff P, Watson D Flann N and Freund R. Genetic simulated annealing for scheduling data-dependent tasks in heterogeneous environments. In: Proceeding of the 5th IEEE Heterogeneous Computing Workshop (HCW ' 96); 1997: p. 98–7.
   Google Scholar
• Wu M, Shu W and Gu J. Local Search for DAG Scheduling and Task Assignment. In: Proceeding of the 1997 Int'l Conf. Parallel Processing; 1997: p. 174–7.
   Google Scholar
• Dorigo M, Maniezzo V and Colorni A. Positive feedback as a search strategy. Final report. Politecnico di Milano; Milan; 1991. Report No.: 91–016.
   Google Scholar
• Dorigo M, DiCaro G and Gambardella L. Ant Algorithm for Discrete Optimization. Artificial Life. 1999; 5(2): 137–36. doi: 10.1162/106454699568728
   PubMed Web of Science ®Google Scholar
• Maniezzo V, Colorni A and Dorigo M. The Ant System applied to the quadratic assignment problem. Final report. Universit´e Libre de Bruxelles; Belgium; 1994. Report No.: IRIDIA=94–28.
   Google Scholar
• Colorni A, Dorigo M, Maniezzo V and Trubian M. Ant System for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science. 1994; 34: 39–15.
   Google Scholar
• Bullnheimer B and Strauss C. Tourenplanung mit dem Ant System. Final report. Instituts f¨ur Betriebwirtschaftslehre, Vienna, Austria; 1996. Report No. 6.
   Google Scholar
• Gambardella L and Dorigo M. HAS-SOP: A hybrid ant system for the sequential ordering problem. Final report. IDSIA, Lugano, Switzerland; 1997. Report No. 11–97.
   Google Scholar
• Costa D and Hertz A. Ants can colour graphs. Journal of the Operational Research Society. 1997; 48: 295–11. doi: 10.1057/palgrave.jors.2600357
   Web of Science ®Google Scholar
• DiCaro G and Dorigo M. AntNet: A mobile agents approach to adaptive routing. Final report. Universit´e Libre de Bruxelles, IRIDIA; 1997. Report No. 97–12.
   Google Scholar
• Al-Mouhamed MA. Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs. IEEE Trans. Software Engineering. 1990 Dec;16(12): 1390–12. doi: 10.1109/32.62447
   Web of Science ®Google Scholar
• Al-Maasarani A. Priority-Based Scheduling and Evaluation of Precedence Graphs with Communication Times [M.S. Thesis]. King Fahd University of Petroleum and Minerals, Saudi Arabia; 1993.
   Google Scholar
• Kwok Y and Ahmad I. Benchmarking and Comparison of the Task Graph Scheduling Algorithms. Final report. Hong Kong Research Grants Council, Hong Kong; 1999. Report No. HKUST 734/96E and HKUST 6076/97E.
   Google Scholar
• Boveiri H. R., ACO-MTS: A new approach for multiprocessor task scheduling based on ant colony optimization, In: Proceeding of the IEEE International Conference on Intelligent and Advanced Systems (ICIAS); 2010 Jun 15–17; Kuala Lumpur (Malaysia): 1–5.
   Google Scholar
• [10] H. R. Boveiri, “An Efficient Task Priority Measurement for List-Scheduling in Multiprocessor Environments,” International Journal of Software Engineering and Its Applications (IJSEIA), vol. 9, no 5, pp. 233–246, May 2015. doi: 10.14257/ijseia.2015.9.5.22
   Google Scholar