### ?

## A New Interpolation-Based Polynomial Algorithm for Estimating Lateness in Single Machine Scheduling Problem

IFAC-PapersOnLine. 2022. Vol. 55. No. 10. P. 2881-2886.

Lazarev A. A., Lemtyuzhnikova D. V., Tyunyatkin A. A., Battaia O.

This research extends the interpolation approach to approximating the objective function value for the minimization maximum lateness problem. The interpolation approach is defined using a special objective function Lmax(α), which is proven to be continuous and depends only on α transform coefficient. Such a function is proven to be monotonically increasing, and this property is used in the presented modified interpolation polynomial algorithm which is used to estimate the approximation error.

Publication based on the results of:

Chistyakov V., Pardalos P. M., Journal of Optimization Theory and Applications 2015 Vol. 167 No. 2 P. 585-616

This paper addresses the tolerance approach to the sensitivity analysis of optimal solutions to a nonlinear optimization problem of the form: minimize the total cost of a trajectory over all admissible discrete trajectories, where the total cost is expressed through individual costs by means of a generalized addition operation on the set of all non-negative ...

Added: February 17, 2015

Puzino Y. A., Вестник Чувашского государственного педагогического университета им. И.Я. Яковлева. Серия: Механика предельного состояния 2014 № 22 С. 46-52

The increasing of the efficiency of technological modes of steel products manufacturing requires simulation of metal forming during hot deformation. To obtain correct results, one should set the correct initial and boundary conditions, including the mechanical properties of materials, which represent the dependence of the stress-strain and strain rate at maintained temperature.
In the experiments one ...

Added: January 19, 2015

Switzerland : Springer, 2015

Recent developments in theory, algorithms, and applications in optimization and control are discussed in this proceedings, based on selected talks from the ‘Optimization Control and Applications in the Information Age’ conference, organized in honor of Panos Pardalos’s 60th birthday. This volume contains numerous applications to optimal decision making in energy production and fuel management, data ...

Added: September 13, 2015

Фотеева А. В., Феофилова А. Е., Ростова Н. Б. et al., Медико-фармацевтический журнал "Пульс" 2022 Т. 24 № 4 С. 38-43

Abstract. The modern regulatory requirements for pharmaceutical development, stricter of requirements of
medicinal products (MP) quality standards, the experience of manufacturers and development companies in terms of MP pharmaceutical development revealed need to create solutions that minimize the risk of medicinal product quality deviations, guaranteeing the release of effective and safe MP with the planned quality. The aim of these study is to ...

Added: May 13, 2022

Чжо М. А., Sidorenko V., Электроника и электрооборудование транспорта 2017 № 6 С. 37-40

This paper is a part of continuation publications on the topic of genetic algorithms application to the scheduling of underground rolling stock maintenance. The authors implemented the adaptive crossover selection algorithms within the genetic algorithm framework according to the features of the scheduling problem. Then the authors investigated the possibilities of genetic algorithm by using ...

Added: January 16, 2018

Bangalore : IEEE Computer Society, 2013

COMSNETS is a premier international conference dedicated to covering all aspects of networking and communications, in both the theoretical and systems aspects. Following the tradition established by the first four COMSNETS conferences, COMSNETS 2013 includes a highly selective technical program, comprising peer-reviewed submitted papers, plenary talks by leaders in the field, and a small set of invited papers on important ...

Added: September 24, 2013

Gafarov E., Lazarev A. A., Werner F., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261

We consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed.We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity ...

Added: November 24, 2012

Maxim Babenko, Goldberg A., Gupta A. et al., Lecture Notes in Computer Science 2013 Vol. 7965 No. PART 1 P. 69-80

Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (l1 norm). We give O(log n)- approximation algorithms for the problems of minimizing the maximum label (l∞ norm) and minimizing lp and lq norms simultaneously. ...

Added: November 13, 2013

M. : [б.и.], 2018

Book include abstracts of reports presented at the IX International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2018) held in Petrovac, Montenegro, October 1 - October 5, 2018. ...

Added: October 9, 2018

Kapalin V. I., Шаповалова Н. Е., Промышленные АСУ и контроллеры 2012 № 10 С. 14-17

An algorithm for the design of linear regulators for nonlinear control objects is suggested. The algorithm is based on interpolation technique and state-space method. An example of the suggested design method in MATLAB is given ...

Added: November 29, 2015

Bobrov E., Kropotov D., Troshin S. et al., Optimization Methods and Software 2022 P. 1-16

The paper studies the multi-user precoding problem as a non-convex optimization problem for wireless multiple inputs and multiple outputs (MIMO) systems. In our work, we approximate the target Spectral Efficiency function with a novel computationally simpler function. Then, we reduce the precoding problem to an unconstrained optimization task using a special differential projection method and ...

Added: October 26, 2022

Ignatov A., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112-116

The paper describes a simulator of parallel Branch and Bound (BnB) method. Several subdomain trees for benchmark functions are analyzed, a characteristic Gaussian-like distribution is discovered. An algorithm of artificial tree generation is formulated according to this criterion. The process of simulator modeling is described, several computational experiments are conducted. Their results show a hyperbolic ...

Added: June 11, 2020

Lazarev A. A., Gafarov E., Доклады Академии наук 2008 Т. 424 № 1 С. 7-9

27.47.19 Исследование операций
28.15.19 Нелинейные детерминированные системы
28.19.15 Оптимальные системы
28.29.15 Методы исследования операций ...

Added: November 23, 2012

A.Yu. Golubin, Gridin V. N., Automation and Remote Control 2012 Vol. 73 No. 9 P. 1529-1538

We find optimal (from the insurer’s point of view) strategies for insurance and reinsurance
in a controllable Cramer–Lundberg risk process that describes the capital dynamics of
an insurance company over an infinite time interval. As the optimality criterion being minimized,
we use the stationary variation coefficient, taking into account additional constraints
on residual risks for both insurers and reinsurer. ...

Added: February 20, 2014

Gafarov E., Lazarev A. A., Information Processing Letters 2012 Т. 112 № 3 С. 72-76

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function.
A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new
graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number
of tardy jobs on a single ...

Added: November 24, 2012

Gafarov E., Lazarev A. A., Werner F., Mathematical Social Sciences 2011 No. 62 P. 7-13

We consider single machine scheduling problems with a non-renewable resource. These types of problems have not been intensively investigated in the literature so far. For several problems of these types with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), we present some complexity ...

Added: November 24, 2012

Lazarev A. A., Журнал вычислительной математики и математической физики 2007 Т. 47 № 6 С. 1087-1099

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding ...

Added: November 23, 2012

Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2010. No. 10.

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. An NP-hardness proof and a pseudo-polynomial time solution algorithm are proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted ...

Added: March 4, 2013

Pardalos P. M., Rassias T. undefined., Springer, 2014

The contributions in this volume have been written by eminent scientists from the international mathematical community and present significant advances in several theories, methods and problems of Mathematical Analysis, Discrete Mathematics, Geometry and their Applications. The chapters focus on both old and recent developments in Functional Analysis, Harmonic Analysis, Complex Analysis, Operator Theory, Combinatorics, Functional ...

Added: May 30, 2014

Stepanov E., Buttazzo G., Pratelli A. et al., Berlin : Springer, 2009

Recently much attention has been devoted to the optimization of transportation networks in a given geographic area. One assumes the distributions of population and of services/workplaces (i.e. the network's sources and sinks) are known, as well as the costs of movement with/without the network, and the cost of constructing/maintaining it. Both the long-term optimization and ...

Added: December 12, 2018

Kondrashova E. V., Kashtanov V., Optimization: A Journal of Mathematical Programming and Operations Research 2018 Vol. 67 No. 6 P. 921-941

Algorithmization of the quality of queueing systems is carried out in oder to optimize the work, constructing the revenue functional on the trajectories of a managed semi-Markov process while managing the system's structure. In particular, we consider both semi-Markov and Markoqueueing systems with control of several parameters chaaractirestics of the system). The task is to find ...

Added: March 22, 2018

A. A. Lazarev, Lemtyuzhnikova D. V., N. A. Pravdivets, Computational Mathematics and Mathematical Physics 2021 Vol. 61 No. 7 P. 1169-1180

Metric functions are introduced for various classes of single-machine scheduling problems.It is shown how approximate solutions of NP-hard problems can be found using these functions. The metric value is determined by solving a linear programming problem with constraints being systems of linear inequalities for polynomial or pseudopolynomial solvable instances of the problem under study.In fact, ...

Added: February 4, 2022

Toporkov V., Anna Toporkova, Tselishchev A. et al., Procedia Computer Science 2015 Vol. 51 No. 1 P. 845-854

Distributed environments with the decoupling of users from resource providers are generally termed as utility Grids. The paper focuses on the problems of efficient job flow distribution and scheduling in virtual organizations (VOs) of utility Grids while ensuring the VO stakeholders preferences and providing dependable strategies for resources utilization. An approach based on the combination ...

Added: June 1, 2015

Alexeeva T., Shirokov N. A., Алгебра и анализ 2024 Т. 36 № 1 С. 40-59

On the chord-arc curve in R^3 classes of functions similar to Hölder functions with smoothness greater than unity are defined. A constructive description of these classes is obtained in terms of the rate of approximation of functions from them by functions that are harmonic in neighborhoods contracting to the curve. The choice of defining these classes ...

Added: January 10, 2024