Boris Goldengorin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Boris Goldengorin has a total of 69 co-authors. Here are the top co-authors by number of shared publications:
Panos M. Pardalos
University of Florida
10 shared publicationsGerard Sierksma
9 shared publications- Diptesh Ghosh
Indian Institute of Management Ahmedabad
8 shared publications - Dmitry Krushinsky
University of Groningen
6 shared publications - Mikhail Batsyn
National Research University Higher School of Economics
5 shared publications - Panos M. Pardalos
Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA
5 shared publications
Latest Publications
- 22 September 2026
- Published by Elsevier in Information Sciences
- Vol. 762
Reducing the weighted tool replacement problem to min-cost flow on a linear-size graph
- 22 September 2026
- Published by Elsevier in Information Sciences
- Vol. 762
Reducing the weighted tool replacement problem to min-cost flow on a linear-size graph
- 1 January 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 38 (1) , 86-101
A Computational Study of the Tool Replacement Problem
In the Tool Replacement Problem (TRP) for the given sequence of jobs, we consider a discretized interval where each point in time corresponds to a specific job and its collection of tools sufficient to complete that job. A passive interval w.r.t. a specific tool is an interval where that tool is not used at any point within that interval but is used at the boundary points in time. The TRP aims to find a loading schedule of tools (tool switches) that minimizes the total number of tool loadings in the magazine. Based on the concept of a passive interval, we introduce our reformulation of the TRP as follows. The minimum total number of tool loadings (switches) in the TRP is equal to the difference between the total number of tools for all scheduled jobs with tool repetitions and the maximum total number of passive intervals. We solve the TRP to optimality by designing and implementing two algorithms: one for finding the optimal objective function value (Insertion Greedy Algorithm (IGA)) and the other (To Full Magazine (ToFullMag) algorithm) for finding an optimal solution, that is, an optimal sequence of tool loadings. We apply our reformulation of the TRP to design the IGA full algorithm starting with IGA and continuing with ToFullMag. The IGA full achieves the best possible running time and thus settles the computational complexity of TRP. We prove that IGA full outperforms the most popular Keep Tool Needed Soonest (KTNS) algorithm by at least an order of magnitude in terms of CPU time. Moreover, after replacing the KTNS algorithm by IGA full within the state-of-the-art Hybrid Genetic Searches heuristic for solving the job Scheduling and tool Switching Problem (SSP), our computational study shows the reduction of CPU times by at least an order of magnitude for medium- and large-scale SSP data sets. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: The research of Y. Qiu and P. M. Pardalos is supported by the National Natural Science Foundation of China [Grant 72371135], the National Foreign Expert Program from the Ministry of Science and Technology of China [Grant G2021014038L], and the Key Project from Jiangsu Social Science Foundation [Grant 23GLA001]. M. Cherniavskii and B. Goldengorin were supported by the Ministry of Science and Higher Education of the Russian Federation (Goszadaniye), Project No. FSMG-2024-0025. The work of P. M. Pardalos was conducted within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE). The article was prepared within the framework of the project “Scientific and Educational Mathematical Center, North-West Center for Mathematical Research named after Sofia Kovalevskaya”, 2025. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0474 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0474 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 1 January 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 38 (1) , 86-101
A Computational Study of the Tool Replacement Problem
In the Tool Replacement Problem (TRP) for the given sequence of jobs, we consider a discretized interval where each point in time corresponds to a specific job and its collection of tools sufficient to complete that job. A passive interval w.r.t. a specific tool is an interval where that tool is not used at any point within that interval but is used at the boundary points in time. The TRP aims to find a loading schedule of tools (tool switches) that minimizes the total number of tool loadings in the magazine. Based on the concept of a passive interval, we introduce our reformulation of the TRP as follows. The minimum total number of tool loadings (switches) in the TRP is equal to the difference between the total number of tools for all scheduled jobs with tool repetitions and the maximum total number of passive intervals. We solve the TRP to optimality by designing and implementing two algorithms: one for finding the optimal objective function value (Insertion Greedy Algorithm (IGA)) and the other (To Full Magazine (ToFullMag) algorithm) for finding an optimal solution, that is, an optimal sequence of tool loadings. We apply our reformulation of the TRP to design the IGA full algorithm starting with IGA and continuing with ToFullMag. The IGA full achieves the best possible running time and thus settles the computational complexity of TRP. We prove that IGA full outperforms the most popular Keep Tool Needed Soonest (KTNS) algorithm by at least an order of magnitude in terms of CPU time. Moreover, after replacing the KTNS algorithm by IGA full within the state-of-the-art Hybrid Genetic Searches heuristic for solving the job Scheduling and tool Switching Problem (SSP), our computational study shows the reduction of CPU times by at least an order of magnitude for medium- and large-scale SSP data sets. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: The research of Y. Qiu and P. M. Pardalos is supported by the National Natural Science Foundation of China [Grant 72371135], the National Foreign Expert Program from the Ministry of Science and Technology of China [Grant G2021014038L], and the Key Project from Jiangsu Social Science Foundation [Grant 23GLA001]. M. Cherniavskii and B. Goldengorin were supported by the Ministry of Science and Higher Education of the Russian Federation (Goszadaniye), Project No. FSMG-2024-0025. The work of P. M. Pardalos was conducted within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE). The article was prepared within the framework of the project “Scientific and Educational Mathematical Center, North-West Center for Mathematical Research named after Sofia Kovalevskaya”, 2025. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0474 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0474 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 3 February 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for A Computational Study of the Tool Replacement Problem
This software aims to compare IGA, IGA-bit, IGA-full and KTNS algorithms for the Tool Replacement Problem. The experiments were conducted on a server running a 64-bit Windows 10 operating system, equipped with Intel(R) Core i5 CPU 2.6 GHz and 4 GB of RAM. To compare the algorithms for each of the 10 problem instances of data sets from Catanzaro et al. we generate 105 job sequences. Additionally, for each of the 5 problem instances of data sets from Mecler et al. we generate 2·105 job sequences.
- 3 February 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for A Computational Study of the Tool Replacement Problem
This software aims to compare IGA, IGA-bit, IGA-full and KTNS algorithms for the Tool Replacement Problem. The experiments were conducted on a server running a 64-bit Windows 10 operating system, equipped with Intel(R) Core i5 CPU 2.6 GHz and 4 GB of RAM. To compare the algorithms for each of the 10 problem instances of data sets from Catanzaro et al. we generate 105 job sequences. Additionally, for each of the 5 problem instances of data sets from Mecler et al. we generate 2·105 job sequences.
- 10 December 2016
- Published by Springer Nature in Journal of Global Optimization
- Vol. 68 (3) , 601-622
The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
- 10 December 2016
- Published by Springer Nature in Journal of Global Optimization
- Vol. 68 (3) , 601-622
The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
- 12 February 2016
- Published by Springer Nature in The International Journal of Advanced Manufacturing Technology
- Vol. 86 (9-12) , 3315-3331
Minimizing the makespan for a serial-batching scheduling problem with arbitrary machine breakdown and dynamic job arrival
- 12 February 2016
- Published by Springer Nature in The International Journal of Advanced Manufacturing Technology
- Vol. 86 (9-12) , 3315-3331
Minimizing the makespan for a serial-batching scheduling problem with arbitrary machine breakdown and dynamic job arrival
- 11 November 2014
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 30 (4) , 727-747
Preemptive scheduling in a two-stage supply chain to minimize the makespan
This paper deals with the problem of preemptive scheduling in a two-stage supply chain framework. The supply chain environment contains two stages: production and transportation. In the production stage jobs are processed on a manufacturer's bounded serial batching machine, preemptions are allowed, and set-up time is required before a new batch is processed. In the transportation stage each batch is delivered to a customer by a single vehicle. The objective is to minimize the makespan by making decisions for both mutually coordinated stages. Specifically, two versions are studied. The first one is that all jobs are available to be processed at time zero, and the second one is that jobs have different release times. An time algorithm is developed for the first version, and we show that it can produce the optimal schedule for the entire problem. For the second version, based on some useful properties we have designed an time heuristic and a novel lower bound. The worst-case performance ratio of our algorithm is bounded by 2. Our computational study with random instances of different scales shows high-quality solutions for either small-scale or large-scale instances returned in a reasonable PC times.
- 11 November 2014
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 30 (4) , 727-747
Preemptive scheduling in a two-stage supply chain to minimize the makespan
This paper deals with the problem of preemptive scheduling in a two-stage supply chain framework. The supply chain environment contains two stages: production and transportation. In the production stage jobs are processed on a manufacturer's bounded serial batching machine, preemptions are allowed, and set-up time is required before a new batch is processed. In the transportation stage each batch is delivered to a customer by a single vehicle. The objective is to minimize the makespan by making decisions for both mutually coordinated stages. Specifically, two versions are studied. The first one is that all jobs are available to be processed at time zero, and the second one is that jobs have different release times. An time algorithm is developed for the first version, and we show that it can produce the optimal schedule for the entire problem. For the second version, based on some useful properties we have designed an time heuristic and a novel lower bound. The worst-case performance ratio of our algorithm is bounded by 2. Our computational study with random instances of different scales shows high-quality solutions for either small-scale or large-scale instances returned in a reasonable PC times.
- 3 May 2014
- Published by Springer Nature
- p. 77-89
A Pseudo-Boolean Approach to the Market Graph Analysis by Means of the p-Median Model
- 3 May 2014
- Published by Springer Nature
- p. 77-89
A Pseudo-Boolean Approach to the Market Graph Analysis by Means of the p-Median Model
- 23 February 2014
- Published by Springer Nature in Journal of Global Optimization
- Vol. 61 (1) , 91-108
Pareto-optimal front of cell formation problem in group technology
- 23 February 2014
- Published by Springer Nature in Journal of Global Optimization
- Vol. 61 (1) , 91-108
Pareto-optimal front of cell formation problem in group technology
- 3 December 2013
- Published by Springer Nature in Journal of Heuristics
- Vol. 20 (1) , 107-124
A backbone based TSP heuristic for large instances
- 3 December 2013
- Published by Springer Nature in Journal of Heuristics
- Vol. 20 (1) , 107-124
A backbone based TSP heuristic for large instances