Распределение процессов
Помогите пожалуйста с алгоритмом.
Задача:
Есть несколько задач, связанных между собой односторонней связью (то есть, к примеру, задача номер 2 не может начать выполнятся, пока не выполнится задача номер 1). По сути своей совокупность этих задач представляет собой граф.
Пользователь вводит количество процессоров, на которых выполняются задачи (на одном процессоре одновременно выполняется только 1 задача).
Программа же должна перебрать все возможные варианты расстановки задач по процессорам (учитывая зависимости) и в итоге выдать наименьшее время выполнения всех задач.
Это вкратце, в принципе есть ещё методичка, находится она здесь: http://pvk170.files.wordpress.com/2009/09/2009-d181d0bfd0be-d0bbd0b0d0b1-1.doc
Суть алгоритма в следующем: расставить вначале задачи без учета количества процессоров, а затем на тех шагах, где количество задач больше чем количество процессоров, выполнять расположение задач различными способами (например задач 3, а процессоров 2. И эти 3 задачи располагаем на двух процессорах всеми возможными вариантами).
Что сделано:
Задачи записаны в виде структур (время выполнения; зависимые задачи; выполнен/выполняется/не выполнен).
Процессоры тоже в виде структур (занят/свободен; номер выполняемой задачи; время занятости).
Без учета ограниченного количества процессоров всё работает.
Проблема с перебором, как сделать так, чтобы был в виде функции, вызываемой рекурсивно. То есть как реализовать сам перебор?
Заранее благодарю за помощь!
Задача:
Есть несколько задач, связанных между собой односторонней связью (то есть, к примеру, задача номер 2 не может начать выполнятся, пока не выполнится задача номер 1). По сути своей совокупность этих задач представляет собой граф.
Пользователь вводит количество процессоров, на которых выполняются задачи (на одном процессоре одновременно выполняется только 1 задача).
Программа же должна перебрать все возможные варианты расстановки задач по процессорам (учитывая зависимости) и в итоге выдать наименьшее время выполнения всех задач.
Это вкратце, в принципе есть ещё методичка, находится она здесь: http://pvk170.files.wordpress.com/2009/09/2009-d181d0bfd0be-d0bbd0b0d0b1-1.doc
Суть алгоритма в следующем: расставить вначале задачи без учета количества процессоров, а затем на тех шагах, где количество задач больше чем количество процессоров, выполнять расположение задач различными способами (например задач 3, а процессоров 2. И эти 3 задачи располагаем на двух процессорах всеми возможными вариантами).
Что сделано:
Задачи записаны в виде структур (время выполнения; зависимые задачи; выполнен/выполняется/не выполнен).
Процессоры тоже в виде структур (занят/свободен; номер выполняемой задачи; время занятости).
Без учета ограниченного количества процессоров всё работает.
Проблема с перебором, как сделать так, чтобы был в виде функции, вызываемой рекурсивно. То есть как реализовать сам перебор?
Заранее благодарю за помощь!