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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 2 участников)
Строка 6: Строка 6:
 
== Описание алгоритма ==
 
== Описание алгоритма ==
 
=== Идея ===
 
=== Идея ===
Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в срок. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке.<br>
+
Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в срок. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке. Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу <tex>i</tex> с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.
Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу <tex>i</tex> с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.<br>
 
  
 
=== Псевдокод ===
 
=== Псевдокод ===
Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Тогда следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
+
Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда работа <tex>j</tex> опаздывает, если <tex>\left\lfloor \dfrac{t}{m} \right\rfloor + p_j > d_j</tex>, где <tex>p_j = 1</tex>. Следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
  
 
   <tex>S = \varnothing</tex>
 
   <tex>S = \varnothing</tex>
 +
  <tex>t = 0</tex>
 
   '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
 
   '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
 
       '''if''' <tex>j</tex> опаздывает, и все более ранние простои заполнены
 
       '''if''' <tex>j</tex> опаздывает, и все более ранние простои заполнены
Строка 19: Строка 19:
 
             заменить <tex>i</tex> на <tex>j</tex> в <tex>S</tex>
 
             заменить <tex>i</tex> на <tex>j</tex> в <tex>S</tex>
 
       '''else'''
 
       '''else'''
 +
        <tex>t = t + 1</tex>
 
         добавить <tex>i</tex> в <tex>S</tex> и поставить <tex>i</tex> на место самого раннего простоя
 
         добавить <tex>i</tex> в <tex>S</tex> и поставить <tex>i</tex> на место самого раннего простоя
Чтобы уметь быстро определять опаздывающие работы, можно, например, завести счетчик <tex>t</tex>, изначально  <tex>t = 0</tex>, и каждый раз, когда мы добавляем в <tex>S</tex> новый элемент, увеличивать на единицу его значение. Тогда <tex>j</tex> опаздывает, если <tex>\lceil \frac{t}{m} \rceil + p_j > d_j</tex>, где <tex>p_j = 1</tex>.<br>
 
 
Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.
 
Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.
  
 
=== Асимптотика ===
 
=== Асимптотика ===
Данный алгоритм может быть реализован за время <tex>O(n\log{n})</tex>.
+
Данный алгоритм может быть реализован за время <tex>O(n\log{n})</tex>, например, если хранить значения <tex>w_i</tex>, которые принадлежат <tex>S</tex>, в [[Приоритетные очереди|приоритетной очереди]] и для множества <tex>S</tex> использовать любую структуру данных, у которой операции поиска и добавления элемента не хуже, чем <tex>O(\log{n})</tex>.
  
 
== Доказательство корректности ==
 
== Доказательство корректности ==
Строка 32: Строка 32:
 
|proof=
 
|proof=
 
Пусть <tex>S</tex> {{---}} множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа <tex>j</tex> заменила работу <tex>i</tex>, которая успевала выполниться до истечения <tex>d_i</tex>, то <tex>j</tex> так же успеет выполниться в срок, потому что <tex>d_i \leqslant d_j</tex>.<br>
 
Пусть <tex>S</tex> {{---}} множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа <tex>j</tex> заменила работу <tex>i</tex>, которая успевала выполниться до истечения <tex>d_i</tex>, то <tex>j</tex> так же успеет выполниться в срок, потому что <tex>d_i \leqslant d_j</tex>.<br>
Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании.<br>
+
Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании. Определим работы <tex>l</tex> и <tex>k</tex> следующим образом:
Определим работы <tex>l</tex> и <tex>k</tex> следующим образом:
 
 
* <tex>l</tex> {{---}} первая работа в <tex>S</tex>: <tex>l \notin S^*</tex>
 
* <tex>l</tex> {{---}} первая работа в <tex>S</tex>: <tex>l \notin S^*</tex>
 
* <tex>k</tex> {{---}} первая работа в <tex>S^*</tex>: <tex>k \notin S</tex>
 
