Complexity of the scheduling problem with the criterion of optimisation of economic effect from the use of emission quotas | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/6

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.