QUEUE SEPARATION AS A METHOD OF OPTIMIZATION OF ANT COLONY ALGORITHM FOR MULTI-MACHINE ASSEMBLY JOB SHOP SCHEDULING

Cover Page

Cite item

Full Text

Abstract

Background. Ant Colony Algorithm is an effective method of solving assembly job shop problem. But its computational complexity makes it impractical for real-life tasks of hundreds and thousands of operations. Materials and methods. This article describes a method to significantly increase computational effectiveness of the algorithm for multimachine problem – the most important case for practical use. The proposed method uses separation of the task queue into a number of subqueues for each type of the processing machines and applying Ant Colony Optimization to each of them separately. Results. It is shown that for large-scale problems (thousands of operations) runtime decreases 10 times or more without losing the quality of solutions. Conclusions. This modification significantly increases ACO algorithm speed when applied to practical tasks of machine manufacturing plants.

About the authors

Mikhail A. Ivanov

NeftemashSistema

Author for correspondence.
Email: mikeaivanov@gmail.com

Lead programmer

(2A Gvardeiskaya street, Saratov, Russia)

References

  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):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):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):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):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):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):504–518 .
  7. Reeja M.K., Rajendran Ch. Dispatching rules for scheduling in assembly jobshops. International Journal of Production Research. 2000;(38):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):127–152.
  10. Dorigo M., Maniezzo V., Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Systems Man Cybernet. 1996;(B26):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;3(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: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;14. 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;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):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. Ivanov M.A. Structural heuristics for scheduling a one-time production workshop with assembly operations using the ant colony method. Problemy upravleniya v sotsialʹnoekonomicheskikh i tekhnicheskikh sistemakh: materialy XX Mezhdunar. nauch.-prakt. konf = Management problems in socio-economic and technical systems: materials of the XX International Scientific and Practical Conference. Saratov: Nauka, 2024:702. (In Russ)

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a 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») на элемент с текстом «Принять и продолжить».