Оптимально назначая задачи работникам

Question

Я работаю над комплексной системой сборки, которая выполняет распределенные сборки на нескольких машинах уже довольно давно. Он корректно обрабатывает зависимости и, кажется, достаточно хорошо масштабируется, поэтому мы добавили больше проектов и больше машин, но похоже, что он может работать лучше.

У меня проблема с распределением ресурсов. У меня есть список доступных компьютеров и список проектов, которые я хотел бы построить, а также на каждом компьютере указано, какое программное обеспечение, ОС, версия компилятора и т. Д. Установлено, и в каждом проекте указано, что ему требуется. Когда работа должна быть назначена, я могу выполнить запрос к базе данных, который перечисляет возможные назначения. Теперь мне нужно выполнить эти задания максимально эффективно.

Наименьший пример - два проекта 1 и 2 с двумя машинами A и B. Машина A может построить любой проект, но машина B может построить только проект 1. Поэтому я получаю список пар (A, 1), ( А, 2), (В, 1). Если я обрабатываю назначения по порядку, машина A создает проект 1, и мне нужно ждать, пока он не завершится, прежде чем я смогу построить проект 2. Возможно, было бы лучше назначить машину A для проекта 2 и машину B для проекта 1. Но. .. машина A может быть намного быстрее, чем машина B, и если машина вообще не используется, это может быть правильным ответом.

Я уверен, что это проблема «оперативных исследований», которая уже неоднократно решалась. Мне не обязательно нужно оптимальное решение ... просто попытка чего-то лучшего, чем у меня - кажется, я часто в конечном итоге сталкиваюсь с поставленными в очередь задачами и простаивающими машинами, которых могло бы избежать лучшее распределение. Любые предложения приветствуются.

Answer 1

Проблема, которую вы пытаетесь решить, эквивалентна классической задаче планирования работы магазина. Поиск оптимального расписания NP-hard.

Люди изобрели много эвристик для создания расписаний, но какие из них хороши, сильно зависит от проблемы.

Пара общих эвристик:

• Запланируйте сначала самое короткое задание.
• Сначала спланируйте задачу с наибольшим ограничением, например, выберите задачу, которая может быть запущена на меньшем количестве машин.

Answer 2

Для начала я предпочитаю модель "тянуть".

Каждая машина извлекает задачи с центрального сервера в режиме ожидания.

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

У вас есть своего рода модель пула, где у вас есть классификации задач и пулы машин, которые имеют соответствующие классификации. Например, машины в пуле 1 могут строить определенные вещи. Машины в пуле 2 могут строить что угодно. Думайте о них как о «навыках», и вы увидите, как это является своего рода проблемой управления проектами.

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

Это может быть все, что вам нужно. Однако, если вам нужна дополнительная оптимизация, вот ваш следующий шаг.

После того, как вы запустили его несколько раз - и у вас есть некоторые ожидания в отношении производительности - вы можете написать модуль, который будет пытаться поддерживать каждую машину максимально загруженной. Это планирование именно то, что делают такие вещи, как Microsoft Project.

С учетом заданий, с продолжительностью и зависимостями, вы пытаетесь выполнить «выравнивание ресурсов». Вы хотите, чтобы каждый ресурс (клиент для вашей компиляции) был как можно более занятым в соответствии с набором навыков и продуктивностью каждого клиента.

Answer 3

На первый взгляд, я бы порекомендовал запускать службу Windows на каждой машине, где на одной машине также запускается главная служба для координации назначений. Основная служба опрашивает каждый компьютер на предмет того, обрабатывает ли он назначение или нет, а затем начинает обработку, какое бы назначение не находилось в очереди, которую оно может обработать.