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

Версия 18:05, 30 июля 2016

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

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

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.

@@ Строка 37: / Строка 37: @@
 Выходные данные: '''{i<sub>1</sub>,i<sub>2</sub>,...,i<sub>n</sub>}; {t<sub>i1н</sub>}; {t<sub>i1к</sub>}; {t<sub>i2н</sub>}; {t<sub>i2к</sub>}; T'''.
 == Другие графики: ==
-*[[алгоритм Джонсона]];
+{{Список ГР}}
-*[[сетевой график]];
-*[[графики Гантта]];
-*[[график c последовательным движением деталей]];
-*[[график c параллельным движением деталей]];
-*[[график c параллельно-последовательным движением деталей]].
 == Другие алгоритмы: ==
 *[[алгоритм Дейкстры]];