A Decomposition Approach in the Problem of Distribution-Type Planning with Priority Constraints

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 taking 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.

References

1. Borisovsky P.A., Eremeev A.V. Production Scheduling of a Multi-Product Plant Using Integer Linear Programming and Evolutionary Computations. Information Technologies, 2015, vol. 21, no. 6, pp. 412-421.
2. Janak S.L., Floudas C.A., Kallrath J., Vormbrock N. Production Scheduling of a Large-Scale Industrial Batch Plant: Short-Term and Medium-Term Scheduling. Industrial and Engineering Chemistry Research, 2006, vol. 45, no. 25, pp. 8234-8252. DOI: 10.1021/ie0600588
3. Slavyanov A.S. Analysis and Practical Application of Resource Allocation Models. Bulletin of Science and Practice, 2018, vol. 4, no. 9, pp. 228-244.
4. Menshikh V.V., Samorokovsky A.F., Avsentev O.S. Models of Resource Allocation Optimization when Solving the Control Problems in Organizational Systems. Journal of Physics: Conference Series, 2018, vol. 973, no. 1, pp. 12-40. DOI: 10.1088/1742-6596/973/1/012040
5. Rezig S., Ezzeddine W., Turki S., Rezg N. Mathematical Model for Production Plan Optimization: a Case Study of Descrete Event Systems. Mathematics, 2020, no. 8(6), pp. 955-971. DOI: 10.3390/math8060955
6. Ganicheva A.V., Ganichev A.V. A Method for Solving the Problem of Optimizing the Distribution of an Integer Resource. Applied Mathematics and Control Sciences, 2021, no. 4, pp. 42-55. DOI: 10.15593/2499-9873/2021.4.03
7. Lazarev A.A., Musatova E.G. Integer Statements of the Problem of Forming Railway Trains and Schedules of their Movement. Management of Large Systems, 2012, vol. 38, pp. 161-169.
8. Gainanov D.N., Ignatov A.N., Naumov A.V., Rasskazova V.A. On Track Procession Assignment Problem at the Railway Network Sections. Automation and Remote Control, 2020, vol. 81, no. 6, pp. 967-977. DOI: 10.1134/S0005117920060028
9. Kabulova E.G. Intelligent Management of Multi-Stage Systems of Metallurgical Production. Modeling, Optimization, and Information Technology, 2018, vol. 7, no. 1(24), pp. 341-351.
10. Gitman M.B., Trusov P.V., Fedoseev S.A. On Optimization of Metal Forming with Adaptable Characteristics. Journal of Applied Mathematics and Computing, 2020, vol. 7, no. 2, pp. 387-396. DOI: 10.1007/BF03012200
11. Gainanov D.N., Berenov D.A. Algorithm for Predicting the Quality of the Product of Metallurgical Production. CEUR Workshop Proceedings, Petrovac, 2017, vol. 1987, pp. 194-200.
12. Qiu Y., Wang L., Xu X., Fang X., Pardalos P. Scheduling a Realistic Hybrid Flow Shop with Stage Skipping and Adjustable Processing Time in Steel Plants. Applied Soft Computing, 2018, vol. 64, pp. 536-549.
13. Kong Min, Pei Jun, Xu Jin, Liu Xinbao, Pardalos P. A Robust Optimization Approach for Integrated Steel Production and Batch Delivery Scheduling with Uncertain Rolling Times and Deterioration Effect. International Journal of Production Research, 2020, vol. 58, no. 17, pp. 5132-5154. DOI: 10.1080/00207543.2019.1693659
14. Long Jianyu, Sun Zhenzhong, Pardalos P., Bai Yun, Zhang Shaohui, Li Chuan. A Robust Dynamic Scheduling Approach Based on Release Time Series Forecasting for the Steelmaking Continuous Casting Production. Applied Soft Computing, 2020, vol. 92, article ID: 106271. DOI: 10.1016/j.asoc.2020.106271
15. Gainanov D.N., Mladenovic N., Urosevic D., Rasskazova V.A. Heuristic Algorithm for Finding the Maximum Independent Set with Absolute Estimate of the Accuracy. CEUR-WS Proceedings, Omsk, 2018, vol. 2098, pp. 141-149.