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