2.4.2. Автомат Мили.

Автомат Мили отличается тем, что его функции выхода в момент t зависят не только от состояния автомата, но и от набора значений входных осведомительных сигналов:

Построим граф автомата Мили (рис.

Рис. 2.10. Граф автомата Мили

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

Описание выходных сигналов автомата Мили:

Автомат Мили, построенный по микропрограмме управления, имеет число состояний, как правило, меньшее числа состояний эквивалентного ему автомата Мура. Однако у автомата Мили есть недостаток, препятствующий его использование в качестве УА. Этот недостаток связан с тем, что при смене сигналов на входе изменения на выходе сигналов могут произойти быстрее, чем произойдёт смена состояния автомата (эффект гонок). Недостаток устраняется введением элементов задержки.

При синтезе автоматов решаются задачи:

• оптимального кодирования, минимизирующего число состояний автомата;

• перехода от недетерминированного автомата к детерминированному автомату.

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

2.5. Моделирование потоков работ методами линейного программирования

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

При поиске оптимального решения задачи линейного программирования достаточно ограничиться перебором базисных допустимых решений. Число базисных решений может быть достаточно велико для их перечисления прямым перебором за реальное время. Для решения ряда прикладных задач линейного программирования разработаны специальные решения, учитывающие особенности постановок задач данного типа и указанное свойство множества допустимых решений [10,22,23].

2.5.1.