?
An efficient exact model for the cell formation problem with a variable number of production cells
Computers & Operations Research. 2018. No. 91. P. 112–120.
Ilya Bychkov, Mikhail Batsyn
The Cell Formation Problem has been studied as an optimization problem in manufacturing for more than 90 years. It consists of grouping machines and parts into manufacturing cells in order to maximize loading of cells and minimize movement of parts from one cell to another. Many heuristic algorithms have been proposed which are doing well even for large-sized instances. However, only a few authors have aimed to develop exact methods and most of these methods have some major restrictions such as a fixed number of production cells for example. In this paper we suggest a new mixed-integer linear programming model for solving the cell formation problem with a variable number of manufacturing cells. The popular grouping efficacy measure is used as an objective function. To deal with its fractional nature we apply the Dinkelbach approach. Our computational experiments are performed on two testsets: the first consists of 35 well-known instances from the literature and the second contains 32 instances less popular. We solve these instances using CPLEX software. Optimal solutions have been found for 63 of the 67 considered problem instances and several new solutions unknown before have been obtained. The computational times are greatly decreased comparing to the state-of-art approaches
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 2026
Shipilov F., Barnyakov A., Ivanov A. et al., / Series Physics "arxiv.org". 2026.
A fast simulation of the detector response is a vital task in high-energy physics (HEP). Traditional Monte-Carlo methods form the backbone of modern particle physics simulation software but are computationally expensive. We present a machine-learning-based approach to fast simulation of the Focusing Aerogel Ring Imaging Cherenkov (FARICH) detector response. Given a particle track and momentum, ...
Added: May 19, 2026
Derkacheva A., Sakirkina M., Kraev G. et al., /. 2026.
Comprehensive data on natural hazards and their consequences are crucial for effective for risk assessment, adaptation planning, and emergency response. However, many countries face challenges with fragmented, inconsistent, and inaccessible data, particularly regarding local-scale events. To address this data gap in Russia, we developed an end-to-end processing pipeline that scrapes news from various online sources, ...
Added: April 28, 2026
Pilé I., Deng Y., Shchur L., / Series arXiv "math". 2026. No. 2604.10254.
We investigate the spatial overlap of successive spin configurations in Markov chain Monte Carlo simulations using the local Metropolis algorithm and the Svendsen-Wang and Wolff cluster algorithms. We examine the dynamics of these algorithms for two models in different universality classes: the Ising model and the Potts model with three components. The overlap of two ...
Added: April 20, 2026
Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.
Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...
Added: April 2, 2026
Sorokin K., Beketov M., Онучин А. et al., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the ...
Added: January 15, 2026
Petrovanov I., Sergeev A., / Series Computer Science "arxiv.org". 2025. No. 2512.18332.
Transport coding reduces message delay in packet-switched networks by introducing controlled redundancy at the transport layer: original packets are encoded into coded packets, and the message is reconstructed after the first successful deliveries, effectively shifting latency from the maximum packet delay to the -th order statistic. We present a concise, reproducible discrete-event implementation of transport coding in OMNeT++, including ...
Added: December 24, 2025
Hessian-based lightweight neural network for brain vessel segmentation on a minimal training dataset
Меньшиков И. А., Бернадотт А. К., Elvimov N. S., / Series arXie "Statistical mechanics". 2025.
Accurate segmentation of blood vessels in brain magnetic resonance angiography (MRA) is essential for successful surgical procedures, such as aneurysm repair or bypass surgery. Currently, annotation is primarily performed through manual segmentation or classical methods, such as the Frangi filter, which often lack sufficient accuracy. Neural networks have emerged as powerful tools for medical image ...
Added: December 1, 2025
Rubchinskiy A., Chubarova D., / Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2025. No. WP7/2025/01.
The article examines one of the most famous examples of socio-economic systems, characterized by significant uncertainty – the S&P-500 stock market, where shares of 500 largest US companies are traded. No assumptions are made about the probabilistic characteristics of the stock market. A flexible algorithm for daily trading has been developed, based on both known fixed data ...
Added: November 9, 2025
Mikhail V. Batsyn, Ekaterina K. Batsyna, Ilya S. Bychkov, International Journal of Production Research 2020 Vol. 58 No. 20 P. 6159–6169
In the current paper we provide a proof of NP-completeness for the Cell Formation Problem (CFP) with the fractional grouping efficacy objective function. First the CFP with a linear objective function is considered. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is ...
Added: November 10, 2019
Irina Utkina, Mikhail Batsyn, , in: Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & StatisticsVol. 156.: Switzerland: Springer, 2016. P. 115–124.
The cell formation problem (CFP) is an NP-hard optimization problem considered for cell manufacturing systems. Because of its high computational complexity several heuristics have been developed for solving this problem. In this paper we present a branch and bound algorithm which provides exact solutions of the CFP. This algorithm finds optimal solutions for 13 problems ...
Added: October 23, 2018
Irina E. Utkina, Mikhail V. Batsyn, Ekaterina K. Batsyna, International Journal of Production Research 2018 Vol. 56 No. 9 P. 3262–3273
The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its ...
Added: March 11, 2018
Utkina I. E., Batsyn M. V., Программные продукты, системы и алгоритмы 2017 № 4 С. 1–10
The Cell Formation Problem (CFP) is an NP-hard optimization problem considered for cellular man- ufacturing systems. Because of its high computational complexity there have been developed a lot of heuristics and almost no exact algorithms for solving this problem. In this paper we suggest a branch- and-bound algorithm which provides exact solutions for the CFP ...
Added: October 18, 2017
Žilinskas J., Goldengorin B. I., Pardalos P. M., Journal of Global Optimization 2015 Vol. 61 No. 1 P. 91–108
The earliest approaches to the cell formation problem in group technology, dealing with a binary machine-part incidence matrix, were aimed only at minimizing the number of intercell moves (exceptional elements in the block-diagonalized matrix). Later on this goal was extended to simultaneous minimization of the numbers of exceptions and voids, and minimization of intercell moves ...
Added: January 6, 2015
Ilya Bychkov, Mikhail Batsyn, Pavel Sukhov, , in: Models, Algorithms, and Technologies for Network AnalysisVol. 59.: NY: Springer, 2013. Ch. 4 P. 43–69.
In this chapter, we introduce a new heuristic for Cell Formation Problem in its most general formulation with grouping efficiency as an objective function. Suggested approach applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated until efficiency can be increased for randomly generated configurations of cells. We consider our ...
Added: November 19, 2013
Mikhail Batsyn, Ilya Bychkov, Boris Goldengorin et al., , in: Models, Algorithms, and Technologies for Network AnalysisIssue 32.: NY: Springer, 2013. Ch. 2 P. 11–50.
In this paper we introduce a new pattern-based approach within the Linear Assignment Model with the purpose to design heuristics for a combinatorial optimization problem (COP). We assume that the COP has an additive (separable) objective function and the structure of a feasible (optimal) solution to the COP is predefined by a collection of cells ...
Added: November 19, 2013
Ilya Bychkov, Mikhail Batsyn, Panos M. Pardalos, Optimization Letters 2014 Vol. 8 No. 8 P. 2203–2210
The Cell Formation Problem (CFP) consists in an optimal grouping of the given machines and parts into cells, so that machines in every cell process as much as possible parts from this cell (intra-cell operations) and as less as possible parts from another cells (inter-cell operations). The grouping efficacy is the objective function for the ...
Added: September 21, 2013