Математическое моделирование процессов выполнения пакетов заданий в конвейерных системах с промежуточными буферами ограниченных размеров
- Авторы: Кротов К.В1
-
Учреждения:
- ФГАОУ ВО «Севастопольский государственный университет» (СевГУ)
- Выпуск: Том 22, № 6 (2023)
- Страницы: 1415-1450
- Раздел: Математическое моделирование и прикладная математика
- URL: https://bakhtiniada.ru/2713-3192/article/view/265840
- DOI: https://doi.org/10.15622/ia.22.6.6
- ID: 265840
Цитировать
Полный текст
Аннотация
Современные методы планирования процессов в конвейерных системах с буферами определенного размера между обрабатывающими приборами позволяют оптимизировать расписания выполнения единичных заданий либо фиксированных пакетов заданий при их ограниченном количестве и ограниченном количестве приборов. Применение математических моделей процессов выполнения единичных заданий (пакетов заданий), используемых этими методами, при оптимизации составов пакетов и расписаний их выполнения в системах с произвольным количеством пакетов и приборов является невозможным. В то же время математические модели процессов выполнения пакетов заданий в конвейерных системах при наличии буферов ограниченных размеров между приборами являются основой для разработки методов оптимизации их (пакетов) составов и расписаний реализации действий с ними на приборах конвейерных систем. В связи с этим в статье разработаны математические модели многостадийных процессов выполнения произвольного количества пакетов заданий в конвейерных системах при наличии промежуточных буферов ограниченных размеров для двух и трех приборов, а также для произвольного количества приборов. Использование этих моделей позволяет определять моменты времени начала выполнения пакетов заданий на приборах конвейерных систем с учетом ограниченных размеров промежуточных буферов, а также длительности интервалов времени использования этих ресурсов и эффективность их использования в течение времени. Также разработан алгоритм математического моделирования процессов выполнения пакетов заданий в конвейерных системах при наличии промежуточных буферов ограниченных размеров, осуществляющий на основе заданного порядка реализации действий с пакетами заданий на приборах конвейерных систем вычисление временных характеристик этих процессов. Осуществлена разработка приложения, реализующего синтезированные математические модели процессов выполнения пакетов заданий в конвейерных системах с промежуточными буферами ограниченных размеров и соответствующий метод моделирования этих процессов. Разностороннее тестирование разработанного приложения показало, что полученные математические модели и метод моделирования адекватно описывают ход многостадийных процессов выполнения пакетов заданий в конвейерных системах, задаваемый с использованием различных значений их (процессов) параметров.
Об авторах
К. В Кротов
ФГАОУ ВО «Севастопольский государственный университет» (СевГУ)
Email: krotov_k1@mail.ru
улица Университетская 33
Список литературы
- Кротов К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах // Вычислительные технологии. 2018. Т. 23. № 3. С. 58–76.
- Кротов К.В. Обоснование методов построения комплексных расписаний обработки партий данных при условии оперативного формировании комплектов из результатов // Вестник Воронежского Государственного Университета. Серия: Системный анализ и информационные технологии. 2018. № 4. C. 58–72.
- Кротов К.В., Скатков А.В. Построение комплексных расписаний выполнения пакетов заданий при формировании комплектов в заданные директивные сроки // Информатика и автоматизация. 2021. Т. 20. № 3. C. 654–689.
- Кротов К.В. Построение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования // Труды учебных заведений связи. 2020. Т. 6. № 3. С. 75–89.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Кононова П.А. Алгоритмы построения расписаний для цеховых задач потокового типа с цифровым буфером // Дисс. канд. физ.-мат. наук. Новосибирск: Институт вычислительной математики и математической геофизики, 2012. 104 с.
- Cakici M.K. Parallel flow shop scheduling with common workstations // MS thesis. Middle East Technical University. 2019. 138 p.
- Кононова П.А., Кочетов Ю.А. Алгоритм локального поиска для построения расписаний работы одного станка с переналадкой оборудования и складом // Дискретный анализ и исследование операций. 2019. Т. 26. № 2. С. 60–78. doi: 10.33048/daio.2019.26.634.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Dai J. Batch Scheduling of Two-machine Limited-buffer Flow Shop with Setup and Removal Times // Georgia Institute of Technology, 2003. 108 p.
Дополнительные файлы
