Алгоритм Джонсона — различия между версиями

Материал из ALL
Перейти к: навигация, поиск
м
Строка 39: Строка 39:
 
{{Список ГР}}
 
{{Список ГР}}
 
== Другие алгоритмы: ==
 
== Другие алгоритмы: ==
*[[алгоритм Дейкстры]];
+
{{Список АлгЛ}}
*[[алгоритм Флойда]];
+
*[[алгоритм Ху]].
+
 
== Ссылки ==
 
== Ссылки ==
 
* [[Участник:Logic-samara]]
 
* [[Участник:Logic-samara]]
 
[[Категория:Логистика]][[Категория:Алгоритмы]]
 
[[Категория:Логистика]][[Категория:Алгоритмы]]

Версия 11:33, 29 декабря 2017

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

Обозначения

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

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

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

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

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

{i1, i2, …, in} – оптимальная последовательность обработки деталей на двух станках;

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

Входные данные: n; {a1,a2,...,an}; {b1,b2,...,bn}.

АДЖ01.JPG

Выходные данные: {i1,i2,...,in}.

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

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

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

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

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

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

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

Входные данные: n; {a1,a2,...,an}; {b1,b2,...,bn}.

АД01.JPG

Выходные данные: {i1,i2,...,in}; {ti1н}; {ti1к}; {ti2н}; {ti2к}; T.

Другие графики:

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

Ссылки