Как нарисовать матрицу задач?

Question

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

Я должен написать алгоритм, который рассчитать лучшее время для выполнения.

Вот вход:

5
9 6
6 2
2 6
10 1
5 6

Первая строка - количество задач, в следующих строках первая цифра - время, затраченное на выполнение задачи на суперкомпьютере, вторая - для компьютера.

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

Кто-нибудь может нарисовать матрицу для этой задачи?

При тестировании сервера ответ 33, я пробовал 2 способа, но у меня 32 и 34.

  | T1 | T2 | T3 | T4 | T5 |minimal
   ________________________________
S | 9  |  6 |  2 | 10 | 5  |2
_________________________________
C | 6  | 2  | 6  | 1  | 6  |1

теперь я ищу минимальное время для (S)upercomputer и (C)omputer, равно 2 и 1 и вычитаем из любой строки.

       | T1 | T2 | T3 | T4 | T5 |
       _________________________
     S | 7  |  4 |  0 | 8  | 3  |
    ____________________________
     C | 5  | 1  | 5  | 0  | 5  |
__________________________________
minimal| 5  | 1  | 0  | 0  | 3

Далее я ищу минимальные сроки выполнения любой задачи и вычитаю. и результаты 2+1 от первого вычитания, 5+1+3 от второго вычитания и 2+3+5+8+2 от этого:

       | T1 | T2 | T3 | T4 | T5 |
       _________________________
     S | 2  |  3 |  0 | 8  | 0  |
    ____________________________
     C | 0  | 0  | 5  | 0  | 2  |

но я не знаю, имеет ли это смысл.

Answer 1

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

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

Следовательно, вы планируете задания на суперкомпьютере в порядке возрастания времени их выполнения на нем.

2 -> 5 -> 6 -> 9 -> 10

После завершения соответствующих заданий на суперкомпьютере у них есть все время для выполнения оставшегося задания на своих отдельных компьютерах. Однако после этой серии на его компьютере остается только последнее задание (1 единица времени).

Hence total time consumed = 2 + 5 + 6 + 9 + 10 + 1 = 33

Как решить такую ​​проблему:

Одна логика, как я уже говорил ранее, заключается в том, чтобы суперкомпьютер был максимально свободным. Однако эта логика ломается для случая, подобного следующему:

5
9 6
6 2
2 6
10 **100**
5 6

Теперь, как вы видите, четвертое задание занимает 100 единиц времени на отдельном компьютере. Следовательно, лучше планировать приоритет, чтобы общее время выполнения составило 110, а не более.

Комбинации грубой силы должны иметь факториальную сложность, поскольку существует N! возможные перестановки графика.

Тем не менее, в интернете есть масса литературы по расписанию работы. Вы можете зайти в Google и найти что-то подходящее для вас.