On the dual and inverse problems of scheduling problems with minimizing the maximum job penalty

?

On the dual and inverse problems of scheduling problems with minimizing the maximum job penalty

2019.

Alexander A. Lazarev, Frank Werner, Nikolay Pravdivets

Рассматривается классическая задача теории расписаний на одной машине с заданными моментами поступления требований. Целевой функцией является минимизация некоторой функции штрафа.Задача является NP-трудной в сильном смысле. Для этой задачи мы вводим двойственную и обратную задачу и показываем, что обе они могут быть решены за полиномиальное время. Поскольку двойственная задача дает нижнюю границу для оптимального значения целевой функции исходной задачи, мы используем оптимальное значение целевой функции подзадачи двойственной задачи в алгоритме ветвей и границ для поиска решения исходной задачи теории расписаний для одного прибора. Представлены некоторые начальные результаты вычислений для тестовых примеров с количеством требований до 20.

Научное направление: Математика Компьютерные науки

Приоритетные направления: компьютерно-математическое математика инженерные науки

Язык: английский

On the Ramsey Number R(K_{1,s},P_t)

Kh. Kh. Abdullin, D. B. Mokeev, D. S. Taletskii, Mathematical notes 2026 Vol. 119 No. 1 P. 3–7

Добавлено: 10 июня 2026 г.

TreeDQN: Sample-efficient off-policy reinforcement learning for combinatorial optimization

Sorokin D., Kostin A., Савченко Л. В. и др., Knowledge-Based Systems 2026 Vol. 348 Article 116258

Добавлено: 10 июня 2026 г.

Microbial diversity and production of milk spirit using traditional Buryat fermentation and distillation technologies

Namsaraev Z., Козлова А. Д., Toshchakov S., Scientific Reports 2026 Vol. 16 No. 17769

Дистиллированные кисломолочные напитки встречаются в пищевой промышленности редко, несмотря на повсеместное распространение растительных спиртных напитков. В настоящее время производство крепких дистиллированных алкогольных напитков из кисломолочных продуктов с использованием традиционных технологий известно лишь среди монголоязычных народов и их сибирских соседей. Данное исследование представляет собой первый междисциплинарный анализ дарасуна, традиционного бурятского спиртного напитка, изготавливаемого из кисломолочного напитка ...

Добавлено: 10 июня 2026 г.

Artificial intelligence and digital twins for failure prediction in data center cooling systems: a comprehensive literature review (2018–2026)

Гущин М. И., Butorova A., Bobakov V. и др., European Physical Journal: Special Topics 2026 P. 1–19

Добавлено: 10 июня 2026 г.

Innovations in Information and Decision Sciences. Proceedings of the 13th International Conference on Frontiers in Intelligent Computing: Theory and Applications (FICTA 2025), Volume 4

Springer, 2026.

Добавлено: 8 июня 2026 г.

Wave dynamics within the Whitham-Ostrovsky equation

Flamarion M. V., Пелиновский Е. Н., Nonlinear Dynamics 2026 Vol. 114 Article 784

Добавлено: 5 июня 2026 г.

On structural stability of 3-diffeomorphisms with the Smale solenoid attractor–repeller dynamics

Медведев Т. В., Починка О. В., Chaos 2026 Vol. 36 No. 6 Article 063107

Добавлено: 4 июня 2026 г.

Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)

Seul: PMLR, 2026.

Добавлено: 4 июня 2026 г.

A model exhibiting all possible types of hyperbolic chaos on the 2-torus

Казаков А. О., Минц Д. И., Петрова Ю. Э. и др., Chaos 2026 Vol. 36 No. 6 Article 063112

Добавлено: 4 июня 2026 г.

Об эквивалентности по надстройке декартовых произведений регулярных гомеоморфизмов с гомеоморфизмами Данжуа

Ноздринова Е. В., Починка О. В., Шмуклер В. И., Математический сборник 2026 Т. 217 № 6 С. 71–89

Гомеоморфизмы топологических пространств называются эквивалентными по надстройке, если надстройки над ними топологически эквивалентны. В частности, топологически сопряженные гомеоморфизмы эквивалентны по надстройке. Известно, что для гомологически неприводимых гомеоморфизмов их топологическая сопряженность является необходимым и достаточным условием их эквивалентности по надстройке. Тогда как инварианты топологической сопряженности гомологически приводимых гомеоморфизмов во многих случаях являются избыточными для эквивалентности по ...

Добавлено: 3 июня 2026 г.

ML-based Fast Simulation of FARICH Responses

Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.

Добавлено: 19 мая 2026 г.

Perovskite nanoparticles Cs4PbBr6 and CsPbBr3: synthesis, analysis and peculiar optical properties

Гущина В. А., / Series chemrxiv-2023-vpzhz-v2 "ChemRxiv". 2023.

Наночастицы полностью неорганических перовскитов CsPbBr3 и Cs4PbBr6 интенсивно изучаются благодаря их уникальным свойствам и широкому спектру применений; однако природа их оптических свойств до сих пор полностью не изучена из-за сложности синтеза однофазных наночастиц. В данной статье мы описываем особенности синтеза однофазных частиц и результаты их химического и фазового анализа. Используя данные о концентрациях наночастиц, мы ...

Добавлено: 14 мая 2026 г.

Bifurcations and Structural Stability of Generic PC-HC Families

Доровский А. А., / Series arXiv "math". 2026.

Добавлено: 14 мая 2026 г.

On the minimum number of maximal distance-k independent sets in trees

Талецкий Д. С., / Series arXiv "math". 2026.

Добавлено: 1 мая 2026 г.

On Arithmetic Mirror Symmetry for smooth Fano fourfolds

Овчаренко М. А., / Series arXiv "math". 2026.

Добавлено: 30 апреля 2026 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

Добавлено: 18 апреля 2026 г.

On the dimension of the space of static potentials on three-manifolds

Медведев В. О., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Добавлено: 3 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

On Joint Satellite, Terrestrial, and Delay Tolerant Networks for Railroad Communications

Тихонов Е. О., Schneps-Schneppe D., Sneps-Sneppe M., , in: 28th Conference of Open Innovations Association (FRUCT).: [б.и.], 2021. P. 472–481.

Добавлено: 9 апреля 2022 г.

OFDMA Uplink Scheduling in IEEE 802.11ax Networks

Банков Д. В., Didenko A., Хоров Е. М. и др., , in: Proceedings of 2018 IEEE International Conference on Communications (ICC).: IEEE, 2018. P. 1–6.

Добавлено: 9 октября 2018 г.

Evaluating Typical Algorithms of Combinatorial Optimization to Solve Continuous-Time Based Scheduling Problem

Лазарев А. А., Pravdivets N., Nekrasov I., Algorithms 2018 Vol. 11 No. 4 P. 1–13

Добавлено: 1 октября 2018 г.

Single machine scheduling: an upper bound on maximum lateness

Лазарев А. А., Архипов Д. И., , in: 28th Conference of the European Chapter on Combinatorial Optimization.: Катания: University of Catania, 2015. P. 64.

The following classical NP-complete scheduling problem is considered. ...

Добавлено: 22 июня 2015 г.