Введение к работе
АКТуалЬНОСТЬ Темы. Теория расписаний - область дискретной оптимизации, возникшая из потребностей практики и оформившаяся в самостоятельную научную дисциплину. Повышение требовательности к оперативности и эффективности принятия решений в различных областях целенаправленной человеческой деятельности в большой степени стимулирует интерес к этому сравнительно молодому разделу исследования операций, сфера возможных приложений которого постоянно расширяется в соответствии с интенсивным ростом современных производств, таких, как гибкие производственные системы, автоматизированные системы управления, вычислительные сети, микропроцессоры, спутниковая связь и пр.
Модель многостадийной обслуживающей системы с различными порядками прохозвдения последовательных приборов требованиями изучалась с середины 50-х годов и стала классической моделью, описание которой традиционно включается в учебники и монографии по теории расписаний. К сожалению, существует очень мало задач этого типа, для которых предложены полиномиальные алгоритмы отыскания точного решения. Подавляющее большинство таких задач являются КР - трудными.
Исследованию некоторых задач теории расписаний, статус которых оставался до недавнего времени открытым, посвящена диссертационная работа.
Связь работы с крупными научными программами, темами.
Диссертационная работа выполнялась с 1991 года по 1995 год в лаборатории математической , кибернетики Института технической кибернетики АКБ в соответствии с плановыми научными исследованиями по теме "Машиностроение 2.25".
Цель И задачи Исследования. Целью работы является выявление полиномиально разрешимых задач для многостадийных обслуживающих систем с различными фиксированными маршрутами обслуживания требований и построение для них точных эффективных алгоритмов решения и установление, тем самым, более четкой границы между полиномиально разрешимыми и КР - трудными задачами теории расписаний.
НауЧНЙЯ НОВИЗНа ПОЛучеННЫХ результатов. Впервые доказана полиномиальная разрешимость минимизации произвольно заданной неубывающей функции для систем, состоящих из фиксированного числа требований и двух приборов при произвольном числе стадий обслуживания и произвольных длительностях операций.
Впервые разработан полиномиальный алгоритм для задачи минимизации суммы моментов завершения обслуживания требований в системе с двумя приборами и одинаковыми длительностями всех операций.
Впервые разработан полиномиальный алгоритм для задачи минимизации числа запаздывающих требований и доказана" WP -трудность в обычном смысле задачи минимизации взвешенного числа запаздывающих требований в системе с двумя приборами и одинаковыми длительностями всех операций.
Исследован класс обслуживающих систем, для которых существуют оптимальные расписания с бесконечно большим радиусом устойчивости, дано исчерпывающее описание таких систем и впервые предложен эффективный критерий их распознавания. Получены необходимые и достаточные условия, при выполнении которых оптимальное по быстродействию расписание обслуживания произвольного множества требований с фиксированными маршрутами имеет бесконечный радиус устойчивости. Полученные условия можно проверить с помощью полиномиального алгоритма. Аналогичные условия получены и для расписаний, минимизирующих максимальное временное смещение.
Практическая ЗНаЧИМОСТЬ ПОЛучеННЫХ результатов. Результаты, полученные в диссертации, являются основой для дальнейшего исследования открытых вопросов теории расписаний и могут быть использованы при решении практических задач календарного планирования.
Зкононическая значимость полученных результатов.
Результаты диссертационной работы носят, в основном, теоретический характер. Оценить их вкономическое значение в настоящий момент не представляется возможным.