Comparison of genetic representation schemes for scheduling soft real-time parallel applications
Pages 523 - 530
Abstract
This paper presents a hybrid technique that combines List Scheduling (LS) with Genetic Algorithms (GA) for constructing non-preemptive schedules for soft real-time parallel applications represented as directed acyclic graphs (DAGs). The execution time requirements of the applications' tasks are assumed to be stochastic and are represented as probability distribution functions. The performance in terms of schedule lengths for three different genetic representation schemes are evaluated and compared for a number of different DAGs.The approaches presented here produce shorter schedules than HLFET, a popular LS approach for all of the sample problems. Of the three genetic representation schemes investigated, PosCT, the technique that allows the GA to learn which tasks to delay in order to allow other tasks to complete produced the shortest schedules for a majority of the sample DAGs.
References
[1]
Abeni, L., and Buttazzo, G. QoS Guarantee Using Probabilistic Deadlines. In Proceedings of the IEEE Euromicro Conference on Real-Time Systems. 1999, 242--249.
[2]
Adam, T. L., Chandy, K. M., and Dickson, J. R. A Comparison of List Schedules for Parallel Processing Systems. Communications of the ACM, Vol. 17. 1974, 685--690.
[3]
Ahmad, I., Kwok, Y., and Wu, M. Analysis, Evaluation, and Comparison of Algorithms for Scheduling Task Graphs on Parallel Processors. In Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks. 1996, 207--213.
[4]
Atlas, A., and Bestavros, A. Statistical Rate Monotonic Scheduling. In Proceedings of the 19th IEEE Real-Time Systems Symposium. 1998, 123--132.
[5]
Coffman, E. G. Computer and Job-Shop Scheduling Theory, John Wiley and Sons, New York, 1976.
[6]
Dandass, Y. S. A Genetic Algorithm for Scheduling Acyclic Digraph in the presence of Communication Contention. In Proceedings of the 17th Annual International Symposium on High Performance Computing Systems and Applications. 2003, 223--230.
[7]
Dandass, Y. S. Genetic List Scheduling for Soft Real-Time Parallel Applications. IEEE Congress on Evolutionary Computation. June 2004, 1164--1171.
[8]
Davis, L. Applying Adaptive Algorithms to Epistatic Domains. In Proceedings of the 9th International Joint Conference on Artificial Intelligence. 1985, 162--164.
[9]
Dogan, A., and Ozguner, F. Stochastic Scheduling of a Meta-task in Heterogeneous Distributed Computing. IEEE International Conference on Parallel Processing Workshops. 2001, 369-374.
[10]
Gardner, M. K. Probabilistic Analysis and Scheduling of Critical Soft Real-Time Systems, Ph.D. Thesis, Department of Computer Science, University of Illinois Urbana-Champaign, 1999.
[11]
Gerasoulis, A., and Yang, T. A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessors. Journal of Parallel and Distributed Computing, Vol. 16, No. 4. 1992, 276--291.
[12]
Gordon, V. S., and Whitley, D. Serial and Parallel Genetic Algorithms as Function Optimizers. Technical Report CS-93-114, Colorado State University, 1993.
[13]
Grajcar, M. Strengths and Weaknesses of Genetic List Scheduling for Heterogeneous Systems. In Proceedings of the 2nd International Conference on Application of Concurrency to System Design, IACSD, 2001.
[14]
Hwang, J. J., Chow, Y. C., Anger, F. D., and Lee, C. Y. Scheduling Precedence Graphs in Systems with Interprocessor Communication Times. SIAM Journal of Computing, Vol. 18, No. 2. 1989, 244--257.
[15]
Kwok Y., and Ahmad, I. Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 5. 1996, 506--521.
[16]
Kwok, Y., and Ahmad, I. Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors using a Parallel Genetic Algorithm. Journal of Parallel and Distributed Computing, Vol. 47, No. 1. 1997, 58--77.
[17]
Liu, J. W. S. Real-Time Systems, Prentice Hall, Upper Saddle River, New Jersey, 2000.
[18]
Tia, T. S., Deng, Z., Shankar, M., Storch, M., Sun, J., Wu, L. C., and Liu, J. W. S. Probabilistic Performance Guarantee for Real-Time Tasks with Varying Computation Times. In Proceedings of the IEEE Real-Time Technology and Applications Symposium. May 1995, 164--173.
[19]
Wu, M-Y., and Gajski, D. D. Hypertool: A Programming Aid for Message Passing Systems. IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 3. 1990, 330--343.
Index Terms
- Comparison of genetic representation schemes for scheduling soft real-time parallel applications
Recommendations
Simulated annealing and genetic algorithm for unrelated parallel machine scheduling considering set-up times
This paper presents the comparative use of Simulated Annealing (SA) and Genetic Algorithm (GA) in a scheduling problem of unrelated parallel machines with set-up times. The problem accounts for allotting batched work parts to the unrelated parallel ...
Parallel robot scheduling to minimize mean tardiness with precedence constraints using a genetic algorithm
Identical parallel robot scheduling problem for minimizing mean tardiness with precedence constraints is a very important scheduling problem. But, the solution of this problem becomes much difficult when there are a number of robots, jobs and precedence ...
A new genetic algorithm for lot-streaming flow shop scheduling with limited capacity buffers
Lot-streaming is the process of splitting a job (lot) into a number of smaller sublots to allow the overlapping of operations between successive machines in a multi-stage production system. The use of sublots usually results in substantially shorter job ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2006 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2006
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 11Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in