Парное дискретное соревнование со свободным выбором маршрута

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