GENETIC ALGORITHM WITH TWO OBJECTIVE FOR REAL-TIME TASK SCHEDULING WITH COMMUNICATION TIME

Main Article Content

Myungryun Yoo
Takanori Yokoyama

Keywords

real-time task scheduling algorithm, two objective genetic algorithm, adaptive weight approach, communication time, execution order

Abstract

Purpose of the study:The real-time task scheduling on multiprocessor system is known as an NP-hard problem. This paper proposes a new real-time task scheduling algorithmwhich considers the communication time between processors and the execution order between tasks.


Methodology:Genetic Algorithm (GA)with Adaptive Weight Approach (AWA) is used in our approach.


Main Findings:Our approach has two objectives. The first objective is to minimize the total amount of deadline-miss. And the second objective is to minimize the total number of processors used.


Applications of this study:For two objectives,the range of each objective is readjusted through Adaptive Weight Approach (AWA) and more useful result is obtained.


Novelty/Originality of this study:This study never been done before.This study also wasprovided current information about scheduling algorithm and heuristics algorithm.

Downloads

Download data is not yet available.
Abstract 169 | PDF Downloads 54

References

1. Bernat G., Burns, A. &Liamosi, (2001). A. Weakly Hard Real-Time Systems. Transactions onComputer Systems, 50(4), 308-321.https://doi.org/10.1109/12.919277
2. Diaz J. L., Garcia, D. F. &Lopez, J. M.(2004).Minimum and Maximum Utilization Bounds forMultiprocessor Rate Monotonic Scheduling.IEEE Transactions on Parallel andDistributed Systems,15(7), 642-653.https://doi.org/10.1109/TPDS.2004.25
3. Kim M. H., Lee, H. G. & Lee, J. W. (1997). A Proportional-Share Scheduler for MultimediaApplications. Proc. of Multimedia Computing and Systems, 484-491.
4. Lin, M., & Yang, L. (1999). Hybrid Genetic Algorithms for Scheduling Partially Ordered Tasksin AMulti-processor Environment. In: Proceedings of the 6th International Conference onReal-Time Computer Systems and Applications, 382–387.
5. Mitra, H., &Ramanathan, P. (1993). A Genetic Approach for Scheduling Non-preemptiveTaskswith Precedence and Deadline Constraints. In: Proceedings of the 26th HawaiiInternational Conference on System Sciences, 556–564.https://doi.org/10.1109/HICSS.1993.284070
6. Monnier, Y., Beauvais, J. P. &Deplanche, A. M. (1998). A Genetic Algorithm for SchedulingTasks in a Real-Time Distributed System. Proc. of 24th Euromicro Conference, 708-714.https://doi.org/10.1109/EURMIC.1998.708092
7. Oh, J., & Wu, C. (2004). Genetic-algorithm-based Real-time Task Scheduling with Multiple Goals. Journal of Systems and Software, 71(3), 245-258.https://doi.org/10.1016/S0164-1212(02)00147-4
8. Yalaoui, F., & Chu, C. (2002).Parallel Machine Scheduling to Minimize Total Tardiness. International Journal of Production Economics, 76(3), 265–279. https://doi.org/10.1016/S0925-5273(01)00175-X
9. Yoo, M. (2016). Continuous Media Tasks Scheduling Algorithm. International Journal of Electronics Communication and Computer Engineering, 7(2), 99-103.