http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=46.183.220.242&* 2026-04-12T15:01:04Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=Ppi1riintegerLmax&diff=54387 2016-06-03T21:52:04Z

<p>46.183.220.242: алгоритм</p> <hr /> <div>&lt;tex dpi = &quot;200&quot;&gt; P \mid p_i=1; r_i - integer \mid L_{max} &lt;/tex&gt;<br /> {{Задача<br /> |definition=<br /> Дано &lt;tex&gt;m&lt;/tex&gt; однородных станков, работающих параллельно, и &lt;tex&gt;n&lt;/tex&gt; работ с временем выполнения &lt;tex&gt;p_i = 1&lt;/tex&gt;, временем появления &lt;tex&gt;r_i&lt;/tex&gt;, заданным целым числом, и момент времени &lt;tex&gt;d_i&lt;/tex&gt;, к которому нужно выполнить работу. Необходимо построить такое расписание, чтобы значение максимального опоздания &lt;tex&gt;L_{max} = \max\limits_{i=1\ldots n} (C_i - d_i)&lt;/tex&gt; было минимальным.<br /> }}<br /> == Описание алгоритма ==<br /> === Идея ===<br /> Отсортируем все работы по времени появления в неубывающем порядке так, что &lt;tex&gt;r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n&lt;/tex&gt;. Теперь будем выполнять доступные на данный момент работы в порядке неубывания дедлайнов &lt;tex&gt;d_i&lt;/tex&gt;. То есть, если в момент времени &lt;tex&gt;t&lt;/tex&gt; есть свободные станки и есть невыполненные работы такие, что &lt;tex&gt;r_i \leqslant t&lt;/tex&gt;, то назначаем работу с наименьшим дедлайном &lt;tex&gt;d_i&lt;/tex&gt; на свободный станок.<br /> <br /> === Псевдокод ===<br /> Алгоритм принимает на вход массив пар, где первый элемент является временем появления &lt;tex&gt;r_i&lt;/tex&gt; работы, а второй её дедлайном &lt;tex&gt;d_i&lt;/tex&gt;, и возвращает расписание, представленное массивом, где на позиции &lt;tex&gt;i&lt;/tex&gt; стоит момент обработки работы &lt;tex&gt;i&lt;/tex&gt;.<br /> <br /> '''function''' scheduling(jobs: '''&lt;int, int&gt;'''[n]) -&gt; '''int[n]'''<br /> sort(jobs) &lt;font color=green&gt;// сортируем работы в порядке неубывания времени появления&lt;/font&gt;<br /> '''int''' j = 1 &lt;font color=green&gt;// последняя невыполненная работа&lt;/font&gt;<br /> '''int[n]''' ans &lt;font color=green&gt;// массив, куда будет записано расписание&lt;/font&gt;<br /> '''heap''' M &lt;font color=green&gt;// куча, в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов&lt;/font&gt;<br /> '''while''' j &lt;= n<br /> '''int''' time = jobs[j].first<br /> '''while''' jobs[j].first &lt;= time &lt;font color=green&gt;// добавляем в кучу все невыполненные работы, доступные на данный момент&lt;/font&gt;<br /> M.push(j)<br /> j++<br /> <br /> '''int''' k = 0 &lt;font color=green&gt;// количество занятых станков в данный момент времени&lt;/font&gt;<br /> '''while''' M.notEmpty()<br /> i = M.pop() &lt;font color=green&gt;// получаем доступную работу с наименьшим дедлайном &lt;/font&gt;<br /> ans[i] = t &lt;font color=green&gt;// назначаем работу i на время t&lt;/font&gt;<br /> '''if''' k + 1 &lt; m &lt;font color=green&gt;// если в момент t есть свободный станок, то назначаем работу i на него&lt;/font&gt;<br /> k++<br /> '''else''' &lt;font color=green&gt;// иначе увеличиваем время и обновляем список доступных работ&lt;/font&gt;<br /> t++<br /> k = 0<br /> '''while''' jobs[j].first &lt;= time<br /> M.push(j)<br /> j++</div>

46.183.220.242