Алгоритм Джонсона — различия между версиями
м |
|||
Строка 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}.
Выходные данные: {i1,i2,...,in}.
Введём дополнительные обозначения:
ti1н – время начала обработки i-детали на первом станке;
ti2н – время начала обработки i-детали на втором станке;
ti1к – время окончания обработки i-детали на первом станке;
ti2к – время окончания обработки i-детали на втором станке;
T – общая длительность обработки всех деталей.
Алгоритм расчёта графика
Входные данные: n; {a1,a2,...,an}; {b1,b2,...,bn}.
Выходные данные: {i1,i2,...,in}; {ti1н}; {ti1к}; {ti2н}; {ti2к}; T.
Другие графики:
Другие алгоритмы:
- алгоритм Дейкстры;
- алгоритм Флойда;
- алгоритм Ху;
- алгоритм Джонсона.