Редактирование: 1ripmtnsumwu

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 62: Строка 62:
 
В этом случае существует простой в <tex>\mathrm{EDD}</tex> расписании для множества <tex>C(S \setminus \{j\})</tex> после <tex>r_{j}</tex>. Пусть <tex>S'</tex> {{---}} последний блок в <tex>C(S \setminus \{j\})</tex>, то есть <tex>r(S') = \max\{r(B) \mid B </tex> является блоком в <tex> C(S \setminus \{j\}) \} </tex>. Тогда <tex>r(S') \geqslant r_{j}</tex>, в таком случае обязано выполняться равенство <tex>C(S') = C_{j - 1}(r(S'), w(s'))</tex>, иначе расписание для <tex>S</tex> будет не оптимально.  
 
В этом случае существует простой в <tex>\mathrm{EDD}</tex> расписании для множества <tex>C(S \setminus \{j\})</tex> после <tex>r_{j}</tex>. Пусть <tex>S'</tex> {{---}} последний блок в <tex>C(S \setminus \{j\})</tex>, то есть <tex>r(S') = \max\{r(B) \mid B </tex> является блоком в <tex> C(S \setminus \{j\}) \} </tex>. Тогда <tex>r(S') \geqslant r_{j}</tex>, в таком случае обязано выполняться равенство <tex>C(S') = C_{j - 1}(r(S'), w(s'))</tex>, иначе расписание для <tex>S</tex> будет не оптимально.  
  
Кроме того, мы можем предположить, что общее количество сделанной работы в <tex>(S \setminus \{j\}) \setminus S'</tex>, лежащих в интервале <tex>[r_{j}, r(S')]</tex>, {{---}} минимально, учитвая выполнимые множества  <tex>S  \subseteq \{1 \ldots j \}</tex> такие, что <tex>r(S'') \geqslant r, C(S'') \leqslant r(S'), w(S'') \geqslant w - w_{j} - w(S')</tex>.
+
Кроме того, мы можем предположить, что общее количество сделанных работ в <tex>(S \setminus \{j\}) \setminus S'</tex>, лежащих в интервале <tex>[r_{j}, r(S')]</tex>, {{---}} минимально, учитвая выполнимые множества  <tex>S  \subseteq \{1 \ldots j \}</tex> такие, что <tex>r(S'') \geqslant r, C(S'') \leqslant r(S'), w(S'') \geqslant w - w_{j} - w(S')</tex>.
  
Пусть <tex>r, r'</tex> {{---}} даты появления <tex>r \leqslant r_{j} < r</tex>, и <tex>w''</tex> {{---}} некоторое целочисленное значение <tex>0 \leqslant w'' < W</tex>. За <tex>P_{j - 1}(r, r', w'')</tex> возьмем минимальное число сделанной работы в итервале <tex>[r_{j}, r']</tex>,  учитвая выполнимые множества <tex>S  \subseteq \{1 \ldots j \}</tex> такие, что <tex>r(S'') \geqslant r, C(S'') \leqslant r', w(S'') \geqslant w''</tex>. Если таких выполнимых множеств нет, то <tex>P_{j - 1}(r, r', w'') = \infty</tex>.
+
Пусть <tex>r, r'</tex> {{---}} даты появления <tex>r \leqslant r_{j} < r</tex>, и <tex>w''</tex> {{---}} некоторое целочисленное значение <tex>0 \leqslant w'' < W</tex>. За <tex>P_{j - 1}(r, r', w'')</tex> возьмем минимальное число выполненных работ в итервале <tex>[r_{j}, r']</tex>,  учитвая выполнимые множества <tex>S  \subseteq \{1 \ldots j \}</tex> такие, что <tex>r(S'') \geqslant r, C(S'') \leqslant r', w(S'') \geqslant w''</tex>. Если таких выполнимых множеств нет, то <tex>P_{j - 1}(r, r', w'') = \infty</tex>.
 
 
Используя данную запись, количество времен доступнух для обработки работы <tex>j</tex> в интервале <tex>[r_j, r(S')]</tex> записывается формулой
 
:<tex>(r(S') - r_j) - P_{j - 1}(r, r(S'), w - w_j - w(S'))</tex>.
 
 
 
Количество готовности работы (какое количество уже сделано) <tex>j</tex> после времени
 
:<tex>\max(0, p_j - (r(S') - r_j) + P_{j - 1}(r, r(S'), w - w_j - w(S'))</tex>.
 
 
 
И время выполнения последней работы <tex>j</tex> из <tex>S</tex>
 
:<tex>C_j(r,w) = \min\limits_{r', w'} \{ C_{j - 1}(r', w') + \max \{ 0, p_j - r' + r_j + P_{j - 1}(r, r', w - w_j - w'  \} \}</tex>.
 
  
 
=== Конечная формула ===
 
=== Конечная формула ===

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: