Изменения

Перейти к: навигация, поиск

J2pij1Lmax

148 байт убрано, 22:01, 21 июня 2012
Описание решения
==Описание решения==
Таким образомСудя по условию, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машинамашиной, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.
Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхняя граница верхнюю границу момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два массива списка <tex>A(t)</tex> и <tex>B(t) (t = 0,\ldots,t_{max})</tex>, где <tex>A(t) = O_{ij}</tex>, если операция <tex>O_ij</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex><tex> \emptyset</tex>, если машина <tex>A</tex> простаивает в этот момент. Будем называть <tex>\emptyset</tex> пустой операцией. И для каждой операции <tex>O_{ij}</tex>, выполняющейся на машине <tex>A</tex> существует <tex>t</tex>, для которого <tex>A(t) = O_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \le n_i</tex> следует <tex>O_{i,j-1} = B(s) (A(s))</tex> для некоторого <tex>s < t</tex>, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех операций будем называть списком. Для данный списка <tex>L</tex> осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующим <tex>L</tex>, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим <tex>L</tex> расписанием.
<tex>С_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:
Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.
Однако, мы будем использовать эвристику с хешами и улучшим асимптотику алгоритма до <tex>O(r)</tex>.
Мы предполагаем, что <tex>d_i \ge 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>
<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>
Каждую операцию мы кладём в соответствующую корзину соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру корзины списка <tex>k</tex> порядку, где операции из одной корзины одного списка могут выполнятся в произвольном порядке.
==Алгоритм==
81
правка

Навигация