* <tex>k</tex> {{---}} первая работа в <tex>S^*</tex>: <tex>k \notin S</tex>
Покажем, что в <tex>S^*</tex> работа <tex>k</tex> может быть заменена работой <tex>l</tex> без увеличения значения целевой функции. Рассмотрим два случая:<br>
+
Покажем, что в <tex>S^*</tex> работа <tex>k</tex> может быть заменена работой <tex>l</tex> без увеличения значения целевой функции. Рассмотрим два случая:
# Пусть <tex>l < k</tex>.<br>
+
# Пусть <tex>l < k</tex>.
#:То, что <tex>k</tex> не принадлежит множеству <tex>S</tex>, значит, что либо на некотором шаге появилась опаздывающая работа <tex>j</tex>, которая заменила <tex>k</tex>, либо работа <tex>k</tex> опаздывала и <tex>w_k</tex> было меньше <tex>\min\limits_{i \in S}w_i</tex>, и поэтому она не была добавлена. В любом случае в это время работа <tex>l</tex> уже принадлежала <tex>S</tex>. Во втором случае очевидно, что <tex>w_k \leqslant w_l</tex>. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали <tex>k</tex>, а не <tex>l</tex>. Следовательно, мы не ухудшим целевую функцию заменой <tex>k</tex> на <tex>l</tex>.<br>
+
#:То, что <tex>k</tex> не принадлежит множеству <tex>S</tex>, значит, что либо на некотором шаге появилась опаздывающая работа <tex>j</tex>, которая заменила <tex>k</tex>, либо работа <tex>k</tex> опаздывала и <tex>w_k</tex> было меньше <tex>\min\limits_{i \in S}w_i</tex>, и поэтому она не была добавлена. В любом случае в это время работа <tex>l</tex> уже принадлежала <tex>S</tex>. Во втором случае очевидно, что <tex>w_k \leqslant w_l</tex>. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали <tex>k</tex>, а не <tex>l</tex>. Следовательно, мы не ухудшим целевую функцию заменой <tex>k</tex> на <tex>l</tex>.
# Пусть <tex>l > k</tex>.<br>
+
# Пусть <tex>l > k</tex>.
#:Замена работы <tex>k</tex> в <tex>S^*</tex> на работу <tex>l</tex> не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как <tex>k</tex> выполнялась в срок, а <tex>d_k \leqslant d_l</tex> и все работы выполняются одинаковое количество времени. Следовательно, <tex>l</tex> так же будет выполнена в срок. Осталось доказать, что <tex>w_k \leqslant w_l</tex>. <br>
+
#:Замена работы <tex>k</tex> в <tex>S^*</tex> на работу <tex>l</tex> не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как <tex>k</tex> выполнялась в срок, а <tex>d_k \leqslant d_l</tex> и все работы выполняются одинаковое количество времени. Следовательно, <tex>l</tex> так же будет выполнена в срок. Осталось доказать, что <tex>w_k \leqslant w_l</tex>.  
#:Пусть работа <tex>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \ldots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \ldots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \ldots < i_r</tex>.<br>
+
#:Пусть работа <tex>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \ldots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \ldots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \ldots < i_r</tex>.
 
#:[[Файл:Sh.jpg|370px|thumb|right|Рис. 1. <tex>i_v</tex> превосходит <tex>i_u</tex>.]]
 
#:[[Файл:Sh.jpg|370px|thumb|right|Рис. 1. <tex>i_v</tex> превосходит <tex>i_u</tex>.]]
#:Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leqslant i_u</tex>. Тогда <tex>w_{k_{i_v}} \geqslant w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.<br>
+
#:Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leqslant i_u</tex>. Тогда <tex>w_{k_{i_v}} \geqslant w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.
 
#:Если из последовательности <tex>i_0 < i_1 < \ldots < i_r</tex> можно выделить подпоследовательность <tex>j_0 = i_0 < j_1 < \ldots < j_s</tex> со свойствами:
 
#:Если из последовательности <tex>i_0 < i_1 < \ldots < i_r</tex> можно выделить подпоследовательность <tex>j_0 = i_0 < j_1 < \ldots < j_s</tex> со свойствами:
 
#:* <tex>j_{v + 1}</tex> превосходит <tex>j_v</tex>, где <tex>v \in [0 \ldots s - 1]</tex>
 
#:* <tex>j_{v + 1}</tex> превосходит <tex>j_v</tex>, где <tex>v \in [0 \ldots s - 1]</tex>
 
#:* <tex>j_{s - 1} < l \leqslant j_s</tex> ,
 
#:* <tex>j_{s - 1} < l \leqslant j_s</tex> ,
#:то <tex>w_l \geqslant w_{k_{j_s}} \geqslant \ldots \geqslant w_{k_{j_0}} = w_k</tex>, что доказывает теорему.<br>
+
#:то <tex>w_l \geqslant w_{k_{j_s}} \geqslant \ldots \geqslant w_{k_{j_0}} = w_k</tex>, что доказывает теорему.
#:В противном случае найдем такую работу <tex>i_t</tex> с наименьшим <tex>t</tex>, что никакая работа <tex>i_v</tex>, где <tex>v > t</tex>, не превосходит <tex>i_t</tex>, причем <tex>i_t < l</tex>. По определению это значит, что после того, как работа <tex>i_t</tex> будет добавлена в <tex>S</tex>, ни одна работа <tex>i \leqslant i_t</tex> не будет удалена из этого множества. Так как <tex>i_t < l</tex>, то по определению <tex>l</tex> все работы, которые на момент добавления <tex>i_t</tex> находятся в <tex>S</tex>, так же должны принадлежать <tex>S^*</tex>. Покажем, что это приведет нас к противоречию.<br>
+
#:В противном случае найдем такую работу <tex>i_t</tex> с наименьшим <tex>t</tex>, что никакая работа <tex>i_v</tex>, где <tex>v > t</tex>, не превосходит <tex>i_t</tex>, причем <tex>i_t < l</tex>. По определению это значит, что после того, как работа <tex>i_t</tex> будет добавлена в <tex>S</tex>, ни одна работа <tex>i \leqslant i_t</tex> не будет удалена из этого множества. Так как <tex>i_t < l</tex>, то по определению <tex>l</tex> все работы, которые на момент добавления <tex>i_t</tex> находятся в <tex>S</tex>, так же должны принадлежать <tex>S^*</tex>. Покажем, что это приведет нас к противоречию.
#:Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:<br>
+
#:Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:
 
