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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 4 участников)
Строка 5: Строка 5:
 
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.
 
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.
 
}}
 
}}
 +
 +
==Более простые варианты исходной задачи==
  
 
Перед решением основной задачи рассмотрим более простые.
 
Перед решением основной задачи рассмотрим более простые.
  
 +
===Вариант 1===
 +
<tex> 1 \mid p_i = 1\mid \sum C_i</tex>
  
==Задача 1==
+
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n k</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\dfrac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание, время работы будет <tex>O(n)</tex>.
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex>
 
 
 
'''Описание алгоритма'''
 
 
 
Входные данные для этой задачи: число работ <tex>n</tex>
 
 
 
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.
 
 
 
==Задача 2==
 
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
 
 
 
'''Описание алгоритма'''
 
 
 
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex>
 
 
 
Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex> \sum_{i = 1}^n(w_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.
 
 
 
==Задача 3==
 
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
 
{{Задача
 
|definition=
 
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.
 
}}
 
 
 
'''Описание алгоритма'''
 
  
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:
+
===Вариант 2===
 +
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
  
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>  
+
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^nw_i C_i</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Данный алгоритм корректен по [[Задача_о_минимуме/максимуме_скалярного_произведения|теореме о минимуме/максимуме скалярного произведения]], так как мы сопоставляем две последовательности, подходящие под условия теоремы. 
  
'''Псевдокод'''
+
Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.
  
  <tex>t_1 \leftarrow r_1 </tex>
+
==Основная задача==  
  '''for'''  <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
+
===Описание алгоритма===
      <tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
 
 
 
==Задача 4==
 
<tex dpi = "200"> 1 \mid r_j,p_j = p \mid \sum f_j</tex>
 
 
 
Вес всех работ <tex>w_i \geqslant 0</tex>
 
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:
 
 
 
<tex>f_j</tex> неубывающая функция для  <tex>j = 1, 2, \ldots, n</tex>
 
 
 
<tex>f_i - f_j</tex> неубывающая функция для  <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex>
 
 
 
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = p \mid \sum w_i C_i </tex>
 
 
 
'''Описание алгоритма'''
 
 
 
Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex>
 
 
 
Пояснение для псевдокода:
 
 
 
<tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>}
 
 
 
<tex>F_k'(s,e)</tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex>
 
 
 
'''Псевдокод'''
 
 
 
  '''for all''' <tex>s, e  \in T \ with \ s \leqslant e</tex> '''do'''
 
      <tex>F_0(s,e) \leftarrow 0</tex>
 
  '''for''' <tex>k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''
 
      '''for all''' <tex>s, e  \in T \ with \ s \leqslant e</tex> '''do'''
 
        <tex>
 
        F_k(s,e) \leftarrow
 
        \begin{cases}
 
        F_{k-1}(s,e) \ if\ r_k \notin [s - p,e);\\
 
        F_k'(s,e) \ overwise;
 
        \end{cases}
 
        </tex>
 
  '''Вычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p)  )</tex>
 
==Описание алгоритма==
 
 
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
 
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
 
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
 
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
 
<ol>
 
<ol>
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
+
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
 
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
 
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
 
<li> Увеличиваем <tex>time</tex> на один.</li>
 
<li> Увеличиваем <tex>time</tex> на один.</li>
 
</ol>
 
</ol>
  
==Доказательство корректности алгоритма==
+
===Доказательство корректности алгоритма===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Строка 107: Строка 48:
 
}}
 
}}
  
==Псевдокод==
+
===Псевдокод===
   <tex> S \leftarrow \{1 \dots n\}</tex>
+
 
 +
====Реализация 1====
 +
   <tex> S \leftarrow \{1 \ldots n\}</tex>
 
   <tex> \mathtt{time} \leftarrow 0</tex>
 
   <tex> \mathtt{time} \leftarrow 0</tex>
 
   <tex> \mathtt{answer} \leftarrow 0</tex>
 
   <tex> \mathtt{answer} \leftarrow 0</tex>
 
   '''while''' <tex> S \neq \varnothing </tex>
 
   '''while''' <tex> S \neq \varnothing </tex>
 
       <tex> j \leftarrow null </tex>
 
       <tex> j \leftarrow null </tex>
       '''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq \mathtt{time}</tex> '''and''' <tex>\max w_{i} </tex>
+
       '''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex>
 
         <tex> j \leftarrow i </tex>
 
         <tex> j \leftarrow i </tex>
 
       '''if''' <tex>j \neq null </tex>
 
       '''if''' <tex>j \neq null </tex>
Строка 120: Строка 63:
 
       <tex> \mathtt{time++}</tex>
 
       <tex> \mathtt{time++}</tex>
  
==Сложность алгоритма==
+
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex>
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
+
 
 +
====Реализация 2====
 +
* <tex>\mathtt{Q}</tex> {{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке,
 +
* <tex>\mathtt{P}</tex> {{---}} [[Приоритетные очереди | приоритетная очередь]] по максимуму.
 +
 
 +
<tex> \mathtt{time} \leftarrow 1</tex>
 +
<tex> \mathtt{answer} \leftarrow 0</tex>
 +
'''while''' <tex>\mathtt{Q} \neq \varnothing </tex> '''and''' <tex>\mathtt{P} \neq \varnothing </tex>
 +
    '''if''' <tex>\mathtt{Q} \neq \varnothing </tex>
 +
        <tex> j \leftarrow \mathtt{Q.head()}</tex>
 +
        '''if''' <tex>\mathtt{time} < r_j</tex>
 +
            <tex>\mathtt{time} \leftarrow r_j</tex>
 +
        '''while''' <tex> \mathtt{time} \geqslant r_j</tex>
 +
            <tex>\mathtt{P.insert}(w_j)</tex>
 +
            <tex>\mathtt{Q.pop()}</tex>
 +
            '''if''' <tex>\mathtt{Q} = \varnothing </tex>
 +
                '''break'''
 +
            '''else'''
 +
                <tex> j \leftarrow \mathtt{Q.head()}</tex>
 +
    <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} </tex>
 +
    <tex> \mathtt{time}\texttt{++}</tex>
 +
 
 +
Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.
 +
В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.
  
 +
==См. также==
 +
* [[Классификация задач]]
 +
* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
 +
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]
  
== Источники информации ==
+
==Источники информации==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
+
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39
+
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85
+
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 101 - 102
+
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

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

[math] 1 \mid r_i,p_i = 1 \mid \sum w_i C_i[/math]


Задача:
Дано [math]n[/math] работ и один станок. Для каждой работы известно её время появления [math]r_{i}[/math] и вес [math]w_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math]. Требуется выполнить все работы, чтобы значение [math]\sum w_{i} C_{i}[/math] было минимальным, где [math]C_{i}[/math] — время окончания работы.


Более простые варианты исходной задачи

Перед решением основной задачи рассмотрим более простые.

Вариант 1

[math] 1 \mid p_i = 1\mid \sum C_i[/math]

Этот случай простейший. Ответом будет [math]\sum\limits_{k = 1}^n k[/math], так как мы [math]n[/math] раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых [math]n[/math] членов арифметической прогрессии алгоритм [math]S_n=\dfrac{a_1+a_n}2 \cdot n[/math] будет работает за [math]O(1)[/math], но если нужно вывести и само расписание, время работы будет [math]O(n)[/math].

Вариант 2

[math] 1 \mid p_i = 1\mid \sum w_i C_i[/math]

Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет [math] \sum\limits_{i = 1}^nw_i C_i[/math], так как мы [math]n[/math] раз сложим время окончания выполнения одной работы (которое в нашем случае [math]C_{i-1}+1[/math]) домноженное на вес этой работы. Данный алгоритм корректен по теореме о минимуме/максимуме скалярного произведения, так как мы сопоставляем две последовательности, подходящие под условия теоремы.

Так как сортировка весов занимает [math]O(n \log n)[/math] время, то асимптотика времени работы алгорита равна [math]O(n + n \log n)[/math].

Основная задача

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

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последней работы, будем:

  1. Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \leqslant time[/math], а значение [math]w_{i}[/math] максимально.
  2. Если мы смогли найти работу [math]j[/math], то выполняем её в момент времени [math]time[/math] и удаляем из множества невыполненных работ.
  3. Увеличиваем [math]time[/math] на один.

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

Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]

Доказательство будем вести от противного.
Рассмотрим расписание [math]S_{1}[/math], полученное после выполнения нашего алгоритма, и оптимальное расписание [math]S_{2}[/math].
Возьмём первый момент времени [math]t_{1}[/math], когда расписания различаются. Пусть в этот момент времени в [math]S_{1}[/math], будет выполняться работа с весом [math]w_{1}[/math], а в [math]S_{2}[/math] — работа с весом [math]w_{2}[/math].
Это первый момент, в котором расписания отличаются, значит в [math]S_{2}[/math] работа с весом [math]w_{1}[/math] выполнится в момент времени [math]t_{2} \gt t_{1}[/math].
Поменяем местами работы с весами [math]w_{1}[/math] и [math]w_{2}[/math] в [math]S_{2}[/math] и полуим расписание [math]S_{3}[/math]. Это возможно, потому что время появления этих работ не меньше [math]t_{1}[/math].
При такой перестановке ответы на задачу для [math]S_{2}[/math] и [math]S_{3}[/math] будут отличаться на

    [math]t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})[/math]

Первая скобка отрицательная: [math]t_{1} \lt t_{2}[/math]. Вторая скобка тоже отрицательная из того, что в [math]S_{1}[/math] работа с весом [math]w_1[/math] выполняется раньше, значит её вес должен быть больше [math]w_2[/math].

Итого имеем, что ответ для [math]S_{2}[/math] больше, чем ответ для [math]S_{3}[/math]. Следовательно расписание [math]S_2[/math] неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание [math]S_{1}[/math] отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
[math]\triangleleft[/math]

Псевдокод

Реализация 1

  [math] S \leftarrow \{1 \ldots n\}[/math]
  [math] \mathtt{time} \leftarrow 0[/math]
  [math] \mathtt{answer} \leftarrow 0[/math]
  while [math] S \neq \varnothing [/math]
     [math] j \leftarrow null [/math]
     if [math] i \in S[/math] and [math] r_{i} \leqslant \mathtt{time}[/math] and [math]w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j[/math]
        [math] j \leftarrow i [/math]
     if [math]j \neq null [/math]
        [math] S \leftarrow S \setminus j[/math]
        [math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}[/math]
     [math] \mathtt{time++}[/math]

Множество [math]S[/math] станет пустым не позже, чем через [math]n + \max\limits_{i = 1 \ldots n} r_{i}[/math] шагов цикла. Определить максимум в множестве можно за время [math]O(\log n)[/math], используя , например, очередь с приоритетами. Значит общее время работы алгоритма [math]O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)[/math]

Реализация 2

  • [math]\mathtt{Q}[/math] — обычная очередь, в которой работы изначально располагаются в отсортированном по [math]r_i[/math] порядке,
  • [math]\mathtt{P}[/math] приоритетная очередь по максимуму.
[math] \mathtt{time} \leftarrow 1[/math]
[math] \mathtt{answer} \leftarrow 0[/math]
while [math]\mathtt{Q} \neq \varnothing [/math] and [math]\mathtt{P} \neq \varnothing [/math]
    if [math]\mathtt{Q} \neq \varnothing [/math]
        [math] j \leftarrow \mathtt{Q.head()}[/math]
        if [math]\mathtt{time} \lt  r_j[/math]
            [math]\mathtt{time} \leftarrow r_j[/math]
        while [math] \mathtt{time} \geqslant r_j[/math]
            [math]\mathtt{P.insert}(w_j)[/math]
            [math]\mathtt{Q.pop()}[/math]
            if [math]\mathtt{Q} = \varnothing [/math]
                break
            else
                [math] j \leftarrow \mathtt{Q.head()}[/math]
    [math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} [/math]
    [math] \mathtt{time}\texttt{++}[/math]

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

См. также

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

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20
  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39
  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85
  • Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.