Планирование работ на основе трехфазной модели ВС.

Планирование на основе двухфазной модели ВС.

Двухфазная модель выполнения работ в ВС представлена на рис.1. Первая фаза — фаза ввода — представлена устройством ввода ВУ и каналом К. Вторая фаза — фаза обработки — реализуется системой «процессор ЦП — оперативная память ОП. Продолжительность выполнения работ J₁…J_M впервой фазе равна τ₁₁, .., τ_Μ1и во второй фазе — τ₁₂, .., τ_Μ2соответственно.

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

Алгоритм оптимального планирования состоит из следующих этапов:

1. Отметим начало очереди работ позицией а =1 и конец очере­ди — позицией b=М.

2. В матрице трудоемкости находится минимальное значение

t = min τ_ij.

3. Выделяются работы, для которых τ_ij = τ (ί =a, ..., ω; j = 1,2).

4. Если выделена единственная работа J_а,то при τ_α1 = τ она

ставится в начало очереди, определяемое позицией а, а при τ_α2 = τ — в конец очереди в позицию b. Затем выполняется п. 7.

5. Если выделено несколько работ J_а, .., ,J_ω, то они разде­ляются на две группы:

1) с одинаковыми значениями τ_α1, ..., τ_ω1, равными τ;

2) с одинаковыми значениями т_a2, ..., τ_ω2, равными τ.

6. Работы из первой группы заносятся в начало очереди в позиции а, а+1,... в порядке увеличения значений τ_α2,..., τ_ω2. Работы из второй группы заносятся в конец очереди в позиции b, b — 1, ... в порядке увеличения значений τ_α1, ..., τ_ω1.

7. После включения работы в очередь (в позицию а или b) работа вычеркивается из матрицы трудоемкости и переменной а или b присваивается новое значение a: = a+1 или b:= b — 1;

8. Процесс продолжается от п. 2 до распределения всех работ по позициям очереди.

Трехфаз­ная модель выполнения работ в ВС изображена на рис. 5.15. Здесь фаза ввода реализуется устройством ввода ВУ_г и каналом К_х. Обработка выполняется системой «процессор Пр — оперативная память 0/7» и вывод — каналом К₂ и устройством ВУ₂. Работа ^_^, г==1; ..., Μ выполняется на первой фазе за время Тл, на второй фазе — за время τ_ί2 и на треть- , ей фазе — за время τ_ί3- . Допу- '024 скается одновременное выполне­ние не более трех работ, одна из которых находится в фазе ввода, другая — в фазе обра­ботки и третья — в фазе выво- ® 0 2 4 да. Как и ранее, исходной для ' ' планирования является матрица трудоемкости (5.1), содержащая для такой модели системы три столбца. С. Джонсон показал, что при выполнении хотя бы одного из следующих ограниче­ний:

т1п(т_[.₁)>тах(т_/2)

гтп(Т|з)>тах(Т/_а)

Рис.2.5- Трехфазная модель выпол­нения работ

Алгоритм оптимального плани­рования работ в трехфазной модели сводится к вышерассмотренному алгоритму плани­рования на основе двухфазной модели.

В этом случае трехстолбцовая матрица трудоемкостей преобра­зуется в двухстолбцовую матрицу путем попарного сложения эле­ментов первого и второго столбцов, а также элементов второго и третьего столбцов. Элементы г>_г1 и Φ_ί2 новой матрицы определяются следующим образом: г)_г1=т_г1-)-т_г2; #_г2—%+% Для всех ί= 1, ..., Μ. К полученной таким образом матрице применяется ранее рассмотрен­ный алгоритм планирования работ.