tuzsutТруды учебных заведений связиProceedings of Telecommunication Universities1813-324X2712-8830СПбГУТ10.31854/1813-324X-2020-6-3-75-90tuzsut-134Research ArticleИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕINFORMATICS, COMPUTER ENGINEERING AND MANAGEMENTПостроение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционированияBuilding Complex Schedules of Data Packets Processing with Setting Time Limits of a Conveyor System FunctioningКротовК. В.KrotovK. ..krotov_k1@mail.ruСевастопольский государственный университетРоссияSebastopol State UniversityRussian Federation202013042021637590Copyright © Кротов К.В., 20212021Кротов К.В.Krotov K...This work is licensed under a Creative Commons Attribution 4.0 License.https://tuzs.sut.ru/jour/article/view/134

Рассматривается задача планирования обработки пакетов данных в конвейерной системе при ограничении на длительности интервалов времени ее функционирования. Решение задачи предполагает определение составов пакетов данных, составов групп пакетов данных, обрабатываемых в течение этих интервалов времени, расписаний обработки пакетов каждой из групп. Для оптимизации решений применен аппарат теории иерархических игр. Введены условия, позволяющие определять пакеты, обработка либо переналадка на обработку которых вызывает максимальные простои сегментов конвейера. Предложен метод построения эффективных составов групп, предполагающий исключение из них пакетов, определяемых в соответствии с этими условиями, и размещение в группах не вошедших в них пакетов.

The problem of planning data packet processing in a pipeline system with a time limit on the duration of its operation intervals is considered. The solution of the problem involves determining the composition of data packets, the composition of groups of data packets processed during these time intervals, and the schedules for processing packets of each group. To optimize solutions, the hierarchical game theory is applied. Conditions have been introduced that allow you to determine packages that are processed or readjusted to processing, which causes maximum downtime of pipeline segments. A method for constructing effective group compositions is proposed, which involves excluding packages that are determined in accordance with these conditions and placing packages that are not included in them in groups.

иерархическая играинтервалы функционирования конвейерной системыгруппы пакетов данныхлокальная оптимизацияhierarchical gameintervals of conveyor system functioningdata packets groupslocal optimizationReferencesКротов К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах // Вычислительные технологии. 2018. Т. 23. № 3. С. 58-76.Кротов К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах // Вычислительные технологии. 2018. Т. 23. № 3. С. 58-76.Mendez C.A., Cerdá J., Grossmann I.E., Harjunkoski I., Fahl M. State-of-the-art review of optimization methods for shortterm scheduling of batch processes // Computers and Chemical Engineering. 2006. Vol. 30. Iss. 6-7. PP. 913-946. DOI:10.1016/j.compchemeng.2006.02.008Mendez C.A., Cerdá J., Grossmann I.E., Harjunkoski I., Fahl M. State-of-the-art review of optimization methods for shortterm scheduling of batch processes // Computers and Chemical Engineering. 2006. Vol. 30. Iss. 6-7. PP. 913-946. DOI:10.1016/j.compchemeng.2006.02.008Adonyi R., Romero J., Puigjaner L., Friedler F. Incorporating heat integration in batch process scheduling // Applied Thermal Engineering. 2003. Vol. 23. Iss. 14. PP. 1743-1762. DOI:10.1016/S1359-4311(03)00141-8Adonyi R., Romero J., Puigjaner L., Friedler F. Incorporating heat integration in batch process scheduling // Applied Thermal Engineering. 2003. Vol. 23. Iss. 14. PP. 1743-1762. DOI:10.1016/S1359-4311(03)00141-8Agha M. Integrated Management of Energy and Production: Scheduling of Batch Process and Combined Heat & Power Plant. PhD Thesis. Toulouse, France: University of Toulouse, 2009. 255 p.Agha M. Integrated Management of Energy and Production: Scheduling of Batch Process and Combined Heat & Power Plant. PhD Thesis. Toulouse, France: University of Toulouse, 2009. 255 p.Zeballos L.J., Henning G.P. A CP approach to the scheduling of resource-constrained multiproduct continuous facilities // Latin American Applied Research. 2006. Iss. 36. PP. 205-212.Zeballos L.J., Henning G.P. A CP approach to the scheduling of resource-constrained multiproduct continuous facilities // Latin American Applied Research. 2006. Iss. 36. PP. 205-212.Díaz-Ramírez J., Huertas J.I. A continuous time model for a short-term multiproduct batch process scheduling // Ingeniería e Investigación. 2018. Vol. 38. Iss. 1. PP. 96-104. DOI:10.15446/ing.investig.v38n1.66425Díaz-Ramírez J., Huertas J.I. A continuous time model for a short-term multiproduct batch process scheduling // Ingeniería e Investigación. 2018. Vol. 38. Iss. 1. PP. 96-104. DOI:10.15446/ing.investig.v38n1.66425Ковалев М.Я. Модели и методы календарного планирования. Минск: БГУ, 2004. URL: https://www.studmed.ru/ kovalev-mya-modeli-i-metody-kalendarnogo-planirovaniya_ca57fbd.html (дата обращения 10.09.2020)Ковалев М.Я. Модели и методы календарного планирования. Минск: БГУ, 2004. URL: https://www.studmed.ru/ kovalev-mya-modeli-i-metody-kalendarnogo-planirovaniya_ca57fbd.html (дата обращения 10.09.2020)Chandra P., Gupta S. Managing batch processors to reduce lead time in a semiconductor packaging line // International Jornal of Production Research. 1997. Vol. 35. Iss. 3. PP. 611-633. DOI:10.1080/002075497195623Chandra P., Gupta S. Managing batch processors to reduce lead time in a semiconductor packaging line // International Jornal of Production Research. 1997. Vol. 35. Iss. 3. PP. 611-633. DOI:10.1080/002075497195623Bein W., Noga J., Wiegley J. Priority Approximation for Batching // Proceedings of the 41st Hawaii International Conference on Systems Science (HICSS-41 2008, Waikoloa, Big Island, Hawaii, 7-10 January 2008). IEEE, 2008. DOI:10.1109/HICSS.2008.508Bein W., Noga J., Wiegley J. Priority Approximation for Batching // Proceedings of the 41st Hawaii International Conference on Systems Science (HICSS-41 2008, Waikoloa, Big Island, Hawaii, 7-10 January 2008). IEEE, 2008. DOI:10.1109/HICSS.2008.508Bein W., Noga J., Wiegley J. Approximation for Batching via Priorities // Scientific Annals of Computer Science. 2017. Vol. 17. PP. 1-18.Bein W., Noga J., Wiegley J. Approximation for Batching via Priorities // Scientific Annals of Computer Science. 2017. Vol. 17. PP. 1-18.Steiner G., Zhang R. Minimizing the weight number of late jobs with Batch setup times and delivery costs on a single machine. Vienna: Itech Education and Published, 2007. DOI:10.5772/5216Steiner G., Zhang R. Minimizing the weight number of late jobs with Batch setup times and delivery costs on a single machine. Vienna: Itech Education and Published, 2007. DOI:10.5772/5216Koehler F. Khuller S. Optimal Batch Schedules for Parrallel Machines // Proceedings of the 13th International Symposium on Workshop on Algorithms and Data Structures (WADS 2013, London, ON, Canada, 12-14 August 2013). Lecture Notes in Computer Science. Berlin: Springer, 2013. Vol. 8037. PP. 475-486. DOI:10.1007/978-3-642-40104-6_41Koehler F. Khuller S. Optimal Batch Schedules for Parrallel Machines // Proceedings of the 13th International Symposium on Workshop on Algorithms and Data Structures (WADS 2013, London, ON, Canada, 12-14 August 2013). Lecture Notes in Computer Science. Berlin: Springer, 2013. Vol. 8037. PP. 475-486. DOI:10.1007/978-3-642-40104-6_41Monch L., Balasubramanian H., Fowler J. W., Pfund M. E. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times // Computers & Operations Research. 2005. Vol. 32. Iss. 11. PP. 2731-2750. DOI:10.1016/j.cor.2004.04.001Monch L., Balasubramanian H., Fowler J. W., Pfund M. E. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times // Computers & Operations Research. 2005. Vol. 32. Iss. 11. PP. 2731-2750. DOI:10.1016/j.cor.2004.04.001Dang Th.T., Frankovic B., Budinska I., Flood B., Sheahan C., Dang B.L. Using heuristic search for solving single machine batch processing problems // Computing and Informatics. 2006. Vol. 25. Iss. 5. PP. 405-420.Dang Th.T., Frankovic B., Budinska I., Flood B., Sheahan C., Dang B.L. Using heuristic search for solving single machine batch processing problems // Computing and Informatics. 2006. Vol. 25. Iss. 5. PP. 405-420.Kohn R., Rose O., Laroque Ch. Study on multi-objective optimization for parallel batch machine scheduling using variable neighbourhood search // Proceedings of the Winter Simulation Conference (WSC, Washington, USA, 8-11 December 2013). IEEE, 2013. PP. 3654-3670. DOI:10.1109/WSC.2013.6721726Kohn R., Rose O., Laroque Ch. Study on multi-objective optimization for parallel batch machine scheduling using variable neighbourhood search // Proceedings of the Winter Simulation Conference (WSC, Washington, USA, 8-11 December 2013). IEEE, 2013. PP. 3654-3670. DOI:10.1109/WSC.2013.6721726Cheng T., Yuan J., Yang A. Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times // Computers and Operations Research. 2005. Vol. 32. Iss. 4. PP. 849-859. DOI:10.1016/j.cor.2003. 09.001Cheng T., Yuan J., Yang A. Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times // Computers and Operations Research. 2005. Vol. 32. Iss. 4. PP. 849-859. DOI:10.1016/j.cor.2003. 09.001Van der Zee D.-J. Dynamic scheduling of batch processing machines with non-identical product sizes // International Journal of Production Research. 2007. Vol. 45. Iss. 10. PP. 2327-2349. DOI:10.1080/00207540600690537Van der Zee D.-J. Dynamic scheduling of batch processing machines with non-identical product sizes // International Journal of Production Research. 2007. Vol. 45. Iss. 10. PP. 2327-2349. DOI:10.1080/00207540600690537Tan 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 and Computing (ICAC, Loughborough, UK, 7-8 September 2012). IEEE, 2012. PP. 424-444.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 and Computing (ICAC, Loughborough, UK, 7-8 September 2012). IEEE, 2012. PP. 424-444.Cheng B.-Y., Chen H.-P., Wang S.-S. Improved Ant Colony Optimization Method for Single Batch-Processing Machine with Non-Identical Job Sizes // Journal of System Simulation. 2009. Vol. 21. Iss. 9. PP. 2687-2695.Cheng B.-Y., Chen H.-P., Wang S.-S. Improved Ant Colony Optimization Method for Single Batch-Processing Machine with Non-Identical Job Sizes // Journal of System Simulation. 2009. Vol. 21. Iss. 9. PP. 2687-2695.Ramasubramanian M., Mathirajan M. A Mathematical Model for Scheduling a Batch Processing Machine with Multiple Incompatible Job Families, Non-identical Job dimensions, Nonidentical Job sizes, Non-agreeable release times and due dates // Proceedings of the International Conference on Manufacturing, Optimization, Industrial and Material Engineering (MOIME 2013, Grand Hyatt, Bandung, Indonesia, 9-10 March 2013). IOP Conference Series: Materials Science and Engineering. 2013. Vol. 46. DOI:10.1088/1757-899X/46/1/012013Ramasubramanian M., Mathirajan M. A Mathematical Model for Scheduling a Batch Processing Machine with Multiple Incompatible Job Families, Non-identical Job dimensions, Nonidentical Job sizes, Non-agreeable release times and due dates // Proceedings of the International Conference on Manufacturing, Optimization, Industrial and Material Engineering (MOIME 2013, Grand Hyatt, Bandung, Indonesia, 9-10 March 2013). IOP Conference Series: Materials Science and Engineering. 2013. Vol. 46. DOI:10.1088/1757-899X/46/1/012013Ogun B., Çigdem A.-U. Mathematical models for a batch scheduling problem to minimizе earliness and tardiness // Journal of Industrial Engineering and Management. 2018. Vol. 11. Iss. 3. PP. 390-405. DOI:10.3926/jiem.2541Ogun B., Çigdem A.-U. Mathematical models for a batch scheduling problem to minimizе earliness and tardiness // Journal of Industrial Engineering and Management. 2018. Vol. 11. Iss. 3. PP. 390-405. DOI:10.3926/jiem.2541Kreipl S., Pinedo M. Planning and Scheduling in Supply Chains: An Overview of Issues in Practice // Production and Operations Management. 2004. Vol. 13. Iss. 1. PP. 77-92. DOI:10.1111/j.1937-5956.2004.tb00146.xKreipl S., Pinedo M. Planning and Scheduling in Supply Chains: An Overview of Issues in Practice // Production and Operations Management. 2004. Vol. 13. Iss. 1. PP. 77-92. DOI:10.1111/j.1937-5956.2004.tb00146.xКротов К.В. Обоснование модели многоуровневого программирования для построения расписаний групповой обработки партий данных в конвейерной системе при наличии ограничений // Вестник Иркутского государственного технического университета. 2016. №1(108). С. 35-48.Кротов К.В. Обоснование модели многоуровневого программирования для построения расписаний групповой обработки партий данных в конвейерной системе при наличии ограничений // Вестник Иркутского государственного технического университета. 2016. №1(108). С. 35-48.Кротов К.В. Использование генетических алгоритмов для построения эффективных комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2020. № 1. С. 71-86. DOI:10.17308/sait.2020.1/2594Кротов К.В. Использование генетических алгоритмов для построения эффективных комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2020. № 1. С. 71-86. DOI:10.17308/sait.2020.1/2594

The authors declare that there are no conflicts of interest present.