![]() |
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Одним из подходов, используемых при рассмотрения NP-трудных задач теории расписаний, является метрический подход. Он основан на введении метрик, с помощью которых по исходному примеру, не являющемуся полиномиально разрешимым, проекцированием на известную полиномиално разрешимую область, получается оптимальное или приближённое решение. Рассматривается проблема минимизации задачи на быстродействие на двух параллельных приборах с использованием известных алгоритмов со сложностью O(n2) и O(e + nα(n)) для получения полиномиальных решений при рассмотрении работ, выполняемых за равные промежутки времени с заданной последовательностью выполнения: P 2|prec, pj = p|Cmax. Для получения оценки абсолютной погрешности и нахождении приближённого решения для задач теории расписаний проводится эксперимент.