http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.66.152.150&* 2026-05-09T11:32:30Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=Opi1sumu&diff=25482 2012-06-16T20:17:03Z

<p>217.66.152.150: Новая страница: «==Описание задачи== Дано &lt;tex&gt;m&lt;/tex&gt; одинаковых станков, которые работают параллельно и &lt;tex&gt;n&lt;/tex...»</p> <hr /> <div>==Описание задачи==<br /> Дано &lt;tex&gt;m&lt;/tex&gt; одинаковых станков, которые работают параллельно и &lt;tex&gt;n&lt;/tex&gt; работ, котороые необходимо выполнить<br /> в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному. <br /> Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ. <br /> <br /> ==Описание алгоритма==<br /> Отсортируем работы в порядке невозрастания дедлайнов. <br /> <br /> {{Утверждение<br /> |statement=Если в оптимальном расписании можно сделать &lt;tex&gt;k&lt;/tex&gt; работ, то можно сделать первые &lt;tex&gt;k&lt;/tex&gt; работ.<br /> |proof=Пусть в оптимальном расписании были сделаны работы &lt;tex&gt;i_1, i_2, \ldots, i_k&lt;/tex&gt;. Докажем, что существует <br /> оптимальное расписание, в котором сделаны работы &lt;tex&gt;1, 2, \ldots, k&lt;/tex&gt;. Пусть работы &lt;tex&gt;i_1, i_2, \ldots, i_k&lt;/tex&gt;<br /> тоже отсортированы в порядке неубывания дедлайна. Тогда &lt;tex&gt;d_{i1} \le d_1, d_{i2}\le d_2, \ldots, d_{ik}\le d_{k}&lt;/tex&gt;.<br /> Тогда, если заменить во всём расписании работу &lt;tex&gt;i_j&lt;/tex&gt; на работу &lt;tex&gt;j&lt;/tex&gt;, то она, тем более, будет выполнена.<br /> }}<br /> <br /> {{Определение<br /> |definition=Обозначим за ''тайм-слот t'' множество из не более, чем &lt;tex&gt;m&lt;/tex&gt; различных чисел {{---}} <br /> номера работ, которые мы хотим выполнить в момент времени &lt;tex&gt;t&lt;/tex&gt;.<br /> }}<br /> <br /> Введем тайм-слот для каждого момента времени от &lt;tex&gt;0&lt;/tex&gt; до &lt;tex&gt;d_n&lt;/tex&gt;.<br /> Каждую работу будем пытаться сделать как можно позже. Будет рассматривать работы в порядке невозрастания дедлайнов. <br /> &lt;tex&gt;i&lt;/tex&gt;-ю работу попытаемся добавить в тайм-слоты с &lt;tex&gt;d_i - m + 1&lt;/tex&gt; по &lt;tex&gt;d_i&lt;/tex&gt;. <br /> После добавления некоторые тайм-слоты могли переполниться (тайм-слот переполнился, если в нём уже находилось<br /> &lt;tex&gt;m&lt;/tex&gt; работ, и в него добавили &lt;tex&gt;m+1&lt;/tex&gt;-ю). <br /> Для переполнившегося тайм-слота найдём найдем самый правый левее него, который ещё не переполнился и перекинем работу, <br /> которой там еще нет, в него. Так как в нем меньше элементов, то, по принципу Дирихле, это можно сделать. <br /> <br /> {{Утверждение<br /> |statement=Следуя этому алгоритму, первый тайм-слот переполнится тогдаи только тогда, когда переполнилнился<br /> нулевой тайм-слот.<br /> |proof=?<br /> }}<br /> <br /> Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить. Обозначим его за &lt;tex&gt;k&lt;/tex&gt;.<br /> <br /> Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным <br /> количеством паросочетаний.</div>

217.66.152.150