Алгоритм решения задачи построения 2-процессорного расписания
Постановка задачи
Задача построения 2-процессорного расписания является NP-полной, поэтому существует возможность ее решения за псевдополиномиальное время. В работе [1] предлагается использовать метод решения задачи разбиения. Но задача разбиения полиномиально сводится к подзадаче задачи "2-процессорное расписание"
Поэтому этот метод не может быть использован для решения общей
постановки задачи "2-процессорное расписание".
множества на т=2 непересекающихся множеств, такое что
Алгоритм решения
больше D, то разбиения не существует, выход.
. Если условие верно, то разбиения не существует, выход.
Методом функциональных уравнений динамического программирования решается задача
, то разбиения не существует, выход.
определяет множество А 2 . Докажем, что если у определяет максимальную выборку из L, такую что
разбиения не существует.
Очевидно, выполняется равенство
выбирается максимально возможной та-
. Следовательно, простой kj является минимально возможным.
При переброске заданий из множества, определяемого у, во множество, определяемое у, простой на первом процессоре может только увеличиться. Пусть мы
перебросили некоторую выборку с первого процессора на второй и наоборот. Таким образом,
увеличиться по
, меньше либо равным D, оставшееся множество, определяемое у , по
сумме элементов будет больше D. То есть, разбиения не существует.
Разработанный алгоритм, в основе которого лежат идеи из работы [2], базируется на методе функциональных уравнений динамического программирования (МФУДП), который решает задачу о рюкзаке:
Задача (1) является частным случаем задачи (2). Но в общем случае коэффициенты в целевой функции не совпадают с коэффициентами в функции ограничении. Идея МФУДП выражается формулой из работы [3]:
Процедура итерируется для каждого ft) и повторяется для k=l,2,...,z. Подсчитаем количество операций, необходимое для нахождения оптимального вектора у АР). На одной итерации:
чтение
нахождение максимума
- 5 операций;
операция.
3. Заключение
На основе алгоритма построения 2-процессорного расписания была разработана программная реализация на языке Си для ЭВМ IBM PC с процессором Cyrix 486. Для D=40 и z=20,40,60,80,100 время работы программы соответственно 1, 5, 12, 20, 25 секунд.
В результате изучения предметной области не было выявлено эффективного способа решения задачи 2-процессорного расписания в общей формулировке. В работе предлагается псевдополиномиальный алгоритм решения поставленной задачи. Планируется развить идею, заложенную в методе, для решения задачи "многопроцессорное расписание". Авторы полностью несут ответственность за результаты.