Заполнение n серверов m задачами

Задача:

Есть n серверов и m задач со временем на исполнение t1, . . . , tm. Задачи поступают онлайн, заранее t1, . . . , tm неизвестны.
Постройте алгоритм, который распределяет задачи так, чтобы получившееся время исполнения (время от начала исполнения первой задачи до времени, когда все задачи будут выполнены) было не хуже оптимального времени в два раза.

Под оптимальным временем подразумевается время исполнения для оптимального распределения задач по серверам в случае, когда t1, . . . , tm известны заранее.

Мысли:

При n >= m все понятно. А при n < m я правильно понимаю, что здесь надо создать очередь с приоритетами ? То есть пока не заполним все серверы одной задачей, мы просто создаем очередь с приоритетом - временем работы каждой задачи. Далее, при поступлении n + 1 задачи, мы определяем ее на сервер, который обрабатывает задачи с наименьшим суммарным временем работы.

Оптимальное время у нас, это вроде как: отсортировать задачи по времени работы - t1, ..., tm - от меньшего к большему. И далее заполнять сервера по такой схеме: пока Sum < tm -> Sum += ti, i += 1. Как только условие не выполняется условие, мы заполняем следующий сервер по такое же схеме. Если серверов не хватило. То снова возвращаемся к 1 серверу и заполняем по той же схеме. Получается что опитмальное время работы не более: (m//n + 1)*max(ti)


Скажите, в этих рассуждениях есть смысл? Или же здесь надо действовать по другому ?

Спасибо

0

может быть, лишь может быть здесь попахивает "Задачей о назначениях"...

0