Mathematical Modeling of the Processes of Executing Packages of Tasks in Conveyor Systems with Intermediate Buffers of Limited Size

Cover Page

Cite item

Full Text

Abstract

Modern methods of process planning in conveyor systems with buffers of a certain size between processing devices allow optimizing schedules for single tasks or fixed task packages with a limited number of them and a limited number of devices. The use of mathematical models of the processes of performing single tasks (task packages) used by these methods in optimizing the composition of packages and schedules for their execution in systems with an arbitrary number of packages and devices is impossible. At the same time, mathematical models of the processes of executing task packages in conveyor systems in the presence of buffers of limited sizes between devices are the basis for the development of methods for optimizing their (package) compositions and schedules for the implementation of actions with them on the devices of conveyor systems. In this regard, the article develops mathematical models of multi-stage processes of performing an arbitrary number of task packages in conveyor systems in the presence of intermediate buffers of limited sizes for two and three devices, as well as for an arbitrary number of devices. The use of these models makes it possible to determine the time points of the start of the execution of task packages on the devices of conveyor systems, taking into account the limited size of intermediate buffers, as well as the duration of time intervals for the use of these resources and the efficiency of their use over time. An algorithm has also been developed for mathematical modeling of the processes of executing task packages in conveyor systems in the presence of intermediate buffers of limited size, which calculates the time characteristics of these processes based on a given order of implementation of actions with task packages on the devices of conveyor systems. An application has been developed that implements synthesized mathematical models of the processes of executing task packages in conveyor systems with intermediate buffers of limited sizes and an appropriate method for modeling these processes. Versatile testing of the developed application has shown that the obtained mathematical models and the modeling method adequately describe the course of multi-stage processes of task packages in pipeline systems, set using different values of their (processes) parameters.

About the authors

K. V Krotov

Sevastopol State University

Email: krotov_k1@mail.ru
Universitetskaya St. 33

