Рассматривается классическая ЫР-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания 1‖∑Тj-. Проведен полный анализ ЫР-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает О (п2Хр;) операций, где п - количество требований, а р;- - продолжительность обслуживания /-го требования,j= 1, 2, ..., п. Библ. 11.
展开▼
