Opij1Cmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 3 участников)
Строка 6: Строка 6:
  
 
===Описание алгоритма===
 
===Описание алгоритма===
Минимальное значение <tex> T_{min} </tex> минимизуруемой функции упирается в следующие ограничения:
+
Минимальное значение <tex> C_{max} </tex> упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T_{min} \geqslant  n </tex>.
+
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> C_{max} \geqslant  n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_{min} \geqslant m </tex>.
+
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> C_{max} \geqslant m </tex>.
Тогда <tex> T_{min} = \max{(m, n)} </tex>.
+
Тогда <tex> C_{max} = \max{(m, n)} </tex>.
  
В случае <tex> n \geqslant m </tex> оптимальное расписание циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
+
В случае <tex> n \geqslant m </tex> оптимальное расписание строится циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
        '''1    2    3  ... k  k+1 ... n-1 n'''
+
{| class="wikitable"
  '''M_1'''    1     2     3   ... k  k+1 ... n-1 n
+
|-
  '''M_2'''    n     1     2   ... k-1 k  ... n-2 n-1
+
!             
  '''.'''      ...  ...  ... ... ... ... ... ... ...
+
!| <tex>\textbf1</tex> || <tex>\textbf2</tex> || <tex>\textbf3</tex> ||<tex>\bf{\cdots}</tex>|| <tex>\textbf{n - 1}</tex> || <tex>\textbf{n}</tex>
  '''.'''      ...  ...  ... ... ... ... ... ... ...
+
|- style="text-align:center;"
  '''M_m'''    n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1
+
!<tex>\bf{M_1}</tex>
 +
|| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> ||<tex>\cdots</tex>|| <tex>n - 1</tex> || <tex>n</tex>
 +
|- style="text-align:center;"
 +
!<tex>\bf{M_2}</tex>
 +
|| <tex>n</tex> || <tex>1</tex> || <tex>2</tex> ||<tex>\cdots</tex>|| <tex>n - 2</tex> || <tex>n - 1</tex>
 +
|- style="text-align:center;"
 +
!<tex>\bf{M_3}</tex>
 +
|| <tex>n - 1</tex> || <tex>n</tex> || <tex>1</tex> ||<tex>\cdots</tex>|| <tex>n - 3</tex> || <tex>n - 2</tex>
 +
|- style="text-align:center;"
 +
!<tex>\bf{\vdots}</tex>           
 +
||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\ddots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
 +
|- style="text-align:center;"
 +
!<tex>\bf{M_m}</tex>
 +
|| <tex>n - m + 2</tex> || <tex>n - m + 3</tex> || <tex>n - m + 4</tex> ||<tex>\cdots</tex>|| <tex>n - m</tex> || <tex>n - m + 1</tex>
 +
|}
  
Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.
+
Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.
  
 
===Оценка сложности алгоритма===
 
===Оценка сложности алгоритма===
Строка 27: Строка 41:
 
==См. также.==
 
==См. также.==
 
* [[Методы решения задач теории расписаний]]
 
* [[Методы решения задач теории расписаний]]
 +
* [[O2Cmax|<tex> O2 \mid \mid C_{max} </tex>]]
 +
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max} </tex>]]
 +
* [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:26, 4 сентября 2022

[math]O \mid p_{ij} = 1 \mid C_{max}[/math]

Задача:
Дано [math]m[/math] одинаковых станков, которые работают параллельно и [math]n[/math] работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.

Алгоритм

Описание алгоритма

Минимальное значение [math] C_{max} [/math] упирается в следующие ограничения:

  1. В допустимом расписании на каждом станке надо обработать каждую работу, поэтому [math] C_{max} \geqslant n [/math].
  2. В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому [math] C_{max} \geqslant m [/math].

Тогда [math] C_{max} = \max{(m, n)} [/math].

В случае [math] n \geqslant m [/math] оптимальное расписание строится циклическими сдвигами последовательности [math] 1 \dots n [/math] и выглядит следующим образом:

[math]\textbf1[/math] [math]\textbf2[/math] [math]\textbf3[/math] [math]\bf{\cdots}[/math] [math]\textbf{n - 1}[/math] [math]\textbf{n}[/math]
[math]\bf{M_1}[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]\cdots[/math] [math]n - 1[/math] [math]n[/math]
[math]\bf{M_2}[/math] [math]n[/math] [math]1[/math] [math]2[/math] [math]\cdots[/math] [math]n - 2[/math] [math]n - 1[/math]
[math]\bf{M_3}[/math] [math]n - 1[/math] [math]n[/math] [math]1[/math] [math]\cdots[/math] [math]n - 3[/math] [math]n - 2[/math]
[math]\bf{\vdots}[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\ddots[/math] [math]\vdots[/math] [math]\vdots[/math]
[math]\bf{M_m}[/math] [math]n - m + 2[/math] [math]n - m + 3[/math] [math]n - m + 4[/math] [math]\cdots[/math] [math]n - m[/math] [math]n - m + 1[/math]

Если же [math] n \lt m [/math], добавим [math] m - n [/math] фиктивных работ с номерами [math] n + 1 \dots m [/math], построим расписание способом выше и удалим из полученного расписания фиктивные работы.

Оценка сложности алгоритма

Минимальное значение [math] C_{max} [/math] вычисляется за [math] \mathcal{O}(1) [/math] времени. Построение расписания сводится к заполнению матрицы размером [math] m \times \max{(m, n)} [/math] и выполняется за [math] \mathcal{O}(m \dot (m + n)) [/math] времени.

См. также.