Алгоритм обработки заданий с одинаковым приоритетом

Question

Я решаю проблемы с упражнениями из книги Пападимитру и Вазирани «Алгоритмы».

Вопрос состоит в следующем:

На сервере есть n клиентов, ожидающих обслуживания.Время обслуживания, необходимое каждому клиенту, известно заранее: для клиента это минуты.Так, если, например, клиенты обслуживаются в порядке увеличения i, то i-й клиент должен ждать Sum (j = 1 - n) tj минут.

Мы хотим минимизировать общее время ожидания.Дайте эффективный алгоритм для того же.

Моя попытка:

Я подумал о паре подходов, но не мог решить, какой из них лучше или какой-либо другой, который лучше моего.

Подход 1:

Служите им по принципу Round Robin с интервалом времени, равным 5. Однако, когда мне нужно быть более осторожным при выборе интервала времени.Оно не должно быть слишком высоким или низким.Итак, я подумал о выборе временного интервала в качестве среднего значения времени обслуживания.

Подход 2: Предположим, что задания сортируются по времени, которое они занимают, и сохраняются в массиве A [1 ... n]

Сначала подайте A [1], затем A [n], затем A [2], затем A [n-1] и так далее.

Я не могу действительно решить, какое решение будет более оптимальным для этой проблемы.Я что-то упустил.

Спасибо, Чандер

Answer 1

Вы можете решить эту проблему, добавив сортировочную часть и импровизируя на подходе Round Robin,

Сначала рассортируйте клиентов по времени обслуживания

Теперь вместо того, чтобы просто давать каждому клиенту времяНарезая t в циклическом порядке, вы также можете проверить, есть ли у клиента меньше, чем t / 2 оставшегося времени, если это так, выполнить свое задание

Таким образом, для каждого клиента в отсортированном списке от первого клиента на сервере за время t, если егооставшееся время составляет

Answer 2

Позвольте мне предположить, что «общее время ожидания» представляет собой сумму времени, которое каждый клиент ожидает, пока сервер не закончит обслуживать его / ее, и предположить, что клиенты обслуживаются в порядке увеличения i, поэтому клиент C1 ждет t1 минут клиент C2 ждет t1+t2 минуты, а клиент C3 ждет t1+t2+t3 минут и ... клиент Cn ждет t1+t2+...+t{n-1}+tn минут.

или

C1 waits: t1
C2 waits: t1+t2
C3 waits: t1+t2+t3
...
Cn waits: t1+t2+t3+...tn

Общее время ожидания составляет n*t1+(n-1)*t2+...1*tn

Опять же, это основано на предположении, что клиенты обслуживаются в порядке увеличения i.

Теперь, какого клиента вы хотите сначала настроить на сервер?