#::<tex>(a)</tex> Если <tex>k^* = k_{i_t} > k</tex>, то есть <tex>d_{k^*} \geqslant d_k</tex>, то мы можем заменить <tex>k</tex> на <tex>k^*</tex> в <tex>S^*</tex>, сохранив условие, что <tex>S^*</tex> не содержит опаздывающих работ. Следовательно, множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что противоречит построению <tex>S</tex>.
 
#::<tex>(a)</tex> Если <tex>k^* = k_{i_t} > k</tex>, то есть <tex>d_{k^*} \geqslant d_k</tex>, то мы можем заменить <tex>k</tex> на <tex>k^*</tex> в <tex>S^*</tex>, сохранив условие, что <tex>S^*</tex> не содержит опаздывающих работ. Следовательно, множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что противоречит построению <tex>S</tex>.
#::<tex>(b)</tex> Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t | j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием.
+
#::<tex>(b)</tex> Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t \mid j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием.
 
}}
 
}}
  

Текущая версия на 19:21, 4 сентября 2022

[math] P \mid p_i=1 \mid \sum w_i U_i[/math]

Задача:
Дано [math]m[/math] одинаковых станков, на которых нужно выполнить [math]n[/math] работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — ожидается, что до этого времени она будет закончена, и штраф [math]w_i[/math], который нужно будет выплатить в случае, если работа была закончена после [math]d_i[/math]. Необходимо минимизировать суммарный штраф, который придется выплатить.

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

Идея

Оптимальное расписание для этой задачи будем задавать множеством работ [math]S[/math], которые будут выполнены в срок. Работы, которые не войдут в [math]S[/math], то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке. Чтобы построить множество [math]S[/math], будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа [math]j[/math] опаздывает, удалим из [math]S[/math] работу [math]i[/math] с минимальным значением [math]w_i[/math] и поставим [math]j[/math] на ее место.

Псевдокод

Пусть есть работы [math]1 \ldots n[/math] с временами окончания [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math]. Будем называть простоем временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени [math]t[/math], который будем модифицировать так, как показано ниже. Тогда работа [math]j[/math] опаздывает, если [math]\left\lfloor \dfrac{t}{m} \right\rfloor + p_j \gt d_j[/math], где [math]p_j = 1[/math]. Следующий алгоритм вычислит оптимальное множество [math]S[/math].

  [math]S = \varnothing[/math]
  [math]t = 0[/math]
  for [math]j = 1[/math] to [math]n[/math]
     if [math]j[/math] опаздывает, и все более ранние простои заполнены
        найти [math]i: w[i] = \min\limits_{k \in S}(w[k])[/math]
        if [math]w[i] \lt  w[j][/math]
           заменить [math]i[/math] на [math]j[/math] в [math]S[/math]
     else
        [math]t = t + 1[/math]
        добавить [math]i[/math] в [math]S[/math] и поставить [math]i[/math] на место самого раннего простоя

Таким образом, работы, не попавшие в [math]S[/math], будут иметь минимальное значение [math]w_i[/math].

Асимптотика

Данный алгоритм может быть реализован за время [math]O(n\log{n})[/math], например, если хранить значения [math]w_i[/math], которые принадлежат [math]S[/math], в приоритетной очереди и для множества [math]S[/math] использовать любую структуру данных, у которой операции поиска и добавления элемента не хуже, чем [math]O(\log{n})[/math].

Доказательство корректности

Теорема:
Вышеописанный алгоритм корректен и строит оптимальное множество работ [math]S[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]S[/math] — множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа [math]j[/math] заменила работу [math]i[/math], которая успевала выполниться до истечения [math]d_i[/math], то [math]j[/math] так же успеет выполниться в срок, потому что [math]d_i \leqslant d_j[/math].
Пусть [math]S^*[/math] — множество работ без штрафов в оптимальном расписании. Определим работы [math]l[/math] и [math]k[/math] следующим образом:

  • [math]l[/math] — первая работа в [math]S[/math]: [math]l \notin S^*[/math]
  • [math]k[/math] — первая работа в [math]S^*[/math]: [math]k \notin S[/math]

