Метод запрещенных клеток

1. Находим любой опорный план (необязательно невырожденный), например, по методу «северо-западного угла».

2. Вычисляем критерий для получения плана Т ₁ = max t_ij.

3. Запрещаем все маршруты в свободных клетках, у которых время t_ij ≥ Т ₁.

4. Зафиксируем в плане занятую клетку с максимальным t_ij ( узкое место ).

5. Ищем цикл, при помощи которого можно «разгрузить» эту клетку, и переносим по этому циклу величину груза k. Циклы необязательно должны быть правильными. Причем может быть, что освободить такую клетку можно только за несколько циклов.

6. Получим план с новым значением Т ₂ = max t_ij. Запрещаем свободные клетки, для которых t_ij Т₂, и переходим к п. 4,

Повторяем до тех пор, пока будет невозможно составить ни одного цикла, разгружающего занятую клетку с максимальным временем.