NP-complexity of Assignment Task of Batches Among Executers Groups
( Pp. 47-54)
More about authors
Ignatyev Yuriy V.
postgraduate student; Bauman Moscow State Technical University; Moscow, Russian Federation
Bauman Moscow State Technical University
Moscow, Russian Federation Afanasyev Gennady I. Cand. Sci. (Eng.), Associate Professor; associate professor; Bauman Moscow State Technical University; Moscow, Russian Federation
Bauman Moscow State Technical University
Moscow, Russian Federation Afanasyev Gennady I. Cand. Sci. (Eng.), Associate Professor; associate professor; Bauman Moscow State Technical University; Moscow, Russian Federation
Abstract:
The paper presents a proof of the polynomial-time reduction of the studied scheduling problem, the assignment task of batches among executers groups, to a generalized variation of the NP-complete Weighted Vertex Cover problem. The initial data and constraints of the problem under study are represented by a hypergraph, utilizing soft edges to circumvent the combinatorial explosion in the processing variants for batches. The research objectives were to provide a formal proof of the NP-completeness of the studied problem and to explore methods and algorithms for solving related problems in the field of computational complexity theory, which is adjacent to scheduling theory. The study proves the polynomial-time reduction of the initial data and constraints of the assignment task of batches among executers groups to a variation of the Weighted Vertex Cover problem. This variation is similar to the Vertex Cover with Hard Capacities (VCHC) problem but is defined on a hypergraph. The reduction avoids the combinatorial explosion of processing variants for batches on executers groups by means of soft edges. It is established that within the field of computational complexity theory, there exist methods and algorithms for solving analogous problems, and their underlying concepts can be potentially applied to solving the problem studied in this work.
How to Cite:
Ignatyev Yu.V. and Afanasyev G.I. NP-complexity of assignment task of batches among executers groups. Computational Nanotechnology. 13, 1 (2026), 47–54. DOI: 10.33693/2313-223X-2026-13-1-47-54. EDN: MKWRNG
Reference list:
Levin L.A. Universal sequential search problems. Problems of Information Transmission. 1973. Vol. 9. No. 3. Pp. 115–116. (In Rus.)
Cook S.A. The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM Symposium on Theory of Computing – STOC’71. N.Y., N.Y., USA: ACM Press, 1971. Pp. 151–158.
Garey M.R., Johnson D.S. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman (ed.). New York: Bell Telephone Laboratories, Incorporated, 1979. 340 p.
Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. 1976. Vol. 1. No. 2. Pp. 117–129. DOI: 10.1287/moor.1.2.117.
Guha S. et al. Capacitated vertex covering. Journal of Algorithms. 2003. Vol. 48. No. 1. Pp. 257–270. DOI: 10.1016/S0196-6774(03)00053-1.
Kao M.-J. Iterative partial rounding for vertex cover with hard capacities. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. Pp. 2638–2653.
Karp R.M. Reducibility among combinatorial problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. (50 years of integer programming 1958–2008)
Khobotov E.N., Ermolova M.A. Formation of work plans and schedules at enterprises with conveyor assembly. In: IFIP advances in information and communication technology. 2021. Pp. 572–579.
Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics. 1977. Vol. 1. Pp. 343–362. DOI: 10.1016/S0167-5060(08)70743-X.
Nemhauser G.L., Trotter L.E. Vertex packings: Structural properties and algorithms. Math. Program. 1975. Vol. 8. No. 1. Pp. 232–248. DOI: 10.1007/BF01580444.
Vazirani V.V. Approximation algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. 380 p.
Wong S.C. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. ArXiv Preprint. 2017. 15 p.
Cook S.A. The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM Symposium on Theory of Computing – STOC’71. N.Y., N.Y., USA: ACM Press, 1971. Pp. 151–158.
Garey M.R., Johnson D.S. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman (ed.). New York: Bell Telephone Laboratories, Incorporated, 1979. 340 p.
Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. 1976. Vol. 1. No. 2. Pp. 117–129. DOI: 10.1287/moor.1.2.117.
Guha S. et al. Capacitated vertex covering. Journal of Algorithms. 2003. Vol. 48. No. 1. Pp. 257–270. DOI: 10.1016/S0196-6774(03)00053-1.
Kao M.-J. Iterative partial rounding for vertex cover with hard capacities. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. Pp. 2638–2653.
Karp R.M. Reducibility among combinatorial problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. (50 years of integer programming 1958–2008)
Khobotov E.N., Ermolova M.A. Formation of work plans and schedules at enterprises with conveyor assembly. In: IFIP advances in information and communication technology. 2021. Pp. 572–579.
Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics. 1977. Vol. 1. Pp. 343–362. DOI: 10.1016/S0167-5060(08)70743-X.
Nemhauser G.L., Trotter L.E. Vertex packings: Structural properties and algorithms. Math. Program. 1975. Vol. 8. No. 1. Pp. 232–248. DOI: 10.1007/BF01580444.
Vazirani V.V. Approximation algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. 380 p.
Wong S.C. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. ArXiv Preprint. 2017. 15 p.
Keywords:
scheduling theory, NP-complexity, vertex cover, hypergraph, weighted vertex cover, combinatorial optimization, short-term scheduling, dynamic task allocation, dispatching, semi-online scheduling, machine scheduling.
