1ripippmtnsumwu — различия между версиями
Swanwarp (обсуждение | вклад) м (→Динамика) |
Swanwarp (обсуждение | вклад) м (→Псевдокод: убрал фигурную скобку) |
||
Строка 84: | Строка 84: | ||
'''else''' | '''else''' | ||
<tex>W'_k = </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы | <tex>W'_k = </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы | ||
− | <tex>W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k | + | <tex>W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k)</tex> |
'''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex> | '''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex> |
Текущая версия на 19:16, 8 июня 2016
Задача: |
Дано | работ и 1 станок. Для каждой работы известны её время появления и вес , а также дедлайн . Время выполнения всех работ равно . Каждую работу можно прервать и продолжить ее выполнение в любой момент времени. Требуется выполнить все работы, чтобы значение (суммарный вес просроченных работ) было минимальным.
Содержание
Решение[править]
Необходимо найти выполнимое множество работ динамического программирования. Предполагается, что работы отсортированы в порядке неубывания дедлайна.
такое, что его суммарный вес максимален. Эта проблема решается с помощьюАлгоритм построения расписания[править]
Пусть у нас есть множества работ
, для которых надо составить расписание. Возможны два случая:- Если машина освободилась, то вставляем в расписание работу с наименьшим .
- Если машина занята работой и в момент времени появилась работа , тогда если , то прервем и поставим на выполнение . В противном случае просто продолжим выполнение .
Можно заметить что, если работа была вставлена в расписание после своего дедлайна, то данное множество работ
не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ , которое будет выполнимым, если построить его по данному алгоритму, и чей вес будет максимален.Лемма: |
Пусть . Тогда время начала и время окончания этой работы в расписании будет принадлежать . |
Доказательство: |
Сначала докажем лемму для . Пусть минимальная временная точка такая, что между и станок не простаивает. По структуре расписания . Работы, которые выполняются между и , не могут выполняться ни до , ни после , даже частично. Это следует из структуры алгоритма построения расписания если работа была прервана работой , то после выполнения мы снова вставляем в расписание . Таким образом, делится на . Возможны следующие два случая:
В любом из этих двух случаев есть такое , такое что станок не простаивает между и . Тогда делится на . Следовательно, не превышает , так как станок не простаивает. Поэтому .
|
Динамика[править]
Для любых
и для любого положим множество работ, индекс которых меньше и чьи лежать в интервале Также определим как максимальный вес множества работ такой, что и расписание от разрешимо и заканчивается до . Если такое существует, будем говорить, что реализует . Если же такого нет, тоБудем основывать динамику на следующей лемме.
Лемма: |
|
Доказательство: |
Если , то работа не может быть поставлена ни в какой такой, что расписание от разрешимо и . Тогда, очевидно, что
|
Псевдокод[править]
int solve(int[n] d, int[n] r, int[n] w): Отсортировать работы поforeach if for to for to foreach if else Подсчитать по формуле из леммы return
Асимптотика[править]
Заметим, что множество
содержит не более элементов. Следовательно, цикл по итерируется раз. Внутри этого цикла мы тратим времени на подсчет , так как зная и мы можем посчитать и . Также алгоритм использует шестимерный массив для хранения . Таким образом, учитывая итерации алгоритма по и , нам потребуется времени и памяти для работы алгоритма.См. также[править]
Источники информации[править]
- Philippe Baptiste Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times