(Макс., +) подход к планированию

Линейный характер простых графов событий привел к развитию алгебраических структур — диодов (мин., +) или (макс., +). Данные структуры отсутствуют в случае, когда соизмеряются графы событий, а также когда сеть Петри содержит индетерминизм, связанный с использованием ресурсов. В данной главе представлены только те сети Петри, индетерминизм которых связан с совместным использованием рассматриваемых ресурсов. Мы показываем, что возможно отобразить изучение данного типа сети Петри на графе событий, а также в системе связанных уравнений.

Гипотезы подстановки и введения

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

В предыдущей работе данная проблема была решена при помощи так называемой инвестиционной политики или функции маршрутизации [OHL 94J. Наша цель заключается в нахождении всех возможных последовательностей ресурсов для обеспечения оптимальной окончательной последовательности. Наш подход предполагает разделение задачи планирования ресурсов на два этапа:

  • — на первом этапе проводится изучение логического поведения, направленное на обобщение всех возможных последовательностей в системе уравнений и неравенств, чьи переменные — это начальные маркировки мест;
  • — на втором этапе проводится оценка длительности цикла полученных решений, при помощи которых можно получить оптимальное решение для фиксированного интервала поиска.

В данной главе мы предлагаем новый подход, выраженный следующим:

  • — количество операций на определенном интервале известно и детерминировано и распределяется только между машинами, выполняющими несколько задач, вызывающих структурные конфликты.
  • — количество назначений для каждого машинного цикла определяется в более ранней фазе потока оптимизации [KOR 98; САМ 97; OHL 95]. Полученная ранняя модель фазы достижимости является сетью Петри определенного типа, поскольку она относительно близка к модели графа проанализированных событий. Анализ чаще всего возникает при рассмотрении большого количества компонентов или частей, а также при проведении сложных сборочных процессов. Кроме этого, единственная отличная остаточная нелинейность возникает в результате возникновения конфликтов доступа к ресурсам, распределение которых определяется не на данном уровне исследования.

В качестве примера рассмотрим случай продуктивного интервала, представленного на рисунке 5.10. Цепь производства позволяет изготавливать продукт, полученный при помощи сборки трех типов компонентов: двух компонентов типа А1, одного компонента каждого типа А2 и Ау

Первый компонент А] получают путем обработки части, расположенной в р 1? используя копию ресурса г, который символизирует срабатывание перехода tv Производство второго компонента выполняется на переходе t2 при помощи двух копий ресурса г. Последний компонент обрабатывается тремя ресурсами типа г и выражается активированием перехода /3. Сборка двух частей Д,, частей А2 и А3 затем выполняется на переходе /4. Наконец, результат сборки контролируется и выражается срабатыванием перехода /5. После этого мы получаем конечный продукт. Фактически модель подается обратно для принятия во внимание циклической продуктивности системы.

Данный пример иллюстрирует практический интерес к максимально возможному уравниванию дуг с целью описания ряда компонентов,

Пример

Рисунок 5.10. Пример

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

Мы будем решать задачу преобразования совместного использования нескольких ресурсов между различными задачами, в которых дуги уже уравновешены, а срабатывание переходов не обязательно объединенное. Данная проблема уже рассматривалась в рамках более ограниченных предположений: совместное использование ресурса без уравновешивания и объединения срабатывания переходов в конфликте обсуждалось в работе [BEN 99], совместное использование нескольких идентичных ресурсов рассматривается в работе [SIL 02], а совместное использование ресурсов с несколькими срабатываниями переходов в конфликте изучалось в работе 1ТРО 02Ь]. В данной главе мы рассмотрим случай добавления уравнителей на дуги, связанных с совместным использованием ресурсов.

Преимущество нашего подхода заключается в возможном расширении области применения формальных математических трактовок (макс., +) и (мин., +), разработанных для оценки эффективности простых графов событий [СОН 89; LAH 99; GAU 95]. В связи с этим выполненное преобразование позволит получить простой или, возможно, уравновешенный граф событий. В последнем случае метод линеаризации описан в работах [JUA 01; TRO 02а]. Он будет использовать диод (мин., +) с целью изучения поведения логической модели путем распространения возможной начальной маркировки.

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

  • — изучение логического поведения: для программирования ресурсов;
  • — изучение временного поведения: для оценки длительности цикла, связанного с каждым графом.

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

В данном случае мы предлагаем план, состоящий из трех этапов. В качестве первого этапа мы предлагаем построение уравновешенного графа событий, полученного из исходной сети Петри. Цель этапа заключается в том, чтобы сделать сеть детерминированной и обладающей свойствами, необходимыми для осуществления алгебраического подхода. На втором этапе мы предлагаем провести внедрение системы уравнений и неравенств, которая оправдывает эквивалентность между всеми возможными последовательностями ресурсов и всех видов поведения, генерируемых в результате системных решений. Третий этап посвящен применению данного метода преобразования.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >