ИППИ РАН, [email protected]

Сравнение эвристических алгоритмов планирования задач в распределенных вычислительных системах с решением задачи планирования как задачи дискретной оптимизации (возможен командный курсовой проект)

Планирование выполнения задач в распределенных вычислительных системах на практике является трудной вычислительной задачей. Предлагается сравнить эффективность работы различных эвристических алгоритмов планирования в условиях неполной информации о трудоемкости и расписании задач с результатом работы «эталонного» планировщика, действующего в условиях полной информированности (о трудоемкости и динамических параметрах очереди заданий) и решающего задачу планирования как задачу дискретной оптимизации. В ходе работы потребуется выбрать несколько алгоритмов планирования, применяемых в Грид, на кластерах и/или в облачных инфраструктурах и сравнить их эффективность с (возможно, приближенным) решением задачи планирования как задачи линейного программирования с частично-целочисленными переменными одним из соответствующих решателей (SCIP, http://scip.zib.de, или CBC, https://projects.coin-or.org/Cbc). Возможны отдельные подтемы и работа в команде.

Оценка константы Хоффмана для систем линейных неравенств численными параллельными методами линейной алгебры и глобальной оптимизации (возможен командный курсовой проект)

В теории и вычислительных методах оптимизации важное значение имеет результат т.н. «теорема» (или «лемма») Алана Хоффмана, доказанная им в 1952 г. Установлено, что для любого множества решений конечной системы линейных неравенств, существует т.н. «константа Хоффмана», зависящая только от коэффициентов неравенств при переменных (а не от правых частей), дающая оценку расстояния до множества решений по легко вычисляемой характеристике нарушения указанных линейных неравенств. Несмотря на относительно несложный способ доказательства существования константы Хоффмана, вычисление ее значения (или - верхней оценки) является нетривиальной задачей. Известные схемы вычислений носят переборный характер. Одна схема — это построение всех крайних точек некоторого многогранного множества. Другая — основана на решении задачи глобальной максимизации выпуклой квадратичной функции на множестве решений системы линейных или квадратичных неравенств. В работе нужно будет сравнить различные способы вычисления (оценки) константы Хоффмана для больших систем линейных неравенств. Можно применять пакеты языка Python SciPy, Pyomo; пакет анализа систем линейных неравенств (с возможностью работать в режиме параллельных вычислений), http://cgm.cs.mcgill.ca/~avis/C/lrslib/; решатель задач глобальной оптимизации SCIP, http://scip.zib.de/ и его параллельную реализацию ParaSCIP, http://ug.zib.de/.