Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах

G. G. Tsegelyk, R. P. Krasniuk

Анотація


Розглянуто задачі оптимізації використання обчислювальних ресурсів розподіленої інформаційної системи. Виконано математичні постановки оптимізаційних задач та запропоновано ефективні обчислювальні алгоритми побудови розв’язку задач, які ґрунтуються на стратегії "жадібного" вибору та використанні генетичних алгоритмів. Для генетичних алгоритмів побудови розв’язків, близьких до оптимальних, у задачах бінарного та дійсного кодування запропоновано та досліджено обчислювальну ефективність уведення параметрів самонавчання алгоритму, що забезпечує коригування популяцій у напрямі найкращої пристосованості.

Ключові слова


математичне моделювання; оптимізація; розподілені інформаційні системи; жадібний алгоритм; генетичний алгоритм

Повний текст:

PDF

Посилання


Sabin G. Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment / G. Sabin, R. Kettimuthu // Job Scheduling Strategies for Parallel Processing (JSSPP’03): Proceedings of the 9th International Workshop (Seattle, WA, USA, June 24, 2003). — Springer, Lecture Notes in Computer Science, 2003. — Vol. 2862. — P. 87–104.

Arora M. A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments / M. Arora, S.K. Das, R. Biswas // International Conference on Parallel Processing Workshops (ICPPW’02): Proceedings of International Conference (Vancouver, British Columbia Canada, August 20–23, 2002). — IEEE Computer Society, 2002. — P. 499–505.

El-Rewini H. Task Scheduling in Parallel and Distributed Systems / H. El-Rewini, T. Lewis, H. Ali. — Prentice Hall, 1994. — 290 p.

Buyya R. The Grid Economy / R. Buyya, D. Abramson, S. Venugopal // Proceedings of the IEEE. — 2005. — Vol. 93, N 3. — P. 698–714.

Zhu Y. Incentive–based P2P Scheduling in Grid Computing / Y. Zhu, L. Xiao // Proceedings of the 3rd International Conference on Grid and Cooperative Computing (GCC2004), Wuhan, China, October 21–24, 2004. Springer, Lecture Notes in Computer Science, 2004. — P. 209–216.

Young L. Scheduling Architecture and Algorithms within the ICENI Grid Middleware / L. Young, S. McGough // Proceedings of UK e–Science All Hands Meeting. — Nottingham, UK: IOP Publishing Ltd., 2003. — P. 5–12.

You S.Y. Task Scheduling Algorithm in GRID Considering Heterogeneous Environment / S.Y. You , H.Y. Kim // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA ‘04), June 21–24, 2004. — Nevada, USA: CSREA Press, 2004. — P. 240–245.

Kim S. A Genetic Algorithm Based Approach for Scheduling Decomposable Data Grid Applications / S. Kim, J.B. Weissman // Proceedings of the 2004 International Conference on Parallel Processing (ICPP’04), Montreal, Quebec Canada, August 15–18, 2004). IEEE Computer Society, 2004. — P. 406–413.

Song S. Security–Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling / S. Song, Y. Kwok, K. Hwang // Proceedings of 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), Denver, Colorado USA, April 25–29, 2005. IEEE Computer Society, 2005. — P. 65–74.

Braun R. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems / R. Braun, H.Siegel // Journal of Parallel and Distributed Computing. — 2001. — Vol. 61, N 6. — P. 810–837.

Young L. Scheduling Architecture and Algorithms within the ICENI Grid Middleware / L. Young, S.McGough // Proceedings of UK e–Science All Hands Meeting, September 2003). — Nottingham, UK: IOP Publishing Ltd., 2003. — P. 5–12.

Abraham A. Nature’s Heuristics for Scheduling Jobs on Computational Grids / A. Abraham, R. Buyya, B. Nath // Proceedings of 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), Cochin, India, December 14–16, 2000. IEEE Computer Society, 2000. — P. 45–52.

Aho A.V. Postroenie i analiz vychislitel'nyh algoritmov / A.V. Aho, D.E. Honkroft, D.D. Ul'man. — M.: Mir, 1979. — 380 c.

Aho A.V. Struktury danyh i algoritmy / A.V. Aho, D.E. Honkroft, D.D. Ul'man. — M.: Izdatel'skij dom "Vil'jams", 2003. — 426 s.

Novikov F.A. Diskretnaja matematika dlja programmistov / F.A. Novikov. — Spb.: Piter, 2011. — 526 s.

Sigal I.H. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel'nye metody / I.H. Sigal, A.P. Ivanova. — M.: Fizmatlit, 2002. — 320 s.

Chambers D.L. Practical Handbook of Genetic algorithms, Applications / D.L. Chambers. — Chapman and Hall; CRC Press, 2001. — 650 p.

Halland J.N. Adaption in natural and artificial systems / J.N. Halland. — Ann Arbor, Michigan: University of Michigan Press, 1975. — 726 p.

Michalewicz Z. Genetic algorithms, numerical optimization and constraints / Z. Michalewicz // Proceedings of the 6th Intern. Coference on Genetic Algorithms, 1995. — P. 151–158.

