Construction of Schedules for the Performance of Task Packages in Multi-Stage Systems when Forming Sets of Results and Limitations

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.

References

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, 2018, vol. 23, no. 3, pp. 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, pp. 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, 2020, vol. 6, no. 3, pp. 75-90. (in Russian)
4. Tanaev V.S., Sotskov Yu.N., Strusevich V.A. Teoriya raspisanij. Mnogostadijnye sistemy [Theory of Schedules. Multi-Stage Systems]. Moscow, Nauka, 1989. (in Russian)
5. Lazarev A.A., Musatova E.G., Kvaratskheliya A.G., Gafarov E.R. Teoriya raspisanij. Zadachi upravleniya transportnymi sistemami [Theory of Schedules. Objectives of the Management of Transport Systems]. Moscow, MSU, 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, Moscow, 2007. (in Russian)
7. Kobak V.G. Metodologiya sopostavitel'no-kriterial'noj analiticheskoj ocenki raspredelitel'nyh zadach i sredstva ee programmno-algoritmicheskoj podderzhki [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, pp. 58-68. (in Russian)
9. Basar Ogun, Cigdem Alabas-Uslu Mathematical Models for a Batch Scheduling Problem to Minimizе Earliness and Tardiness. Journal of Industrial Engineering and Management, 2018, no. 11 (3), pp. 390-405. DOI: 10.3926/jiem.2541
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, no. 2018, Article ID: 3124182. DOI: 10.1155/2018/3124182
11. Cheng Ba-Yi, Chen Hua-Ping, Wang Shuan-Shi. Improved Ant Colony Optimization Method for Single Batch-Processing Machine With non-Identical Job Sizes. Journal of System Simulation, 2009, vol. 21, no. 9, pp. 2687-2695.
12. Koehler F., Khuller S. Optimal Batch Schedules for Parrallel Machines. Algorithms and Data Structures: 13th International Symposium, 2013, pp. 475-486.
13. Surjandari I., Rachman A., Purdianta, Dhini A. 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, pp. 84-96. DOI: 10.14716/ijtech.v6i1.783
14. Monch L., Balasubramanian H., Fowler J.W., Pfund M.E. Heuristic Scheduling of Jobs on Parallel Batch Machines With Incompatible Job Families Andunequal Ready Times. Computers & Operations Research, 2005, no. 32, pp. 2731-2750.
15. Dang Th.-T., Frankovic B., Budinska I. Using Heuristic Search for Solving Single Machine Batch Processing Problems. Computing and Informatics, 2006, no. 25, pp. 405-420.
16. Kohn R., Rose O., Laroque Ch. Study on Multi-Objective Optimization for Parallel Batch Machine Scheduling Using Variable Neighbourhood Search. Proceedings of the 2013 Winter Simulation Conference, 2013, pp. 3654-3670.
17. Shisheng Li, Cheng T.C.E., Ng C.T, Jinjiang Yuan. Single-Machine Batch Scheduling with Job Processing Time Compatibility. Theoretical Computer Science, 2015, no. 583, pp. 57-66. DOI:10.1016/j.tcs.2015.03.043
18. Miaomiao Jin, Xiaoxia Liu, Wenchang Luo. Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection. Mathematics, 2020, no. 8, Article ID: 258. DOI: 10.3390/math8020258
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), pp.23-34. (in Russian)