Thursday, June 18, 2009

Двухкритериальная задача о выполнении работ на параллельных машинах

Рассматривается задача о выполнении работ на параллельных машинах с двумя критериями: минимума числа машин и минимума длины расписания. При этом требуется найти лексикографическое множество оптимумов.

Monday, June 1, 2009

Vector Packing Problem

Задача о минимуме максимальной загрузки может быть сформулирована как задача упаковки векторов (vector packing problem). В задаче упаковки векторов имеется n m-координатных векторов. Требуется упаковать эти векторы в контейнеры с m ограничениями для каждой координаты вектора, соответственно, при этом использовав минимальное количество контейнеров. Задача упаковки векторов является обобщением задачи упаковки контейнеров (bin packing problem).
Задача о минимуме максимальной загрузки может быть описана как обобщение задачи упаковки в полосу (strip packing problem) до задачи упаковки векторов в полосу (strip vector packing problem).
Таким образом, название задачи упаковки векторов может быть уточнено до задачи упаковки векторов в контейнеры (bin vector packing problem).