32
правки
Изменения
Новая страница: «<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex> {{Задача |definition= Дано <tex>n</tex> работ и 1 станок. Для каждой раб...»
<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>
{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Каждую работу можно прервать и продолжить ее выполнение в любой момент времени. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}
== Решение ==
=== Постановка цели ===
Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна.
=== Jackson Preemptive Schedule ===
<tex>JPS</tex> - это алгоритм построения расписания работ для одной машины с прерываниями. Пусть у нас есть множества работ <tex>O</tex>, для которых надо составить расписание, и множество <tex>P \subset O</tex>, которое состоит из работ, доступных для выполнения на данный момент. Возможны два случая:
# Если машина освободилась, то вставляем в расписание работу <tex>J_i\in P</tex> с наименьшим <tex>d_i</tex>. Также удалим <tex>J_i</tex> из <tex>P</tex>.
# Если машина занята работой <tex>J_k</tex> и в момент времени <tex>r_i</tex> появилась работа <tex>J_i</tex>, тогда если <tex>d_i < d_k</tex>, то прервем <tex>J_k</tex> и поставим на выполнение <tex>J_i</tex>, а <tex>J_k</tex> добавим в <tex>P</tex>. В противном случае просто добавим <tex>J_i</tex> в <tex>P</tex>.
Можно заметить что, если работа была вставлена в <tex>JPS</tex> после своего дедлайна, то данное множество работ <tex>O</tex> не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ <tex>O</tex>, которое будет выполнимым по <tex>JPS</tex> и чей вес будет максимален.
{{Лемма
|statement=Пусть <tex>\Theta=\{t \mid t = r_i + l \cdot p; i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>. Тогда <tex>\forall J_i \in O</tex> время начала <tex>s_i</tex> и время окончания <tex>e_i</tex> этой работы в <tex>JPS</tex> будет принадлежать <tex>\Theta</tex>.
|proof=
Сначала докажем лемму для <tex>e_i</tex>. Пусть <tex>t</tex> - минимальная временная точка такая, что между <tex>t</tex> и <tex>s_i</tex> <tex>JPS</tex> не простаивает. По структуре <tex>JPS</tex> <tex>t = r_x</tex>. Работы, которые выполняются между <tex>s_i</tex> и <tex>e_i</tex>, не могут выполняться ни до <tex>s_i</tex>, ни после <tex>e_i</tex>, даже частично. Это следует из структуры <tex>JPS</tex> - если работа <tex>J_u</tex> была прервана работой <tex>J_v</tex>, то после выполнения <tex>J_v</tex> мы снова вставляем в расписание <tex>J_u</tex>. Таким образом, <tex>e_i - s_i</tex> делится на <tex>p</tex>. Возможны следующие два случая:
# <tex>J_i</tex> вызвало прерывание, тогда <tex>s_i = r_i</tex>.
# <tex>J_i</tex> не вызывало прерываний, следовательно между <tex>r_x</tex> и <tex>s_i</tex> выполнилось некоторое количество работ, тогда <tex>s_i - r_x</tex> делится на <tex>p</tex>.
В любом из этих двух случаев есть такое <tex>r_y = r_x \vee r_i</tex>, такое что <tex>JPS</tex> не простаивает между <tex>r_y</tex> и <tex>e_i</tex>. Тогда <tex>e_i - r_y</tex> делится на <tex>p</tex>. Следовательно, <tex>e_i - r_y</tex> не превышает <tex>n \cdot p</tex>, так как <tex>JPS</tex> не простаивает. Поэтому <tex>e_i \in \Theta</tex>.
Теперь докажем принадлежность <tex>s_i</tex> к <tex>\Theta</tex>. По структуре <tex>JPS</tex> <tex>s_i</tex> - это либо окончание предыдущей работы <tex>e_u</tex>, либо <tex>r_i</tex>. Таким образом, легко понять, что <tex>s_i \in \Theta</tex>.
}}
=== Динамика ===
{{Определение
|id = def1
|definition = <tex>\forall t_u, t_v \in \Theta, u <= v, \forall k = 1, \dots ,n:</tex>
#<tex>U_k(t_u, t_v) = \{J_i \mid i < k ; t_u <= r_i < t_v\};</tex>
#<tex>W_k(t_u, t_v, m)</tex> - максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и <tex>JPS</tex> от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такого <tex>Z</tex> не существует, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}
== См. также ==
* [[P1sumu]]
* [[1pi1sumwu]]
* [[1ripipsumwu]]
== Источники информации ==
Philippe Baptiste - Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Каждую работу можно прервать и продолжить ее выполнение в любой момент времени. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}
== Решение ==
=== Постановка цели ===
Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна.
=== Jackson Preemptive Schedule ===
<tex>JPS</tex> - это алгоритм построения расписания работ для одной машины с прерываниями. Пусть у нас есть множества работ <tex>O</tex>, для которых надо составить расписание, и множество <tex>P \subset O</tex>, которое состоит из работ, доступных для выполнения на данный момент. Возможны два случая:
# Если машина освободилась, то вставляем в расписание работу <tex>J_i\in P</tex> с наименьшим <tex>d_i</tex>. Также удалим <tex>J_i</tex> из <tex>P</tex>.
# Если машина занята работой <tex>J_k</tex> и в момент времени <tex>r_i</tex> появилась работа <tex>J_i</tex>, тогда если <tex>d_i < d_k</tex>, то прервем <tex>J_k</tex> и поставим на выполнение <tex>J_i</tex>, а <tex>J_k</tex> добавим в <tex>P</tex>. В противном случае просто добавим <tex>J_i</tex> в <tex>P</tex>.
Можно заметить что, если работа была вставлена в <tex>JPS</tex> после своего дедлайна, то данное множество работ <tex>O</tex> не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ <tex>O</tex>, которое будет выполнимым по <tex>JPS</tex> и чей вес будет максимален.
{{Лемма
|statement=Пусть <tex>\Theta=\{t \mid t = r_i + l \cdot p; i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>. Тогда <tex>\forall J_i \in O</tex> время начала <tex>s_i</tex> и время окончания <tex>e_i</tex> этой работы в <tex>JPS</tex> будет принадлежать <tex>\Theta</tex>.
|proof=
Сначала докажем лемму для <tex>e_i</tex>. Пусть <tex>t</tex> - минимальная временная точка такая, что между <tex>t</tex> и <tex>s_i</tex> <tex>JPS</tex> не простаивает. По структуре <tex>JPS</tex> <tex>t = r_x</tex>. Работы, которые выполняются между <tex>s_i</tex> и <tex>e_i</tex>, не могут выполняться ни до <tex>s_i</tex>, ни после <tex>e_i</tex>, даже частично. Это следует из структуры <tex>JPS</tex> - если работа <tex>J_u</tex> была прервана работой <tex>J_v</tex>, то после выполнения <tex>J_v</tex> мы снова вставляем в расписание <tex>J_u</tex>. Таким образом, <tex>e_i - s_i</tex> делится на <tex>p</tex>. Возможны следующие два случая:
# <tex>J_i</tex> вызвало прерывание, тогда <tex>s_i = r_i</tex>.
# <tex>J_i</tex> не вызывало прерываний, следовательно между <tex>r_x</tex> и <tex>s_i</tex> выполнилось некоторое количество работ, тогда <tex>s_i - r_x</tex> делится на <tex>p</tex>.
В любом из этих двух случаев есть такое <tex>r_y = r_x \vee r_i</tex>, такое что <tex>JPS</tex> не простаивает между <tex>r_y</tex> и <tex>e_i</tex>. Тогда <tex>e_i - r_y</tex> делится на <tex>p</tex>. Следовательно, <tex>e_i - r_y</tex> не превышает <tex>n \cdot p</tex>, так как <tex>JPS</tex> не простаивает. Поэтому <tex>e_i \in \Theta</tex>.
Теперь докажем принадлежность <tex>s_i</tex> к <tex>\Theta</tex>. По структуре <tex>JPS</tex> <tex>s_i</tex> - это либо окончание предыдущей работы <tex>e_u</tex>, либо <tex>r_i</tex>. Таким образом, легко понять, что <tex>s_i \in \Theta</tex>.
}}
=== Динамика ===
{{Определение
|id = def1
|definition = <tex>\forall t_u, t_v \in \Theta, u <= v, \forall k = 1, \dots ,n:</tex>
#<tex>U_k(t_u, t_v) = \{J_i \mid i < k ; t_u <= r_i < t_v\};</tex>
#<tex>W_k(t_u, t_v, m)</tex> - максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и <tex>JPS</tex> от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такого <tex>Z</tex> не существует, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}
== См. также ==
* [[P1sumu]]
* [[1pi1sumwu]]
* [[1ripipsumwu]]
== Источники информации ==
Philippe Baptiste - Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
