Требуется найти оптимальную последовательность обработки деталей

Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i-й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через Xi - время простоя в ожидании i-й детали, то:
A1
X1 + X2 = max(A1 + A2 - B1, A1)
X1 + X2 + X3 = max(A1 + A2 +A3 - B1 - B2, A1 + A2 - B1, A1)
∑Xi = max(∑Ai - ∑Bi)
Если обозначить через F(t, Ak, Bk/k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, Ak, Bk/k = 1..N) = min(Ai + F(Bi + max(t-Ai,0),Ak,Bk=1..N,k≠i))
Если после i-й детали при оптимальном порядке обрабатывается j-я, то:
F(t, Ak, Bk/k=1..N) = Ai + Aj + F(tij, Ak, Bk/k=1..N; k≠i,j)
где
tij = Bi + max[Bj + max(t-Aj,0) - Aj,0] = Bi + Bj - Ai - Aj + max[t, max(t,max(Aj - Ai - Bj,Aj))]
Если max(Ai + Aj - Bi,Ai) <max(Aj + Ai - Bj, Aj), то сначала разумнее обрабатывать j-ю деталь