Функция расчета расписания обработки изображений индикаторов панели приборов

Функция расчета расписания обработки

определяет расписание в виде множества С моментов времени

в которые выполняется подача набора тестовых сигналов для определения правильности показаний /-го индицируемого параметра [59].

Входными параметрами функции являются:

1) n- число индицируемых параметров;

2) G- множество индицируемых параметров панели приборов;

3) T_λp- множество значений t_flpι, каждое из которых представляет

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

внутреннего состояния панели приборов под действием набора тестовых сигналов, необходимое для вычисления индицируемого параметра

4) T_pπ- множество значений t_pπi, каждое из которых представляет собой время распознавания показания индицируемого параметра

т.е. значение t_pπописывает время, требуемое для определения индицируемого параметрас использованием алгоритмов обработки

стрелочных, жидкокристаллических или световых индикаторов;

5) A- двумерный массив размерности (n, n), кодирующий функцию допустимости одновременной обработки изображений двух индикаторов, в

котором элементесли индицируемый параметр g_iвозможно

вычислить одновременно с индицируемым параметром g, a_ij= 0- в противном случае, i, j = 1, n \

6) B- множество ограничений предшествования вида

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

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

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

- время снятия изображения t_c∏;

- время установления динамического режима индикатора t_ffpi.

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

Таким образом,Значение ^tси устанавливается на

основе анализа экспериментальных данных.

Для вычисления расписание требуется найти минимум целевой функции f (t) вида

определяющего наименьшее время, требуемое для параллельного контроля всех индицируемых параметров

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

Поскольку каждый индицируемый параметр характеризуется временем распознавания показаний, зависящим от типа индикатора, а также от временных характеристик применяемого алгоритма распознавания, определены необходимые и достаточные условия для осуществления одновременного параллельного распознавания нескольких индицируемых параметров на основе анализа области значений целевой функции (3.1).

Пусть для распознавания показаний индицируемого параметра каждого типа (стрелочный, жидкокристаллический или световой индикатор) используется единственный вычислительный узел. Тогда суммарное время загрузки вычислительного узла рассчитывается как

Выполнение условия

обеспечивает выполнение операций вычисления всех индицируемых параметров за время меньшее или равное общему рассчитанному времени обработки T_min.

Таким образом, осуществление параллельной обработки изображений индикаторов с использованием единственного вычислительного узла возможно при удовлетворении условия где- критический путь в рассчитанном расписании, w-

длина критического пути. В данном случае диаграмма загрузки вычислительного узла будет иметь вид, аналогичный приведенному на рисунке 3.1. Функция L(t)определяет процент загрузки вычислительного узла, функция Q(t)- количество параллельно диагностируемых

индицируемых параметров.

Рисунок 3.1. Пример диаграммы загрузки вычислительного узла

Если условие (3.4) не выполняется, для обеспечения параллельного распознавания нескольких индицируемых параметров требуемое количество распознающих вычислительных узлов - более одного.

Таким образом, задача нахождения минимума T_minописывается математической моделью M_m = (С, T, G, A, B, п).

Для нахождения минимума T_minв диссертационной работе использовались методы теории расписаний, поскольку задача минимизации времени обработки изображений индикаторов панели приборов представляет собой частный случай более общей задачи построения расписания проекта с учетом ограничения на ресурсы с запрещением прерывания процесса обслуживания (Resource-Constrained Project Scheduling Problem, RCPSP).

Задача построения расписания проекта описывается математической моделью M_s = (j, R, P, K), которая включает в себя:

1) множество Jиз Nработ, для которых определены их длительности d_j∈Z⁺. Предполагается, что задача планирования решается в дискретной шкале времени: t = 0,1,.... Расписанием называется множество

моментов стартов работ. При этом работа считается активной (выполняющейся) в моменты

2) множество Rиз М возобновимых (renewable) дискретных ресурсов, для которых определены их количества

3) множество Pограничений предшествования (job order, precedence constraints). Каждое ограничение задается четвёркой (j₁,j₂,t,l), где t∈{‘start­finish’, ‘start-start’, ‘finish-finish’, ‘finish-start’}, - временной промежуток (лаг) между работами j₁и j₂. Определяют технологический порядок следования работ: если, например, t = ’finish-start’, то работа j₂не может начаться раньше, чем через lединиц времени после окончания

Смысл остальных типов аналогичен.

4) множество Kназначений ресурсов работам (assignments)

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

В случае, когда матрица (k_jr) разреженная, экономнее эти назначения задавать в виде списка троек (Job, Resource, Capacity).

Между математическими моделями М_м и М существует следующие соответствия:

1. Множеству с в модели М_м однозначно соответствует множество J в модели M.

2. Множеству Tв модели Mоднозначно соответствует множество длительностей d_j∈Z⁺работ в модели M_s.

3. Множеству Gв модели М_м однозначно соответствует множество N работ в модели M_s.

4. Множеству Bв модели Mоднозначно соответствует множество ^P ограничений предшествования в модели M .

5. Двумерному массиву Aв модели М_м однозначно соответствует множество Kназначений ресурсов работам в модели M.

Рассмотрим более подробно приведенные соответствия 4 и 5.

