Optimization for one class of combinatorial problems under uncertainty

Скорочена інформація про документ
dc.contributor.authorPavlov, A. A.
dc.date.accessioned2020-03-12T14:03:14Z
dc.date.available2020-03-12T14:03:14Z
dc.date.issued2019
dc.description.abstractenWe formalize uncertainty and compromise solution concepts, compromise criteria and conditions for a sufficiently common class of combinatorial optimization problems which functional contains a linear convolution of weights and of arbitrary numerical characteristics of a feasible solution. We present algorithms for compromise solutions finding as an original implementation of the well-known idea of linear convolution of criteria. Efficiency of the proposed algorithms is unambiguously determined by the efficiency of solving the combinatorial optimization problem in a deterministic formulation. We show that previously obtained efficient PSC-algorithms for NP-hard combinatorial optimization problems — the total weighted tardiness of tasks minimization on one machine, the total weighted completion time of interrelated tasks (by arbitrary acyclic oriented graph) minimization on one machine — allow to solve these problems efficiently under uncertainty conditions.uk
dc.description.abstractruДля достаточно общего класса задач комбинаторной оптимизации, функционал которых содержит линейную свертку весов и произвольных числовых характеристик допустимого решения, формализуются понятия неопределенности, компромиссного решения, компромиссные критерии и условия. Приводятся алгоритмы нахождения компромиссных решений как оригинальная реализация известной идеи линейной сверстки критериев. Эффективность предложенных алгоритмов однозначно определяется эффективностью решения задачи комбинаторной оптимизации в детерминированной постановке. Показано, что полученные ранее эффективные ПДС-алгоритмы для NP-трудных задач комбинаторной оптимизации – минимизация суммарного взвешенного запаздывания заданий на одном приборе, минимизация суммарного взвешенного момента окончания выполнения взаимосвязанных заданий (произвольный ацикличный ориентированный граф) одним прибором – позволяют эффективно решать эти задачи в условиях неопределенности.uk
dc.description.abstractukДля досить загального класу задач комбінаторної оптимізації, функціонал яких містить лінійну згортку ваг і довільних числових характеристик допустимого розв’язку, формалізуються поняття невизначеності, компромісного розв’язку, компромісні критерії та умови. Наводяться алгоритми знаходження компромісних розв’язків як оригінальна реалізація відомої ідеї лінійної згортки критеріїв. Ефективність запропонованих алгоритмів однозначно визначається ефективністю розв’язання задачі комбінаторної оптимізації в детермінованій постановці. Показано, що отримані раніше ефективні ПДС-алгоритми для NP-трудних задач комбінаторної оптимізації – мінімізація сумарного зваженого запізнення виконання завдань одним приладом, мінімізація сумарного зваженого моменту закінчення виконання взаємозв’язаних завдань (довільний ациклічний орієнтований граф) одним приладом – дозволяють ефективно розв’язувати ці задачі в умовах невизначеності.uk
dc.format.pagerangePp. 81-89uk
dc.identifier.citationPavlov, A. A. Optimization for one class of combinatorial problems under uncertainty / A. A. Pavlov // Адаптивні системи автоматичного управління : міжвідомчий науково-технічний збірник. – 2019. – № 1 (34). – С. 81–89. – Бібліогр.: 7 назв.uk
dc.identifier.doihttps://doi.org/10.20535/1560-8956.1.2019.178233
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/32231
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.sourceАдаптивні системи автоматичного управління : міжвідомчий науково-технічний збірник, 2019, № 1 (34)uk
dc.subjectcombinatorial optimizationuk
dc.subjectuncertaintyuk
dc.subjectprobabilityuk
dc.subjectefficient algorithmuk
dc.subjectuncertainty resolutionuk
dc.subjectPSC-algorithmuk
dc.subjectNP-hard problemsuk
dc.subjectкомбінаторна оптимізаціяuk
dc.subjectневизначеністьuk
dc.subjectймовірністьuk
dc.subjectефективний алгоритмuk
dc.subjectрозв’язання невизначеностіuk
dc.subjectПДС-алгоритмuk
dc.subjectNP-трудні задачіuk
dc.subjectкомбинаторная оптимизацияuk
dc.subjectнеопределенностьuk
dc.subjectвероятностьuk
dc.subjectэффективный алгоритмuk
dc.subjectразрешение неопределенностиuk
dc.subjectNP-трудные задачиuk
dc.subject.udc519.854.2uk
dc.titleOptimization for one class of combinatorial problems under uncertaintyuk
dc.title.alternativeОптимізація для одного класу комбінаторних задач в умовах невизначеностіuk
dc.title.alternativeОптимизация для одного класса комбинаторных задач в условиях неопределенностиuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
asau2019-1_10Pavlov.pdf
Розмір:
273.4 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.06 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Адаптивні системи автоматичного управління: міжвідомчий науково-технічний збірник, № 1 (34)