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

Версия 17:23, 1 февраля 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 последовательным движением деталей]];
-* [[График c параллельно-последовательным движением деталей]].
+*[[график c параллельным движением деталей]];
+*[[график c параллельно-последовательным движением деталей]].
 == Другие алгоритмы: ==
-*[[Алгоритм Дейкстры]];
+*[[алгоритм Дейкстры]];
-*[[Алгоритм Флойда]];
+*[[алгоритм Флойда]];
-*[[Алгоритм Ху]].
+*[[алгоритм Ху]].
 == Ссылки ==
 * [[Участник:Logic-samara]]
 [[Категория:Логистика]][[Категория:Алгоритмы]]