Постановка задачи оптимизации обслуживания многоочередных структур данных

Пусть МВС состоит из n идентичных, параллельно работающих процессоров.

E={ei|i=1,2,…, n}.

На вход МВС поступает множество m независимых программ.

W={wj|j=1,2,…, m},.

которые требуется распределить между процессорами. Если время rj непрерывного использования процессора для выполнения каждой программы wj, одинаково для всех процессоров, то множеству W сопоставляется множество.

R={rj|j=1,2,…, m}.

l-м решением задачи планирования в этом случае является множество.

Vl={Wli|i=1,2,…, n},.

где Wli подмножество программ, выполняемых на процессоре ei:

(i, j)[((ij)&(WliVl)&(WljVl))>((WliWlj =)&(Wli= W))]. (1).

Запланированная вариантом решения Vl загрузка программами каждого процессора ei оценивается ресурсом:

Rli =rk; где rk |wk Wli. (2).

Если производительность процессоров различна, то задается время rij непрерывного использования процессора ei для выполнения программы wj. Таким образом, множествам E и W сопоставляется множество R={rij| i=1,2,…, n; j=1,2,…, m}. В этом случае формула (2) примет вид:

Rli =rik, где k|wk Wli. (3).

Представим некоторую очередь программ, поступающих на процессор ei в виде списка.

Pli=p1,p2,p3,…, ps,…, pm.,.

где ps это индекс программы, у которой порядковый номер в очереди Pli равен s.

Загрузка программами каждого процессора, рассчитываемая по формулам (2) или (3), не учитывает время переключения между различными заявками. Отметим, что время переключения для каждой пары соседних заявок в очереди имеет свое значение.

Продолжительность переключения между соседними в очереди заявками, поступающими на обслуживающий прибор ei, задается матрицей переключений.

Тi=||tk, s||mm.

Таблица № 1 Матрица переключений Тi.

tk, s — время переключения между соседними в очереди заявками (wk, ws).

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

Pli = p1, t12, p2, t23, p3, ,…, ps, ts, s+1, ps+1 ,…, pm-1, tm-1,m, pm.

Здесь ts, s+1 — время переключения между соседними в очереди Pli программами с порядковыми номерами s и s+1.

Общее время Tli переключения между заявками, поступающими на вход обслуживающего прибора ei, определится как сумма переключений:

Tli =tk-1,k, где k| tk-1,k Pli. (4).

Таким образом, загрузка Rli заявками процессора ei с учетом времени переключения между соседними заявками в очереди Pli, а также времени rij непрерывного использования процессора ei для выполнения каждой программы wj Wli определится как:

Rli =Tli +rik, где k|wk Wli (5).

Для обеспечения максимальной эффективности использования существующих ресурсов необходимо упорядочить очередь заявок в каждом списке Pli. Будем считать, что.

Pl={Pli|i=1,2,…, n} ;

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

В этом случае решением Zl задачи распределения заявок между обслуживающими приборами является совокупность двух множеств Vl и Pl, т. е.

Zl=(Vl; Pl).

В качестве оценки решения Zl рассматривается величина:

Fl=max (Rli). i.

Наиболее распространённым критерием оптимизации при планировании в случае многоуровневой очереди является «минимаксный» критерий:

F=min Fl = min max (Rli). l l i.

Это связано с тем, что в большинстве реальных задач при планировании чаще всего требует решения задача уменьшения времени выполнения всех заявок. Поскольку, чем быстрее СМО обслуживает поступающие заявки, тем выше ее производительность, а значит, и выше экономическая эффективность предприятия, использующего данную систему.

Для отображения распределения заявок по обслуживающим приборам используется полный двудольный граф.

Hnm=(EW, U), где E={ei|i=1,2,…, n}.

— множество вершин (первая доля), соответствующих множеству обслуживающих приборов, а.

W={wj|j=1,2,…, m} ;

множество вершин (вторая доля), соответствующих множеству заявок (потоков). U — множество ребер, связывающих вершины множества E с вершинами множества W. Конкретное решение задачи распределения заявок представляется в виде подграфа.

Hl=(EW, Ul). HlHnm, UlU.

Вершина wjW связана с вершиной eiE в том и только в том случае, когда wj назначена в ei. Пусть Uli множество ребер двудольного графа Hl, связывающих вершину ei с вершинами множества Wli.

Uli=Ul.

Для наглядности представления конкретного распределения заявок (рис. 1) множество заданий W сгруппировано в подмножества Wli, где Wliподмножество заявок, поступающих на обслуживающий прибор ei.

Отличительной особенностью представленного двудольного графа.

Hl=(EW, Ul).

является то, что число ребер множества Uli равно числу вершин множества Wli. Каждое ребро uzUli, с одной стороны, инцидентно вершине ei, а с другой стороны, инцидентно одной и только вершине wkWli.

Назовем двудольный граф, представляющий распределение заявок, граф — распределением Hl. Отметим, что в графе — распределении Hl локальная степень любой вершины wjW равна единице, а локальная степень вершины ei равна мощности множества Wli, т. е.

с (wj)=1, с (ei)= |Wli|.

Таким образом, поиск распределение заявок сводится к поиску на полном двудольном графе Hnm подграфа Hl.

Рис. 1 Интерпретация распределения программ в МВС