Optprob/Планирование задач с приоритетом и временами перенастройки — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
м (StasFomin переименовал страницу Optprob/Планирование задач с приоритетом и временами настройки в [[Optprob/Планирование задач с приоритетом и вре…)
Строка 2: Строка 2:
 
{{checked|}}
 
{{checked|}}
  
−
Пусть имеется набор из n=20 производственных задач.  
+
Пусть имеется набор из n=10 производственных задач.  
  
 
Каждая задача имеет время выполнения.  
 
Каждая задача имеет время выполнения.  
 +
  
 
{| class=wikitable
 
{| class=wikitable
Строка 18: Строка 19:
 
| 9
 
| 9
 
| 10
 
| 10
−
| 11
 
−
| 12
 
−
| 13
 
−
| 14
 
−
| 15
 
−
| 16
 
−
| 17
 
−
| 18
 
−
| 19
 
−
| 20
 
 
|-
 
|-
−
| 12
+
|  
 
| 14
 
| 14
 
| 25
 
| 25
Строка 39: Строка 30:
 
| 11
 
| 11
 
| 18
 
| 18
−
| 29
 
−
| 10
 
−
| 5
 
−
| 9
 
−
| 14
 
−
| 16
 
−
| 15
 
−
| 16
 
−
| 20
 
−
| 25
 
 
|}
 
|}
  
 
Надо составить график выполнения заданий на производственном станке.  
 
Надо составить график выполнения заданий на производственном станке.  
 
Для этого устанавливаются n позиций в последовательности обработки, так что каждая задача должна быть назначена на позицию.  
 
Для этого устанавливаются n позиций в последовательности обработки, так что каждая задача должна быть назначена на позицию.  
−
 
  
  
Строка 80: Строка 60:
 
| 7
 
| 7
 
| 1
 
| 1
−
|-
 
−
| 14
 
−
| 12
 
−
| 11
 
 
|-
 
|-
 
| 10
 
| 10
 
| 5
 
| 5
 
| 8
 
| 8
−
|-
 
−
| 12
 
−
| 11
 
−
| 4
 
−
|-
 
−
| 19
 
−
| 20
 
−
| 5
 
−
|-
 
−
| 16
 
−
| 18
 
−
| 4
 
−
|-
 
−
| 5
 
−
| 8
 
−
| 10
 
 
|}
 
|}
−
 
  
 
* Между задачами нужна перенастройка станка. Если задача i находится на позиции k, а задача j — на позиции k + 1, добавляется дополнительное машинное время, s_ij.
 
* Между задачами нужна перенастройка станка. Если задача i находится на позиции k, а задача j — на позиции k + 1, добавляется дополнительное машинное время, s_ij.
  
−
{{WikiCutBegin|матрица 20×20}}
+
{{WikiCutBegin|матрица 10×10}}
 
