Материал из Викиконспекты
[math]R \mid \mid \sum C_i[/math]
| Задача: |
| Дано [math] n [/math] работ и [math] m [/math] станков, причем для каждого станка длительность выполнения на нем [math]i[/math]-й работы составляет [math] p_{ij} [/math]. Необходимо минимизировать сумму времени выполнения работ. |
Описание алгоритма
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок [math] j [/math], пусть на нем выполняется [math]n_j[/math] работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от [math]1 [/math] до [math]n_j[/math]) рассчитывается как:
[math]
\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} \cdot p_qj \right) =
n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
[/math]
Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент [math] k [/math], означающий, что соответствующая работа выпллняется [math] k [/math]-й с конца. Понятно, что в различных расписаниях [math] k [/math] может принимать значения от [math]1[/math] до [math]n[/math].
Сведем задачу к назначению каждой работы [math] i [/math] позиции с конца [math] k [/math] на станке [math] j [/math] с помощью алгоритма поиска максимального потока минимальной стоимости. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности [math]1[/math] и стоимости [math]k \cdot p_{ij}[/math], соответствующие вкладу работы в целевую функцию, если она окажется в позиции [math] k [/math] с конца на станке [math] j [/math]. Проведем из стока в левую долю ребра стоимости [math]0[/math] и пропускной способности [math]1[/math], из правой доли в сток — также ребра стоимости [math] 0 [/math] и пропускной способности [math]1[/math]. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
| Утверждение: |
Eсли ребро [math] i \to (j, k) [/math] насыщено потоком, то работа [math] i [/math] в оптимальном расписании должна стоять на станке [math] j [/math] в позиции [math] k [/math] с конца. |
| [math]\triangleright[/math] |
- Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
- Расписание, построенное по вышепредставленному способу действительно будет допустимым.
- Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
- Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
- Докажем, что не возникает ситуации такой, что существует такая позиция [math] l [/math], что в этой позиции с конца стоит какая-то работа, а в позиции [math] l - 1 [/math] с конца — нет (это противоречит определению [math]l[/math]-й с конца работы). Такая ситуация означает, что ребро [math] i \to (j, l) [/math] оказалось насышено потоком, а ребро [math]i \to (j, l - 1) [/math] — не насыщено. Но стоимость ребра [math] i \to (j, l - 1) [/math] меньше стоимости ребра [math] i \to (j, l) [/math], поэтому можем переместить поток с ребра [math] i \to (j, l) [/math] на ребро [math] i \to (j, l - 1) [/math], не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
|
| [math]\triangleleft[/math] |
Время выполнения
Время выполнения алгоритма поиска максимального потока минимальной стоймости равно [math] \mathcal{O}(V \cdot E^2) [/math]. Количество вершин в получаемой сети равно [math] \mathcal{O}(m \cdot n) [/math]. Количество ребер в сети равно [math] \mathcal{O}(m \cdot n^2) [/math]. Следовательно, ассимптотика алгоритма равна [math] \mathcal{O}(m^3 \cdot n^5) [/math].
См. также
