Построение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования
https://doi.org/10.31854/1813-324X-2020-6-3-75-90
Аннотация
Рассматривается задача планирования обработки пакетов данных в конвейерной системе при ограничении на длительности интервалов времени ее функционирования. Решение задачи предполагает определение составов пакетов данных, составов групп пакетов данных, обрабатываемых в течение этих интервалов времени, расписаний обработки пакетов каждой из групп. Для оптимизации решений применен аппарат теории иерархических игр. Введены условия, позволяющие определять пакеты, обработка либо переналадка на обработку которых вызывает максимальные простои сегментов конвейера. Предложен метод построения эффективных составов групп, предполагающий исключение из них пакетов, определяемых в соответствии с этими условиями, и размещение в группах не вошедших в них пакетов.
Список литературы
1. Кротов К.В. Комплексный метод определения эффективных решений по составам партий данных и расписаниям их обработки в конвейерных системах // Вычислительные технологии. 2018. Т. 23. № 3. С. 58-76.
2. 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.008
3. Adonyi 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-8
4. 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.
5. 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.
6. 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.66425
7. Ковалев М.Я. Модели и методы календарного планирования. Минск: БГУ, 2004. URL: https://www.studmed.ru/ kovalev-mya-modeli-i-metody-kalendarnogo-planirovaniya_ca57fbd.html (дата обращения 10.09.2020)
8. 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/002075497195623
9. Bein 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.508
10. Bein W., Noga J., Wiegley J. Approximation for Batching via Priorities // Scientific Annals of Computer Science. 2017. Vol. 17. PP. 1-18.
11. 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/5216
12. Koehler 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_41
13. Monch 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.001
14. 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.
15. 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.6721726
16. Cheng 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.001
17. Van 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/00207540600690537
18. 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.
19. 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.
20. 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/012013
21. Ogun 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.2541
22. Kreipl 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
23. Кротов К.В. Обоснование модели многоуровневого программирования для построения расписаний групповой обработки партий данных в конвейерной системе при наличии ограничений // Вестник Иркутского государственного технического университета. 2016. №1(108). С. 35-48.
24. Кротов К.В. Использование генетических алгоритмов для построения эффективных комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2020. № 1. С. 71-86. DOI:10.17308/sait.2020.1/2594
Рецензия
Для цитирования:
Кротов К.В. Построение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования. Труды учебных заведений связи. 2020;6(3):75-90. https://doi.org/10.31854/1813-324X-2020-6-3-75-90
For citation:
Krotov K... Building Complex Schedules of Data Packets Processing with Setting Time Limits of a Conveyor System Functioning. Proceedings of Telecommunication Universities. 2020;6(3):75-90. (In Russ.) https://doi.org/10.31854/1813-324X-2020-6-3-75-90
Просмотров:
1315
Послать статью по эл. почте 