Нижняя оценка минимального числа

Алгоритм 5.

1. Первоначально полагаем n = 0.

2. Организуем перебор всех отрезков [?1, ?2]

   

   [0, T] в порядке

   

   Всего таких отрезков T(T+1)/2.

3. Для очередного анализируемого отрезка времени [?1, ?2] находим значение
   

4. Если n' > n, выполняем операцию n := n'. После перебора всех отрезков окажется найденным значение n, которое равно максимальному из значений, удовлетворяющих (7.2).

Пример. Нахождение оценки n.

Нахождение

(4)(?1,?2) будем иллюстрировать графически, возможными временными диаграммами (рис. 7.19).

увеличить изображение
Рис. 7.19.  Нахождение нижней оценки числа исполнителей

Рис. 7.19.  Окончание

В результате анализа всех отрезков находим n = max n' = 2.

Содержание раздела

---