Покажем, что в [math]S^*[/math] работа [math]k[/math] может быть заменена работой [math]l[/math] без увеличения значения целевой функции. Рассмотрим два случая:

  1. Пусть [math]l \lt k[/math].
    То, что [math]k[/math] не принадлежит множеству [math]S[/math], значит, что либо на некотором шаге появилась опаздывающая работа [math]j[/math], которая заменила [math]k[/math], либо работа [math]k[/math] опаздывала и [math]w_k[/math] было меньше [math]\min\limits_{i \in S}w_i[/math], и поэтому она не была добавлена. В любом случае в это время работа [math]l[/math] уже принадлежала [math]S[/math]. Во втором случае очевидно, что [math]w_k \leqslant w_l[/math]. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали [math]k[/math], а не [math]l[/math]. Следовательно, мы не ухудшим целевую функцию заменой [math]k[/math] на [math]l[/math].
  2. Пусть [math]l \gt k[/math].
    Замена работы [math]k[/math] в [math]S^*[/math] на работу [math]l[/math] не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как [math]k[/math] выполнялась в срок, а [math]d_k \leqslant d_l[/math] и все работы выполняются одинаковое количество времени. Следовательно, [math]l[/math] так же будет выполнена в срок. Осталось доказать, что [math]w_k \leqslant w_l[/math].
    Пусть работа [math]k_{i_0} = k[/math] была заменена работой [math]i_0[/math], а так же [math]k_{i_1} \ldots k_{i_r}[/math] — последовательность работ из [math]S[/math], каждая из которых была на некотором шаге заменена работой [math]i_1 \ldots i_r[/math] соответственно. Тогда [math]i_0 \lt i_1 \lt \ldots \lt i_r[/math].
    Рис. 1. [math]i_v[/math] превосходит [math]i_u[/math].
    Будем говорить [math]i_v[/math] превосходит [math]i_u[/math], где [math]u \lt v[/math], если [math]k_{i_v} \leqslant i_u[/math]. Тогда [math]w_{k_{i_v}} \geqslant w_{k_{i_u}}[/math], так как когда мы вставляли работу [math]i_u[/math] мы выбрали для замены [math]k_{i_u}[/math], то есть ее вес был минимальным среди всех работ, находившихся на тот момент в [math]S[/math], включая [math]k_{i_v}[/math]. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.
    Если из последовательности [math]i_0 \lt i_1 \lt \ldots \lt i_r[/math] можно выделить подпоследовательность [math]j_0 = i_0 \lt j_1 \lt \ldots \lt j_s[/math] со свойствами:
    • [math]j_{v + 1}[/math] превосходит [math]j_v[/math], где [math]v \in [0 \ldots s - 1][/math]
    • [math]j_{s - 1} \lt l \leqslant j_s[/math] ,
    то [math]w_l \geqslant w_{k_{j_s}} \geqslant \ldots \geqslant w_{k_{j_0}} = w_k[/math], что доказывает теорему.
    В противном случае найдем такую работу [math]i_t[/math] с наименьшим [math]t[/math], что никакая работа [math]i_v[/math], где [math]v \gt t[/math], не превосходит [math]i_t[/math], причем [math]i_t \lt l[/math]. По определению это значит, что после того, как работа [math]i_t[/math] будет добавлена в [math]S[/math], ни одна работа [math]i \leqslant i_t[/math] не будет удалена из этого множества. Так как [math]i_t \lt l[/math], то по определению [math]l[/math] все работы, которые на момент добавления [math]i_t[/math] находятся в [math]S[/math], так же должны принадлежать [math]S^*[/math]. Покажем, что это приведет нас к противоречию.
    Пусть [math]S_t[/math] — множество [math]S[/math] после удаления [math]k_{i_t}[/math] и добавления [math]i_t[/math]. Рассмотрим два случая:
    [math](a)[/math] Если [math]k^* = k_{i_t} \gt k[/math], то есть [math]d_{k^*} \geqslant d_k[/math], то мы можем заменить [math]k[/math] на [math]k^*[/math] в [math]S^*[/math], сохранив условие, что [math]S^*[/math] не содержит опаздывающих работ. Следовательно, множество [math]S_t \cup \{k^*\}[/math] не содержит работ со штрафами, что противоречит построению [math]S[/math].
    [math](b)[/math] Пусть [math]k^* \lt k[/math]. Тогда все работы из [math]S_t \cup \{k\}[/math] могут быть выполнены в срок, так как [math]S_t[/math] и [math]k[/math] принадлежат [math]S^*[/math]. Более того, все работы из множества [math]\{j \in S_t \mid j \lt k\}[/math] могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество [math]S_t \cup \{k^*\}[/math] не содержит работ со штрафами, что является противоречием.
[math]\triangleleft[/math]

См. также

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

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