4501
правка
Минимальное время завершения для взвешенной системы: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальное время завершения для взвешенной системы (посмотреть исходный код)
Версия от 18:33, 19 сентября 2016
, 19 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
== Основные результаты == | == Основные результаты == | ||
Афрати и др. [ ] первыми разработали PTAS-алгоритмы для задач поиска минимального времени завершения для взвешенной системы с указанием дат запуска. В таблице 1 приведено время выполнения этих PTAS-алгоритмов. | |||
Результаты, представленные в таблице 1, были получены благодаря тщательному подбору последовательности преобразований на входе и последующему динамическому программированию. Преобразования на входе гарантируют, что входные данные будут иметь нужную структуру, за счет незначительного снижения оптимальности, а динамическое программирование обеспечивает эффективное перечисление всех почти оптимальных решений для хорошо структурированного экземпляра задачи. | |||
Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения 1 + e, в результате чего общая эффективность снижается не более чем на 1 + e. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Это полезные свойства, которые могут использоваться алгоритмом динамического программирования. | |||
Задача Время выполнения схем PTAS | |||
Mn\T,wjq 0(2Р°М?)п+п|одп) | |||
PjrjjPwjCj O((m + 1 У0'* е >n + n log n) | |||
Pjrj;pmtnjPwjCj 0(2P°Mi-)n+n|ogn) | |||
Rmjrj jPwjCj O(f(m, ^)poly(n)) | |||
Rmjrj; pmtn jP wjCj O(f(m, j)n + nlogn) | |||
RmjjPwjCj O(f(m, j)n + nlogn) | |||
Таблица 1. Основные результаты Афрати и др. [ ] | |||