Время простоя определяется графически

В некоторых частных случаях алгоритм Джонсона применяется и для решения задач, требующих трехэтапного обслуживания. Это можно сделать, когда соблюдается одна из следующих систем неравенств:

1) максимальное время обработки изделия на первой машине больше или равно максимальному времени обработки изделия на второй машине:

;

2) минимальное время обработки изделия на третьей машине больше или равно максимальному времени обработки на второй машине:

.

После этого составляется новая таблица для суммы вместо или вместо и к ней применяется алгоритм Джонсона.

Класс задач, к которым применяется алгоритм Джонсона, ограничен. Решение же методом прямого перебора всех возможных вариантах уже при десяти изделиях требует более трех миллионов переборов. В некоторых задачах упорядочения для решения можно использовать методы линейного и динамического программирования.

Задача о назначении.

Задача о назначении в общем виде формулируется так.

Пусть имеется n работ и n кандидатов для выполнения этих работ, назначение кандидата на работу связано с затратами .

Требуется найти назначения кандидатов на все работы, дающие минимальные суммарные затраты: при этом каждого кандидата можно назначить только на одну работу и каждая работа может быть занята только одним кандидатом.

Это типичная экстремальная задача комбинаторного вида, ее решение путем прямого перебора практически невозможно при сколько-нибудь больших , так как число перестановок !