| Peer-Reviewed

On-Line Scheduling Algorithm for Real-Time Multiprocessor Systems with ACO

Received: 16 January 2015     Accepted: 19 January 2015     Published: 29 January 2015
Views:       Downloads:
Abstract

The Ant Colony Optimization algorithms (ACO) are computational models inspired by the collective foraging behavior of ants. By looking at the strengths of ACO, they are the most appropriate for scheduling of tasks in soft real-time systems. In this paper, ACO based scheduling algorithm for real-time operating systems (RTOS) has been proposed. During simulation, results are obtained with periodic tasks, measured in terms of Success Ratio & Effective CPU Utilization and compared with Kotecha’s algorithm in the same environment. It has been observed that the proposed algorithm is equally optimal during underloaded conditions and it performs better during overloaded conditions.

Published in International Journal of Intelligent Information Systems (Volume 4, Issue 2-1)

This article belongs to the Special Issue Logistics Optimization Using Evolutionary Computation Techniques

DOI 10.11648/j.ijiis.s.2015040201.13
Page(s) 13-17
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2015. Published by Science Publishing Group

Keywords

Real-Time Systems, Scheduling, ACO, EDF

References
[1] K. Ramamritham and J. A. Stankovik, “Scheduling algorithms and operating support for real-time systems”, Proceedings of the IEEE, vol. 82, pp. 56-76, January 1994.
[2] C. L. Liu and L. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment”, Journal of ACM, vol.20, pp: 46-61, January 1973.
[3] M. Dertouzos and K. Ogata, “Control robotics: The procedural control of physical process,” Proc. IFIP Congress, pp. 807-813, 1974.
[4] A. Mok, “Fundamental Design Problems of Distributed Systems for the Hard-Real-Time Environment,” Ph.d. thesis, MIT, Cambridge, Massachusetts, May 1983.
[5] G. Saini, “Application of Fuzzy logic to Real-time scheduling”, Real-Time Conference, 14th IEEE-NPSS.pp.113-116, 2005.
[6] M. Dorigo and G. Caro, “The Ant Colony Optimization Metaheuristic in D. Corne, M. Dorigo and F. Glover(eds)”, New Ideas in Optimization, McGraw Hill, 1999.
[7] V. Ramos, F. Muge, and P. Pina, “Self-organized data and image retrieval as a consequence of inter-dynamic synergistic relationships in artificial ant colonies”, In Second International Conference on Hybrid Intelligent System, IOS Press, Santiago, 2002.
[8] Kotecha and A Shah, “Scheduling Algorithm for Real-Time Opeating Systems using ACO”, 2010 Intelligence and Communication Networks, pp. 617–621, Nov 2010.
[9] C. D. Locke, “Best Effort Decision Making for Real-Time Scheduling”, Ph.d. thesis, Computer Science Department, Carnegie-Mellon University, 1986.
[10] G. Koren and D. Shasha, “Dover: An optimal on-line scheduling algorithm for overloaded real-time systems”, SIAM Journal of Computing, 24(2): 318-339 April 1995. 

[11] A Shah, K Kotecha and D Shah, “Adaptive scheduling algorithm for real-time distributed systems”, To appear in International Journal of Intelligent Computing and Cybernetics.
[12] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” In: Proceedings of European Conf. on Artificial Life. Elsevier, Amsterdam, pp. 134-142, 1991.
[13] K. Ramamritham, J. A. Stankovik, and P. F. Shiah, “Efficient scheduling algorithms for real-time multiprocessor systems”, IEEE Transaction on Parallel and Distributed Systems, vol. 1, April 1990.
[14] S. Baruah, G. Koren, B. Mishra, A. Raghunath, L. Roiser, and D. Shasha, “On-line scheduling in the presence of overload,” In FOCS, pp. 100–110 1991.
Cite This Article
  • APA Style

    Cheng Zhao, Myungryun Yoo, Takanori Yokoyama. (2015). On-Line Scheduling Algorithm for Real-Time Multiprocessor Systems with ACO. International Journal of Intelligent Information Systems, 4(2-1), 13-17. https://doi.org/10.11648/j.ijiis.s.2015040201.13

    Copy | Download

    ACS Style

    Cheng Zhao; Myungryun Yoo; Takanori Yokoyama. On-Line Scheduling Algorithm for Real-Time Multiprocessor Systems with ACO. Int. J. Intell. Inf. Syst. 2015, 4(2-1), 13-17. doi: 10.11648/j.ijiis.s.2015040201.13

    Copy | Download

    AMA Style

    Cheng Zhao, Myungryun Yoo, Takanori Yokoyama. On-Line Scheduling Algorithm for Real-Time Multiprocessor Systems with ACO. Int J Intell Inf Syst. 2015;4(2-1):13-17. doi: 10.11648/j.ijiis.s.2015040201.13

    Copy | Download

  • @article{10.11648/j.ijiis.s.2015040201.13,
      author = {Cheng Zhao and Myungryun Yoo and Takanori Yokoyama},
      title = {On-Line Scheduling Algorithm for Real-Time Multiprocessor Systems with ACO},
      journal = {International Journal of Intelligent Information Systems},
      volume = {4},
      number = {2-1},
      pages = {13-17},
      doi = {10.11648/j.ijiis.s.2015040201.13},
      url = {https://doi.org/10.11648/j.ijiis.s.2015040201.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijiis.s.2015040201.13},
      abstract = {The Ant Colony Optimization algorithms (ACO) are computational models inspired by the collective foraging behavior of ants. By looking at the strengths of ACO, they are the most appropriate for scheduling of tasks in soft real-time systems. In this paper, ACO based scheduling algorithm for real-time operating systems (RTOS) has been proposed. During simulation, results are obtained with periodic tasks, measured in terms of Success Ratio & Effective CPU Utilization and compared with Kotecha’s algorithm in the same environment. It has been observed that the proposed algorithm is equally optimal during underloaded conditions and it performs better during overloaded conditions.},
     year = {2015}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - On-Line Scheduling Algorithm for Real-Time Multiprocessor Systems with ACO
    AU  - Cheng Zhao
    AU  - Myungryun Yoo
    AU  - Takanori Yokoyama
    Y1  - 2015/01/29
    PY  - 2015
    N1  - https://doi.org/10.11648/j.ijiis.s.2015040201.13
    DO  - 10.11648/j.ijiis.s.2015040201.13
    T2  - International Journal of Intelligent Information Systems
    JF  - International Journal of Intelligent Information Systems
    JO  - International Journal of Intelligent Information Systems
    SP  - 13
    EP  - 17
    PB  - Science Publishing Group
    SN  - 2328-7683
    UR  - https://doi.org/10.11648/j.ijiis.s.2015040201.13
    AB  - The Ant Colony Optimization algorithms (ACO) are computational models inspired by the collective foraging behavior of ants. By looking at the strengths of ACO, they are the most appropriate for scheduling of tasks in soft real-time systems. In this paper, ACO based scheduling algorithm for real-time operating systems (RTOS) has been proposed. During simulation, results are obtained with periodic tasks, measured in terms of Success Ratio & Effective CPU Utilization and compared with Kotecha’s algorithm in the same environment. It has been observed that the proposed algorithm is equally optimal during underloaded conditions and it performs better during overloaded conditions.
    VL  - 4
    IS  - 2-1
    ER  - 

    Copy | Download

Author Information
  • Department of Computer Science, Tokyo City University, Tokyo, Japan

  • Department of Computer Science, Tokyo City University, Tokyo, Japan

  • Department of Computer Science, Tokyo City University, Tokyo, Japan

  • Sections