Optprob/Планирование задач с приоритетом и временами перенастройки — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | <!-- p29 --> | + | {{reserve-task|[[Участник:PankratovViktor|PankratovViktor]] 17:38, 29 ноября 2022 (UTC)}}<!-- p29 --> |
{{checked|}} | {{checked|}} | ||
Версия 17:38, 29 ноября 2022
Задача зарезервирована: PankratovViktor 17:38, 29 ноября 2022 (UTC)
Пусть имеется набор из 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 |
Цель задачи — минимизировать общее время производства.