Geodesic
Construction of schedules for the performance of task packages in multi-stage systems when forming sets of results and limitations
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 15 (2022) no. 2, pp. 70-85 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider a complex problem on scheduling of performance of task packages in a multi-stage systems when there is a limit on the duration of time intervals for its operation. Solution of such a problem implies (taking into account the requirements of forming sets of results) determination of composition of packages, groups of packages performed within time intervals of specified duration, schedules for performance of packages on devices of multi-stage system. To determine complex solutions, the apparatus of the theory of hierarchical games is used. We construct the model of a hierarchical game to make decision on the composition of packages, package groups and scheduling of package performance. The model takes into account the requirement to create sets from the results of performance of task packages. The problem of determining the composition of groups of packages is NP-hard, so solution of this problem requires the use of approximate optimization methods. We formulate a method for constructing an initial solution based on the composition of groups of packages and a method for distributing the results of performance of task packages by sets. Also, we formulate a method for optimizing the composition of groups of task packages taking into account the formation of sets. A method for construction of new solutions by composition of group of task packages is formulated. We obtain conditions that allow to determine packages excluded from groups based on the number of results of performance of task of each type, which are not included in sets. The method of local optimization of solutions by composition of packages groups is proposed. The software for the considered method of complex optimization of the compositions of task packages, groups of task packages, and schedules for performance of task packages from groups is implemented.
Keywords: task packages, multi-stage system, sets of results, restriction on duration of time intervals of system operation. 
@article{VYURU_2022_15_2_a5,
     author = {K. V. Krotov and A. V. Skatkov},
     title = {Construction of schedules for the performance of task packages in multi-stage systems when forming sets of results and limitations},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {70--85},
     year = {2022},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2022_15_2_a5/}
}
TY  - JOUR
AU  - K. V. Krotov
AU  - A. V. Skatkov
TI  - Construction of schedules for the performance of task packages in multi-stage systems when forming sets of results and limitations
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2022
SP  - 70
EP  - 85
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURU_2022_15_2_a5/
LA  - ru
ID  - VYURU_2022_15_2_a5
ER  - 
%0 Journal Article
%A K. V. Krotov
%A A. V. Skatkov
%T Construction of schedules for the performance of task packages in multi-stage systems when forming sets of results and limitations
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2022
%P 70-85
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/VYURU_2022_15_2_a5/
%G ru
%F VYURU_2022_15_2_a5
K. V. Krotov; A. V. Skatkov. Construction of schedules for the performance of task packages in multi-stage systems when forming sets of results and limitations. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 15 (2022) no. 2, pp. 70-85. http://geodesic.mathdoc.fr/item/VYURU_2022_15_2_a5/

[1] Krotov K. V., “A Complex Method for Determining Effective Solutions for the Composition of Data Batches and Schedules of Their Processing in Conveyor Systems”, Computational technologies, 23:3 (2018), 58–76 (in Russian)

[2] Krotov K. V., “Justification of Methods for Constructing Complex Schedules for Processing Data Batches Under the Condition of Rapid Formation of Sets of Results”, Bulletin of the Voronezh State University. System Analysis and Information Technologies, 2018, no. 4, 58–72 (in Russian)

[3] Krotov K. V., “Building Complex Schedules for Processing Data Packets in a pipeline System When Setting Restrictions on the Duration of Time Intervals for Its Operation”, Proceedings of Educational Institutions of Communications, 6:3 (2020), 75–90 (in Russian) | MR

[4] Tanaev V. S., Sotskov Yu.N., Strusevich V. A., Theory of Schedules. Multi-Stage Systems, Nauka, M., 1989 (in Russian) | MR

[5] Lazarev A. A., Musatova E. G., Kvaratskheliya A. G., Gafarov E. R., Theory of Schedules. Objectives of the Management of Transport Systems, MSU, M., 2012 (in Russian)

[6] Lazarev A. A., Methods and Algorithms for Solving Problems of the Theory of Schedules for One and Several Devices and Their Application for Combinatorial Optimization Problems, PhD thesis, M., 2007 (in Russian)

[7] Kobak V. G., Methodology of Comparative-Criteria Analytical Evaluation of Distributive Tasks and Means of Its Software and Algorithmic Support, Dissertation of the Doctor of Technical Sciences, Rostov-on-Don, 2008 (in Russian)

[8] Neidorf R. A., Zhigulin A. A., “Investigation of a Selective Permutation Method for Solving an Inhomogeneous Distributive Problem Using Multi-Permutations”, System Analysis, Management and Information Processing, Proceedings of the 3rd International Seminar, 2012, 58–68 (in Russian)

[9] Basar Ogun, Cigdem Alabas-Uslu, “Mathematical Models for a Batch Scheduling Problem to Minimize Earliness and Tardiness”, Journal of Industrial Engineering and Management, 11:3 (2018), 390–405 | DOI

[10] XiaoLin Li, Yu Wang, “Scheduling Batch Processing Machine Using Max-Min Ant System Algorithm Improved by a Local Search Method”, Mathematical Problems in Engineering, 2018 (2018), 3124182 | DOI | MR | Zbl

[11] Ba-Yi Cheng, Hua-Ping Chen, Shuan-Shi Wang, “Improved Ant Colony Optimization Method for Single Batch-Processing Machine with Non-Identical Job Sizes”, Journal of System Simulation, 21:9 (2009), 2687–2695

[12] F. Koehler, S. Khuller, “Optimal Batch Schedules for Parrallel Machines”, Algorithms and Data Structures, 13th International Symposium, Springer, Berlin, 2013, 475–486 | DOI | MR | Zbl

[13] I. Surjandari, A. Rachman, A. Purdianta, A. Dhini, “The Batch Scheduling Model for Dynamic Multi-Item, Multi-Level Production in an Assembly Job Shop with Parallel Machines”, International Journal of Technology, 2015, no. 1, 84–96 | DOI

[14] L. Monch, H. Balasubramanian, J. Fowler, M. Pfund, “Heuristic Scheduling of Jobs on Parallel Batch Machines with Incompatible Job Families Andunequal Ready Times”, Computers Operations Research, 32 (2005), 2731–2750 | DOI | Zbl

[15] Th. Dang, B. Frankovic, I. Budinska, “Using Heuristic Search for Solving Single Machine Batch Processing Problems”, Computing and Informatics, 25 (2006), 405–420 | Zbl

[16] R. Kohn, O. Rose, Ch. Laroque, “Study on Multi-Objective Optimization for Parallel Batch Machine Scheduling Using Variable Neighbourhood Search”, Proceedings of the 2013 Winter Simulation Conference, 2013, 3654–3670 | DOI

[17] Shisheng Li, T.C.E. Cheng, C.T. Ng, Jinjiang Yuan, “Single-Machine Batch Scheduling with Job Processing Time Compatibility”, Theoretical Computer Science, 583 (2015), 57–66 | DOI | MR | Zbl

[18] Miaomiao Jin, Xiaoxia Liu, Wenchang Luo, “Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection”, Mathematics, 2020, no. 8, 258 | DOI | MR

[19] Krotov K. V., “The Use of the Apparatus of Genetic Algorithms in the Formation of Decisions on the Composition of Data Batches in the Two-Level Task of Constructing Complex Schedules for Their Processing”, Automated Technologies and Production. International Scientific and Technical Journal, 2017, no. 2(16), 23–34 (in Russian)