Annotation of the results obtained in 2022
The aim of the project is researching new mathematical models and developing effective optimization algorithms for the actual scheduling problems with complex technological relations, resource constraints and inaccurate input data that arise in production and computer systems. The following main results were obtained during the first year of the project implementation. The study of computational complexity and the construction of mathematical models: 1. For the two-machine routing open shop on a link a special case with proportional processing times is investigated. The upper bound of the tight optima localization interval is described as a function of the proportionality factor. It is shown that the optimal makespan is guaranteed to coincide with the standard lower bound, if and only if the proportionality factor is not smaller than the golden ratio. 2. The NP-hardness of the problem of minimizing the total processing time of identical parts and pseudopolynomial solvability for a fixed number of parts are proved. An exact algorithm for solving this problem is proposed. Algorithms based on using of cyclic schedules are investigated. It is shown that an optimal solution may not exist in the class of cyclic schedules with subsequent compaction. Lower bounds on the optimum are constructed. The concept of L-periodic schedules is introduced, the dependence of the accuracy of the solution on L is investigated. 3. New integer programming models with continuous representation of time are proposed for scheduling problems with resources specified by convex and linear functions, and structural connections that take into account the multistage and multiprocessor nature of jobs (operations). Polynomially solvable and NP-hard cases were provided. 4. We propose an integer linear programming model and adopt solving approaches for the problem of forming clusters of client orders taking into account availability of machines and time slots. NP-hard and polynomially solvable cases are identified. 5. The connection of clustering problems and hereditary systems with problems of combinatorial optimization (scheduling theory) was studied. We investigate the connection of cluster graphs and graph matroid. We construct forbidden graph characterization of cluster graphs. Development and research of algorithms: 1. The tight optima localizatiion interval for the two-machine asymmetric proportionate routing open shop on a tree is found. A 7/6-approximation algorithm with linear running time for this problem is described. 2. A new hybrid evolutionary algorithm with optimized operators is proposed for the total weighted tardiness problem on the single machine. The NP-hardness of the optimal recombination problem in a crossover operator is proved. An enumeration approach for its solving is proposed, as well as a modified version, which allows reducing the enumeration of variants and implementing a parallel version. A computational experiment on the instances from the known libraries showed that the proposed algorithm yields results competitive to those of well-known algorithms and confirms that the optimal recombination may be used successfully in evolutionary algorithms. 3. A hybrid algorithm of local improvements has been developed for the two-processor scheduling problem with energy constraint. The algorithm is based on the Karush-Kuhn-Tucker conditions and list-type strategies. The algorithm was tested on the instances of various structures. The experimental evaluation shows that the proposed algorithm may be used successfully for solving the considered set of instances. 4. The random local search algorithm in combination with the "go with the winners" scheme is proposed for problems on permutations. This algorithm shows good experimental results, it is generic and easy to implement, adapts quite easily to the GPU features, and can be used to solve production problems. 5. The scheduling problem on one machine, where weights of jobs are given by triangular fuzzy numbers, is considered. The modification of the problem was formulated as a two-criteria problem with a criterion consisting of the original objective function and its membership function. The Pareto set was constructed using test instances of the OR-Library. An estimate of the degree of the Pareto set reduction for particular cases of the problem is established under consideration of additional information about the decision maker’s preference relation. 6. A heuristic algorithm with local search improvements for a regression and classification problem with a tree representation of solution is constructed. The algorithm is based on optimized and randomized operators, where the "useful" properties of the solutions of the previous stages are preserved. The computational experiment was carried out on test instances with Boolean functions of various structures. 7. We experimentally study approximation algorithms for graph clustering problems. Local search significantly improves the quality of a feasible solution constructed by the approximation combinatorial algorithm. At the same time, a single local search is slightly inferior in quality to a multiple local search, but it is much faster. The results have been presented at Russian and International conferences. The six papers were prepared for publications indexed in foreign bibliographic databases of publications and/or Russian Science Citation Index (RSCI). The articles have been accepted for publication or are under review. Scientific seminar "Models and algorithms for scheduling problems" (http://ofim.oscsbras.ru/~scheduling/) is organized in Omsk department of Sobolev Institute of Mathematics SB RAS within the framework of the RSF project No. 22-71-10015. The reports of the project participants are presented at the meetings of the seminar.

 

Publications

---

Annotation of the results obtained in 2023
The aim of the project is researching new mathematical models and developing effective optimization algorithms for the actual scheduling problems with complex technological relations, resource constraints and uncertain input data that arise in production and computer systems. The following main results were obtained during the second year of the project. The study of computational complexity and the construction of polynomial algorithms with approximation guarantee: 1. The tight optima localization intervals for the two-machine proportionate routing open shop with unrelated travel times on a triangle and a star are found. A 7/6-approximation algorithms with linear running time for these problems are described. 2. For two-machine routing open shop with proportional processing times and at most three nodes of transportation network, the tight optima localization interval in terms of proportionality factor is found. A new polynomially-solvable special case and approximation algorithm with best theoretically possible worst-case performance ratio in terms of the standard lower bound are described. 3. The tight optima localization interval for the two-machine routing open shop on a cycle of length 4 is found: it is proved, that the optimal makespan can be as much (but never exceeds) as 5/4 times standard lower bound. Therefore, a 5/4-approximation algorithm, based on the instance reduction procedure, is described. 4. NP-hardness is proven and solving approaches based on integer programming and graph theory methods are proposed for a number of scheduling problems with job requisitions of the cardinality at most two. It is shown that the problem is polynomially solvable for “almost all” systems of requisitions. 5. The NP-hardness of the optimal recombination problem for a regression problem with a tree representation of solutions is proved. 6. A one-to-one correspondence between the independence systems and the rank function of the system is constructed. Construction and research of mathematical models and metaheuristics: 1. An adaptive evolutionary algorithm with optimized operators for scheduling problems on permutations has been proposed. The algorithm demonstrates a statistically significant advantage over the known metaheuristics for two scheduling problems in computer systems with a small number of processors under the energy consumption conditions. A hybrid algorithm has also been developed for an online problem with predictions of job durations and a given degree of parallelization. 2. Mixed integer programming models for problems taking into account energy consumption and the possibility of parallelization of operations were proposed. As a result we obtain new upper and lower bounds for a series of test instances of different structures for the case of a small number of processors. 3. For the problem of a production line design with uncertainty in the duration of operations within a given interval, a method for calculating the stability radius is obtained. To find solutions with a maximum stability radius, a hybrid parallel "go with the winners" algorithm has been proposed, which has shown high speed and good quality of approximate solutions. 4. A comparative analysis of integer linear programming models for the customer order scheduling problem using Gurobi and SCIP was carried out. An evolutionary algorithm with a criterion minimizing the total completion time was constructed, which showed an advantage over solving integer linear programming models. Lower and upper bounds on the objective functions are obtained. 5. Series of a bi-criteria problem with a special structure of Pareto set minimizing total completion time and maximizing the importance of orders are considered. Approximations of the Pareto set were constructed based on the conditional optimization method. 6. A computational experiment was carried out to solve the problem of Boolean data regression using genetic programming with optimized operators and techniques, such as, restarting the algorithm, various approaches to generating the initial population, using various sets of basic functions. Optimized operators showed advantages over randomized counterparts. A parallel optimized single-point crossover operator has been developed, which has reduced the running time of the algorithm. 7. A variable neighborhood search algorithm was implemented and adapted for mixed integer programming (MIP) solver parameter configuration. To optimize configuration process machine learning methods, such as kMeans, MeanShift and large language models for feature extraction were used. All considered methods were tested and compared. 8. New approximation and exact algorithms for weighted and unweighted variants of correlation clustering are studied. New integer linear programming models for different variants of correlation clustering are proposed. A randomized approximation algorithm for weighted 2-correlation clustering is constructed. Scientific seminar "Models and algorithms for scheduling problems" (http://ofim.oscsbras.ru/~scheduling/) is organized in Omsk department of Sobolev Institute of Mathematics SB RAS within the framework of the RSF project No. 22-71-10015. The reports of the project participants are presented at the meetings of the seminar. The results have been presented in Russian and International conferences. Twelve papers were prepared for publications indexed in foreign bibliographic databases of publications and/or Russian Science Citation Index (RSCI). The articles have been accepted for publication or are under review.

 

Publications

---