In this study, we presented scheduling algorithm for soft real-time tasks.
Several derived algorithms from Rate Monotonic (RM), Earliest Deadline First (EDF) for hard real-time tasks or some scheduling algorithms such as Rate Regulating Proportional Share (rrPS) and Modified Proportional Share (mPS) have been used for soft real-time tasks. However, these algorithms have some drawbacks in resource utilization and pattern of degradation under the overloaded situation. Furthermore, the scheduling on multiprocessor system is NP-hard problem.
The objective of this study is to propose reasonable alternative for NP-hard scheduling problem which can not be solved by traditional methods. The proposed algorithms in this study use a Genetic Algorithm (GA). GA has been known to offer significant advantages against conventional heuristics by using simultaneously several search principles and heuristics.
In the hybrid GA (hGA) combined with Simulated Annealing (SA), the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of the new trial solution. This hybridization does not hurt own advantages of GA but finds more accurate solutions in later stage of searching process.
The multiobjective GA for soft real-time task scheduling also is presented. Not only minimization the total tardiness but also minimization the total number of processor used and the makespan are taken into considerations. However, since these objectives are in conflicting (trade-offs) relations, the Pareto optimum concept is introduced to solution process.
In chapter 4, two scheduling algorithms are proposed for periodic tasks. The first algorithm is designed for scheduling algorithm on uniprocessor system. This algorithm is to determine execution sequence of tasks with the objective of minimizing the weighted sum of variance of tardiness and the total number of context switching among tasks. From the numerical results, the results of the proposed algorithm are better than that of other scheduling algorithms. Also, three evaluation methods are compared. The second algorithm is designed for scheduling algorithm on multiprocessor system. The proposed algorithm is to determine the execution sequence of tasks with the objective of minimizing the total tardiness. From the numerical results, the result of the proposed algorithm is better than that of other algorithms.
In chapter 5, two scheduling algorithms on homogeneous multiprocessor system are presented. The communication time between processors is not considered in the first algorithm.
The second algorithm is designed for scheduling on multiprocessor system with communication time between processors. The objective of proposed scheduling algorithms is to minimize the total tardiness and total number of processors used. From the numerical results, the results of
the proposed algorithms are better than that of other algorithms.
In chapter 6, two scheduling algorithms on heterogeneous multiprocessor system are presented. The objective of the first algorithm is to minimize the total tardiness and the objective of the second algorithm is to minimize the total tardiness and completion time simultaneously.
From the numerical results, the results of the proposed algorithms are better than that of other algorithms.
In conclusion, from these experiment results we can see that the scheduling algorithm using GA is very promising approach for obtaining relatively satisfactory solutions to soft real-time task scheduling problem, which belong to the difficult NP-hard problem. All of the techniques developed for theses problems in this research are useful and applicable for other scheduling problems. The research field will be extended to logistic problem and process planning problem.
Bibliography
Al-Sharaeh, S. and B. E. Wells, “A Comparison of Heuristics for List Schedules using The Box-method and P-method for Random Digraph Generation”, Proc. of the 28th Southeastern Symposium on System Theory, pp. 467–471, 1996.
Anagnostou, M. E., M. E. Theologou, K. M. Vlakos and D. Tournis, “Quality of service requirements in ATM-based B-ISDNs”, Computer Commun, vol. 14, no. 4, pp. 197-204, 1991.
Bernat G., A. Burns and A. Liamosi, “Weakly Hard Real-Time Systems”, Transactions on Computer Systems, vol. 50, no. 4, pp. 308-321, 2001.
Budin L., J. Domagoj and G. Marin, “Genetic Algorithm in Real-Time Imprecise Computing”, Proc. of Industrial Electronics, pp.84-89, 1999.
Chen M. S., “Stream Conversion to Support Interactive Video Playout”, Proc. of IEEE multimedia, pp. 51-58, 1996.
Deb, K., Multi-objective Optimization using Evolutionary Algorithms, John Wiley & Sons, 2001.
Denouzos M. L. and Mok, A. K., “Multiprocessor on-line scheduling of hard-real-time tasks”, IEEE Transactions on Software Engineering, vol. 15, no. 12, pp. 392–399, 1989.
Dhodhi, M. K., I. Ahmad, A. Yatama and I. Ahmad, “An Integrated Technique for Task Matching and Scheduling onto Distributed Heterogeneous Computing Systems”, Journal of Parallel and Distributed Computing, vol. 62, pp. 1338-1361, 2002.
Diaz J. L., D. F. Garcia and J. M. Lopez, “Minimum and Maximum Utilization Bounds for Multiprocessor Rate Monotonic Scheduling”, IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 642-653, 2004.
Du, J. and J. Leung, “Minimizing Total Tardiness on One Machine is NP-hard”, Mathematics of Operational Research, vol. 15, pp. 483–495, 1990.
Emilda S., L. Jacob, D. Ovidiu and B. Prabhakaran, “Flexible Disk Scheduling for Multimedia Presentation Servers”, IEEE International Conference on Networks, pp.151-155, 2002.
Fogel, D. and A. Ghozeil, “Using fitness distributions to design more efficient evolutionary computations”, Fogel, D., editor, Proc. of the Third IEEE conference on Evolutionary Computation, IEEE Press, Nagoya, Japan, pp. 11-19, 1996.
Fonseca, C. and P. Fleming, “An overview of evolutionary algorithms in multiobjective optimization”, Evolutionary Computation, vol. 3, no. 1, pp. 1-16, 1995.
Gen M. and R. Cheng, Genetic Algorithms & Engineering Design, John Wiley & Sons, 1997.
Gen M. and R. Cheng, Genetic Algorithms & Engineering Optimization, John Wiley & Sons, 2000.
Gen, M. and J. R. Kim, “GA-based Optimization of Reliability Design”, in P. Bentley ed.
Evolutionary Design by Computers, Morgan Kaufman, San Francisco, pp. 191-218, 1999.
Goldberg D. E., Genetic Algorithms in Search, Optimization & Machine Learning, Addison-Wesley, 1989.
Hehmann, D. B., M. G. Salmony and H. J. Stuttgen, “High-Speed Transport Systems for Multimedia Applications”, Protocols for High-Speed Networks, 1989.
Hou E. S. H., R. Hong and N, Ansari, “Efficient multiprocessor scheduling based on genetic algorithms ”, IEEE Conference on Industrial Electronics Society, pp.1239-1243, 1990.
Ishii, H., H. Shiode, and T. Murata, “A Multiobjective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling”, IEEE Trans. on Systems, Man and Cybernetics, vol.
28, no. 3, pp. 392-403, 1998.
Jackson L. E. and G. N. Rouskas, “Optimal Quantization of Periodic Task Requests on Multiple Identical Processors”, IEEE Transactions on Parallel and Distributed Systems, vol.14, no.8, pp.795-806, 2003.
Kim, H. C, Y. Hayashi and K. Nara, “An Algorithm for Thermal Unit Maintenance Scheduling through combined use of GA, SA and TS”, IEEE Transactions on Power Systems, vol. 12, no. 1, pp. 329-335, 1997.
Kim M. H., H. G. Lee and J. W. Lee, “A Proportional-Share Scheduler for Multimedia Applications”, Proc. of Multimedia Computing and Systems, pp.484-491, 1997.
Kirkpatrick, S., C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing”, Science, vol. 220, no. 4598, pp. 671-680, 1983.
Krishna C. M. and G. S. Kang, Real-Time System, McGraw-Hill, 1997.
Lenstra, J. K., R. Kan and P. Brucker, ”Complexity of Machine Scheduling Problems”, Annals of Discrete Mathematics, pp. 343–362, 1997.
Lin, M. and L. Yang, “Hybrid Genetic Algorithms for Scheduling Partially Ordered Tasks in A Multi-processor Environment”, Proc. of the 6th International Conference on Real-Time Computer Systems and Applications, pp. 382–387, 1999.
Liu C. L. and J. W. Layland, “Scheduling Algorithm for Multiprogramming in a Hard Real-Time Environment”, Journal of the ACM, vol. 20, no. 1, pp. 46-59, 1973.
Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Program, Second Extended Edition, Spring-Verlag, 1994.
Mitra, H. and P. Ramanathan, “A Genetic Approach for Scheduling Non-preemptive Tasks with Precedence and Deadline Constraints”, Proc. of the 26th Hawaii International Conference on System Sciences, pp. 556–564, 1993.
Monnier, Y., J. P. Beauvais and A. M. Deplanche, “A Genetic Algorithm for Scheduling Tasks in a Real-Time Distributed System”, Proc. of 24th Euromicro Conference, pp. 708-714, 1998.
Oh, J. and C. Wu, “Genetic-algorithm-based Real-time Task Scheduling with Multiple Goals”, Journal of Systems and Software, vol. 71, no. 3, pp. 245-258, 2004.
Page A. J. and T. J. Naughton, “Dynamic Task Scheduling using Genetic Algorithm for Heterogeneous Distributed Computing”, Proc. of 19th IEEE International Parallel and Distributed Processing Symposium, 189.1, 2005.
Sancho, N. G., “A Multi-objective Routing Problem”, Engineering Optimization, vol. 10, pp. 71-76, 1986.
Theys, M. D., T. D. Braun, H. J. Siegal, A. A. Maciejewski and Y. K. Kwok, “Mapping Tasks onto Distributed Heterogeneous Computing Systems Using a Genetic Algorithm Approach”, Zomaya, A. Y., F. Ercal and S. Olariu, editors, Solutions to Parallel and Distributed Computing Problems, chapter 6, pp. 135-178, John Wiley & Sons, 2001.
Tracy M. and S. Douglass, “Genetic Algorithms and Their Application to Continuum Generation”, Ohio State University, REU, Technical Report, p.12, 2001.
Tsun P. J. and H. Babak, “Dynamic real time scheduling strategies for interative continuous media servers”, Miltimedia Systems, vol. 7, no. 1, pp. 91-95, 1999.
Xu, H. and G. Vukovich, “Fuzzy Evolutionary Algorithms and Automatic Robot Trajectory Generation”, Fogel, D. editor, Proc. of the First IEEE Conference on Evolutionary Computation, IEEE Press, Piscataway, NJ, pp. 595-600, 1998.
Yalaoui, F. and C. Chu, “Parallel Machine Scheduling to Minimize Total Tardiness”, International Journal of Production Economics, vol. 76, no. 3, pp. 265–279, 2002.
Yoo, M. R., B. C. Ahn, D. H. Lee and H. C. Kim, “A New Real-Time Scheduling Algorithm for Continuous Media Tasks”, Proc. of Computers and Signal Processing, pp.26-28, 2001.
Yoo M. R., “A Scheduling Algorithm for Multimedia Process”, Ph.D. dissertation, University of YeoungNam, 2002 (in korean).
Yun, Y. S., “Study on Adaptive Hybrid Genetic Algorithm and Its Applications to Engineering Design Problems”, Ph.D. dissertation, University of Waseda, 2005.
Zhu K., Y. Zhuang and Y. Viniotis, “Achieving End-to-End Delay Bounds by EDF Scheduling without Traffic Shaping”, Proc. of 20th Annual Joint Conference on the IEEE Communications Societies, pp. 1493-1501, 2001.
Publication List
International Journals:
1. Yoo, Myungryun and M. Gen, “Scheduling Algorithm for Real-time Tasks in Heterogeneous Multiprocessors System using Multiobjective Hybrid Genetic Algorithm”, Computer and Operations Research. (In Press, Available online 2005. 12)
2. Yoo, Myungryun and M. Gen, “Multimedia Tasks Scheduling using Genetic Algorithm”, Asia Pacific Management Review. (採録決定：2005年9月29日, 8pp)
3. Yoo, Myungryun and M. Gen, “Bicriteria real-time tasks scheduling using genetic algorithm”, Journal of Complexity International, Vol. 11, pp. 233-232, 2005. 11.
4. Yoo, Myungryun and M. Gen, “Multimedia Task Scheduling using Proportion-based Genetic Algorithm”, 電気学会論文誌C部門, 平成18年3月.
Proceedings of International Conferences:
1. Yoo, Myungryun and Mitsuo Gen, “Time Constrained Task Scheduling by Genetic Algorithm on Heterogeneous Multiprocessors System”, Proc. of the 6th Asia Pacific Industrial Engineering and Management Systems, Manila in Philippines, Dec. 4, 2005.
2. Yoo, Myungryun and M. Gen, “Multiobjective Genetic Algorithm for Real-time Task Scheduling in Heterogeneous Multiprocessors System”, 6th International Symposium on Advanced Intelligent Systems, Yeosu in Korea, Sep. 28, 2005, pp. 838-843.
3. Yoo, Myungryun and Mitsuo Gen, “Genetic Algorithm for Joint Replenishment Problem with Multisupplier”, Proc. of Intelligent Manufacturing & Logistics Systems, Kitakyushu in Japan, Aug. 2, 2005.
4. Yoo, Myungryun and M. Gen, “Continuous Tasks Scheduling in Real-time Multiprocessor System using Genetic Algorithm”, Proc. of the 5th Asia Pacific Industrial Engineering and Management Systems, Gold Coast in Australia, Dec. 12, 2004, pp. 31.11.1-31.11.10.
5. Yoo, Myungryun and M. Gen, “Bicriteria Real-time Tasks Scheduling using Proportion-based Genetic Algorithm”, Proc. of the 8th Asia Pacific Symposium on Intelligent and Evolutionary Systems, Cairns in Australia, Dec. 6, 2004, pp. 213-222.
6. Yoo, Myungryun and M. Gen, “Periodic Task Scheduling in Soft Real-Time System using Multiobjective Genetic Algorithm”, Proc. of the 1st International Congress On Logistics and SCM Systems, Tokyo, Japan, Nov. 22, 2004, pp. 332-339
7. Yoo, Myungryun. and M. Gen, “Multimedia Tasks Scheduling on Multiprocessor System by Hybrid Genetic Algorithm”, Proc. of the 34th International Conference on Computers &