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

Cheng Zhao; Myungryun Yoo; Takanori Yokoyama

doi:doi:10.11648/j.ijiis.s.2015040201.13

| Peer-Reviewed

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

Cheng Zhao, Myungryun Yoo, Takanori Yokoyama

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

Received: 16 January 2015 Accepted: 19 January 2015 Published: 29 January 2015

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Cheng Zhao

Department of Computer Science, Tokyo City University, Tokyo, Japan
Myungryun Yoo

Department of Computer Science, Tokyo City University, Tokyo, Japan
Takanori Yokoyama

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

Download PDF

Sections

Plain Text BibTeX RIS

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