Минимизация максимальной стоимости назначения задачи в машине

Question

У меня есть m машины и n задачи. Существует а т матрицей п стоимости А где Aij является стоимость выполнения задачи J на машине я. Каждая задача должна быть назначена ровно на одну машину, но каждая машина может принимать несколько задач.

Моя проблема заключается в том, чтобы найти способ назначения задач машинам свести к минимуму MakeSpan, максимальная стоимость одной машины.

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

Answer 1

Вы можете выразить эту проблему как целочисленная линейная программа. Пусть B[i][j] - это матрица 0 и 1 со значением, которое B[i][j] = 1, если мы назначим j-ю задачу на машину i. Тот факт, что задачи не расщепляются, делает это скорее ILP, чем LP, иначе мы могли бы просто настаивать на том, чтобы 0 <= B[i][j] <= 1.

Мы хотим минимизировать максимальную стоимость любой машины. Это не линейная функция, но есть стандартный трюк, чтобы выразить ее как таковую, введя фиктивную переменную (которая в программе здесь называется MakeSpan).

НРП это программа, которая имеет т + п ограничения:

minimize MakeSpan such that 

sum(B[i][j] for i=1..m) = 1 for all j 
sum(B[i][j]*A[i][j] for j=1..n) <= MakeSpan for all i 

Первый набор ограничений формализует идею, что каждая задача назначена ровно в одну машину. Второй набор ограничений заключается в том, что стоимость каждой машины не превышает MakeSpan.

Минимум MakeSpan достигается локально, когда MakeSpan равен максимальной стоимости любой машины и достигается в глобальном масштабе, когда эта максимальная стоимость также минимизирована.

Для решения ILP вы можете использовать свой любимый решатель ILP. Например, GLPK является открытым исходным кодом.