Deb K. Realcoded genetic algorithms with simulated binary crossover: Studies on multimodal and multiobjective problems / K. Deb, A. Kumar // Complex Systems, 1995. — Vol. 9, N 6. — P. 431–454.


Пристатейна бібліографія ГОСТ


1. Sabin G. Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment / G. Sabin, R. Kettimuthu // Job Scheduling Strategies for Parallel Processing (JSSPP’03): Proceedings of the 9th International Workshop (Seattle, WA, USA, June 24, 2003). — Springer, Lecture Notes in Computer Science, 2003. — Vol. 2862. — P. 87–104.

2. Arora M. A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments / M. Arora, S.K. Das, R. Biswas // International Conference on Parallel Processing Workshops (ICPPW’02): Proceedings of International Conference (Vancouver, British Columbia Canada, August 20–23, 2002). — IEEE Computer Society, 2002. — P. 499–505.

3. El-Rewini H. Task Scheduling in Parallel and Distributed Systems / H. El-Rewini, T. Lewis, H. Ali. — Prentice Hall, 1994. — 290 p.

4. Buyya R. The Grid Economy / R. Buyya, D. Abramson, S. Venugopal // Proceedings of the IEEE. — 2005. — Vol. 93, N 3. — P. 698–714.

5. Zhu Y. Incentive–based P2P Scheduling in Grid Computing / Y. Zhu, L. Xiao // Proceedings of the 3rd International Conference on Grid and Cooperative Computing (GCC2004), Wuhan, China, October 21–24, 2004. Springer, Lecture Notes in Computer Science, 2004. — P. 209–216.

6. Young L. Scheduling Architecture and Algorithms within the ICENI Grid Middleware / L. Young, S. McGough // Proceedings of UK e–Science All Hands Meeting. — Nottingham, UK: IOP Publishing Ltd., 2003. — P. 5–12.

7. You S.Y. Task Scheduling Algorithm in GRID Considering Heterogeneous Environment / S.Y. You , H.Y. Kim // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA ‘04), June 21–24, 2004. — Nevada, USA: CSREA Press, 2004. — P. 240–245.

8. Kim S. A Genetic Algorithm Based Approach for Scheduling Decomposable Data Grid Applications / S. Kim, J.B. Weissman // Proceedings of the 2004 International Conference on Parallel Processing (ICPP’04), Montreal, Quebec Canada, August 15–18, 2004). IEEE Computer Society, 2004. — P. 406–413.

9. Song S. Security–Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling / S. Song, Y. Kwok, K. Hwang // Proceedings of 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), Denver, Colorado USA, April 25–29, 2005. IEEE Computer Society, 2005. — P. 65–74.

10. Braun R. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems / R. Braun, H.Siegel // Journal of Parallel and Distributed Computing. — 2001. — Vol. 61, N 6. — P. 810–837.

11. Young L. Scheduling Architecture and Algorithms within the ICENI Grid Middleware / L. Young, S.McGough // Proceedings of UK e–Science All Hands Meeting, September 2003). — Nottingham, UK: IOP Publishing Ltd., 2003. — P. 5–12.

12. Abraham A. Nature’s Heuristics for Scheduling Jobs on Computational Grids / A. Abraham, R. Buyya, B. Nath // Proceedings of 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), Cochin, India, December 14–16, 2000. IEEE Computer Society, 2000. — P. 45–52.

13. Ахо А.В. Построение и анализ вычислительных алгоритмов / А.В. Ахо, Д.Э. Хонкрофт, Д.Д. Ульман. — М.: Мир, 1979. — 380 c.

14. Ахо А.В. Структуры даных и алгоритмы / А.В. Ахо, Д.Э. Хонкрофт, Д.Д. Ульман. — М.: Издательский дом "Вильямс", 2003. — 426 с.

15. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. — Спб.: Питер, 2011. — 526 с.

16. Сигал И.Х. Введение в прикладное дискретное программирование: модели и вычислительные методы / И.Х. Сигал, А.П. Иванова. — М.: Физматлит, 2002. — 320 с.

17. Chambers D.L. Practical Handbook of Genetic algorithms, Applications / D.L. Chambers. — Chapman and Hall; CRC Press, 2001. — 650 p.

18. Halland J.N. Adaption in natural and artificial systems / J.N. Halland. — Ann Arbor, Michigan: University of Michigan Press, 1975. — 726 p.

19. Michalewicz Z. Genetic algorithms, numerical optimization and constraints / Z. Michalewicz // Proceedings of the 6th Intern. Coference on Genetic Algorithms, 1995. — P. 151–158.

20. Deb K. Realcoded genetic algorithms with simulated binary crossover: Studies on multimodal and multiobjective problems / K. Deb, A. Kumar // Complex Systems, 1995. — Vol. 9, N 6. — P. 431–454.





DOI: https://doi.org/10.20535/SRIT.2308-8893.2018.2.07

Посилання

  • Поки немає зовнішніх посилань.