Здравствуйте, Assasin291, Вы писали:

A>Есть сервер с двумя процессорами и задачи, которые он должен скачать и обработать. Каждой задаче E_ki соответствует три числа: номер процессора k, на котором задача должна быть обработана, время загрузки T_ki и время обработки P_ki. Необходимо обработать задачи так, чтобы время окончания обработки последней задачи было наименьшим. В каждый момент времени сервер может загружать не более одной задачи и процессоры могут обрабатывать не более одной задачи в каждый момент времени. Процессор не может обрабатывать одну задачу и скачивать другую.

A>Решение довольно простое: строится дерево решений и с помощью обхода и отсечений заранее невыгодных расписаний ищется наиболее подходящее расписание. Проблема в том, что для отсечения по рекорду нужно знать нижнюю оценку(НО). Мне предложили в качестве НО взять сумму обработок всех задач, но мне кажется, что эта недостижимая НО даст довольно слабые результаты. Может быть кто-нибудь придумает оценку получше?

T0=sum(Tki+Pki,i)/Ncpu

Есть сервер с двумя процессорами и задачи, которые он должен скачать и обработать. Каждой задаче E_ki соответствует три числа: номер процессора k, на котором задача должна быть обработана, время загрузки T_ki и время обработки P_ki. Необходимо обработать задачи так, чтобы время окончания обработки последней задачи было наименьшим. В каждый момент времени сервер может загружать не более одной задачи и процессоры могут обрабатывать не более одной задачи в каждый момент времени. Процессор не может обрабатывать одну задачу и скачивать другую.

Решение довольно простое: строится дерево решений и с помощью обхода и отсечений заранее невыгодных расписаний ищется наиболее подходящее расписание. Проблема в том, что для отсечения по рекорду нужно знать нижнюю оценку(НО). Мне предложили в качестве НО взять сумму обработок всех задач, но мне кажется, что эта недостижимая НО даст довольно слабые результаты. Может быть кто-нибудь придумает оценку получше?

Дерево решений с отсечением — ИМХО пушкой по воробьям по этой задаче. Эта задача абсолютно не будет ИМХО NP-полной.
Интуиция подсказывает, что для выполнения условия минимальности в любое время выполнения предыдущего задания (в частности в нач. момент, если есть >=2 задания с T_i=0) на конвеер просто надо ставить следующую задачу с наибольшим временем выполнения. Алгоритм также не зависит от кол-ва доступных процессоров.

Здравствуйте, icegood, Вы писали:

I>Дерево решений с отсечением — ИМХО пушкой по воробьям по этой задаче. Эта задача абсолютно не будет ИМХО NP-полной.
I>Интуиция подсказывает, что для выполнения условия минимальности в любое время выполнения предыдущего задания (в частности в нач. момент, если есть >=2 задания с T_i=0) на конвеер просто надо ставить следующую задачу с наибольшим временем выполнения. Алгоритм также не зависит от кол-ва доступных процессоров.

Не, вру... В случае трех заданий при Т1=Т2=0 и Т3=Е>0 , также при Р1=Р2=Р3/2=Р, если Е<Р, то лучше подождать... Ну тогда этот алгоритм будет неплохой верхней оценкой для отсечения... А нижняя чего, в задачах минимальности нужна?

Здравствуйте, icegood, Вы писали:

I>Дерево решений с отсечением — ИМХО пушкой по воробьям по этой задаче.
Но надо сделать именно дерево решений с отсечениями.

I>А нижняя чего, в задачах минимальности нужна?
В задачнике, который нам дали, есть формула для отсечения в задачах по минимизации:
F < F(x) + НО(X), где F — рекорд, F(x) — значение целевой функции в вершине x, НО(X) — нижняя оценка для X, X — вектор из оставшихся(ещё не обработанных) вершин.

А>T0=sum(Tki+Pki,i)/Ncpu
Это, похоже, получше, чем было. Спасибо.
Только что такое Р_ki,i? Опечатка?

Здравствуйте, Аноним, Вы писали:

А>T0=sum(Tki+Pki,i)/Ncpu

И как это предполагается достичь?

Пусть:
Задача для первого процессора: (T1=90, P1=10)
Задача для второго процессора: (T2=90, P2=10)
Выполнение:
Загружаем первую задачу, затем сразу за ней вторую задачу (одновременно загружать нельзя). Сразу после загрузки выполняем их. Минимальное время исполнения = Т1 + Т2 + Р2 = 90 + 90 + 10 = 190

А по твоей формуле: (90+10 + 90+10) / 2 = 100, т.е. меньше 190, чего быть не должно. Т.е. эту формулу нельзя использовать для отсечения поиска.

Здравствуйте, Assasin291, Вы писали:

A>Есть сервер с двумя процессорами и задачи, которые он должен скачать и обработать. Каждой задаче E_ki соответствует три числа: номер процессора k, на котором задача должна быть обработана, время загрузки T_ki и время обработки P_ki. Необходимо обработать задачи так, чтобы время окончания обработки последней задачи было наименьшим. В каждый момент времени сервер может загружать не более одной задачи и процессоры могут обрабатывать не более одной задачи в каждый момент времени. Процессор не может обрабатывать одну задачу и скачивать другую.

A>Решение довольно простое: строится дерево решений и с помощью обхода и отсечений заранее невыгодных расписаний ищется наиболее подходящее расписание. Проблема в том, что для отсечения по рекорду нужно знать нижнюю оценку(НО). Мне предложили в качестве НО взять сумму обработок всех задач, но мне кажется, что эта недостижимая НО даст довольно слабые результаты. Может быть кто-нибудь придумает оценку получше?

Это же классическая np-полная задача, поэтому ,скорей всего, что-то сочинить здесь на ходу не получится.
Предлагаю поискать литературу.
http://en.wikipedia.org/wiki/Multiprocessor_scheduling

В классическом методе ветвей и границ нижняя оценка улучшается на каждом успешном шаге, нужно ли что-то ещё придумывать?