Планирование разнородных задач на разнородных машинах

Question

У нас есть n рабочих мест и m машин. У каждой работы у меня есть время выпуска r [i]. Обработка задания i на машине j занимает p [i] [j] время. Для одной работы k, | {p [i] [j] | я == k} | <= c, где c << m. Мы определяем задержку задания i как f [i] - r [i], где f [i] - время завершения задания i. Система не является вытесняющей, то есть когда одно задание запускается на каком-либо компьютере, оно не может быть прервано до завершения. Цель состоит в том, чтобы предоставить алгоритм планирования, который минимизирует сумму задержки всех заданий. Есть идеи? </p>

Answer 1

Вот сокращение от 3-х секционной проблемы .

Пусть S = {x ₁ ,…, x _3m } будет экземпляром 3-разбиения, так что для каждого i B / 4 i i / m - целевая сумма.

Пусть будет m идентичных машин. В момент времени 0 освободите задания длиной 3 м x ₁ ,…, x _3m . В каждый раз, когда B, B + 1,…, B + 4 мБ - 1, освобождайте m заданий длиной 1, всего 4 млн. ² B заданий.

Экземпляр с 3 разделами имеет решение в том и только в том случае, если рабочий диапазон начальных заданий меньше или равен B. Если решение существует, то вклад начальных заданий в цель составляет не более 3 мБ. , Вклад других рабочих мест составляет 4m ² B.

Если рабочий диапазон длиннее, чем B, то цепочка из 4 мБ заданий задерживается как минимум на одну единицу, внося 4 мБ в цель. Таким образом, цель составляет не более 3 мБ + 4 м ² B, если проблема с 3 разделами разрешима, и не менее 4 мБ + 4 м ² B, если проблема с 3 разделами не решаема.