Математическая модель и алгоритм метода ветвей и границ для оптимизации решений по составам пакетов в многостадийных системах
Ключевые слова:
многостадийная система, пакеты заданий, метод ветвей и границ, эвристическое правило, расписанияАннотация
Современные методы решения задач планирования выполнения пакетов заданий в многостадийных системах характеризуются наличием ограничений на их размерность, невозможностью гарантированного получения лучших результатов в сравнении с фиксированными пакетами при различных значениях входных параметров задачи. В статье автором решена задача оптимизации составов пакетов заданий, выполняющихся в многостадийных системах, с использованием метода ветвей и границ. Проведены исследования различных способов формирования порядков выполнения пакетов заданий в многостадийных системах (эвристических правил упорядочивания пакетов заданий в последовательностях их выполнения на приборах МС). Определен способ упорядочивания пакетов в последовательностях их выполнения (эвристическое правило), обеспечивающий минимизацию общего времени реализации действий с ними на приборах. На основе полученного правила сформулирован способ упорядочивания типов заданий, в соответствии с которым их пакеты рассматриваются в процедуре метода ветвей и границ. Построена математическая модель процесса реализации действий с пакетами на приборах системы, которая обеспечивает вычисление его параметров. Выполнено построение метода формирования всех возможных решений по составам пакетов заданий для заданного их количества. Решения по составам пакетов заданий разных типов интерпретируются в процедуре метода ветвей и границ с целью построения оптимальной их комбинации. Для реализации метода ветвей и границ сформулирована процедура ветвления (разбиения), предполагающая формирование подмножеств решений, включающих пакеты разных составов заданий одного типа. Построены выражения для вычисления нижних и верхних оценок значений критерия оптимизации составов пакетов для сформированных в процедуре ветвления подмножеств. Процедура отсева предполагает исключение подмножеств, нижняя оценка которых не меньше рекорда. Для поиска оптимальных решений применена стратегия поиска в ширину, предусматривающая исследование всех подмножеств решений, включающих различные пакеты заданий одного типа, полученных в результате процедуры разбиения подмножеств заданий, не исключенных из рассмотрения после реализации процедуры отсева. Разработанные алгоритмы реализованы программно, что позволило получить результаты планирования выполнения пакетов заданий в многостадийной системе, являющиеся в среднем на 30 % лучшими, чем для фиксированных пакетов.
Литература
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.
Опубликован
Как цитировать
Раздел
Copyright (c) Кирилл Викторович Кротов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).