Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Задачи теории расписаний для системы с нефиксированными маршрутами и ресурсными ограничениями Лушакова, Ирина Николаевна

Данная диссертационная работа должна поступить в библиотеки в ближайшее время
Уведомить о поступлении

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Лушакова, Ирина Николаевна. Задачи теории расписаний для системы с нефиксированными маршрутами и ресурсными ограничениями : автореферат дис. ... кандидата физико-математических наук : 01.01.09.- Минск, 1992.- 13 с.: ил.

Введение к работе

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

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

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

Целью работы- является исследование различных классе задач для многостадийных обслуживающих систем с нефиксирован-ыми маршрутами и ограниченными восстанавливаемыми ресурсами, а менно: доказательство А/Р -трудности некоторых задач; выявление олиномиально разрешимых задач и построение для них.точных эффек-ивных алгоритмов решения.

Научная новизна. Доказана NP -трудность в силь-эм смысле задачи построения оптимального по быстродействию .распития для двухстадийной системы при условии,, что в процессе обслу-івания требований используются восстанавливаемые ресурсы, запас іхдого из которых равен единице. Показано, что задача является 19 -трудной, если имеется точно два ресурса.

Доказана Л/Р -трудность в сильном смысле задачи построения ітимального по быстродействию расписания .для трехстадийной системы >и условиях, что длительности обслуживания требе ваши одинаковы и

- 3 ~

в процессе обслучшвания требований используется ресурс произвольного запаса.

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

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

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

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

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

Публикации и апробация работы. Основные результаты диссертации опубликованы в работах А-8/ и докладывались на ill Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеры" (гЛаштагол, 1987), на XI Всесоюзной школе-семи-нарз "Системы программного обеспечения решения задач оптимального планирования" (г.Кострома, 1990), на республиканской конференции молодых ученых и специалистов "Применение информатики и вычислительной техники при решении народнохозяйственных задач" (г.Минск, 1989), на межреспубликанской научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" (г.Иинск, 1990), на научном семинаре по теории расписаний под руководством В.С.Танаева

- «і ,

В ИТК АН БССР (г.Минск, IS8S, 1991).

Структура и объем работы. Диссертация состоит из введения, трех глав, списка литературы (95 наименований) , содержит ПО страниц машинописного текста.