Алгоритм Джонсона

Алгоритм Джонсона — это алгоритм нахождения оптимальной последовательности обработки деталей на двух станках.

Обозначения

Введём обозначения:

n – число деталей;

a_i – длительность обработки i-детали на первом станке;

b_i – длительность обработки i-детали на втором станке;

i_j – номер детали на j-ом месте в последовательности;

{i₁, i₂, …, i_n} – оптимальная последовательность обработки деталей на двух станках;

Алгоритм Джонсона

Входные данные: n; {a₁,a₂,...,a_n}; {b₁,b₂,...,b_n}.

Выходные данные: {i₁,i₂,...,i_n}.

Введём дополнительные обозначения:

t_i1н – время начала обработки i-детали на первом станке;

t_i2н – время начала обработки i-детали на втором станке;

t_i1к – время окончания обработки i-детали на первом станке;

t_i2к – время окончания обработки i-детали на втором станке;

T – общая длительность обработки всех деталей.

Алгоритм расчёта графика

Входные данные: n; {a₁,a₂,...,a_n}; {b₁,b₂,...,b_n}.

Выходные данные: {i₁,i₂,...,i_n}; {t_i1н}; {t_i1к}; {t_i2н}; {t_i2к}; T.

Другие алгоритмы:

• алгоритм Дейкстры;
• алгоритм Флойда;
• алгоритм Ху;
• алгоритм Джонсона;
• алгоритм построения сетевого графика;
• алгоритм построения графика Гантта.

Ссылки

• Участник:Logic-samara