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