QpmtnCmax - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:31:13Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:31, 1 сентября 2022

2022-09-01T04:31:42Z

46.183.217.186 в 23:35, 7 июня 2016

2016-06-07T23:35:04Z

46.183.217.186: переписан псевдокод

2016-06-07T22:39:27Z

переписан псевдокод

46.183.217.186: /* Описание алгоритма */

2016-06-07T19:16:26Z

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

46.183.217.186 в 19:14, 7 июня 2016

2016-06-07T19:14:27Z

Внесённые изменения

91.221.67.89: правки

2016-06-05T10:47:17Z

правки

Внесённые изменения

109.248.7.75 в 18:23, 1 июля 2012

2012-07-01T18:23:29Z

AVasilyev: /* Алгоритм построения расписания */

2012-06-23T14:04:30Z

‎Алгоритм построения расписания

194.85.161.2: /* Алгоритм построения расписания */

2012-06-23T13:59:21Z

‎Алгоритм построения расписания

← Предыдущая		Версия 16:31, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	<tex dpi = "200">Q \mid pmtn \mid C_{max}</tex>		<tex dpi = "200">Q \mid pmtn \mid C_{max}</tex>
	{{Задача		{{Задача

← Предыдущая		Версия 04:31, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	<tex dpi = "200">Q \mid pmtn \mid C_{max}</tex>		<tex dpi = "200">Q \mid pmtn \mid C_{max}</tex>
	{{Задача		{{Задача

@@ Строка 10: / Строка 10: @@
 *<tex>P_i = p_1 + \ldots + p_i</tex>, <tex>i = 1 \ldots n</tex> {{---}} сумма первых <tex>i</tex> работ
-*<tex>S_j = s_1 + \ldots + s_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} сумма первых <tex>j</tex> станков
+*<tex>S_j = s_1 + \ldots + s_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} сумма скоростей первых <tex>j</tex> станков
 Необходимое условие для выполнения всех работ в интервале <tex>[0 \ldots T]</tex>:
@@ Строка 25: / Строка 23: @@
 </tex>
-Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
+Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>.
 Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>\mathrm{level}</tex>-алгоритма.
@@ Строка 31: / Строка 29: @@
 ===Псевдокод===
 Функция <tex>\mathrm{level}</tex> принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.
-    '''function''' level(p : '''int[]''', s : '''int[]''', n : '''int''', m : '''int''') : '''vector<int, int, int, int>'''
+    '''function''' level(p : '''int[n]''', s : '''int[m]''') : '''vector<int, int, int, int>'''
        '''vector<int, int, int, int>''' ans
        '''int''' t = 0
-       '''int''' k = n
+       '''int''' k = n  <font color=green> // количество еще не выполненных работ </font>
        sort(p)  <font color=green> // сортируем время обработки работ по убыванию </font>
        sort(s)  <font color=green> // сортируем станки по убыванию скоростей </font>
@@ Строка 40: / Строка 38: @@
           '''int[]''' to = assign(p, k, m)  <font color=green> // получаем распределение работ по станкам </font>
           Найдем минимальное dt1 отличное от нуля такое, что (p[i] - s[to[i]] * dt1) = 0
-          Найдем минимальное dt2 отличное от нуля такое, что p[i] > p[j] и (p[i] - s[to[i]] * dt2 = p[j] - s[to[j]] * dt2)
+          Найдем минимальное dt2 такое, что p[i] > p[j] и (p[i] - s[to[i]] * dt2 = p[j] - s[to[j]] * dt2)  <font color=green> // то есть такое минимальное время, через которое, </font>
           '''int''' dt = min(dt1, dt2)
           '''for''' j = 0 '''to''' n - 1
@@ Строка 53: / Строка 52: @@
 Функция <tex>\mathrm{assign}</tex> принимает на вход массив с объемами работ и возвращает массив с распределением работ.
-    '''function''' assign (p : '''int[]''', n : '''int''', m : '''int''') : '''int[]'''
+    '''function''' assign(p : '''int[n]''', k : '''int''', m : '''int''') : '''int[]'''
-       '''int[]''' to  <font color=green> // j работа обрабатывается на to[j] станке </font>
+       '''int[n]''' to  <font color=green> // j работа обрабатывается на to[j] станке </font>
        fill(to, -1)
        '''int''' i = 0
-       '''while''' i < m '''and''' i < n
+       '''while''' i < m '''and''' i < k
-          Находим первый j такой что p[j] максимальный
+          Находим первый j такой что p[j] максимальный и s не содержит j
           m[j] = i++
        '''return''' to
@@ Строка 92: / Строка 93: @@
 Предположим, что <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \leqslant i \leqslant m-1 </tex>. Тогда <tex>\mathrm{level}</tex> последней работы, выполнявшейся на станке <tex> M_i </tex> в момент времени <tex> f_i - \varepsilon </tex> (где <tex> \varepsilon > 0</tex> достаточно мал) меньше, чем <tex>\mathrm{level}</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию, так как при распределении, работы с наибольшим <tex>\mathrm{level}</tex> выставлялись на самые быстрые станки.
-Пусть <tex> T </tex> = <tex> f_1 = f_2 = f_3 = \ldots = f_j > f_{j+1}</tex> ,где <tex> j < m </tex>. Чтобы работы завершились в момент времени <tex> T </tex>, необходимо начать их в момент времени 0, поскольку если это не выполняется, то у нас найдется работа <tex> J_i </tex> , которая начинается позже <tex> t = 0 </tex> и заканчивается в <tex> T </tex>. Это означает, что в момент времени <tex> 0 </tex> начинаются как минимум <tex> m </tex> работ. Пусть первые <tex> m </tex> работ стартовали вместе на всех машинах. Мы получаем <tex> p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_m(0) \geqslant p_i(0) </tex>, из чего следует, что <tex> p_1(T - \varepsilon) \geqslant \ldots \geqslant p_m(T - \varepsilon) \geqslant p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex>, удовлетворяющего условию <tex> 0 \leqslant \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Пришли к противоречию. Получаем <tex> T = {P_j \over S_j} </tex>.
+Пусть <tex> T </tex> = <tex> f_1 = f_2 = f_3 = \ldots = f_j > f_{j+1}</tex> ,где <tex> j < m </tex>. Чтобы работы завершились в момент времени <tex> T </tex>, необходимо начать их в момент времени 0, поскольку если это не выполняется, то у нас найдется работа <tex> J_i </tex> , которая начинается позже <tex> t = 0 </tex> и заканчивается в <tex> T </tex>. Это означает, что в момент времени <tex> 0 </tex> начинаются как минимум <tex> m </tex> работ. Пусть первые <tex> m </tex> работ стартовали вместе на всех машинах. Мы получаем <tex> p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_m(0) \geqslant p_i(0) </tex>, из чего следует, что <tex> p_1(T - \varepsilon) \geqslant \ldots \geqslant p_m(T - \varepsilon) \geqslant p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex>, удовлетворяющего условию <tex> 0 \leqslant \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Пришли к противоречию. Получаем <tex> T = \dfrac{P_j}{S_j} </tex>.
 }}
@@ Строка 108: / Строка 109: @@
 * Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 124 {{---}} 129 стр. {{---}} ISBN 978-3-540-69515-8
-[[Категория: Дискретная математика и алгоритмы]]
+[[Категория: Алгоритмы и структуры данных]]
 [[Категория: Теория расписаний]]

@@ Строка 2: / Строка 2: @@
 {{Задача
 |definition=
-Дано несколько станков с разной скоростью выполнения работ, работающих параллельно. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.
+Дано <tex>m</tex> станков с разной скоростью выполнения работ, работающих параллельно, и <tex>n</tex> работ. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.
 }}
 ==Алгоритм построения расписания==
 ===Описание алгоритма===
-Пусть нам даны <tex>n</tex> работ и <tex>m</tex> станков. Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнения:<tex> p_1 \geqslant p_2 \geqslant p_3 \ldots \geqslant p_n</tex>, а все машины в порядке убывания скоростей: <tex> s_1 \geqslant s_2 \geqslant s_3 \ldots \geqslant s_m</tex>. Введем следующие обозначения:
+Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнения:<tex> p_1 \geqslant p_2 \geqslant p_3 \ldots \geqslant p_n</tex>, а все машины в порядке убывания скоростей: <tex> s_1 \geqslant s_2 \geqslant s_3 \ldots \geqslant s_m</tex>. Введем следующие обозначения:
-<tex> P_i = p_1 + \ldots + p_i</tex>
+*<tex>P_i = p_1 + \ldots + p_i</tex>, <tex>i = 1 \ldots n</tex> {{---}} сумма первых <tex>i</tex> работ
-<tex> S_j = s_1 + \ldots + s_j</tex>
+<tex> p_i </tex> {{---}} время выполнения <tex>i</tex>-ой работы, <tex> s_j</tex> {{---}} скорость работы <tex> j </tex>-oй машины.
 Необходимое условие для выполнения всех работ в интервале <tex>[0 \ldots T]</tex>:
-<tex> P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT</tex> или <tex>P_n/S_m \leqslant T</tex>
+<tex> P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT</tex> или <tex>\dfrac{P_n}{S_m} \leqslant T</tex>
-Кроме того, должно выполняться условие <tex>P_j/S_j \leqslant T</tex> для всех <tex> j = 1 \ldots m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1 \ldots J_j</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</tex> :
+Кроме того, должно выполняться условие <tex>\dfrac{P_j}{S_j} \leqslant T</tex> для всех <tex> j = 1 \ldots m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1 \ldots J_j</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</tex> :
 <tex>C_{max} = \max
@@ Строка 31: / Строка 30: @@
 ===Псевдокод===
-Функция <tex>\mathrm{level}</tex>:
+Функция <tex>\mathrm{level}</tex> принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.
-    '''function''' level():
+    '''function''' level(p : '''int[]''', s : '''int[]''', n : '''int''', m : '''int''') : '''vector<int, int, int, int>'''
-       '''int''' <tex>t = 0 </tex>
+      '''vector<int, int, int, int>''' ans
-       '''while''' <tex>\exists p(t) > 0</tex>
+      '''int''' t = 0
-          assign(t)
+      '''int''' k = n
-          '''int''' <tex>t_1 = \min (s \mid s > t </tex> '''and''' <tex>p(s) = 0)</tex>
+      sort(p)  <font color=green> // сортируем время обработки работ по убыванию </font>
-          '''int''' <tex>t_2 = \min (s \mid s > t</tex> '''and''' <tex>\exists i</tex>, <tex>j : p_i(t) > p_j(t)</tex> '''and''' <tex>p_i(s) = p_j(s))</tex>
+      sort(s)  <font color=green> // сортируем станки по убыванию скоростей </font>
-          <tex>t = \min(t_1</tex>, <tex>t_2)</tex>  <font color=green> // поиск следующего момента времени, в который нужно будет перераспределить машины/работы </font>
+      '''while''' k > 0
-       Построение расписания
+         '''int[]''' to = assign(p, k, m)  <font color=green> // получаем распределение работ по станкам </font>
+         Найдем минимальное dt1 отличное от нуля такое, что (p[i] - s[to[i]] * dt1) = 0
-Функция <tex>\mathrm{assign}(t)</tex>:
+         Найдем минимальное dt2 отличное от нуля такое, что p[i] > p[j] и (p[i] - s[to[i]] * dt2 = p[j] - s[to[j]] * dt2)
-   '''function''' assign (<tex>t</tex> : '''int'''):
+         '''int''' dt = min(dt1, dt2)
-      <tex>J = \{i \mid p_i(t) > 0\}</tex>  <font color=green> // множество работ с положительным level </font>
+         '''for''' j = 0 '''to''' n - 1
-      <tex>M = \{M_1 \ldots M_m\}</tex>  <font color=green> // множество всех станков </font>
+            '''if''' p[j] > 0
-      '''while''' <tex>J \ne \varnothing</tex> '''or''' <tex>M \ne \varnothing</tex>
+               '''if''' to[j] <tex> \neq </tex> -1  <font color=green> // рассматриваем работы которые обрабатываются в данном распределении</font>
-         '''int''' <tex>maxLevel = \max(p_i(t) \mid i \in J)</tex>  <font color=green> // максимальное значение level из J </font>
+                  ans.push(to[j], j, t, t + dt)
-         '''int''' <tex>count = J.getCount(maxLevel)</tex>  <font color=green> // количество работ с level = maxLevel </font>
+                  p[j] -= s[to[i]] * dt
-         '''int''' <tex>r = \min(|M|</tex>, <tex>count)</tex>
+                  '''if''' p[j] == 0
-         <tex>I \leftarrow \{r</tex> работ из <tex>J \mid p(t) = maxLevel\}</tex>
+                     k--
-         <tex>M' \leftarrow \{r</tex> самых быстрых машин из <tex>M\}</tex>
+         t += dt  <font color=green> // поиск следующего момента времени, в который нужно будет перераспределить машины/работы </font>
-         Распределяем работы
+      '''return''' ans
 ===Асимптотика===
@@ Строка 74: / Строка 80: @@
 Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \geqslant p_2(t) \geqslant \ldots \geqslant p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени <tex>T</tex> нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:
-<tex>  T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n </tex> или <tex> T = {P_n \over S_m} </tex>
+<tex>  T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n </tex> или <tex> T = \dfrac{P_n}{S_m} </tex>
 Таким образом необходимая оценка достигается нашим алгоритмом.

@@ Строка 15: / Строка 15: @@
 <tex>i = 1 \ldots n</tex>,  <tex>j = 1 \ldots m</tex>, <tex> p_i </tex> {{---}} время выполнения <tex>i</tex>-ой работы, <tex> s_j</tex> {{---}} скорость работы <tex> j </tex>-oй машины.
-Необходимое условие для выполнения всех работ в интервале <tex>[0..T]</tex>:
+Необходимое условие для выполнения всех работ в интервале <tex>[0 \ldots T]</tex>:
 <tex> P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT</tex> или <tex>P_n/S_m \leqslant T</tex>
@@ Строка 26: / Строка 26: @@
 </tex>
-Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
+Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
 Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>\mathrm{level}</tex>-алгоритма.

← Предыдущая		Версия 18:23, 1 июля 2012
Строка 1:		Строка 1:
−	<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
−	~~<includeonly>[[Категория: В разработке]]</includeonly>~~
−
	==Постановка задачи==		==Постановка задачи==
	Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.		Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

@@ Строка 12: / Строка 12: @@
 ==Алгоритм построения расписания==
-Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </tex>, а все машины в порядке убывания скоростей: <tex> s_1 \ge s_2 \ge s_3 ... </tex>
+Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </tex>, а все машины в порядке убывания скоростей: <tex> s_1 \ge s_2 \ge s_3 ... </tex>. Введем следующие обозначения:
 <tex> P_i = p_1 + ... + p_i</tex>
@@ Строка 18: / Строка 18: @@
 <tex> S_j = s_1 + ... + s_j</tex>
-Где <tex>i = 1 ... n</tex>;  <tex>j = 1 ... m</tex>; <tex> p_i</tex> - стоимость <tex>i</tex>-ой работы ;<tex> s_j</tex> - скорость работы <tex> j </tex>-oй машины ;
+<tex>i = 1 ... n</tex>,  <tex>j = 1 ... m</tex>, <tex> p_i</tex> - время выполнения <tex>i</tex>-ой работы, <tex> s_j</tex> - скорость работы <tex> j </tex>-oй машины.
-Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:
+Необходимое условие для выполнения всех работ в интервале <tex>[0..T]</tex>:
 <tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или  <tex>P_n/S_m \le T</tex>
@@ Строка 28: / Строка 28: @@
 <tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>
-Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
+Перейдем к описанию алгоритма. Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
 Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level</tex>-алгоритма.
@@ Строка 37: / Строка 37: @@
     '''WHILE''' существуют работы с положительным <tex>level</tex>
         Assign(t)
-        <tex>t1 \leftarrow min(s>t |</tex>находим следующую выполненную работу,где <tex> s</tex> - время ее окончания <tex> ) </tex>
+        <tex>t1 \leftarrow \min (s > t \mid s</tex> - время окончания какой-то работы <tex> ) </tex>
-        <tex>t2 \leftarrow </tex> найти минимальное <tex>s > t</tex>. Для которого выполняется для некоторых работ <tex>i</tex> , <tex>j</tex>:<tex> level_i(t)>level_j(t)</tex> и <tex>  level_i(s) == level_j(s)</tex>
+        <tex>t2 \leftarrow \min (s > t \mid </tex> для некоторых работ <tex>i, j : p_i(t) > p_j(t)</tex> и <tex>  p_i(s) = p_j(s))</tex>
-        <tex> t \leftarrow min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
+        <tex> t \leftarrow \min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
     Построение расписания
@@ Строка 47: / Строка 47: @@
     <tex>M = \{M_1,...,M_m\}</tex> - множество всех станков
     '''WHILE''' множества <tex>J</tex> и <tex>M</tex> не пустые
-       Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,<tex>level</tex> которых максимальный
+       Найти множество работ <tex>I \subset J</tex>, <tex>level</tex> которых максимален.
        <tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
        Назначаем работы из множества <tex>I</tex> на <tex>r</tex> самых быстрых машин из множества <tex>M</tex>
        <tex>J \leftarrow J</tex>\<tex>I</tex>
-       удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин
+       Удаляем из множества <tex>M</tex> <tex>r</tex> самых быстрых машин
 ==Доказательство корректности алгоритма==