Алгоритм построения ДЗ P1

Алгоритмы распределения задач по ЭМ в ВС при произвольной трудоемкости фрагментов

В рамках планирования решения задач с произвольной трудоемкостью присутствует 2 подхода:

1.min t_диаг — минимизация времени диагностирования, когда при заданном времени решения минимизируют период цикла контроля

2.min t_реш — минимизация времени решения прикладных задач при заданном периоде цикла контроля

Пусть заданы 2 графа:

1. ДГ G(U,T)

2. граф ИС D(W,P,Г)

n = |U| - количество ЭМ, m = |T| - количество проверок, P = {p_q}-трудоемкость

Для однородных ВС p_q определяет время решения фрагментов

Необходимо построить план решения прикладных задач на данной ВС таким образом, чтобы обеспечить решение всех фрагментов определенных множеством w, за время < Tцр_max и выполнение всех диагностических проверок предусмотренных ДГ за t_min.

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

ЭМ используемые для решения прикладных задач образуют подмножество U1. Дополнительные ЭМ не задействованы в решении прикладных задач образуют множество U2 => U = U1 ν U2; U1 Λ U2 = Ø. Мощность U1: |U1| = n — (U2)

Чем меньше ЭМ задействовано в решении прикладных задач, тем больше может быть использовано для диагностических операций. Используя метод парных элементарных проверок, поэтому max количество элементарных проверок ограничено величиной int(n/2)

На 1м этапе строится ДЗ P1, критериями построения которой является Tцр =< Tцр_max, |U1| >= n/2, |U1| → min.

На 2м этапе ДЗ P1 модифицируются в целевую диаграмму загрузки P2, которая предусматривает выполнение элементарных проверок и обеспечивает период цикла решения не более чем в ДЗ P1.

1. k = n1

2. с помощью заданного алгоритма спланировать решение фрагмента задач на k ЭМ

3. k = k -1

4. если k >= n/2 и Tцр =< Tцр_max, то переход на шаг 2

5. если Tцр =< Tцр_max, то переход на шаг 8

6. k = k + 2

7. с помощью заданного алгоритма спланировать решение фрагмента задач на k ЭМ

8. конец алгоритма

Для построения итоговой ДЗ вводится понятие — Раннее время начала выполнения элементарной проверки i-й ЭМ

Алгоритм построения итоговой ДЗ заключается в следующем: из множества элементарных проверок определяется в ДГ выбираются такие, выполнение которых может начаться в первую очередь. Для каждой выбранной проверки из графа ИС выбирается фрагмент, который может быть одновременно выполнен на соответствующей ЭМ. После этого для каждой проверки определяется время окончания ее проведения. На основе полученных данных выбирается проверка, которая будет выполнена и корректируется ДЗ.