?
Pattern-Based Heuristic for the Cell Formation Problem in Group Technology
Ch. 2. P. 11–50.
In press
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 (positions) in an input file. We define a pattern as a collection of positions in an instance problem represented by its input file (matrix). We illustrate the notion of pattern by means of some well known problems in COP among them the Linear Ordering Problem, Cell Formation Problem (CFP) just to mention a couple. The CFP is defined on a Boolean input matrix which rows represent machines and columns - parts. The CFP consists in finding three optimal objects: a block-diagonal collection of rectangles, a rows (machines) permutation, and a columns (parts) permutation such that the grouping efficacy is maximized. The suggested heuristic combines two procedures: the pattern-based procedure to build an initial solution and an improvement procedure to obtain a final solution with high grouping efficacy for the CFP. Our computational experiments with the most popular set of 35 benchmark instances show that our heuristic outperforms all well known heuristics and returns either the best known or improved solutions to the CFP.
Martinez-Saito M., Algorithms 2025 Vol. 18 No. 12 Article 741
Detecting trajectories of hierarchical structures in a dynamical system of multiple interacting particles is an open problem that is typically addressed by imposing strong constraints on the structures to be found. Here, we describe BUNCH, a dynamical filtering algorithm that can efficiently and on-the-fly fit dynamical trajectories of multiple particles to a tree structure of ...
Added: December 1, 2025
Ilyin A., Закон 2024 № 9 С. 91–98
Every serious lawyer in his professional life is faced with a situation when, coming into contact with unknown legal matter in his work, revealing the hidden meaning of legal norms or legal institutions, he finds an unexpected way out of the impasse, discovering something new in law. Is such an expert analytical work of a ...
Added: September 26, 2024
Маневич В. Е., Российский химико- техногогический университет им. Менделеева, 2012.
В книге представлена информация по важнейшим эксплуатационным свойствам стекол, технологии их производства, перерабготки в изделия, методам разбраковки и контроля качкства. Авторы книги являются ведущими специалистами важнейших направлений науки о стекле, промышленной технологии производства материалов и изделий из стекла. ...
Added: October 2, 2022
Kham T., Вестник Томского государственного университета. Философия. Социология. Политология 2022 № 65 С. 37–50
The problems of automation of research activities are considered, primarily from the perspective of the epistemic potential of gaining new scientific knowledge without the participation of a human as a subject of science. The bases of automation are considered from the standpoint of jointly working methodological approaches to cognition: empiricism and logical positivism. The author ...
Added: July 30, 2022
Sulimov P., Kertesz-Farkas A., Journal of Proteome Research 2020 No. 19(4) P. 1481–1490
Peptide-spectrum-match (PSM) scores used in database searching are calibrated to spectrum- or spectrum-peptide-specific null distributions. Some calibration methods rely on specific assumptions and use analytical models (e.g., binomial distributions), whereas other methods utilize exact empirical null distributions. The former may be inaccurate because of unjustified assumptions, while the latter are accurate, albeit computationally exhaustive. Here, ...
Added: June 29, 2020
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
Lokshin I., Политическая экспертиза: ПОЛИТЭКС 2019 Т. 15 № 1 С. 45–58
The paper makes an attempt at inserting (positivistic) political science in a broader epistemological
context than it is usually conceived. The implied context is that of the contingency of the
human world which was pointed out by Aristotle in “Nicomachean Ethics” when he stated that
politics deals more with particulars than with general principles, and more with changeable ...
Added: October 29, 2019
Максимова Елизавета Андреевна, В кн.: Системное моделирование социально-экономических процессов: труды 40-й Международной научной школы-семинара.: Воронеж: Воронежский государственный педагогический университет, 2017. С. 530–533.
The creation of an effective regular timetable for railway infrastructure provides a number of advantages for both passengers being transported and for staff is involved in the management and maintenance of the network. The for-mation of a regular schedule for it under conditions of variable demand is an ac-tual problem and a rather difficult task. ...
Added: November 21, 2018
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 Utkina, Mikhail Batsyn, Ekaterina Batsyna, , in: Discrete Optimization and Operations Research/9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings.: Springer, 2016. P. 244–255.
We consider a fractional 0-1 programming problem arising in manufacturing. The problem consists in clustering of machines together with parts processed on these machines into manufacturing cells so that intra-cell processing of parts is maximized and inter-cell movement is minimized. This problem is called Cell Formation Problem (CFP) and it is an NP-hard optimization problem ...
Added: October 3, 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
Toporkov V., Yemelyanov D., Anna Toporkova, , in: PROCEEDINGS 46th International Conference on Parallel Processing Workshops ICPPW 2017.: Piscataway: IEEE Computer Society, 2017. P. 271–280.
In this work, a job-flow scheduling approach for Grid virtual organizations (VOs) is proposed and studied. Users’ and resource providers’ preferences, VOs internal policies, resources geographical distribution along with local private utilization impose specific requirements for efficient scheduling according to different, usually contradictive, criteria. With increasing resources utilization level the available resources set and corresponding ...
Added: January 30, 2018
Toporkov V., Yemelyanov D., Anna Toporkova, , in: Supercomputing. RuSCDays 2017. Communications in Computer and Information Science. Revised Selected Papers.Vol. 793.: Springer, 2017. P. 482–493.
In this work, a job-flow scheduling approach for grid virtual organizations (VOs) is proposed and studied. Users’ and resource providers’ preferences, VOs internal policies, resources geographical distribution along with local private utilization impose specific requirements for efficient scheduling according to different, usually contradictive, criteria. With increasing level of resources utilization, the set of available resources ...
Added: January 30, 2018
Toporkov V., Yemelyanov D., Anna Toporkova et al., , in: Parallel Computing Technologies. 14th International Conference, PaCT 2017, Nizhny Novgorod, Russia, September 4-8, 2017, ProceedingsVol. 10421: Lecture Notes in Computer Science .: Cham, Switzerland: Springer, 2017. P. 372–383.
In this work, a job-flow scheduling approach for Grid virtual organizations (VOs) is proposed and studied. Users’ and resource providers’ preferences, VOs internal policies, resources geographical distribution along with local private utilization impose specific requirements for efficient scheduling according to different, usually contradictive, criteria. With increasing resources utilization level the available resources set and corresponding ...
Added: January 26, 2018
Ilya Bychkov, Mikhail Batsyn, Computers & Operations Research 2018 No. 91 P. 112–120
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 ...
Added: December 6, 2017
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
Baibikova T., В кн.: Актуальные проблемы развития речи и межкультурной коммуникации. Сборник материалов IX Кирилло-Мефодиевских чтений в Международном гуманитарно-лингвистическом институте 17 мая 2016 года.: М.: МФЮА, 2016. С. 109–113.
В статье рассматриваются концепты «когнитология» и «эвристика», которые являются неотъемлемой частью когнитивно-эвристической модели перевода. Обосновывается применимость данных понятий к такой отрасли человеческих знаний, как перевод и переводоведение. ...
Added: March 9, 2017
Ilya Bychkov, Mikhail Batsyn, Panos M. Pardalos, , in: Models, Algorithms, and Technologies for Network Analysis. Springer Proceedings in Mathematics & StatisticsVol. 197.: Springer, 2017. P. 11–26.
In our paper, we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell ...
Added: November 29, 2016
Toporkov V., Anna Toporkova, Tselishchev A. et al., , in: Intelligent Distributed Computing IX. Proceedings of the 9th International Symposium on Intelligent Distributed Computing – IDC'2015, Guimarães, Portugal, October 2015Vol. 616: Studies in Computational Intelligence.: Dordrecht, L., Cham, Heidelberg, NY: Springer, 2016. P. 189–198.
In this paper, we propose a meta-data based approach for a deliberate job flow distribution in computing environments, such as utility Grids. Under condi- tions of a heterogeneous job flow composition and a variety of resource domains, we examine how different job and resource characteristics affect the efficiency of the scheduling process. Based on the ...
Added: July 13, 2016
Komosko L. F., Batsyn M. V., Информационные технологии 2015 № 7 С. 488–494
Graph coloring problem is one of the classical combinatorial optimization problems. This problem consists in finding the minimal number of colors in which it is possible to color vertices of a graph so that any two adjacent vertices are colored in different colors. The graph coloring problem has a wide variety of applications including timetabling ...
Added: July 13, 2015