Построение комплексных расписаний выполнения пакетов заданий при формировании комплектов в заданные директивные сроки
Ключевые слова:
многостадийная система, пакеты зданий, расписание, комплекты результатов, директивные сроки, иерархическая играАннотация
Современное состояние решения задачи комплексного планирования выполнения пакетов заданий в многостадийных системах характеризуется отсутствием универсальных способов формирования решений по составам пакетов, наличием ограничений на размерность задачи и невозможностью гарантированного получения эффективных решений при различных значениях ее входных параметров, а также невозможностью учета условия формирования комплектов из результатов. В статье авторами реализовано решение задачи планирования выполнения пакетов заданий в многостадийных системах при формировании комплектов результатов в заданные для них директивные сроки. Для решения задачи планирования выполнена декомпозиция обобщенной функции системы на совокупность иерархически взаимосвязанных подфункций. Применение декомпозиции позволило использовать иерархический подход для планирования выполнения пакетов заданий в многостадийных системах, предусматривающий определение решений по составам пакетов на верхнем уровне иерархии и построение расписаний выполнения пакетов на нижнем уровне иерархии. Для оптимизации решений по составам пакетов и расписаниям их выполнения в соответствии с иерархическим подходом применена теория иерархических игр. Построена математическая модель иерархической игры для определения эффективных составов пакетов заданий и расписаний их выполнения, представляющая собой систему критериев на уровнях принятия решений. Оценка эффективности решений по составам пакетов на верхнем уровне иерархии обеспечивается распределением результатов выполнения заданий по комплектам в соответствии с сформированным расписанием. Для оценки эффективности решений по составам пакетов сформулирован метод упорядочивания идентификаторов типов комплектов с учетом директивных сроков и метод распределения результатов выполнения заданий по комплектам, реализующий вычисление моментов времени окончания формирования комплектов и запаздываний с их формированием относительно заданных директивных сроков. Выполнены исследования планирования процесса выполнения пакетов заданий в многостадийных системах при условии формирования комплектов в заданные директивные сроки. На их основе сформулированы выводы, касающиеся зависимости эффективности планирования от входных параметров задачи.
Литература
2. Mendez C.A. et al. State-of-the-art review of optimization methods for short-term scheduling of batch processes // Computers and Chemical Engineering, 2006, vol. 30, pp. 913–946.
3. Adonyi R., Romero J., Puigjaner L., Friedler F. Incorporating heat integration in batch process scheduling // Applied Thermal Engineering, 2003, vol. 23, pp. 1743–1762.
4. Agha M. Integrated management of energy and production: scheduling of batch process and Combined Heat & Power plant // University of Toulouse. National Polytechnic Institute of Toulouse (FRANCE), 2009.
5. Zeballos L.J., Henning G.P. A CP approach to the scheduling of resource-constrained multiproduct continuous facilities // Latin American Applied Research, 2006, №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, №1, pp. 96-104. DOI: 10.15446/ing.investig.v38n1.66425
7. Ning Ch., You F. Batch Process Scheduling under Uncertainty using Data-Driven Multistage Adaptive Robust Optimization // Сhemical engineering transactions, 2017, vol. 61, pp. 1567-1572. DOI: 10.3303/CET1761259
8. 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. DOI: 10.15446/ing.investig.v38n3.75281
9. Ogun B., Cigdem A.-U. Mathematical Models for a Batch Scheduling Problem to Minimizе Earliness and Tardiness // Journal of Industrial Engineering and Management. JIEM, 2018, № 11(3), pp. 390–405. DOI: 10.3926/jiem.2541.
10. 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, Article ID: 3124182, 10 pages. DOI: 10.1155/2018/3124182.
11. 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.
12. 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, № 9, pp. 2687–2695.
13. Koehler F. Khuller S. Optimal Batch Schedules for Parrallel Machines // Algorithms and Data Structures: 13th International Symposium. Berlin: Springer, 2013, pp. 475–486.
14. Monch L., Balasubramanian H., Fowler J. W., Pfund M. E. Heuristic scheduling of jobs on parallel batch machines with incompatible job families andunequal ready times // Computers & Operations Research, 2005, №32, pp. 2731–2750.
15. Dang Th.-T., Frankovic B., Budinska I. Using heuristic search for solving single machine batch processing problems // Computing and Informatics, 2006, vol. 25, pp. 405–420.
16. Kohn R., Rose O., Laroque Ch. Study on multi-objective optimization for parallel batch machine scheduling using variable neighbourhood search // Proceedings of the 2013 Winter Simulation Conference. 8th-11th December 2013, pp. 3654-3670.
17. 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. DOI: 10.1016/j.tcs.2015.03.043.
18. Jin M., Liu X., Luo W. Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection // Mathematics, 2020, vol. 8, Article ID:258. DOI: 10.3390/math8020258.
19. 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. DOI: 10.14716/ijtech.v6i1.783.
20. Joglekar G. Using Simulation for Scheduling and Rescheduling of Batch Processes // Processes, 2017, # 5, Article ID 66. DOI: 10.3390/pr5040066.
21. Ковалев М.Я. Модели и методы календарного планирования. Курс лекций. Минск: БГУ. 2004. 63 с.
22. Кротов К.В. Обоснование методов построения комплексных расписаний обработки партий данных при условии оперативного формировании комплектов из результатов // Вестник Воронежского Государственного Университета. Серия: Системный анализ и информационные технологии, №4, 2018, C. 58–72.
23. Кротов К.В. Использование аппарата генетических алгоритмов при формировании решений по составам партий данных в двухуровневой задаче построения комплексных расписаний их обработки // Автоматизированные технологии и производства. Международный научно-технический журнал, 2017, №2(16). C. 23–34.
24. Кротов К.В. Построение комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования // Труды учебных заведений связи, 2020, т.6, №3. С. 75–89.
Construction of Complex Schedules for Execution of Task Packages at Forming Sets in Specified Directive Terms
Abstract
The current state with the solution of the problem complex planning of the execution of task packets in multistage system is characterized by the absence of universal methods of forming decisions on the composition of packets, the presence of restrictions on the dimension of the problem and the impossibility of guaranteed obtaining effective solutions for various values of its input parameters, as well the impossibility of registration the condition of the formation of sets from the results. The solution of the task of planning the execution of task packets in multistage systems with the formation of sets of results within the specified deadlines has been realized of authors in article. To solve the planning problem, the generalized function
of the system was decomposed into a set of hierarchically interrelated subfunctions. The use of decomposition made it possible to use a hierarchical approach for planning the execution of task packets in multistage systems, which involves defining solutions based on the composition of packets at the top level of the hierarchy and scheduling the execution of packages at the bottom level of the hierarchy. The theory of hierarchical games is used to optimize solutions for the compositions of task packets and schedules for their execution is built, which is a system of criteria at the decision-making levels. Evaluation of the effectiveness of decisions by the composition of packets at the top level of the hierarchy is ensured by the distribution of the
results of task execution by packets in accordance with the formed schedule. To evaluate the effectiveness of decisions on the composition of packets, method for ordering the identifiers of the types of sets with registration of the deadlines and a method for distributing the results of the tasks performed by packets has been formulated, which calculates the moments of completion of the formation of sets and delays with their formation relative to the specified deadlines. The studies of planning the process of the executing task packages in multistage systems have been carried out, provided that the sets are formed within specified deadlines. On their basis, conclusions, regarding the dependence of the planning efficiency from the input parameters of the problem, were formulated.
Опубликован
Как цитировать
Раздел
Copyright (c) Кирилл Викторович Кротов, Александр Владимирович Cкатков
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).