Пошук академічних текстів

Інформація × Реєстраційний номер 0205U006896, 0104U000886 , Науково-дослідна робота Назва роботи Розвиток конструктивної теорії розв'язання комбінаторних задач як алгоритмічного забезпечення інформаційно-управляючих систем Назва етапу роботи Керівник роботи Павлов О.А., Дата реєстрації 23-12-2005 Організація виконавець Національний технічний університет України "Київський політехнічний інститут імені Ігоря Сікорського" Опис етапу Об'єкт дослiдження - планування функцiонування складних систем. Мета роботи - розвиток розробленої авторами нової, що не має аналогiв у свiтi, конструктивної теорiї розв'язання важкорозв'язуваних задач комбiнаторної оптимiзацiї (ВЗКО), розробка теоретичних основ та методiв проектування ефективних точних ПДС-алгоритмiв (алгоритмiв з поліномiальною та декомпозицiйною складовими) їх розв'язання. В результатi виконання проекту на основi нової конструктивної теорiї та методологiї проектування ПДС-алгоритмiв отримано новi ефективнi ПДС-алгоритми розв'язання вiдомих ВЗКО для одного приладу "Мінімiзацiя сумарного зваженого моменту закiнчення виконання завдань при вiдношеннi порядку, заданому орiєнтованим ациклiчним графом" (МЗМ) та "Мінімiзацiя сумарного запiзнення при виконаннi незалежних завдань"; визначено новi поліномiально розв'язуванi їх пiдкласи, правила декомпозицiї на пiдзадачi меншого розмiру, правила вiдсiкань безперспективних варiантiв при їх розв'язаннi. На основi точних ПДС-алгоритмiв розробленiефективнi евристичнi алгоритми розв'язання задач МЗМ для її окремого випадку, коли ваговi коефiцiєнти усiх вершин графу зв'язностi крiм кiнцевих дорiвнюють нулю та "Мінімiзацiя сумарного зваженого запiзнення при виконаннi незалежних завдань одним приладом". Розробленi алгоритми дозволяють розв'язувати практичнi задачi великої розмiрностi. Дослiджено властивостi та розроблено новий ефективний алгоритм розв'язання задачi "Мінімiзацiя сумарного випередження/запiзнення вiдносно директивних строкiв при виконаннi незалежних завдань одним приладом". Розроблено систему взаємозв'язаних алгоритмiв у складi системи планування та управлiння дрiбносерiйним виробництвом, що у комплексi розв'язують задачi узгодженого планування за критерiями максимiзацiї прибутку. Опис продукції Автори роботи Додано в НРАТ 2020-04-02 Закрити