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

Обложка

Цитировать

Полный текст

Аннотация

Актуальность и цели. Рассматривается применение алгоритма муравьиной колонии для решения задачи составления расписания для цеха единичного производства со сборочными операциями (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.

Согласие на обработку персональных данных

 

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