РАЗДЕЛЕНИЕ ОЧЕРЕДЕЙ КАК МЕТОД ОПТИМИЗАЦИИ АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ ПРИ ПОСТРОЕНИИ РАСПИСАНИЯ МНОГОСТАНОЧНОГО ЦЕХА РАЗОВОГО ПРОИЗВОДСТВА СО СБОРОЧНЫМИ ОПЕРАЦИЯМИ

Обложка

Цитировать

Полный текст

Аннотация

Актуальность и цели. Рассматривается применение алгоритма муравьиной колонии для решения задачи составления расписания для цеха единичного производства со сборочными операциями (assembly job shop). Он дает хорошие результаты, однако из-за высокой вычислительной сложности слабо подходит для решения реальных практических задач с размерностью в сотни и тысячи операций. Материалы и методы. Предлагается метод существенного повышения вычислительной эффективности данного алгоритма применительно к многостаночной задаче – наиболее часто встречающемуся на практике случаю. Он состоит в разделении единой очереди работ на отдельные очереди по типам используемых станков и применении алгоритма муравьиной колонии к каждой из них по отдельности. Результаты. Показывается, что на крупных (тысячи операций) задачах временные затраты сокращаются в 10 и более раз без потери качества находимых решений. Выводы. Предложенная модификация позволяет существенно улучшить производительность алгоритма муравьиной колонии при практическом применении для решения производственных задач машиностроительных предприятий.

Об авторах

Михаил Андреевич Иванов

НефтемашСистема

Автор, ответственный за переписку.
Email: mikeaivanov@gmail.com

ведущий программист

(Россия, г. Саратов, ул. Гвардейская, 2А)

Список литературы

  1. Fry T. D., Olife M. D., Minor E. D., Keong Leong G. The effect of product structure and sequencing rule on assembly shop performance // International Journal of Production Research. 1989. № 27 (4). P. 671–686.
  2. Philipoom P. R., Russel R. S. L., Fry T. D. A preliminary investigation of multi-attribute based sequencing rules for assembly shops // International Journal of Production Research. 1991. № 29 (4). P. 739–753.
  3. Doctor S. R., Cavalier T. M., Egbelu P. J. Scheduling for machining and assembly in a job-shop environment // International Journal of Production Research. 1993. № 31 (6). P. 1275–1297.
  4. McCoy D. H. C., Egbelu P. J. Minimizing production flow time in a process and assembly job shop // International Journal of Production Research. 1998. № 36 (8). P. 2315– 2332.
  5. Park M. W., Kim Y. D. A heuristic algorithm for a production planning problem in an assembly system // Journal of Operational Research Society. 1999. № 50. P. 138–147.
  6. Moon-Won P., Kim Y. D. A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints // European Journal of Operational Research. 2000. № 123 (3). P. 504–518 .
  7. Reeja M. K., Rajendran Ch. Dispatching rules for scheduling in assembly jobshops // International Journal of Production Research. 2000. № 38 (9). P. 2051–2066.
  8. Cao W., Xie Z., Yang J. [et al.]. A Reverse Order Hierarchical Integrated Scheduling Algorithm Considering Dynamic Time Urgency Degree of the Process Sequences // Electronics. 2022. № 11. doi: 10.3390/electronics11121868
  9. Omkumar M., Shahabudeen P. Ant Colony Optimisation for multi-level assembly job shop scheduling // International Journal of Manufacturing Research. 2009. № 1. P. 127– 152.
  10. Dorigo M., Maniezzo V., Colorni A. Ant system: Optimization by a colony of cooperating agents // IEEE Trans. Systems Man Cybernet. 1996. Part B26 (1). P. 29–41.
  11. Sasikala B., Eswaramurthy V. P. Ant Colony Optimization for Job Shop Scheduling Problem Using Priority Rules // International Journal of Engineering and Techniques. 2017. Vol. 3, is. 6.
  12. Abidia M. H., Al-Harkanb I., El-Tamimib A. M. [et al.]. Ant Colony Optimization for Job Shop Scheduling to Minimize the Total Weighted Tardiness // Proceedings of the 2014 Industrial and Systems Engineering Research Conference. 2013.
  13. Huang M., Guo D., Guo F. An Improved Ant Colony Algorithm for Multi-objective Flexible Job-shop Scheduling Problem // 2022 IEEE 10th International Conference on Computer Science and Network Technology (ICCSNT). 2022. P. 1–3. doi: 10.1109/ICCSNT56096.2022.9972994
  14. Chen F., Xie W., Ma J. Textile flexible job-shop scheduling using PACO algorithm // Applied Sciences. 2024. Vol. 14 (9). doi: 10.3390/app14104082
  15. Rahman M. L., Sazol A. Application of an improved ant colony optimization algorithm of hybrid strategies using scheduling for patient management in hospitals // Heliyon. 2024. Vol. 10 (21). doi: 10.1016/j.heliyon.2024.e40134
  16. Matrenin P. V. Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics // Algorithms. 2023. № 16. P. 15. doi: 10.3390/a16010015
  17. Tang Q., Wang H. Data-driven automated job shop scheduling optimization considering AGV obstacle avoidance // Sci Rep. 2025. № 15. doi: 10.1038/s41598-024-82870-1
  18. Merkle D., Middendorf M. An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problems // Real-World Applications of Evolutionary Computing. EvoWorkshops 2000. Lecture Notes in Computer Science. № 1803. Springer, Berlin, Heidelberg. doi: 10.1007/3-540-45561-2_28
  19. Иванов М. А. Структурная эвристика для построения расписания цеха разового производства со сборочными операциями методом муравьиной колонии // Проблемы управления в социально-экономических и технических системах : матери- алы XX Междунар. науч.-практ. конф. Саратов : Наука, 2024. 702 с

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».