References

  1. Кротов К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах // Вычислительные технологии. 2018. Т. 23. № 3. С. 58–76.
  2. Кротов К.В. Обоснование методов построения комплексных расписаний обработки партий данных при условии оперативного формировании комплектов из результатов // Вестник Воронежского Государственного Университета. Серия: Системный анализ и информационные технологии. 2018. № 4. C. 58–72.
  3. Кротов К.В., Скатков А.В. Построение комплексных расписаний выполнения пакетов заданий при формировании комплектов в заданные директивные сроки // Информатика и автоматизация. 2021. Т. 20. № 3. C. 654–689.
  4. Кротов К.В. Построение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования // Труды учебных заведений связи. 2020. Т. 6. № 3. С. 75–89.
  5. Papadimitriou C.H., Kanellakis P.C. Flowshop scheduling with limited temporary storage // Jounal of Association for Computing Machinery. 1980. vol. 27. no. 3. pp. 533–549.
  6. Leisten R. Flowshop sequencing problems with limited buffer storage // International Journal of Production Research. 1990. vol. 28. no. 11. pp. 2085–2100. doi: 10.1080/00207549008942855.
  7. Crowder B. Minimizing the makespan in a flexible flowshop with sequence dependent setup times, uniform machines and limited buffers // Graduate Theses, Dissertations and Problem Reports. Morgantown: West Virginia University, 2006. 145 p.
  8. Han Zh., Zhang Q., Shi H., Qi Yu., Sun L. Research on limited buffer scheduling problems in flexible flow shops with setup times // International Journal of Modelling. Identification and Control. 2019. vol. 32. no. 2. pp. 93–104.
  9. Eddaly M., Jarboui B., Siarry P., Rebaï A. An Estimation of Distribution Algorithm for Flowshop Scheduling with Limited Buffers // Natural Intelligence for Scheduling, Planning and Packing Problems. Part of the Studies in Computational Intelligence book series. 2009. vol. 250. pp. 89–110.
  10. Frasch J.V., Krumke S.O., Westphal S. MIP Formulations for Flowshop Scheduling with Limited Buffers // Proceedings of the First International ICST Conference «Theory and Practice of Algorithms in (Computer) Systems» (TAPAS). 2011. pp. 127–138.
  11. Fu Q., Sivakumar A.I., Li K. Optimisation of flow-shop scheduling with batch processor and limited buffer // International Journal of Production Research. 2012. vol. 50. no. 8. pp. 2267–2285.
  12. Кононова П.А. Алгоритмы построения расписаний для цеховых задач потокового типа с цифровым буфером // Дисс. канд. физ.-мат. наук. Новосибирск: Институт вычислительной математики и математической геофизики, 2012. 104 с.
  13. Cakici M.K. Parallel flow shop scheduling with common workstations // MS thesis. Middle East Technical University. 2019. 138 p.
  14. Кононова П.А., Кочетов Ю.А. Алгоритм локального поиска для построения расписаний работы одного станка с переналадкой оборудования и складом // Дискретный анализ и исследование операций. 2019. Т. 26. № 2. С. 60–78. doi: 10.33048/daio.2019.26.634.
  15. Lin C.C., Liu W.-Y., Chen Y.-H. Considering Stockers in Reentrant Hybrid Flow Shop Scheduling with Limited Buffer Capacity // Computers and Industrial Engineering. 2020. vol. 139. no. 106154. doi: 10.1016/j.cie.2019.106154.
  16. Takano M.I., Nagano M.S. Solving the permutation flow shop problem with blocking and setup time constraints // International Journal of Industrial Engineering Computations. 2020. no. 11. pp. 469–480. doi: 10.5267/j.ijiec.2019.11.002.
  17. Zhang C., Tan J., Peng K., Gao L., Shen W., Lian K. A discrete whale swarm algorithm for hybrid flow-shop scheduling problem with limited buffers // Robotics and Computer–Integrated Manufacturing. 2021. no. 68. doi: 10.1016/j.rcim.2020.102081.
  18. Gao Z., Feng Ya., Xing K. A hybrid estimation-of-distribution algorithm for scheduling flexible job shop with limited buffers based on Petri Nets // IEEE Access. 2020. vol. 8. pp. 165396–165408. doi: 10.1109/ACCESS.2020.3022655.
  19. Kazemi Esfeh M., Shojaie A.A., Javanshir H., Khalili-Damghani K. Flexible flow shop scheduling problem with reliable transporters and intermediate limited buffers via considering learning effects and budget constraint // Hindawi journal. Complexity. 2022. vol. 2022. no. 1253336. doi: 10.1155/2022/1253336.
  20. Jiang S.-L., Zhang L. Energy-oriented scheduling for hybrid flow shop with limited buffers through efficient multi-objective optimization // IEEE Access. 2019. vol. 7. pp. 34477–34487. doi: 10.1109/ACCESS.2019.2904848.
  21. Liang X., Wang P., Huang M. Flow shop scheduling problem with limited buffer based on hybrid shuffled frog leaping algorithm // 7th International Conference on Computer Science and Network Technology (ICCSNT). 2019. pp. 87–93. doi: 10.1109/iccsnt47585.2019.8962427.
  22. Zhang G., Wang L., Xing K. Dual-space co-evolutionary memetic algorithm for scheduling hybrid differentiation flow shop with limited buffer constraints // IEEE Transactions on systems, man and cybernetics systems. 2021. vol. 52. no. 11. pp. 6822–6836. doi: 10.1109/TSMC.2021.3102658.
  23. Benda F., Braune R., Doerner K.F., Hartl R.F. A machine learning approach for flow shop scheduling problems with alternative resources, sequence-dependent setup times and blocking // OR Spectrum. 2019. vol. 41. pp. 871–893. doi: 10.1007/s00291-019-00567-8.
  24. Han Zh., Han Ch., Lin Sh., Dong X., Shi H. Flexible flow shop scheduling method with public Buffer // Processes. 2019. vol. 7(10). no. 681. doi: 10.3390/pr7100681.
  25. Rooeinfar R., Raissi S., Ghezavati V.R. Stochastic flexible flow shop scheduling problem with limited buffers and fixed interval preventive maintenance: a hybrid approach of simulation and metaheuristic algorithms // Simulation. 2019. vol. 95(6). pp. 509–528.
  26. Kazemi Esfeh M., Shojaei A.A., Javanshir H., Khalili Damghani K. Solving a bi-objective flexible flow shop problem with transporter preventive maintenance planning and limited buffers by NSGA-II and MOPSO // International Journal Nonlinear Analysis and Applications. 2022. vol. 13. no. 1. pp. 217–246.
  27. Agnetis A., Pacciarelli D., Rossi F. Batch scheduling in a two-machine flow shop with limited buffer // Discrete Applied Mathematics. 1997. vol. 72. no. 3. pp. 243–260.
  28. Pranzo M. Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times // European Journal of Operational Research. 2004. vol. 153. no. 3. pp. 581–592.
  29. Dai J. Batch Scheduling of Two-machine Limited-buffer Flow Shop with Setup and Removal Times // Georgia Institute of Technology, 2003. 108 p.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

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

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») на элемент с текстом «Принять и продолжить».