В случае полного отсутствия ресурсов (а, следовательно, и ограничений типа 4) все ограничения задачи содержатся в ориентированном графе предшествования G = (J, P). В этом случае длина оптимального расписания равна длине критического, то есть самого длинного пути в G. Под длиной пути подразумевается сумма весов всех вершин (длительностей соот­ветствующих работ) и весов всех дуг, входящих в этот путь. В этом расписании время старта любой работы определяется как длина критического пути до этой работы.

Найдем ранние и поздние старты работ для безресурсной задачи с помощью метода критического пути [27]. Пусть T- множество ранних времен работ- множество поздних стартов работ

Предлагается следующий алгоритм прямого прохода:

и алгоритм обратного прохода:

Помимо ограничений предшествования в задаче RCPSP имеются ресурсные ограничения.

Рассмотрим множество R, состоящее из Mвозобновимых дискретных ресурсов. Количество подмножеств вида {q, z} q, z∈J, q ≠ zиз двух различных работ есть количество ресурсов M, то есть

47

где n - число работ.

С учетом формулы (3.8) множество Rбудет иметь следующий вид

Примем количествокаждого ресурса за константную

величину K = 1. Таким образом, если какие-либо две работы конкурируют за общий разделяемый ресурс(не исполняются

одновременно друг с другом), то для того чтобы выполнялось условие (3.5), необходимо задать потребности каждой из работ q, zв ресурсе pкак Если две работыне конкурируют за

ресурс p ∈R(возможно их одновременное исполнение), для выполнения условия (3.5) необходимо и достаточно принять

Входным параметром алгоритма определения ресурсных ограничений (инициализации множеств R, K) является двумерный массив A.

Предлагаемый алгоритм для определения ресурсных ограничений будет иметь следующий вид.

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

методы теории расписаний для решения задачи определения минимума T_min как частного случая задачи RCPSP.

Как было отмечено ранее, задача RCPSP является NP-трудной, поэтому не существует эффективных алгоритмов получения её оптимального решения. Однако для сложных проектов хорошим результатом является нахождение допустимого расписания приемлемой длины (например, на 10­30% длиннее оптимального). В настоящее время в этом направлении разработано множество алгоритмов [28-30].

Для решения задачи RCPSP был выбран метод serial scheduling scheme, разработанный Робертом Колишем (R. Kolish) [30], отличающийся своей простотой, общностью и имеющий квадратичную трудоёмкость. По своей сути данный метод является так называемым последовательным жадным алгоритмом.

Работа алгоритма состоит из Nэтапов, на каждом из которых фиксируется время выполнения одной из работ (то есть, после к этапов имеется частичное расписание для к работ, удовлетворяющее всем ограничениям).

Обозначим через S (scheduled set) множество работ, уже фиксированных к моменту начала этапа n(таким образом, ∣S = n -1). Через D_n (decision set) обозначим множество ещё не фиксированных работ, у которых фиксированы все их предшественники, то есть

Из множества Sвыбирается работа, фиксируемая на этапе ⁿ. Этот выбор производится в соответствии с эвристическим правилом, которое может быть определено тем или иным образом в соответствии с некоторыми соображениями, отвечающими здравому смыслу.

Примером такого эвристического правила является LST-правило (latest start time): из всех работ D_nвыбирать ту, для которой время старта в позднем расписании для соответствующей безресурсной задачи наименьшее. Это означает, что эта работа, скорее всего, имеет самую длинную цепочку 49

последователей, и ее выгодно поставить в расписании как можно раньше. Выбрав h ∈D_n, мы фиксируем её в расписании, выбирая самое раннее время, на которое можно поставить эту работу, удовлетворив все ограничения предшествования и ресурсные ограничения. Формальный алгоритм для серийного метода опубликован в работе [30] и имеет вид:

Получаемое алгоритмом расписание также является ранним: ни одну из работ нельзя сдвинуть на более ранний срок, не сдвигая другие работы. Легко заметить, что среди ранних расписаний задачи RCPSP есть оптимальное решение. Действительно, если взять какое-либо оптимальное не раннее расписание, то из него можно простым поочередным сдвигом работ на более ранний срок получить раннее расписание, длина которого будет не больше, чем длина исходного расписания; следовательно, оно также будет оптимальным. Все ранние расписания можно получить, если на каждом этапе перебирать все варианты выбора h ∈D_n. Таким образом, существует схема полного перебора, позволяющая найти оптимальное решение задачи. На этой схеме основан оптимальный метод ветвей и границ [27]. Естественно, этот метод не является вычислительно эффективным, поскольку решаемая задача поиска оптимального расписания NP-трудна. Выбранный серийный метод [30] просматривает только одну ветвь из этого дерева перебора, находя одно допустимое решение.

Таким образом, решение задачи RCPSP представляется в виде

множества С моментов времени .и одновременно

является решением задачи минимизации функции (3.1).

Следовательно, выходной параметр функции расчета расписания представляет собой расписание подачи наборов тестовых сигналов на входы панели приборов в виде множества Cмоментов временигенерации

тестовых сигналов, соответствующих индицируемому параметру i.

3.1