Optprob/Планирование задач с приоритетом и временами перенастройки — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
| 10 | | 10 | ||
|- | |- | ||
| − | | | + | | 12 |
| 14 | | 14 | ||
| 25 | | 25 | ||
| Строка 84: | Строка 84: | ||
|- | |- | ||
| 1 | | 1 | ||
| − | | | + | | 0 |
| 1 | | 1 | ||
| 2 | | 2 | ||
Версия 13:25, 27 ноября 2022
Пусть имеется набор из n=10 производственных задач.
Каждая задача имеет время выполнения.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 12 | 14 | 25 | 10 | 13 | 18 | 7 | 9 | 11 | 18 |
Надо составить график выполнения заданий на производственном станке. Для этого устанавливаются n позиций в последовательности обработки, так что каждая задача должна быть назначена на позицию.
Кроме того:
- Между задачами существуют условные прецеденты: Задача i должна быть обработана после j, если задача t была обработана до i. Это собрано в бинарном атрибуте A_ijt.
| I | j | t |
| 1 | 2 | 3 |
| 4 | 6 | 3 |
| 3 | 10 | 8 |
| 8 | 7 | 1 |
| 10 | 5 | 8 |
- Между задачами нужна перенастройка станка. Если задача i находится на позиции k, а задача j — на позиции k + 1, добавляется дополнительное машинное время, s_ij.
матрица 10×10
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 1 | 0 | 2 | 2 | 2 | 2 | 1 | 1 | 0 | 9 |
| 3 | 1 | 1 | 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 4 | 2 | 2 | 3 | 0 | 1 | 2 | 2 | 13 | 12 | 11 |
| 5 | 4 | 1 | 10 | 20 | 0 | 2 | 1 | 1 | 2 | 2 |
| 6 | 4 | 15 | 6 | 3 | 0 | 0 | 1 | 10 | 1 | 20 |
| 7 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 0 |
| 8 | 1 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 1 | 2 |
| 9 | 9 | 1 | 1 | 1 | 4 | 3 | 3 | 4 | 0 | 3 |
| 10 | 8 | 2 | 4 | 4 | 4 | 4 | 4 | 4 | 7 | 0 |
Цель задачи — минимизировать общее время производства.