Two-Level Optimization of Task Distribution into Batches and Scheduling Their Execution in Pipeline Systems with Limited Buffers

Cover Page

Cite item

Full Text

Abstract

Currently, existing mathematical models and algorithms provide optimization of schedules for the execution of single tasks or fixed task packages on devices of conveyor systems containing buffers of limited sizes. These models and algorithms do not allow searching for optimal solutions for grouping the same type of tasks into packages and by sequence of packages to implement operations with them on devices of conveyor systems. Increasing the efficiency of using the resources of conveyor systems is achieved by optimizing solutions for grouping the same type of tasks into packages and by sequences of packages for performing operations with them. The solution to this problem is carried out in the work by using an approach that implements two-level optimization, which allows you to form a hierarchy of subtasks for finding effective solutions. The involvement of the mentioned approach involves the development of mathematical models of hierarchical games that allow identifying effective solutions of the type under consideration. Two mathematical models of hierarchical games have been constructed, the use of which makes it possible to optimize package compositions at the upper level by the leading player and optimize package execution schedules in pipeline systems at the lower level by the slave player. The method of determining the optimal solutions for each of the players provides for the order of moves set in the game and the exchange of solutions between them during the game. The first mathematical model of the hierarchical game implements the definition of effective solutions when taking into account the downtime of processing devices in the process of implementing operations with packages. The second mathematical model of the game implements the definition of effective solutions, taking into account the total waiting time for buffers to place tasks in them, with which operations on previous devices were completed. To do this, expressions have been formed that allow you to determine buffer downtime while waiting for tasks from packages to be ready for placement based on the time characteristics of the processes of performing operations with them on the devices of the systems under consideration. The algorithm for determining optimal solutions according to the order of operations with packages at the lower level in each of the hierarchical games is based on a developed mathematical model of the processes of implementing actions with packages in these systems and the corresponding modeling algorithm. The implementation of the optimization approach under consideration allowed us to obtain results that showed that the use of buffers can significantly increase the efficiency of the processes of performing operations with packets on the devices of the systems under consideration; increasing the size of intermediate buffers allows us to increase the efficiency of these processes to a greater extent with significant heterogeneities in the values of time parameters characterizing them; using the first model of a hierarchical game allows us to achieve a greater increase in the efficiency of processes in comparison with the second model.

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. Кротов К.В., Скатков А.В. Построение комплексных расписаний выполнения пакетов заданий при формировании комплектов в заданные директивные сроки // Информатика и автоматизация. 2021. Т. 20(3). С. 654–689. doi: 10.15622/ia.2021.3.6.
  3. Кротов К.В., Скатков А.В. Оптимизация планирования выполнения пакетов заданий в многостадийных системах при ограничениях и формировании комплектов // Компьютерные исследования и моделирование. 2021. Т. 13. № 5. С. 917–946.
  4. Кротов К.В. Математическое моделирование процессов выполнения пакетов заданий в конвейерных системах с промежуточными буферами ограниченных размеров // Информатика и автоматизация. 2023. Т. 22(6). С. 1415–1450.
  5. Papadimitriou Ch.H., Kanellakis P.C. Flowshop scheduling with limited temporary storage // Journal 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.
  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. doi: 10.33915/etd.4220.
  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. Studies in Computational Intelligence. 2009. (SCI). vol. 250. pp. 89–110.
  10. Frasch J.V., Krumke S.O., Westphal S. MIP Formulations for Flowshop Scheduling with Limited Buffers // Proceedings First International ICST Conference «Theory and Practice of Algorithms in (Computer) Systems» (TAPAS). 2011. vol. 6595. pp. 127–138.
  11. Fu Q., Sivakumar A., Li K. Optimisation of flow-shop scheduling with batch processor and limited buffer // International Journal of Production Research. 2012. vol. 50. pp. 2267–2285.
  12. Çakici M.K. Parallel flow shop scheduling with common workstations // A thesis submitted to the graduate school of natural and applied sciences of Middle East technical university. 2019. 138 p.
  13. Кононова П.А., Кочетов Ю.А. Алгоритм локального поиска для построения расписаний работы одного станка с переналадкой оборудования и складом // Дискретный анализ и исследование операций. 2019. Т. 26. № 2. С. 60–78.
  14. Lin Ch.-Ch., Liu W.-Y., Chen Y.-H. Considering Stockers in Reentrant Hybrid Flow Shop Scheduling with Limited Buffer Capacity // Computers & Industrial Engineering. 2020. vol. 139. doi: 10.1016/j.cie.2019.106154.
  15. 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. vol. 11. no. 3. pp. 469–480. doi: 10.5267/j.ijiec.2019.11.002.
  16. Zhang Ch., 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. vol. 68. doi: 10.1016/j.rcim.2020.102081.
  17. 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. doi: 10.1177/0037549718809542.
  18. Ernst A., Fung J., Singh G., Zinder Ya. Flexible flow shop with dedicated buffers // Discrete Applied Mathematics. 2019. no. 261. pp. 148–163. doi: 10.1016/j.dam.2018.07.002.
  19. Berlinska J. Heuristics for scheduling data gathering with limited base station memory // Annals of Operations Research. 2020. no. 285(1). pp. 149–159. doi: 10.1007/s10479-019-03185-3.
  20. Berlinska J., Kononov A., Zinder Ya. Two-machine flow shop with dynamic storage space // Optimization Letters. 2021. vol. 15. pp. 2433–2454. doi: 10.1007/s11590-020-01645-5.
  21. Souiden S., Cerqueus A., Delorme X., Rascle J.-L. Retail order picking scheduling with missing operations and limited buffer // IFAC-Papers On Line, 21st IFAC World Congress. 2020. voo. 53(2). pp. 10767–10772. doi: 10.1016/j.ifacol.2020.12.2859.
  22. Esfeh M.K., Shojaei A.A., Javanshir H., Damghani K.K. Solving a bi-objective flexible flow shop problem with transporter preventive maintenance planning and limited buffers by NSGA-II and MOPSO // The International Journal of Nonlinear Analysis and Applications (IJNAA). 2022. vol. 13. no. 1. pp. 217–246. doi: 10.22075/ijnaa.2021.24335.2719.
  23. Koh J., Bodin B. K-periodic scheduling for throughput-buffering trade-off exploration of CSDF // ACM Transactions on Embedded Computing Systems. 2022. vol. 22. no. 1. doi: 10.1145/3559760.
  24. Honorat A., Dardaillon M., Miomandre H., Nezan J.-F. Automated buffer sizing of dataflow applications in a high-level synthesis workflow // ACM Transactions on Reconfigurable Technology and Systems (TRETS). 2024. no. 17(1). pp. 1–26. doi: 10.1145/3626103.
  25. Van Schilt I.M., Van Kalker J., Lefter I., Kwakkel J., Verbraeck A. Buffer scheduling for improving on-time performance and connectivity with a multi-objective simulation–optimization model: A proof of concept for the airline industry // Journal of Air Transport Management. 2024. no. 115(7). doi: 10.1016/j.jairtraman.2024.102547.
  26. Agnetis A., Pacciarelli D., Rossi F. Batch scheduling in a two-machine flow shop with limited buffer // Discrete Applied Mathematics. 1997. no. 72. pp. 243–260.
  27. 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. no. 153(3). pp. 581–592.
  28. Dai J. Batch Scheduling of Two-machine Limited-buffer Flow Shop with Setup and Removal Times // A Thesis for the Degree of Doctor of Philosophy in the School of Industrial and Systems Engineering. Georgia Institute of Technology. 2003. 108 p.
  29. Belaid R., T’kindt V., Esswein C. Scheduling batches in flow shop with limited buffers in the shampoo industry // European Journal of Operational Research. 2012. vol. 223(2). pp. 560–572.
  30. Ruhbakhsh R., Mehdizadeh E., Adibi M. A Mathematical Model for Lot-streaming Hybrid Flow Shop Scheduling Problem by Considering Learning Effect and Buffer Capacity // Scientia Iranica. 2022. doi: 10.24200/SCI.2022.58131.5582.
  31. Janeš G., Ištokovi´c D., Jurkovi´c Z., Perinic M. Application of modified steady-state genetic algorithm for batch sizing and scheduling problem with limited buffers // Applied Sciences. 2022. no. 12(22). doi: 10.3390/app122211512.

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