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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идея)
(Идея)
Строка 13: Строка 13:
  
 
=== Идея ===
 
=== Идея ===
 +
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>.
  
Назовем множество работ <tex>S</tex> '''выполнимым'''(англ. feasible), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией [[1precpmtnriLmax#edd|EDD правила]]:  
+
Назовем множество работ <tex>S</tex> '''выполнимым'''(англ. ''feasible''), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией EDD правила (см. стр 70 в Брукере):  
  
 
:Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.
 
:Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.
  
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже [[1precpmtnriLmax#correctness|доказанной теоремы]]. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение EDD расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
+
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 (Брукер). Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение EDD расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
  
 
Для данного непустого множества <tex>S</tex> определим следующие величины
 
Для данного непустого множества <tex>S</tex> определим следующие величины
 
:<tex>r(S) =  \min\limits_{i \in S} r_{i} ; p(S) = \sum\limits_{i \in S} p_{i}; w(S) = \sum\limits_{i \in S} w_{i}</tex>
 
:<tex>r(S) =  \min\limits_{i \in S} r_{i} ; p(S) = \sum\limits_{i \in S} p_{i}; w(S) = \sum\limits_{i \in S} w_{i}</tex>
 +
Кроме того, обозначим за <tex>C(S)</tex> время последней выполненной работы из <tex>S</tex> в EDD расписании. Оно состоит из периодов непрерывного выполнения работы, разделенных периодами бездействия, когда нет доступных работ для выполнения. Это означает, что <tex>S</tex> может быть разделено на множества <tex>S_{1} \ldots S_{x}</tex>, для которых выполняется <tex>C(S_{i}) = r(S_{i}) + p(S_{i}) <  r(S_{i + 1})</tex> для <tex>i = 1 \ldots x - 1 </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> методами динамического программирования.
  
 
==Источники информации==
 
==Источники информации==

Версия 01:32, 6 июня 2016

[math]1 \mid r_i, pmtn \mid \sum w_{i}U_{i}[/math]


Задача:
Дана задача на нахождение расписания:
  1. У нас есть несколько работ, которе необходимо выполнит на одном станке.
  2. У работ есть время появления [math]r_i[/math]
  3. Работы разрешается прерывать в любой момент времени.
  4. Все значения целочисленны, веса [math]w_{i}[/math] положительны.
Требуется выполнить все работы, чтобы значение [math]\sum w_i U_i[/math] (суммарный вес просроченных работ) было минимальным.


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

Идея

Пусть работы заданы в порядке неубывания их дедлайнов, то есть [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math]. За [math]k[/math] обозначим количество различных [math]r_{i}[/math].

Назовем множество работ [math]S[/math] выполнимым(англ. feasible), если существует такое расписание для работ из [math]S[/math], что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией EDD правила (см. стр 70 в Брукере):

Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением [math]r_{i}[/math]. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.

[math]S[/math] выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 (Брукер). Если в [math]S[/math] содержится [math]n[/math] работ, то построение EDD расписание может быть выполнено за [math]O(n \log n)[/math] времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.

Для данного непустого множества [math]S[/math] определим следующие величины

[math]r(S) = \min\limits_{i \in S} r_{i} ; p(S) = \sum\limits_{i \in S} p_{i}; w(S) = \sum\limits_{i \in S} w_{i}[/math]

Кроме того, обозначим за [math]C(S)[/math] время последней выполненной работы из [math]S[/math] в EDD расписании. Оно состоит из периодов непрерывного выполнения работы, разделенных периодами бездействия, когда нет доступных работ для выполнения. Это означает, что [math]S[/math] может быть разделено на множества [math]S_{1} \ldots S_{x}[/math], для которых выполняется [math]C(S_{i}) = r(S_{i}) + p(S_{i}) \lt r(S_{i + 1})[/math] для [math]i = 1 \ldots x - 1 [/math].

Выполнимое множество [math]S[/math] является блоком (англ. block), если работы из [math]S[/math] обрабатываются непрерывно с начала и до конца, и [math]S[/math] не может быть разделен на подмножества, расписания для которых не пересекаются, например, если [math]C(S) = r(S)+ p(S)[/math] и [math]S[/math] не является объединением [math]S_{1}[/math] и [math]S_{2}[/math] таких, что [math]C(S_{1}) \lt r(S_{2})[/math]. Решим задачу [math]1 \mid r_i, pmtn \mid \sum w_{i}U_{i}[/math] методами динамического программирования.

Источники информации

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 88-93 ISBN 978-3-540-69515-8