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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
{{Задача
 
{{Задача
 
|definition=Дана задача на нахождение расписания:
 
|definition=Дана задача на нахождение расписания:
# У нас есть несколько работ, которые необходимо выполнить на одном станке.
+
# У нас есть несколько работ, которе необходимо выполнить на одном станке.
 
# У работ есть время появления <tex>r_i</tex>.
 
# У работ есть время появления <tex>r_i</tex>.
 
# Работы разрешается прерывать в любой момент времени.
 
# Работы разрешается прерывать в любой момент времени.
Строка 15: Строка 15:
 
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>. За <tex>W = \sum\limits_{j = 1}^{n} {w_j}</tex>
 
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>. За <tex>W = \sum\limits_{j = 1}^{n} {w_j}</tex>
  
Назовем множество работ <tex>S</tex> '''выполнимым''' (англ. ''feasible''), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией <tex>\mathrm{EDD}</tex> правила <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 70</ref> (<tex>\mathrm{EDD}</tex> (''earliest due date'') правило {{---}} правило наименьшего срока):  
+
Назовем множество работ <tex>S</tex> '''выполнимым''' (англ. ''feasible''), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией <tex>\mathrm{EDD}</tex> правила<ref>см. стр 70 в Брукере</ref> (<tex>\mathrm{EDD}</tex>{{---}} правило наименьшего срока (англ.  ''earliest due date''):  
  
 
:''Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.''
 
:''Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.''
  
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в <tex>\mathrm{EDD}</tex> расписании выполняются без опозданий. Это прямое следствие из теоремы 4.4 <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 70</ref>. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение <tex>\mathrm{EDD}</tex> расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
+
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в <tex>\mathrm{EDD}</tex> расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 <ref>см. стр 70 в Брукере</ref>. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение <tex>\mathrm{EDD}</tex> расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
  
 
Для данного непустого множества <tex>S</tex> определим следующие величины:
 
Для данного непустого множества <tex>S</tex> определим следующие величины:
Строка 29: Строка 29:
 
Выполнимое множество <tex>S</tex> является '''блоком''' (англ. ''block''), если работы из <tex>S</tex> обрабатываются непрерывно с начала и до конца, и <tex>S</tex> не может быть разделен на подмножества, расписания для которых не пересекаются, например, если <tex>C(S) = r(S)+ p(S)</tex> и <tex>S</tex> не является объединением <tex>S_{1}</tex> и <tex>S_{2}</tex> таких, что <tex>C(S_{1}) < r(S_{2})</tex>. Решим задачу <tex dpi>1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex> методами [[Динамическое программирование|динамического программирования]].
 
Выполнимое множество <tex>S</tex> является '''блоком''' (англ. ''block''), если работы из <tex>S</tex> обрабатываются непрерывно с начала и до конца, и <tex>S</tex> не может быть разделен на подмножества, расписания для которых не пересекаются, например, если <tex>C(S) = r(S)+ p(S)</tex> и <tex>S</tex> не является объединением <tex>S_{1}</tex> и <tex>S_{2}</tex> таких, что <tex>C(S_{1}) < r(S_{2})</tex>. Решим задачу <tex dpi>1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex> методами [[Динамическое программирование|динамического программирования]].
  
Введем величину <tex>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое, причём выполняется <tex> r(S) \geqslant r \wedge w(S) \geqslant w  \}</tex> и <tex>C_{i}(r, w) = \infty</tex>, если множеств, удовлетворяющих условиям, нет.
+
Введем величину <tex>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое <tex> \wedge r(S) \geqslant r \wedge w(S) \geqslant w  \}</tex> и <tex>C_{i}(r, w) = \infty</tex>, если множеств, удовлетворяющих условиям, нет.
  
 
Максимальный вес выполнимого множества задается максимальным значением <tex>w</tex> такого, что <tex>C_{n}(r_{\min}, w)</tex> конечно, где <tex>r_{\min} = \min\limits_{j = 1 \ldots n} r_{i}</tex>. Посчитаем значения <tex>C_{j}(r, w)</tex> за <tex>n</tex> итераций с начальными значениями:
 
Максимальный вес выполнимого множества задается максимальным значением <tex>w</tex> такого, что <tex>C_{n}(r_{\min}, w)</tex> конечно, где <tex>r_{\min} = \min\limits_{j = 1 \ldots n} r_{i}</tex>. Посчитаем значения <tex>C_{j}(r, w)</tex> за <tex>n</tex> итераций с начальными значениями:
Строка 35: Строка 35:
 
:<tex>C_{0}(r, w) = \infty</tex> для всех <tex>r</tex> и <tex>w > 0</tex>
 
:<tex>C_{0}(r, w) = \infty</tex> для всех <tex>r</tex> и <tex>w > 0</tex>
  
<tex>j</tex> не может содержаться в выполнимом множестве, если <tex>r(S) > r_{j}</tex>. Следовательно,
+
<tex>j</tex> не может содержаться в выполнимом множестве, если <tex>r(S) > r_{j}</tex>. Следовательно
 
:<p>
 
:<p>
 
<tex>C_{j}(r, w)  
 
<tex>C_{j}(r, w)  
\left \{\begin{array}{ll} = C_{j - 1}(r, w), & \text{if } r > r_{j} \\
+
\left \{\begin{array}{ll} = C_{j - 1}(r, w)  & \text{if } r > r_{j} \\
 
\leqslant  C_{j - 1}(r, w), & \text{otherwise} \end{array} \right.  
 
\leqslant  C_{j - 1}(r, w), & \text{otherwise} \end{array} \right.  
 
</tex>
 
</tex>
Строка 45: Строка 45:
 
Отсюда следует, что нам нужно посчитать только такие значения <tex>C_{j} (r, w)</tex> для которых <tex>r \leqslant r_{j}</tex>. Пусть <tex> S \subseteq \{ 1 \ldots j \} </tex> и <tex>C_{j}(r, w) = C(S)</tex>. Если <tex>j \notin S</tex>, тогда <tex>C_{j}(r, w) = C_{j - 1}(r, w)</tex>. Иначе рассмотрим два случая.
 
Отсюда следует, что нам нужно посчитать только такие значения <tex>C_{j} (r, w)</tex> для которых <tex>r \leqslant r_{j}</tex>. Пусть <tex> S \subseteq \{ 1 \ldots j \} </tex> и <tex>C_{j}(r, w) = C(S)</tex>. Если <tex>j \notin S</tex>, тогда <tex>C_{j}(r, w) = C_{j - 1}(r, w)</tex>. Иначе рассмотрим два случая.
  
=== Разбор случаев ===
+
=== Первый случай ===
 
 
==== Первый случай ====
 
 
Работа <tex>j</tex> начинается после <tex>C(S \setminus \{j\})</tex>.  
 
Работа <tex>j</tex> начинается после <tex>C(S \setminus \{j\})</tex>.  
  
Рассмотрим два подслучая:
+
Рассмотрим два подслучая, для <tex>C(S \setminus \{j\}) \leqslant r_{j}</tex> и <tex>C(S \setminus \{j\}) > r_{j}</tex>.
# <tex>C(S \setminus \{j\}) \leqslant r_{j}</tex> <br> В этом случае <tex>C(S) = r_{j} + p_{j}</tex>
+
# В первом случае <tex>C(S) = r_{j} + p_{j}</tex>
# <tex>C(S \setminus \{j\}) > r_{j}</tex> <br>Работы из <tex>C(S \setminus \{j\})</tex> обрабатываются непрерывно в интервале <tex>[r_{j}, C(S \setminus \{j\})]</tex>, потому что иначе <tex>j</tex> начнет обрабатываться до <tex>C(S \setminus \{j\})</tex>.
+
# Во втором работы из <tex>C(S \setminus \{j\})</tex> обрабатываются непрерывно в интервале <tex>[r_{j}, C(S \setminus \{j\})]</tex>, потому что иначе <tex>j</tex> начнет обрабатываться до <tex>C(S \setminus \{j\})</tex>.
  
 
Делаем вывод, что <tex>C_{j} (r, w) = \max(r_{j} , C(S \setminus \{j\}) + p_{j}</tex>. Предположим, что <tex>C(S \setminus \{j\})</tex> такое, что <tex>C(S \setminus \{j\}) = C_{j - 1}(r, w - w_{j})</tex> и, если это не так, заменим  <tex>C(S \setminus \{j\})</tex> на выполнимое подмножество из <tex>1 \ldots j - 1</tex> для которого это выполняется. Из этого следует, что
 
Делаем вывод, что <tex>C_{j} (r, w) = \max(r_{j} , C(S \setminus \{j\}) + p_{j}</tex>. Предположим, что <tex>C(S \setminus \{j\})</tex> такое, что <tex>C(S \setminus \{j\}) = C_{j - 1}(r, w - w_{j})</tex> и, если это не так, заменим  <tex>C(S \setminus \{j\})</tex> на выполнимое подмножество из <tex>1 \ldots j - 1</tex> для которого это выполняется. Из этого следует, что
 
:<tex>C_{j}(r, w) = \max(r_{j} , C_{j - 1}(r, w − w_{j})) + p_{j}</tex>.
 
:<tex>C_{j}(r, w) = \max(r_{j} , C_{j - 1}(r, w − w_{j})) + p_{j}</tex>.
  
==== Второй случай ====
+
=== Второй случай ===
 
Работа <tex>j</tex> начинается перед <tex>C(S \setminus \{j\})</tex>.  
 
Работа <tex>j</tex> начинается перед <tex>C(S \setminus \{j\})</tex>.  
  

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

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

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

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