• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • A metric approach for scheduling problems with minimizing the maximum penalty
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
November 17, 2026
Physicists Show How a Solvent Shapes the Response of Drug Molecules
Many drug molecules can switch between different three-dimensional shapes. Using a mathematical model of ibuprofen dissolved in supercritical CO₂, researchers from HSE University and the Institute of Solution Chemistry of the Russian Academy of Sciences have shown that the solvent can make these molecules appear to respond unusually slowly. The molecules themselves continue to change shape rapidly, but their surroundings rearrange much more slowly, and this lag shows up in the measurements. The study has been published in The Journal of Chemical Physics. 
November 10, 2026
Physicists Train AI to Optimise Particle Beams in Accelerators
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science and the Budker Institute of Nuclear Physics at the Siberian Branch of the Russian Academy of Sciences have developed RLABC (Reinforcement Learning for Accelerator Beamline Control), a framework that uses reinforcement learning to identify optimal settings for a particle accelerator. In a computer simulation, RLABC optimised the accelerator's parameters to achieve a particle transmission rate of 70%. The study has been published in Computer Physics Communications.
November 9, 2026
'Organ-on-a-Chip Technology Could Eliminate the Need for Animal Testing'
The Laboratory of Molecular Physiology at the HSE Faculty of Biology and Biotechnology investigates how molecular regulators known as microRNAs control gene expression and contribute to the development of diseases, including cancer, viral and inflammatory conditions, and pregnancy complications. At HSE University, researchers develop organ-on-a-chip models: miniature devices containing living cells that mimic the functions of human organs, such as the placenta and intestines. These models help researchers understand how diseases develop and how drugs affect them. HSE News Service spoke with Evgeny Knyazev, Head of the Laboratory.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

A metric approach for scheduling problems with minimizing the maximum penalty

Applied Mathematical Modelling. 2021. Vol. 89. No. 2. P. 1163–1176.
Lazarev A. A., Lemtyuzhnikova D., Werner F.

NP -hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is deter- mined for which a polynomial or pseudo-polynomial algorithm is known. A schedule is constructed for this determined instance which is then applied to the original instance. It is shown how this approach can be applied to different scheduling problems.

