Введение к работе
Актуальность темы. Развитие теории расписаний связано с потребностями практики. Эффективность функционирования современного производства во многом определяется решениями, принимаемыми на этапах календарного планирования и оперативного .управления. Более жесткими становятся требования к качеству плановых решений, сокращению сроков их выработки, повышению оперативности и гибкости управления. Всё это обусловило заметное возрастание интереса к вопросам построения оптимальных расписаний для различных эбслуживающих систем.
Многостадийные обслуживающие системы с нефиксированными маршрутами привлекли внимание специалистов в семидесятые годы. Не толь-0 чисто научный интерес, но и необходимость решать новые практи-іеские задачи (например, задачи, возникавшие при организации спут-іиковой связи) привели к появлению целого ряда публикаций, посвя-іенньїх этим системам. С конца семидесятых годов в теории расписа-;ий сформировалось, также направление, в котором изучаются различите одностадийные и многостадийные системы с ограниченными восста-іавливаемнми ресурсами.
Однако до настоящего времени получено крайне мало результатов, :асаюпихся многостадийных систем с нефиксированными маршрутами и граниченными восстанавливаемыми ресурсами. Изучению таких систем посвящена диссертационная работа.
Целью работы- является исследование различных классе задач для многостадийных обслуживающих систем с нефиксирован-ыми маршрутами и ограниченными восстанавливаемыми ресурсами, а менно: доказательство А/Р -трудности некоторых задач; выявление олиномиально разрешимых задач и построение для них.точных эффек-ивных алгоритмов решения.
Научная новизна. Доказана NP -трудность в силь-эм смысле задачи построения оптимального по быстродействию .распития для двухстадийной системы при условии,, что в процессе обслу-івания требований используются восстанавливаемые ресурсы, запас іхдого из которых равен единице. Показано, что задача является 19 -трудной, если имеется точно два ресурса.
Доказана Л/Р -трудность в сильном смысле задачи построения ітимального по быстродействию расписания .для трехстадийной системы >и условиях, что длительности обслуживания требе ваши одинаковы и
- 3 ~
в процессе обслучшвания требований используется ресурс произвольного запаса.
Впервые разработан алгоритм линейной трудоемкости, построения оптимального по быстродействию расписания обслуживания множества требований в двухстадийной системе с нефиксированными маршрутами . при условии, -что .в процессе обслуживания некоторых требований некоторыми приборами используется ресурс единичного запаса.
Шервые рассмотрена задача выбора оптимальных скоростей приборов в двухстадийной системе с нефиксированными маршрутами при условии, что в процессе обслуживания некоторых требований некоторыми приборами используется более половины запаса восстанавливав- мого ресурса. Эта задача сведена к известной в литературе полиномиально разрешимой задача.
Шервые рассмотрена задача построения оптимального по быстродействию расписания обслуживания множества требований в многостадийной системе при условиях, что длительности обслуживания требований приборами одинаковы и в процессе обслуживания некоторых требований некоторыми приборами используется ресурс единичного запаса. Для трехстадийной системы разработан полиномиальный алгоритм, демонстрирующий возможный подход к решению задачи в общем случав.
Практическая ценность. Теоретические результаты, полученные в диссертации, являются основой для дальнейшего развития одного из новых разделов теории расписаний.
Разработанные алгоритмы можно использовать при решении различных практических задач календарного планирования, при создании автоматизированных систем проектирования и управления.
Публикации и апробация работы. Основные результаты диссертации опубликованы в работах А-8/ и докладывались на ill Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеры" (гЛаштагол, 1987), на XI Всесоюзной школе-семи-нарз "Системы программного обеспечения решения задач оптимального планирования" (г.Кострома, 1990), на республиканской конференции молодых ученых и специалистов "Применение информатики и вычислительной техники при решении народнохозяйственных задач" (г.Минск, 1989), на межреспубликанской научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" (г.Иинск, 1990), на научном семинаре по теории расписаний под руководством В.С.Танаева
- «і ,
В ИТК АН БССР (г.Минск, IS8S, 1991).
Структура и объем работы. Диссертация состоит из введения, трех глав, списка литературы (95 наименований) , содержит ПО страниц машинописного текста.