{| class=wikitable
 
{| class=wikitable
 
|-
 
|-
Строка 123: Строка 82:
 
| 9
 
| 9
 
| 10
 
| 10
−
| 11
 
−
| 12
 
−
| 13
 
−
| 14
 
−
| 15
 
−
| 16
 
−
| 17
 
−
| 18
 
−
| 19
 
−
| 20
 
 
|-
 
|-
 
| 1
 
| 1
−
| 0
+
|  
 
| 1
 
| 1
 
| 2
 
| 2
Строка 143: Строка 92:
 
| 6
 
| 6
 
| 7
 
| 7
−
| 7
+
| 8
−
| 7
+
| 9
−
| 6
+
−
| 5
+
−
| 4
+
−
| 4
+
−
| 4
+
−
| 3
+
−
| 3
+
−
| 2
+
−
| 2
+
−
| 1
+
 
|-
 
|-
 
| 2
 
| 2
Строка 167: Строка 106:
 
| 0
 
| 0
 
| 9
 
| 9
−
| 8
 
−
| 7
 
−
| 6
 
−
| 5
 
−
| 4
 
−
| 3
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 12
 
 
|-
 
|-
 
| 3
 
| 3
Строка 182: Строка 111:
 
| 1
 
| 1
 
| 0
 
| 0
−
| 2
 
−
| 2
 
 
| 2
 
| 2
−
| 3
 
−
| 3
 
−
| 3
 
−
| 3
 
−
| 3
 
−
| 3
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
 
| 3
 
| 3
 
| 4
 
| 4
−
| 4
+
| 5
 +
| 6
 +
| 7
 +
| 8
 
|-
 
|-
 
| 4
 
| 4
Строка 208: Строка 127:
 
| 2
 
| 2
 
| 2
 
| 2
−
| 2
+
| 13
−
| 2
+
| 12
−
| 2
+
| 11
−
| 1
+
−
| 1
+
−
| 0
+
−
| 9
+
−
| 8
+
−
| 7
+
−
| 6
+
−
| 4
+
−
| 3
+
−
| 4
+
 
|-
 
|-
 
| 5
 
| 5
 
| 4
 
| 4
 
| 1
 
| 1
−
| 1
+
| 10
−
| 2
+
| 20
 
| 0
 
| 0
 
| 2
 
| 2
Строка 233: Строка 142:
 
| 2
 
| 2
 
| 2
 
| 2
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
−
| 7
 
−
| 6
 
−
| 3
 
−
| 3
 
 
|-
 
|-
 
| 6
 
| 6
 
| 4
 
| 4
−
| 5
+
| 15
 
| 6
 
| 6
 
| 3
 
| 3
Строка 252: Строка 151:
 
| 0
 
| 0
 
| 1
 
| 1
 +
| 10
 
| 1
 
| 1
−
| 1
+
| 20
−
| 2
+
−
| 2
+
−
| 2
+
−
| 1
+
−
| 1
+
−
| 0
+
−
| 9
+
−
| 8
+
−
| 7
+
−
| 6
+
−
| 3
+
 
|-
 
|-
 
| 7
 
| 7
Строка 277: Строка 166:
 
| 1
 
| 1
 
| 0
 
| 0
−
| 2
 
−
| 2
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
−
| 7
 
−
| 6
 
 
|-
 
|-
 
| 8
 
| 8
Строка 299: Строка 178:
 
| 1
 
| 1
 
| 2
 
| 2
−
| 2
+
|-
−
| 2
+
−
| 1
+
−
| 1
+
−
| 0
+
 
| 9
 
| 9
−
| 8
 
−
| 7
 
−
| 6
 
−
| 3
 
−
|-
 
 
| 9
 
| 9
−
| 2
 
 
| 1
 
| 1
 
| 1
 
| 1
Строка 320: Строка 189:
 
| 4
 
| 4
 
| 0
 
| 0
−
| 3
 
−
| 3
 
−
| 3
 
−
| 1
 
−
| 0
 
−
| 7
 
−
| 7
 
−
| 7
 
−
| 3
 
−
| 3
 
 
| 3
 
| 3
 
|-
 
|-
 
| 10
 
| 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
 
| 8
−
| 7
 
−
| 6
 
−
| 0
 
−
| 1
 
 
| 2
 
| 2
−
| 3
 
 
| 4
 
| 4
−
| 5
 
−
| 6
 
 
| 4
 
| 4
−
| 2
 
−
| 2
 
−
|-
 
−
| 12
 
−
| 2
 
−
| 2
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
−
| 7
 
−
| 6
 
−
| 1
 
−
| 0
 
−
| 1
 
−
| 2
 
−
| 3
 
 
| 4
 
| 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
 
| 4
−
| 1
 
−
| 0
 
−
| 2
 
−
| 0
 
−
| 3
 
 
| 4
 
| 4
−
| 5
 
−
| 5
 
−
| 1
 
−
|-
 
−
| 16
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 2
 
−
| 2
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
−
| 7
 
−
| 6
 
−
| 5
 
 
| 4
 
| 4
−
| 0
 
−
| 2
 
−
| 1
 
−
| 2
 
−
| 2
 
−
|-
 
−
| 17
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
 
| 7
 
| 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
 
| 0
 
|}
 
|}

Версия 13:24, 27 ноября 2022

Пусть имеется набор из n=10 производственных задач.

Каждая задача имеет время выполнения.


1 2 3 4 5 6 7 8 9 10
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.

Цель задачи — минимизировать общее время производства.

Источник — «https://discopal.ispras.ru/index.php?title=Optprob/Планирование_задач_с_приоритетом_и_временами_перенастройки&oldid=22021»