Mathematical Model and Algorithm of Branch and Boundary Method for Optimizing Solutions for Package Compositions in Multi-Stage Systems

Cover Page

Cite item

Full Text

Abstract

Modern methods for solving problems of planning of task packages execution in multi-stage systems are characterized by the presence of restrictions on their dimension, the impossibility of obtaining guaranteed best results in comparison with fixed packages for different values of the input parameters of tasks. The problem of optimizing the composition of task packages executed in multi-stage systems using the method of branches and borders is solved in the paper. Studies of various ways of forming the order of execution of task packages in multi-stage systems (heuristic rules for ordering task packages in the sequences of their execution on MS devices) have been carried out. The method of ordering packets in the sequence of their execution (a heuristic rule), which minimizes the total time for implementing actions with them on the devices, is defined. The method of ordering the types of tasks, according to which their packages are considered in the procedure of the method of branches and borders, is formulated on the basis of the obtained rule. A mathematical model of the process of implementing actions with packages on the system devices, which provides the calculation of its parameters, has been built. The construction of a method for forming all possible solutions for the composition of task packages for a given number of them has been completed. Decisions on the composition of task packages of different types are interpreted in the procedure of the method of branches and borders in order to build the optimal combination of them. To implement the method of branches and borders, a branching (splitting) procedure is formulated, which assumes the formation of subsets of solutions that include packages of different compositions of tasks of the same type. Expressions for calculating the lower and upper estimates of the values of the optimization criterion for the composition of packages for subsets formed in the branching procedure are constructed. The dropout procedure involves the exclusion of subsets whose lower estimate is not less than the record. To find optimal solutions, a breadth-first search strategy is applied, which provides for the study of all subsets of solutions that include various packages of tasks of the same type obtained as a result of the procedure for splitting subsets of tasks that are not excluded from consideration after the implementation of the dropout procedure. The developed algorithms are implemented programmatically, which allowed to obtain the results of planning the execution of task packages in a multi-stage system, which are on average 30 % better than fixed packages.

About the authors

K. V Krotov

Sevastopol State University

Email: krotov_k1@mail.ru
St. University 33

References

  1. Ogun B., Cigdem A.-U. Mathematical Models for a Batch Scheduling Problem to Minimizе Earliness and Tardiness. Journal of Industrial Engineering and Management. JIEM, 2018. № 11(3). pp. 390-405.
  2. Chaudhry I.A., Elbadawi I. A-Q., Usman M., Chugtai M.T. Minimising Total Flowtime in a No-Wait Flow Shop (NWFS) using Genetic Algorithms. Ingeniería e Investigación. 2018. Vol. 38. № 3. pp. 68-79.
  3. Tan Y., Huangi W., Sun Y., Yue Y. Comparative Study of Different Approaches to Solve Batch Process Sheduling and Optimisation Problems. Proceedings of the 18th International Conference on Automation & Computing. Loughborough University. Leicestershire. UK. 2012. pp 424–444.
  4. Кротов К.В. Использование аппарата генетических алгоритмов при формировании решений по составам партий данных в двухуровневой задаче построения комплексных расписаний их обработки. Автоматизированные технологии и производства // Международный научно-технический журнал. 2017. №2 (16). С. 23-34.
  5. Li X.L., Wang Y. Scheduling Batch Processing Machine Using Max–Min Ant System Algorithm Improved by a Local Search Method. Mathematical Problems in Engineering. 2018. Vol. 2018.
  6. Li Sh., Cheng T.C.E., Ng C.T., Yuan J. Single-machine batch scheduling with job processing time compatibility. Theoretical Computer Science. 2015. Vol. 583. pp. 57-66.
  7. Jin M., Liu X., Luo W. Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection. Mathematics. 2020. Vol. 8.
  8. Surjandari I., Rachman A., Purdianta, Dhini A. The batch scheduling model for dynamic multi-item, multi-level production in an assembly job shop with parallel machines. International Journal of Technology. 2015. № 1. pp. 84-96.
  9. Joglekar G. Using Simulation for Scheduling and Rescheduling of Batch Processes. Processes. 2017. № 5.
  10. Ковалев М.Я. Модели и методы календарного планирования. Курс лекций. Минск: БГУ. 2004. 63 с.
  11. Morrison D.R., Jacobson Sh.H., Sauppe J.J., Sewell E.C. Branch-and-bound algorithms: A survey of recent advances in searching, branching and pruning. Discrete Optimization. 2016. № 19. pp. 79-102.
  12. Dawd S.T., Ayvaz B. A branch and bound approach for single machine scheduling problem. Istanbul Commerce University. Journal of Science. 2017. № 16 (31). pp. 43-55.
  13. Rasti-Barzoki M., Hejazi S.R. A branch and bound algorithm to minimize the total weighted number of tardy jobs and delivery costs with late deliveries for a supply chain-scheduling problem. Journal of Industrial and Systems Engineering. 2017. Vol. 10. № 1. pp 50- 60.
  14. Прилуцкий М.Х., Власов В.С. Метод ветвей и границ с эвристическими оценками для конвейерной задачи теории расписаний // Математическое моделирование. Оптимальное управление. Вестник Нижегородского университета им. Н.И. Лобачевского. 2008. № 3. 147-153 с.
  15. Takano M.I., Nagano M.S. A branch-and bound method to minimize the makespan in a permutation flow shop with blocking and setup times. Cogent Engineering. 2017.
  16. Григорьева Н.С. Алгоритм ветвей и границ для задачи составления расписания на параллельных процессорах // Вестник Санкт-Петербургского университета. серия 10. 2009. выпуск 1. 44-55 с.
  17. Mazda Ch.N., Kurniawati D.A. Branch and Bound Method to Overcome Delay Delivery Order in Flow Shop Scheduling Problem. IOP Conf. Series: Materials Science and Engineering. 2020.
  18. Watermeyer K., Zimmermann J. A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints. OR Spectrum. 2020. № 42. pp. 427–460.
  19. Hu Sh., Wang S., Kao Y., Ito T., Sun X. A Branch and Bound Algorithm for Project Scheduling Problem with Spatial Resource Constraints. Hindawi Publishing Corporation. Mathematical Problems in Engineering. Vol. 2015. P. 9.
  20. Могилев А.А. Обзор методов решения задач теории расписаний // Информатика, вычислительная техника и инженерное образование. 2019. № 4 (37). 19-32 с.
  21. Кротов К.В. Информационная модель многоуровневой системы выполнения конвейеризированных программ // Международный научно-технический журнал «Проблемы управления и информатики». 2014. № 3. 89-101 c.
  22. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. Sequencing and Scheduling: Algorithms and Complexity. Handbook in Operations Research and Managment Science. North-Holland, Amsterdam. 1993. Vol. 4. pp. 445-522.
  23. Кротов К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах // Журнал «Вычислительные технологии». Новосибирск. Изд-во Института вычислительных технологий СО РАН. 2018. № 3. 58-76 с.
  24. Кротов К.В., Скатков А.В. Организация web-ориентированного сервиса мониторинга окружающей среды с использованием данных дистанционного зондирования Земли и конвейеризации обработки данных // Труды учебных заведений связи. 2021. Т. 7. №1. 105-121 c.

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