Минимизация продолжительности потока: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы Продолжительность потока; время отклика Постановка задачи Эв…») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Ключевые слова и синонимы | == Ключевые слова и синонимы == | ||
Продолжительность потока; время отклика | Продолжительность потока; время отклика | ||
Постановка задачи | == Постановка задачи == | ||
Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны дата запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом. | Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны дата запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом. | ||
Дано: | Дано: | ||
Множество m идентичных компьютеров и множество n заданий 1, 2, …, n. Каждому заданию j присвоены дата запуска rj и продолжительность обработки pj. Обозначим за I множество допустимых экземпляров входных данных. | Множество m идентичных компьютеров и множество n заданий 1, 2, …, n. Каждому заданию j присвоены дата запуска rj и продолжительность обработки pj. Обозначим за I множество допустимых экземпляров входных данных. | ||
Цель: | Цель: | ||
Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за Cj время завершения выполнения задания j системой. Продолжительность потока или время отклика Fj задания j определяется как Fj = Cj — rj. Цель заключается в минимизации значения | Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за Cj время завершения выполнения задания j системой. Продолжительность потока или время отклика Fj задания j определяется как Fj = Cj — rj. Цель заключается в минимизации значения | ||
mm — и j=1 Fj. | mm — и j=1 Fj. | ||
Поскольку n является частью входных данных, задача эквивалентна минимизации общей продолжительности потока, т. е. | Поскольку n является частью входных данных, задача эквивалентна минимизации общей продолжительности потока, т. е. | ||
Оффлайновые и онлайновые конфигурации | Оффлайновые и онлайновые конфигурации | ||
В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj. | В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj. | ||
Напротив, в онлайновой конфигурации в любой момент времени t алгоритму известно только множество задач, запущенных до времени t. | Напротив, в онлайновой конфигурации в любой момент времени t алгоритму известно только множество задач, запущенных до времени t. | ||
Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I. | Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I. | ||
Предположения для онлайнового случая | Предположения для онлайнового случая | ||
Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (отсутствие предвидения) [1, 3]. | Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (отсутствие предвидения) [1, 3]. | ||
Метрика эффективности | Метрика эффективности | ||
Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности определяется следующим образом: | Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности определяется следующим образом: | ||
PA = max | PA = max | ||
I2I OPT (I) | I2I OPT (I) | ||
В оффлайновом случае p^ является коэффициентом аппроксимации алгоритма. В онлайновом случае будем называть p^ коэффициентом конкурентоспособности A. | В оффлайновом случае p^ является коэффициентом аппроксимации алгоритма. В онлайновом случае будем называть p^ коэффициентом конкурентоспособности A. | ||
Вытеснение | Вытеснение | ||
Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6]. | Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6]. | ||
Основные результаты | == Основные результаты == | ||
Алгоритмы | Алгоритмы | ||
Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за wj(t) количество времени, проведенного A над выполнением задания j до t. Обозначим за xj(t) = pj - wj(t) его оставшееся время обработки в момент t. | Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за wj(t) количество времени, проведенного A над выполнением задания j до t. Обозначим за xj(t) = pj - wj(t) его оставшееся время обработки в момент t. | ||
Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика наименьшего оставшегося времени обработки (shortest remaining processing time, SRPT). В любое время t, эвристика SRPT выполняет «повисшее» задание j, для которого xj(t) минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику «сначала самое короткое задание» (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения. | Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика наименьшего оставшегося времени обработки (shortest remaining processing time, SRPT). В любое время t, эвристика SRPT выполняет «повисшее» задание j, для которого xj(t) минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику «сначала самое короткое задание» (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения. | ||
Сложность | Сложность | ||
Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с вытеснением [9,10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с разрешенным вытеснением достигается алгоритмом SRPT, который является O(logmin n/m; P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [ ] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы. | Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с вытеснением [9,10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с разрешенным вытеснением достигается алгоритмом SRPT, который является O(logmin n/m; P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [ ] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы. | ||
В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить Q (nll3~€)-аппроксимацию, для любого e > 0, а наилучшая верхняя граница составляет O(n/m log(n/m)) [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид [5]. | В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить Q (nll3~€)-аппроксимацию, для любого e > 0, а наилучшая верхняя граница составляет O(n/m log(n/m)) [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид [5]. | ||
Расширения | Расширения | ||
Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что некоторые простые эвристики могут продемонстрировать эффективность, близкую к оптимальной. | Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что некоторые простые эвристики могут продемонстрировать эффективность, близкую к оптимальной. | ||
Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в [1,3]. В частности, авторы [ ] доказали, что рандомизированный вариант эвристики MLF, описанный выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент. | Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в [1,3]. В частности, авторы [ ] доказали, что рандомизированный вариант эвристики MLF, описанный выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент. | ||
Применение | == Применение == | ||
Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [ ]. В частности, использование эвристик, подобных «сначала самое короткое задание», в особенности эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8,11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2]. | Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [ ]. В частности, использование эвристик, подобных «сначала самое короткое задание», в особенности эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8,11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2]. | ||
Открытые вопросы | == Открытые вопросы == | ||
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница £?(logn) была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая. | Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница £?(logn) была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая. | ||
См. также | == См. также == | ||
* [[Минимальная продолжительность потока]] | |||
* [[Минимальное время завершения для взвешенной системы]] | |||
* [[Многоуровневые очереди с обратными связями]] | |||
* [[Планирование с учетом наименьшего прошедшего времени обработки]] | |||
Литература | == Литература == | ||
1. Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51 (4), 517-539 (2004) | 1. Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51 (4), 517-539 (2004) | ||
2. Crovella, M.E., Frangioso, R., Harchal-Balter, M.: Connection scheduling in web servers. In: Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems (USITS-99), 1999 pp. 243-254 | 2. Crovella, M.E., Frangioso, R., Harchal-Balter, M.: Connection scheduling in web servers. In: Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems (USITS-99), 1999 pp. 243-254 | ||
3. Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. J. ACM 50(4), 551 -567 (2003) | 3. Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. J. ACM 50(4), 551 -567 (2003) | ||
4. Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617-643 (2000) | 4. Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617-643 (2000) | ||
5. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC '96), 1996, pp. 418-426 | 5. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC '96), 1996, pp. 418-426 | ||
6. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of the Annual ACM Symposium on the Theory of Computing STOC, 1997, pp. 110-119 | 6. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of the Annual ACM Symposium on the Theory of Computing STOC, 1997, pp. 110-119 | ||
7. Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor.Comput.Sci. 130(1), 17-47 (1994) | 7. Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor.Comput.Sci. 130(1), 17-47 (1994) | ||
8. Nutt, G.: Operating System Projects Using Windows NT. Addison-Wesley, Reading (1999) | 8. Nutt, G.: Operating System Projects Using Windows NT. Addison-Wesley, Reading (1999) | ||
9. Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(1), 687-690 (1968) | 9. Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(1), 687-690 (1968) | ||
10. Smith, D.R.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197-199 (1976) | 10. Smith, D.R.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197-199 (1976) | ||
11. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992) | 11. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992) | ||
Версия от 11:56, 6 августа 2018
Ключевые слова и синонимы
Продолжительность потока; время отклика
Постановка задачи
Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны дата запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом.
Дано:
Множество m идентичных компьютеров и множество n заданий 1, 2, …, n. Каждому заданию j присвоены дата запуска rj и продолжительность обработки pj. Обозначим за I множество допустимых экземпляров входных данных.
Цель:
Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за Cj время завершения выполнения задания j системой. Продолжительность потока или время отклика Fj задания j определяется как Fj = Cj — rj. Цель заключается в минимизации значения
mm — и j=1 Fj.
Поскольку n является частью входных данных, задача эквивалентна минимизации общей продолжительности потока, т. е.
Оффлайновые и онлайновые конфигурации
В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj.
Напротив, в онлайновой конфигурации в любой момент времени t алгоритму известно только множество задач, запущенных до времени t.
Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I.
Предположения для онлайнового случая
Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (отсутствие предвидения) [1, 3].
Метрика эффективности
Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности определяется следующим образом:
PA = max I2I OPT (I)
В оффлайновом случае p^ является коэффициентом аппроксимации алгоритма. В онлайновом случае будем называть p^ коэффициентом конкурентоспособности A.
Вытеснение
Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6].
Основные результаты
Алгоритмы
Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за wj(t) количество времени, проведенного A над выполнением задания j до t. Обозначим за xj(t) = pj - wj(t) его оставшееся время обработки в момент t. Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика наименьшего оставшегося времени обработки (shortest remaining processing time, SRPT). В любое время t, эвристика SRPT выполняет «повисшее» задание j, для которого xj(t) минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику «сначала самое короткое задание» (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.
Сложность
Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с вытеснением [9,10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с разрешенным вытеснением достигается алгоритмом SRPT, который является O(logmin n/m; P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [ ] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы.
В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить Q (nll3~€)-аппроксимацию, для любого e > 0, а наилучшая верхняя граница составляет O(n/m log(n/m)) [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид [5].
Расширения
Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что некоторые простые эвристики могут продемонстрировать эффективность, близкую к оптимальной.
Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в [1,3]. В частности, авторы [ ] доказали, что рандомизированный вариант эвристики MLF, описанный выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент.
Применение
Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [ ]. В частности, использование эвристик, подобных «сначала самое короткое задание», в особенности эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8,11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2].
Открытые вопросы
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница £?(logn) была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.
См. также
- Минимальная продолжительность потока
- Минимальное время завершения для взвешенной системы
- Многоуровневые очереди с обратными связями
- Планирование с учетом наименьшего прошедшего времени обработки
Литература
1. Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51 (4), 517-539 (2004)
2. Crovella, M.E., Frangioso, R., Harchal-Balter, M.: Connection scheduling in web servers. In: Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems (USITS-99), 1999 pp. 243-254
3. Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. J. ACM 50(4), 551 -567 (2003)
4. Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617-643 (2000)
5. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC '96), 1996, pp. 418-426
6. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of the Annual ACM Symposium on the Theory of Computing STOC, 1997, pp. 110-119
7. Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor.Comput.Sci. 130(1), 17-47 (1994)
8. Nutt, G.: Operating System Projects Using Windows NT. Addison-Wesley, Reading (1999)
9. Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(1), 687-690 (1968)
10. Smith, D.R.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197-199 (1976)
11. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992)