интересно
Предыдущая | Содержание | Следующая

Алгоритм решения задачи построения 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-процессорного расписания в общей формулировке. В работе предлагается псевдополиномиальный алгоритм решения поставленной задачи. Планируется развить идею, заложенную в методе, для решения задачи "многопроцессорное расписание". Авторы полностью несут ответственность за результаты.