Optprob/Планирование задач с приоритетом и временами перенастройки — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена Категория:OptimizationProblems на {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}) |
||
| Строка 214: | Строка 214: | ||
{{enddiv}} | {{enddiv}} | ||
| − | + | {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}} | |
Версия 11:59, 23 декабря 2023
Проверено: StasFomin 12:41, 23 декабря 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 |
Цель задачи — минимизировать общее время производства.