Abstract:
The paper considers the problem of distribution-type planning with priority constraints. For a given set of requirements and resources with established usage parameters, it is necessary to construct an assignment plan that satisfies a system of priority constraints. In this case, two queues of constraints on quantitative and qualitative characteristics are distinguished, respectively. At the stage of solving the problem with the first queue of constraints, a basic integer linear programming (ILP) model and a dynamic scheme for its formation are developed. Within this approach, the original problem is reduced to solving a sequence of similar problems of significantly smaller dimension, which allows to take into account the priorities of resource use directly in the construction and guarantees the convergence of the basic ILP model at the final iteration of the dynamic scheme. At the stage of implementing the second queue of constraints for the obtained basic solution, an integral criterion in the form of an upper estimate is introduced, and a modified ILP model is considered. The model modification procedure is based on the penalty function method and includes the additional equipment of the constraint system, the objective function, and the functional space by a subset of auxiliary Boolean variables. It is proved that the modified model is guaranteed to be solvable and determines the maximal feasible subsystem of constraints of the second queue for the original problem. Within the analysis of the operability and efficiency of the proposed approach, a computational experiment is conducted using real-scale data.
Keywords:scheduling theory, integer linear programming, discrete production, production planning system, decomposition approach.
Fulltext:
PDF file (231 kB)