Библиографическое описание:Сложность задачи календарного планирования с критерием оптимизации экономического эффекта от использования квот на выбросы : научное издание / А. М. Булавчук. - Текст : непосредственный // Прикладная дискретная математика. - 2026. - № 71. - С. 86-96. - Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки РФ (соглашение № 075-02-2025-1790). - ISSN 2071-0410. - ISSN 2311-2263, DOI 10.17223/20710410/71/6.
Аннотация:Рассматривается модель задачи календарного планирования с оптимизацией экономического эффекта от использования квот на выбросы. При построении модели учитывается актуальная российская практика обращения с углеродными единицами. Модель предполагает поиск оптимального расписания инвестиционного проекта, при реализации которого используются углеродные квоты. Критерием оптимальности выступает разница между доходами и расходами, обусловленными операциями с углеродными единицами. Ограничениями задачи выступают организационные и технологические взаимосвязи между работами, а также предельный срок завершения проекта. Все параметры модели являются детерминированными. Сформулирована и доказана теорема о том, что задача календарного планирования с критерием оптимизации экономического эффекта от использования квот на выбросы является NP-трудной в сильном смысле даже в случае работ единичной длительности. Взаимосвязи между проектными работами могут быть представлены в виде неориентированного графа. Это позволяет в процессе доказательства использовать сведение к данной задаче задачи о клике, NP-трудность которой известна. Рассмотрены также особые случаи соотношений между ценами квот и штрафами. Доказано утверждение о том, что при условии равенства и постоянной величине цен и штрафов в каждый момент времени задача календарного планирования с оптимизацией экономического эффекта от использования квот на выбросы может быть сведена к известному варианту задачи календарного планирования с неограниченными ресурсами и критерием максимизации NPV. Для решения численных примеров использована модификация разработанной ранее программы для IBM ILOG CPLEX.
We consider a scheduling model that optimizes the economic impact of using emission quotas. When constructing the model, the current Russian practice of handling carbon units is taken into account. The model involves searching for the optimal schedule of an investment project, the implementation of which uses carbon quotas. The optimality criterion is the difference between income and expenses resulting from transactions with carbon units. The problem constraints include the organizational and technological dependencies between activities, as well as the project deadline. All model parameters are deterministic. We prove that the scheduling problem with the objective of optimizing the economic impact of emission quotas is strongly NP-hard, even when all tasks have the same duration. We show that the relationships between project activities can be represented in the form of an undirected graph. This allowed us to use a reduction of the clique problem, whose NP-hardness is known, to this problem during the proof process. Special cases of relationships between quota prices and fines are also considered. It was proved that, assuming constant prices and fines over time, the problem of scheduling to optimize the economic effect of emission quotas can be reduced to the well-known scheduling problem with unlimited resources and the NPV maximization criterion. To solve numerical examples, a modification of the previously developed algorithm for IBM ILOG CPLEX was used.
