Рассмотрена расширенная постановка задачи анализа устойчивости оптимального оперативно-календарного плана работ гибких производственных систем (ГПС) с различными маршрутами. Параметрический анализ решения произведен на основе методов и моделей параметрического программирования. Предложен итерационный алгоритм процедуры постоптимального анализа.

Запропоновано нові поліноміальні підкласи важкорозв'язуваної задачі теорії розкладу "Мінімізація сумарного зваженого моменту", отримані внаслідок реалізації поліноміальної складової ПДС-алгоритму цієї задачі.

Запропонована перебірна процедура з відсіченням для розв'язку адитивної задачі про оптимальний розподіл завдань між виконавцями з можливими дублюваннями деяких з них. Наводяться результати числових розрахунків.

Індекс рубрикатора НБУВ: В173.124 + У9(4УКР)210

Рубрики:

Теорія розкладів і планів

Економіка окремих країн і частин світу

Шифр НБУВ: Ж69027 Пошук видання у каталогах НБУВ 

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

Рассмотрены локально-оптимальные алгоритмы построения статических расписаний, основанные на использовании функции Ляпунова. В качестве меры эффективности расписания рассмотрено время его выполнения на заданном наборе ресурсов. Эти алгоритмы могут быть использованы как для улучшения расписаний, получаемых эвристическими алгоритмами, так и автономно.

Індекс рубрикатора НБУВ: В173.124

Рубрики:

Теорія розкладів і планів

Шифр НБУВ: Ж14024 Пошук видання у каталогах НБУВ 

Розглянуто можливість використання генетичних алгоритмів у задачах пошуку оптимальних календарних планів. Запропоновано методику використання операторів генетичного алгоритму, пристосованого для розв'язання такого класу задач.

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

Розв'язано задачу планування робіт у багатопроцесорній системі, що складається з ідентичних процесорів, за заданих директивних інтервалів і тривалості виконання робіт. Передбачено, що граф зв'язків між процесорами може бути неповним. Розроблено поліноміальний алгоритм складання припустимого розкладу.

Зазначено, що розв'язок задач знаходження субоптимальних розкладів з використанням генетичного алгоритму має ряд відмінностей від класичної теорії. Розглянуто нові методи кодування генетичної інформації, модифіковані алгоритми генетичних операторів. Запропоновано використання імітаційної моделі роботи виробничої системи для одержання оцінки пристосованості кожної особини популяції. Розроблено керуючий модуль, що здійснює зв'язок генетичного алгоритму й імітаційної моделі.

Предложены метод и алгоритм нахождения квазиоптимального плана назначения при прямоугольных матрицах эффективности. Разработанный алгоритм позволяет существенно снизить затраты времени и памяти ЭВМ на его реализацию по сравнению с оптимальными методами.

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

Побудовано формалізовану постановку задачі укладання циклічних семестрових розкладів навчальних занять. З урахуванням особливостей багатопрофільного вищого навчального закладу розроблено метод покрокового формування рішення з переміщенням раніше призначених подій. Наведена система вимог та оптимізаційних критеріїв відображає формальні параметри та джерела слабоструктурованості процесу прийняття рішень. Запропоновано методи побудови тест-опитувань для визначення показників оптимізаційних критеріїв, ефективність яких обгрунтовано теоретично та підтверджено практично, а також алгоритми оптимального розподілу основних ресурсів задачі укладання розкладу з урахуванням формальних і неформальних обмежень.

На підставі виробничо-часового подання, введених спеціальних операцій з перетворення виробничо-часових графів запропоновано графову модель роботи автоматизованої виробничої системи (АВС), що дозволяє будувати виробничі розклади за умов портфеля замовлень, що змінюється. Удосконалено методи вирішення задачі побудови виробничих розкладів для розгляду взаємодії основного та допоміжного обладнання з управління АВС і урахуванням реальних виробничих обмежень, а також планування АВС, який дозволяє враховувати паралельне обслуговування замовлень для багатопроцесорних ліній та ділянок.

Наведено результати дослідження послідовно-паралельних процесів, базовою моделлю яких є модель оптимального упорядкування і призначення робіт у дворівневій системі, що представлена однією машиною на першому рівні і кількома паралельними неідентичними машинами на другому. Оптимізаційні задачі, що формулюються з залученням даної моделі, складають новий клас узагальнень про призначення та основоположних задач теорії розкладів. Зазначено, що необхідність їх розв'язання викликана питаннями ефективної організації транспортного процесу. Запропоновано підхід до розв'язання узагальнень задачі про призначення, що базується на ідеї послідовної побудови локальних оптимальних розв'язків у підматрицях вхідної матриці призначень. Надано обгрунтування алгоритмам розв'язання задач послідовно-паралельного упорядкування, наведено докази їх коректності з гарантованою оцінкою часу розв'язання кожної задачі.

Досліджено моделі задач упрядкування, заданих на перестановках, розвинуто методи їх розв'язання, близькі до оптимального. Задачі теорії розкладів у своїй більшості можуть бути зведені до задач, заданих на перестановках. Як правило, ці задачі є NP-повними. Тому для їх розв'язання запропоновано модифікацію генетичних алгоритмів, а для одержання більш точних розв'язків - метод, побудований як комбінація методу гілок і меж та генетичного алгоритму, що дозволяє одержувати розв'язки задачі з заданою точністю. Для підвищення швидкодії розробленого методу запропоновано його паралельну версію та реалізацію на кластерних комп'ютерних системах. На підставі одержаних результатів створено пакет прикладних програм побудови навчального розкладу.

Сформулирована задача построения комплексных расписаний, обоснована оптимизационная модель задачи построения комплексных расписаний как модель двухуровневого программирования, сформулированы предпосылки формирования метода построения комплексных расписаний на основе аппарата бескоалиционных и иерархических игр.

Приводится анализ требований, предъявляемых к алгоритмам составления расписаний на данном этапе развития информационных технологий, а также ряд решений, применяемых в системе планирования летной деятельности авиакомпании "Международные авиалинии Украины".

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