394
правки
Изменения
Новая страница: «==Постановка задачи== Рассмотрим задачу: <ol> <li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li> <li>Для ...»
==Постановка задачи==
Рассмотрим задачу:
<ol>
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
<li>Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. <tex>1</tex>.</li>
<li>Длина любой последовательности <tex><=2</tex>.
</ol>
Требуется минимизировать время окончания выполнения всех работ.
==Описание алгоритма==
==Доказательство корректности алгоритма==
{{Теорема
|statement=
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Доказательство будем вести от противного.<br/>
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на
<ul><tex>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})</tex></ul>
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
}}
==Псевдокод==
<tex> S \leftarrow \{1 \dots n\}</tex>
<tex> time \leftarrow 0</tex>
<tex> answer \leftarrow 0</tex>
while <tex> S \neq \varnothing </tex>
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
if <tex>j \neq null </tex>
<tex> S \leftarrow S \setminus j</tex>
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex>
<tex> time++</tex>
==Сложность алгоритма==
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
Рассмотрим задачу:
<ol>
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
<li>Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. <tex>1</tex>.</li>
<li>Длина любой последовательности <tex><=2</tex>.
</ol>
Требуется минимизировать время окончания выполнения всех работ.
==Описание алгоритма==
==Доказательство корректности алгоритма==
{{Теорема
|statement=
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Доказательство будем вести от противного.<br/>
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на
<ul><tex>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})</tex></ul>
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
}}
==Псевдокод==
<tex> S \leftarrow \{1 \dots n\}</tex>
<tex> time \leftarrow 0</tex>
<tex> answer \leftarrow 0</tex>
while <tex> S \neq \varnothing </tex>
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
if <tex>j \neq null </tex>
<tex> S \leftarrow S \setminus j</tex>
<tex> Answer \leftarrow Answer + time \cdot w_{j}</tex>
<tex> time++</tex>
==Сложность алгоритма==
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
