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

Материал из DISCOPAL
Перейти к: навигация, поиск
м (StasFomin переименовал страницу Optprob/Планирование задач с приоритетом и временами настройки в [[Optprob/Планирование задач с приоритетом и вре…)
 
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
<!-- p29 -->
 
<!-- p29 -->
−
{{checked|}}
+
{{checked|[[Участник:StasFomin|StasFomin]] 12:41, 23 декабря 2022 (UTC)}}
  
−
Пусть имеется набор из n=20 производственных задач.  
+
[[File:Планирование задач с приоритетом и временами перенастройки_2023-12-23_04-09-41_image0.png|right]]
 +
 
 +
Пусть имеется набор из n=10 производственных задач.  
  
 
Каждая задача имеет время выполнения.  
 
Каждая задача имеет время выполнения.  
 +
  
 
{| class=wikitable
 
{| class=wikitable
Строка 18: Строка 21:
 
| 9
 
| 9
 
| 10
 
| 10
−
| 11
 
−
| 12
 
−
| 13
 
−
| 14
 
−
| 15
 
−
| 16
 
−
| 17
 
−
| 18
 
−
| 19
 
−
| 20
 
 
|-
 
|-
 
| 12
 
| 12
Строка 39: Строка 32:
 
| 11
 
| 11
 
| 18
 
| 18
−
| 29
 
−
| 10
 
−
| 5
 
−
| 9
 
−
| 14
 
−
| 16
 
−
| 15
 
−
| 16
 
−
| 20
 
−
| 25
 
 
|}
 
|}
  
 
Надо составить график выполнения заданий на производственном станке.  
 
Надо составить график выполнения заданий на производственном станке.  
 
Для этого устанавливаются n позиций в последовательности обработки, так что каждая задача должна быть назначена на позицию.  
 
Для этого устанавливаются n позиций в последовательности обработки, так что каждая задача должна быть назначена на позицию.  
−
 
  
  
Строка 80: Строка 62:
 
| 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: Строка 84:
 
| 9
 
| 9
 
| 10
 
| 10
−
| 11
 
−
| 12
 
−
| 13
 
−
| 14
 
−
| 15
 
−
| 16
 
−
| 17
 
−
| 18
 
−
| 19
 
−
| 20
 
 
|-
 
|-
 
| 1
 
| 1
Строка 143: Строка 94:
 
| 6
 
| 6
 
| 7
 
| 7
−
| 7
+
| 8
−
| 7
+
| 9
−
| 6
+
−
| 5
+
−
| 4
+
−
| 4
+
−
| 4
+
−
| 3
+
−
| 3
+
−
| 2
+
−
| 2
+
−
| 1
+
 
|-
 
|-
 
| 2
 
| 2
Строка 167: Строка 108:
 
| 0
 
| 0
 
| 9
 
| 9
−
| 8
 
−
| 7
 
−
| 6
 
−
| 5
 
−
| 4
 
−
| 3
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 12
 
 
|-
 
|-
 
| 3
 
| 3
Строка 182: Строка 113:
 
| 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: Строка 129:
 
| 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: Строка 144:
 
| 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: Строка 153:
 
| 0
 
| 0
 
| 1
 
| 1
 +
| 10
 
| 1
 
| 1
−
| 1
+
| 20
−
| 2
+
−
| 2
+
−
| 2
+
−
| 1
+
−
| 1
+
−
| 0
+
−
| 9
+
−
| 8
+
−
| 7
+
−
| 6
+
−
| 3
+
 
|-
 
|-
 
| 7
 
| 7
Строка 277: Строка 168:
 
| 1
 
| 1
 
| 0
 
| 0
−
| 2
 
−
| 2
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
−
| 7
 
−
| 6
 
 
|-
 
|-
 
| 8
 
| 8
Строка 299: Строка 180:
 
| 1
 
| 1
 
| 2
 
| 2
−
| 2
 
−
| 2
 
−
| 1
 
−
| 1
 
−
| 0
 
−
| 9
 
−
| 8
 
−
| 7
 
−
| 6
 
−
| 3
 
 
|-
 
|-
 
| 9
 
| 9
−
| 2
+
| 9
 
| 1
 
| 1
 
| 1
 
| 1
Строка 320: Строка 191:
 
| 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
 
|}
 
|}
Строка 578: Строка 209:
  
 
Цель задачи — минимизировать общее время производства.
 
Цель задачи — минимизировать общее время производства.
 +
 +
{{optsolv|Планирование_задач_с_приоритетом_и_временами_перенастройки}}
 +
{{vim|784110182}}
 +
* [[Участник:PankratovViktor/Планирование задач с приоритетом и временами перенастройки]]
  
 
{{enddiv}}
 
{{enddiv}}
  
−
[[Категория:OptimizationProblems]]
+
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

Текущая версия на 11:19, 3 октября 2024

Проверено: StasFomin 12:41, 23 декабря 2022 (UTC)

Планирование задач с приоритетом и временами перенастройки 2023-12-23 04-09-41 image0.png

Пусть имеется набор из 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.

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

📺 видео 📺

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