Построение расписаний выполнения пакетов заданий в многостадийных системах при формировании комплектов результатов и ограничениях

Задача планирования выполнения пакетов заданий в многостадийных системах при наличии ограничения на длительность интервалов времени ее функционирования является комплексной. Ее решение предполагает (с учетом требования формирования комплектов из результатов) определение составов пакетов, составов групп пакетов, выполняемых в течение временных интервалов заданной длительности, расписаний выполнения пакетов на приборах многостадийной системы. Для определения комплексных решений применен аппарат теории иерархических игр. Реализуется построение модели иерархической игры для принятия решений по составам пакетов, групп пакетов и расписаниям выполнения пакетов. В модели учтено требование формирования комплектов из результатов выполнения пакетов заданий. Задача определения составов групп пакетов является NP-трудной, поэтому для ее решения требуется применение приближенных методов оптимизации. Формулируются метод построения начального решения по составам групп пакетов и метод распределения результатов выполнения пакетов заданий по комплектам. Сформулирован способ построения новых решений по составам групп пакетов заданий. Введены условия, позволяющие определять исключаемые из групп пакеты на основе количества результатов выполнения заданий каждого типа, не включаемых в комплекты. Предложен метод локальной оптимизации решений по составам групп пакетов.

Ключевые слова

пакеты заданий; многостадийная система; комплекты результатов; ограничение на длительность интервалов времени функционирования системы.

Литература

1. Кротов, К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах / К.В. Кротов // Вычислительные технологии. - 2018. - № 3. - С. 58-76.
2. Кротов, К.В. Обоснование методов построения комплексных расписаний обработки партий данных при условии оперативного формировании комплектов из результатов / К.В. Кротов // Вестник Воронежского государственного университета. Системный анализ и информационные технологии. - 2018. - № 4. - С. 58-72.
3. Кротов, К.В. Построение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования / К.В. Кротов // Труды учебных заведений связи. - 2020. - Т. 6, № 3. - С. 75-90.
4. Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев, Ю.Н. Сотсков, В.А. Струсевич. - М.: Наука, 1989.
5. Лазарев, А.А. Теория расписаний. Задачи управления транспортными системами / А.А. Лазарев, Е.Г. Мусатова, А.Г. Кварцхелия, Е.Р. Гафаров. - М.: МГУ, 2012.
6. Лазарев, А.А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации: дисс. ... доктора физ.-мат. наук / А.А. Лазарев. - Москва, 2007.
7. Кобак, В.Г. Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки: дисс. ... доктора техн. наук / В.Г. Кобак. - Ростов-на-Дону, 2008.
8. Нейдорф, Р.А. Исследование селективно-перестановочного метода решения однородной распределительной задачи с использованием мультиперестановок / Р.А. Нейдорф, А.А. Жикулин // Системный анализ, управление и обработка информации. - 2012. - С. 58-68.
9. Ogun Basar. Mathematical Models for a Batch Scheduling Problem to Minimizе Earliness and Tardiness / Basar Ogun, Cigdem Alabas-Uslu // Journal of Industrial Engineering and Management. - 2018. - № 11 (3). - P. 390-405.
10. Li XiaoLin. Scheduling Batch Processing Machine Using Max-Min Ant System Algorithm Improved by a Local Search Method / XiaoLin Li, Yu Wang // Mathematical Problems in Engineering. - 2018. - V. 2018. - Article ID: 3124182.
11. Cheng Ba-Yi. Improved Ant Colony Optimization Method for Single Batch-Processing Machine with Non-Identical Job Sizes / Ba-Yi Cheng, Hua-Ping Chen, Shuan-Shi Wang // Journal of System Simulation. - 2009. - V. 21, № 9. - P. 2687-2695.
12. Koehler, F. Optimal Batch Schedules for Parrallel Machines / F. Koehler, S. Khuller // Algorithms and Data Structures: 13th International Symposium. - Berlin: Springer, 2013. - P. 475-486.
13. Surjandari, I. The Batch Scheduling Model for Dynamic Multi-Item, Multi-Level Production in an Assembly Job Shop with Parallel Machines / I. Surjandari, A. Rachman, A. Purdianta, A. Dhini // International Journal of Technology. - 2015. - № 1. - P. 84-96.
14. Monch, L. Heuristic Scheduling of Jobs on Parallel Batch Machines with Incompatible Job Families Andunequal Ready Times / L. Monch, H. Balasubramanian, J. Fowler, M. Pfund // Computers & Operations Research. - 2005. - № 32. - P. 2731-2750.
15. Dang, Th. Using Heuristic Search for Solving Single Machine Batch Processing Problems / Th. Dang, B. Frankovic, I. Budinska // Computing and Informatics. - 2006. - № 25. - P. 405-420.
16. Kohn, R. Study on Multi-Objective Optimization for Parallel Batch Machine Scheduling Using Variable Neighbourhood Search / R. Kohn, O. Rose, Ch. Laroque // Proceedings of the 2013 Winter Simulation Conference. - 2013. - P. 3654-3670.
17. Li Shisheng. Single-Machine Batch Scheduling with Job Processing Time Compatibility / Shisheng Li, T.C.E. Cheng, C.T. Ng, Jinjiang Yuan // Theoretical Computer Science. - 2015. - № 583. - P. 57-66.
18. Jin Miaomiao. Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection / Miaomiao Jin, Xiaoxia Liu, Wenchang Luo // Mathematics. - 2020. - № 8. - Article ID: 258.
19. Кротов, К.В. Использование аппарата генетических алгоритмов при формировании решений по составам партий данных в двухуровневой задаче построения комплексных расписаний их обработки / К.В. Кротов // Автоматизированные технологии и производства. Международный научно-технический журнал. - 2017. - № 2 (16). - С. 23-34.