Алгоритм Джонсона — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
'''Алгоритм Джонсона''' — это алгоритм нахождения оптимальной последовательности обработки деталей на двух станках. | '''Алгоритм Джонсона''' — это алгоритм нахождения оптимальной последовательности обработки деталей на двух станках. | ||
| − | + | == Обозначения == | |
Введём обозначения: | Введём обозначения: | ||
| Строка 13: | Строка 12: | ||
'''{i<sub>1</sub>, i<sub>2</sub>, …, i<sub>n</sub>}''' – оптимальная последовательность обработки деталей на двух станках; | '''{i<sub>1</sub>, i<sub>2</sub>, …, i<sub>n</sub>}''' – оптимальная последовательность обработки деталей на двух станках; | ||
| + | == Алгоритм Джонсона == | ||
| + | Входные данные: '''n; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {b<sub>1</sub>,b<sub>2</sub>,...,b<sub>n</sub>}'''. | ||
| + | |||
| + | [[файл:АДЖ01.JPG]] | ||
| + | |||
| + | Выходные данные: '''{i<sub>1</sub>,i<sub>2</sub>,...,i<sub>n</sub>}'''. | ||
| + | |||
| + | Введём дополнительные обозначения: | ||
'''t<sub>i1н</sub>''' – время начала обработки '''i'''-детали на первом станке; | '''t<sub>i1н</sub>''' – время начала обработки '''i'''-детали на первом станке; | ||
| Строка 23: | Строка 30: | ||
'''T''' – общая длительность обработки всех деталей. | '''T''' – общая длительность обработки всех деталей. | ||
| − | |||
== Алгоритм расчёта графика == | == Алгоритм расчёта графика == | ||
Входные данные: '''n; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {b<sub>1</sub>,b<sub>2</sub>,...,b<sub>n</sub>}'''. | Входные данные: '''n; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {b<sub>1</sub>,b<sub>2</sub>,...,b<sub>n</sub>}'''. | ||
| Строка 30: | Строка 36: | ||
Выходные данные: '''{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'''. | Выходные данные: '''{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 параллельно-последовательным движением деталей]]. | ||
| + | == Другие алгоритмы: == | ||
| + | *[[Алгоритм Дейкстры]]; | ||
| + | *[[Алгоритм Флойда]]; | ||
| + | *[[Алгоритм Ху]]. | ||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Логистика]][[Категория:Алгоритмы]] | [[Категория:Логистика]][[Категория:Алгоритмы]] | ||
Версия 16:56, 15 января 2016
Алгоритм Джонсона — это алгоритм нахождения оптимальной последовательности обработки деталей на двух станках.
Содержание
Обозначения
Введём обозначения:
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.
Другие графики:
- Сетевой график;
- Графики Гантта;
- График c последовательным движением деталей;
- График c параллельным движением деталей;
- График c параллельно-последовательным движением деталей.
