Использование генетических алгоритмов для построения эффективных комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования
Аннотация
В статье решается задача формирования эффективных комплексных расписаний обработки пакетов данных при задании ограничений на интервалы времени функционирования конвейерной системы. Задача формирования комплексных расписаний разделена на три подзадачи, каждая из которых решается на определенном уровне иерархии. На первом уровне определяются составы пакетов данных, на втором уровне определяются составы групп пакетов данных, которые обрабатывается в течение заданных интервалов времени функционирования системы, на третьем уровне определяется расписание обработки пакетов данных, входящих в каждую группу. Для решения задачи построения комплексных расписаний в составе такой иерархической системы применен аппарат теории иерархических игр. Рассматривается модель иерархической игры, позволяющая определять локально оптимальные решения на каждом уровне иерархии. Выполнено обоснование применения генетических алгоритмов для определения составов групп пакетов данных, которые являются эффективными с точки зрения минимизации простоев сегментов конвейера в течение заданных временных интервалов. Сформулирован способ кодирования решений по составам групп пакетов данных. Определены способы реализации генетических операторов, которые позволяют осуществить поиск локально оптимальных решений по составам групп пакетов на основе начального решения. Выполнена программная реализация процедур оптимизации составов пакетов данных, составов групп пакетов данных и расписаний обработки пакетов, входящих в группы. Исследования предложенного метода оптимизации, использующего генетические алгоритмы, показало, что его применение для формирования составов групп пакетов данных позволяет до 45 % повысить эффективность использования ресурса времени сегментов конвейера по сравнению с начальным решением.
Скачивания
Литература
2. Hermeyer Yu. B. Games with non-contradictory interests. M. Nauka publishing House, 1976. 327 p.
3. Mendez C. A. et al. State-of-the-art review of optimization methods for short-term scheduling of batch processes. Computers and Chemical Engineering. 2006. V. 30. pp. 913–946. DOI
4. Kovalev М. М. Models and methods of calendar planning: a course of lectures. Minsk. Publishing house of BSU. 2004. 63 p.
5. Tan Y., Huangi W., Sun Y., Yue Y. Comparative Study of Different Approaches to Solve Batch Process Sheduling and Optimisation Problems. Proceedings of the 18th International Conference on Automation & Computing. Loughborough University. Leicestershire. UK. 2012. P. 424–444.
6. Adonyi R., Romero J., Puigjaner L., Friedler F. Incorporating heat integration in batch process scheduling. Applied Thermal Engineering. 2003. V. 23. P. 1743–1762. DOI.
7. Kreipl S. Planning and Scheduling in supply chains: An Overview of Issues in Practice. Production and Operations Management. 2004. V. 17. No. 1. P. 77 92.
8. Steiner G., Zhang R. Minimizing the weighted number of late jobs with Batch setup times and delivery costs on a single machine. Multiprocessor Scheduling, Theory and Applications. Edited by Levner E. Itech Education and Published. 2007. P. 85–98. DOI: 10.5772/5216.
9. Koehler F., Khuller S. Optimal Batch Schedules for Parrallel Machines. Algorithms and Data Structures: 13th International Symposium. Berlin. Springer. 2013. P. 475–486. DOI.
10. Yugma G. C., Dauzere-Peres S., Artigues C., Sibille O. Batching and Scheduling Algoritm for the diffusion Area in Semiconductor Manufacturing. International Journal of Production Research. 2012. V. 50. No. 8. P. 2118–2132. DOI.
11. Chandra P. Managing Batch Processors to reduce lead time in a semiconductor packaging line. International Journal of Production Research. 1997. V. 35(3). P. 611–633.
12. Surjandari I., Rachman A., Dhini A. The Batch Scheduling Model for Dynamic multi-item, Multilevel Production in an assembly Job-Shop with Parrallel Machines. International Journal of Technology. 2015. V. 6. No 1. P. 84–96. DOI.
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