Research target: Mathematics
Language: English
Full text
DOI
Keywords: schedulingapproximation algorithmsmetric approach to measuring uncertaintyMinimization of maximum penaltyMaximum lateness
Publication based on the results of:
Decision making and data analysis in socio-economic and political systems (2020)
Similar publications
Genus zero Whitham hierarchy via Hurwitz–Frobenius manifolds
Basalaev A., Journal of Geometry and Physics 2027 Vol. 232 Article 106032
B. Dubrovin introduced the structure of a Dubrovin–Frobenius manifold on a space of ramified coverings of a sphere by a genus g Riemann surface with the prescribed ramification profile. This is now known as a genus g Hurwitz–Frobenius manifold. We investigate the genus zero Hurwitz–Frobenius manifolds and their connection to the integrable hierarchies. In particular, ...
Added: November 19, 2026
FLowRA: Flow-Guided Rank Allocation for Parameter-Efficient Fine-Tuning of Deep Neural Networks
Aleksei Samarin, Nazarenko A., Kotenko E. et al., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 11 Article 389
Low-rank adaptation (LoRA) is widely used for parameter-efficient fine-tuning, yet uniform rank assignment ignores the varying contribution of layers to a downstream task. Adaptive methods such as AdaLoRA allocate ranks via gradient and singular-value importance, but they do not exploit the representation change induced by the task. We introduce FLowRA, a calibration-based rank-allocation framework that ...
Added: November 19, 2026
Uniqueness of addition in Schrödinger algebras
Sosnov G., / Series arXiv "math". 2026.
We obtain a criterion for the uniqueness of addition in Schrödinger Lie algebras, applicable to both bijections and injections. This allows us to construct the first example of a Lie algebra with unique addition and a non-trivial center over a field of characteristic zero. Furthermore, a necessary and sufficient condition is established for the Schrödinger ...
Added: November 19, 2026
Uniqueness of addition in Lie rings gl_n(K) and sl_n(K)
Sosnov G., / Series math "arxiv.org". 2026.
We prove that for any Lie ring R and any commutator-preserving bijection α:gln(K)→R, the map α is additive on sln(K), where n≥2 and K is an arbitrary field. Using this result we find criteria for Lie rings gln(K) and sln(K) to be unique addition. We also show that any commutator-preserving injection of Lie rings β:sl2(K)→S ...
Added: November 19, 2026
Soliton turbulence within the modified Benjamin–Bona–Mahony equation
Flamarion M. V., Pelinovsky E., Physica D: Nonlinear Phenomena 2027 Vol. 500 Article 135452
In this work, we investigate soliton turbulence in the modified Benjamin–Bona–Mahony (mBBM) equation. A key advantage of this model is that it admits solitary wave solutions of both polarities while also being interpretable as a perturbation of the integrable modified Korteweg–de Vries (mKdV) equation. This framework enables a direct comparison of the main properties of soliton turbulence in ...
Added: November 18, 2026
Топология 3-многообразий, допускающих НМС-потоки с единственной седловой орбитой
Yagilev A., Pochinka O., Shubin D., Математический сборник 2026 Т. 217 № 11 С. 130–144
Рассматриваются неособые потоки Морса-Смейла (НМС-потоки) на замкнутых ориентируемых 3-многообразиях $M^3$, в предположении, что среди периодических орбит ровно одна седловая. Устанавливается, что  многообразие $M^3$ допускает такой поток  тогда и только тогда, когда оно гомеоморфно  линзовому пространству, связной сумме линзовых пространств или многообразию Зейферта вида $M(\mathbb S^2, (p_1,q_1), (p_2,q_2), (p_3,q_3))$. ...
Added: November 17, 2026
The medial septum model as a pacemaker of theta rhythm: the key role of short-term synaptic plasticity
Mysin I. E., Dubrovin S. V., Cognitive Neurodynamics 2026 Vol. 20 No. 191 P. 1–30
The hippocampal theta rhythm is crucial for memory and navigation. It is paced by parvalbumin-expressing GABAergic neurons in the medial septum. These neurons segregate into two subpopulations—Teevra and Komal cells—which fire in anti-phase bursts at theta frequency, with a stable phase shift of approximately 150 degrees, and exhibit mutual inhibition. While essential, the network mechanism ...
Added: November 14, 2026
Upper Bound for Permanent Saturation of Metric Graphs using Interval Exchange Transformations
Ермолаев Е. С., Chernyshev V. L., Skripchenko A., Journal of Nonlinear Science 2026 Vol. 36 No. 122 (2026) Article 122 (2026)
We study upper bounds for the moment of permanent -saturation in finite metric graphs. The dynamics is generated by moving points travelling with unit speed along edges and branching into all outgoing directions whenever they reach a vertex. We first reformulate this branched dynamics in terms of birth times at vertices and prove a sufficient ...
Added: November 12, 2026
On β-function of 𝒩 = 2 supersymmetric integrable sigma models. Part II
Alfimov Mikhail, Kurakin Andrey, Journal of High Energy Physics 2026 Vol. 2026 Article 99
We continue studying regularization scheme dependence of the 𝒩 = 2 supersymmetric sigma models. In the present work the previous result for the four loop β-function is extended to the five loop order. Namely, we find the renormalization scheme, in which the fifth loop contribution is completely eliminated, while the fourth loop contribution is represented ...
Added: November 12, 2026
Kripke Completeness For Predicate Modal Logics Of Bounded Alternativity: First Steps
Shehtman V. B., Shkatov D., Review of Symbolic Logic 2026 Vol. 19 No. 4 P. 859–882
We study Kripke completeness for predicate modal logics with propositional axioms of bounded alternativity corresponding to the condition on Kripke frames that every world sees at most n worlds. We prove that minimal predicate modal logics with axioms of bounded alternativity, as well as their extensions with the axiom of reflexivity, are strongly Kripke complete, whereas the ...
Added: November 12, 2026
On flexibility of trinomial varieties
Ignatev M., Vilkin T., Mediterranean Journal of Mathematics 2026 Vol. 23 No. 2 Article 70
Trinomial varieties are affine varieties given by a system of equations consisting of polynomials with three terms. Such varieties are total coordinate spaces of normal varieties with torus action of complexity one. For an affine variety X, we consider the subgroup SAut(X) of the automorphism group generated by all algebraic subgroups isomorphic to the additive ...
Added: November 12, 2026
Линейные отображения, сохраняющие матрицы с n или n − 1 различными собственными значениями
Maksaev A., Promyslov V., Тишутин П. С., Записки научных семинаров ПОМИ РАН 2026 Т. 554 С. 218–235
Let K be an algebraically closed field and let ℰₖ be the set of n × n matrices over K with exactly k distinct eigenvalues. Previously, the classification of linear maps T: Mₙ(K) → Mₙ(K) satisfying T(ℰₙ) ⊆ ℰₙ was obtained for invertible maps over fields of characteristic 0. In this paper, the classification is ...
Added: November 11, 2026
Nonexistence of Energy Function for Surface Diffeomorphisms with Nontrivial Basic Sets of Serpentine Geometric Type
Barinova M., Tirskaya Karina, Владикавказский математический журнал 2026 Vol. 28 No. 3 P. 25–43
In this paper, the problem of the existence of an energy function for discrete dynamical systems defined by structurally stable diffeomorphisms is studied. For the considered class of dynamical systems, such a function is defined as a continuous function that decreases along the orbits of the system outside the non-wandering set and remains constant on ...
Added: November 11, 2026
О статистических свойствах наилучших диофантовых приближений
Illarionov A., Математический сборник 2026 Т. 217 № 11 С. 56–87
Let $b(\alpha;T)$ be the number of best simultaneous Diophantine approximations with common denominator $\le T$ to the point $\alpha \in {\Bbb R}^n$. We derive asymptotic formulas for the mean value of this quantity (averaging is performed over all rational points of the form $\alpha = (k_1/N,\ldots, k_n/N)$, $N\le R$), as well as for its mathematical ...
Added: November 10, 2026
К теореме Гудмана-Штрауса
Vereshchagin N., Математический сборник 2026 Т. 217 № 10 С. 3–46
Теорема Гудмана-Штрауса утверждает, что для “почти всякой” подстановки семейство подстановочных замощений софично, т.е. может быть задано локальными правилами для некоторой раскраски плиток. Условия на подстановку, гарантирующие софичность, довольно сложные. В настоящей работе мы предлагаем версию теоремы Гудмана-Штрауса с более простыми условиями на подстановку. Хотя эти условия достаточно ограничительны, мы показываем, что в сочетании с двумя простыми приемами (взятием достаточно ...
Added: November 10, 2026
Dispersionless modified DKP hierarchy as the Yang-Baxter equation
Zabrodin A., Journal of Mathematical Physics 2026 Vol. 67 No. 10 Article 103505
We show that the dispersionless version of the modified DKP hierarchy originally defined as the limit of relations for the tau-function of the Hirota-Miwa type has an equivalent reformulation as the Yang-Baxter equation for Baxter's R-matrix of Boltzmann weights for the 8-vertex model. ...
Added: November 9, 2026
MFL-ScrollNet: Recurrent Sliding-Window Detection for Panoramic Pipeline Magnetic Flux Leakage Images
Aleksei Samarin, Belous F., Торопов А. Г. et al., Technologies 2026 Vol. 14 No. 11 P. 1–21
Abstract Automated interpretation of magnetic flux leakage (MFL) data is central to condition assessment of long-distance oil and gas pipelines. Yet, full-resolution panoramas are difficult to process without either suppressing small anomalies through resizing or fragmenting elongated objects at sliding-window boundaries. We propose MFL-ScrollNet, a recurrent sliding-window detector that formulates panoramic analysis as an ordered sequence ...
Added: November 8, 2026
Average Connection Establishment Time in Random Access Channel with Limited Resources
Батыгин А. А., Бурков А. А., Tyurlikov A., IEEE, 2024.
In 4G and 5G cellular networks, a 4-step random access procedure is used. A significant challenge arises when a large number of users attempt to connect within a short period of time. To address this issue, the access class barring mechanism is employed. There are numerous studies that analyze the average connection time for users ...
Added: October 24, 2026
Characterizing the Scheduling Performance of 5G NR Base Stations Under Signaling and Data Traffic Constraints
Eduard Sopin, Nazarin A., Begishev V. et al., IEEE Transactions on Vehicular Technology 2026 Vol. 75 No. 6 P. 10995–11007
Aimed at rate-greedy applications having extreme requirements for the data rate at the air interface, 5G New Radio (NR) systems may experience problems when the number of user equipment (UE) in the coverage of the cell increases due to limited capacity of the physical downlink control channel (PDCCH).The aim of this study is to explore ...
Added: August 26, 2026
A Versatile Simulator for Complex Cluster Workloads
Makogon A., Oleg Sukhoroslov, , in: Supercomputing. 10th Russian Supercomputing Days, RuSCDays 2024, Moscow, Russia, September 23–24, 2024, Revised Selected Papers, Part I* 1.: Springer, 2025. P. 300–318.
Resource allocation and scheduling algorithms play a crucial role in operation of modern computing clusters. The algorithms used and their settings can significantly impact cluster utilization, application performance, and user experience. This area of research requires the use of simulators to quickly test a hypothesis or conduct comparative testing of different algorithms. This paper presents ...
Added: February 22, 2025
Instances generation for a single machine scheduling problem
A. Lazarev, N. Pravdivets, Grishin E. et al., , in: 13th Multiconference on Control Problems (MCCP 2020) 6-8 October 2020, Saint Petersburg, RussiaVol. 1864.: IOP Publishing, 2021. Ch. 012057.
Added: December 16, 2022
A New Interpolation-Based Polynomial Algorithm for Estimating Lateness in Single Machine Scheduling Problem
Lazarev A. A., Lemtyuzhnikova D. V., Tyunyatkin A. A. et al., IFAC-PapersOnLine 2022 Vol. 55 No. 10 P. 2881–2886
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 ...
Added: December 5, 2022
Decomposition of the Knapsack Problem for Increasing the Capacity of Operating Rooms
Lazarev A. A., Lemtyuzhnikova D. V., Somov M. L., Mathematics 2022 Vol. 10 No. 5 P. 1–18
This paper is aimed at the problem of scheduling surgeries in operating rooms. To solve this problem, we suggest using some variation of the bin packing problem. The model is based on the actual operation of 10 operating rooms, each of which belongs to a specific department of the hospital. Departments are unevenly loaded, so ...
Added: December 5, 2022
Towards a General Framework for Studying Resource Management in Large Scale Distributed Systems
Oleg Sukhoroslov, Maxim Gorokhovskii, Roman Ilgovskiy et al., , in: Материалы IV Международного семинара по информационным, вычислительным и управляющим системам для распределенных сред (ICCS-DE 2022).: Иркутск: ИДСТУ СО РАН, 2022. P. 79–96.
Resource management is a critical part of modern large-scale distributed systems and an active area of research. The diversity of systems, workloads and requirements have lead to many domain-specific problem statements, solutions and simulation tools proposed by researchers, which are hard to compare and reuse. In this paper, an overview of related resource management problems ...
Added: October 30, 2022
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit