4446
правок
Минимизация продолжительности потока: различия между версиями
Материал из WEGA
Минимизация продолжительности потока (посмотреть исходный код)
Версия от 12:07, 6 августа 2018
, 6 августа 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
'''Оффлайновые и онлайновые конфигурации''' | '''Оффлайновые и онлайновые конфигурации''' | ||
В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны | В ''оффлайновой конфигурации'' экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1, ..., n алгоритму известны <math>r_j \;</math> и <math>p_j \;</math>. | ||
Напротив, в ''онлайновой конфигурации'' в любой момент времени t алгоритму известно только множество задач, запущенных до времени t. | |||
Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I. | |||
'''Предположения для онлайнового случая''' | |||
Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (''отсутствие предвидения'') [1, 3]. | |||
'''Метрика эффективности''' | |||
Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности <math>\rho_A \;</math> определяется следующим образом: | |||
<math>\rho_A = max_{I \in \mathcal{I}} \frac{A(I)}{OPT(I)}</math>. | |||
В оффлайновом случае <math>\rho_A \;</math> является коэффициентом ''аппроксимации алгоритма''. В онлайновом случае будем называть <math>\rho_A \;</math> ''коэффициентом конкурентоспособности'' A. | |||
Вытеснение | '''Вытеснение''' | ||
Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6]. | Если ''вытеснение'' разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6]. | ||
== Основные результаты == | == Основные результаты == | ||
