Точный алгоритм для планирования задач на N одинаковых процессоров? - PullRequest
Новая
       32

Точный алгоритм для планирования задач на N одинаковых процессоров?

2 голосов
/ 13 января 2011

Я ищу точный алгоритм, который находит лучшее решение по расписанию задач на N идентичных процессорах.

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

В теории уравнение, описывающее этот алгоритм, выглядит следующим образом: P || Cmax

Если у кого-то есть алгоритм (особенно на Java) или псевдокод, я буду благодарен за помощь.

Я попытался написать собственный точный алгоритм, но id не работает :(. В приведенном ниже коде permUtil - это класс, который соответствует перестановкам.

Метод args:
- задачи -> все задачи, где индекс идентичности задачи и значение времени
- op -> процессор назначения (процессор, который назначает задачи)
// у нас есть глобальный массив процессоров op proc, где index - это идентификатор, а value - время расписания задачи на этом процессоре 

public void schedule(Byte[] tasks, int op)
{
    PermUtil<Byte> permA = new PermUtil<Byte>(tasks);
    Byte[] a;
    // permutation of all tasks
    while ((a = permA.next()) != null)
    {

        // assign tasks
        for(int i=1; i< a.length; i++)
        {
            // get the b set from i to end
            Byte[] b = Arrays.copyOfRange(a, i, a.length);
            // all permutations off b set
            PermUtil<Byte> permB = new PermUtil<Byte>(b);
            while ((b = permB.next()) != null)
            {
                // task on assign processor
                proc[op] = sum(Arrays.copyOfRange(a, 0, i));
                if (op < proc.length)
                    schedule(b, ++op);
                else
                {
                    proc[++op] = sum(b);
                }
            }
        }
    }
}

1 Ответ

2 голосов
/ 14 января 2011

Вот схема перебора всех возможных заданий. В реальной реализации вы должны заменить long на BigInteger, и переместите инициализацию массива за пределы внутреннего цикла. 

public void processOne(int nProcs, int nTasks, int[] assignment) {
    /* ... */
}

public void checkAll(int nProcs, int nTasks) {
    long count = power(nProcs, nTasks);
    /* Iterate over all the possible assignments */
    for (long j = 0; j < count; j++) {
        int[] assignment = new int[nTasks];
        for (int i = 0; i < nTasks; i++)
            assignment[i] = (int) (j / power(nProcs, i) % nProcs);
        processOne(nProcs, nTasks, assignment);
    }
}

Хитрость заключается в том, чтобы закодировать присвоение в число. Поскольку назначение представляет nTasks решений, каждое из которых имеет nProcs результатов, его можно рассматривать как число в базе nProcs, имеющее nTasks цифр. Каждое такое число соответствует действительному присвоению, и каждое присвоение имеет уникальный номер в таком диапазоне. Легко перебирать все присваивания, поскольку мы в основном перебираем диапазон целых чисел.

Все, что вам нужно сделать, это заполнить функцию processOne(int, int, int[]), которая должна быть довольно простой.

...