Докторская диссертация «Оптимизация процессов обработки заданий в дискретных многостадийных системах» защищена 27.11.2003 в Пензенском государственном университете по специальности 05.13.01 - системный анализ, управление и обработка информации (дата утверждения ВАК 9.04.2004).

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

Основные результаты докторской диссертации:

- Дана новая формализация задачи Беллмана–Джонсона, предложено матричное представление процесса обработки заданий в системах конвейерного типа (построена математическая модель). Построена математическая модель для оптимизационных исследований систем последовательной обработки с повторным обслуживанием.

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

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

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

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

- Определены необходимые и достаточные условия оптимальности расписания в 1-окрестности.