Комбинаторные методы решения задач теории расписаний



Министерство Образования Украины

Севастопольский Государственный Технический Университет

 

 

Департамент КиВТ

 

 

Методические указания

по курсовому проектированию по дисциплине

«Вычислительный практикум»

для студентов дневной и заочной формы обучения специальности 7.091501

 

Севастополь 1997


Цель методических указаний - обеспечить эффективную работу студентов при выполнении курсового проекта по дисциплине «Вычислительный практикум».

Методические указания утверждены на заседании кафедры кибернетики и вычислительной техники «____»                           199__ г. Протокол N___

Рецензент:                                                                                             

Методические указания составили: профессор Скатков А.В., ассистент Сергеев Г.Г.


Введение

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

       В задачи курсовой работы по дисциплине «Вычислительный практикум» входит:

· развитие у студентов навыка научно-исследовательской работы в области разработки сложных программных систем;

· умение составлять многошаговые итерационные алгоритмы;

· навык анализа научно-технической литературы в области программирования и прикладной математики;

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

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

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

      
1. Основные этапы выполнения курсовой работы

 

Подготовительный этап (1-3 неделя). Уточнение постановки задачи. Анализ научно-технической литературы с целью обоснования выбора метода решения. Разработка спецификации на программную систему.

Проектный этап.(4-8 недели). На этом этапе рассматриваются различные пути реализации поставленной задачи, предлагаются критерии оценки эффективности алгоритма и оценка с их помощью различных вариантов решения. На этом этапе разрабатывается алгоритмическое и программное обеспечение моделирования.

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

Оформительский этап (13-14 недели). На данном этапе выполняется оформление пояснительной записки в соответствии с требованиями к оформлению технической документации, регламентируемыми стандартом Украины.

Заключительный этап (15-16 недели). На этом этапе проводится защита курсовых работ. Студент обязан представить окончательно оформленную пояснительную записку к курсовой работе не позже чем за два дня до защиты. На заключительном этапе проводится подготовка доклада и защита курсовой работы перед комиссией. Доклад должен сопровождаться демонстрацией работы программы. В докладе в сжатой форме следует представить поставленную задачу, основное содержание курсовой работы, краткий анализ состояния изучаемого вопроса, обоснование и принятие решения, анализ полученных результатов.


    2. Методы решения задачи планирования работы вычислительных систем.

 

2.1 Задача планирования работы вычислительных систем. В настоящем разделе рассматриваются основные методы решения задач, связанных с планированием работы вычислительных систем. Круг вопросов, связанных с построением наилучших планов работ (расписаний), особенно с разработкой математических методов получения решений с использованием соответствующих моделей, изучается в рамках теории расписаний [1]. Наиболее известной в теории расписаний задачей является задача построения оптимального (в том или ином смысле) расписания процесса решения задач (выполнения программ) некоторой совокупностью «машин». При решении данной задачи в рассматриваемой системе необходимо закрепить решаемые задачи за ЭВМ, согласовать длительности решения задач и установить порядок их выполнения во времени.

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

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

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

На практике предложены и используются различные способы представления расписаний. Наиболее наглядны из них графические представления - графики Ганта, ленточные графики, планировочные графики, циклограммы и т.п. Во многих случаях общепринятым является табличное представление, в достаточной степени наглядное и не требующее дополнительных пояснений. Для представления в ЭВМ широко используется специфическая форма представления расписаний посредством задания вектор-функции времени. Компоненты вектор-функции s(t)={s1(t),s2(t),...sn(t)} описывают загрузку обслуживающих приборов 1,2,3,...,n во времени. Если si(t’)=0, то в момент времени t=t’ обслуживающий прибор свободен. Если si(t’)=k, то в момент времени t=t’ прибор обслуживает требование с номером k. Выбор той или иной формы представления расписаний определяется конкретными условиями, в которых возникает необходимость в их составлении и рассмотрении.

 

Комбинаторные методы решения задач теории расписаний

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

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

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

Понятие перестановки хорошо рассматривается в [1] — расположение элементов некоторого множества в любом порядке (без повторений) представляет собой перестановку элементов этого множества. Перестановка обычно представляется последовательностью элементов (чисел) из N == {1,2,...,n}. Символической записью этой конструкции является p = (i1,i2,i3,..., in).

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

Пусть Р — некоторое множество (не обязательно всех) перестановок p=(i1, i2,i3 . . ., in) элементов множества N = {1, 2, ..., n}.

Под st-окрестностью k-то по порядку элемента в перестановке p (обозначение Qst (p, k)) будем понимать упорядоченный набор <Q,ss,st >, где ss== (imax(1,k-s+i), ... , ik-1,ik) и st== (ik+1,i k+2 ... , imin(n,k+\t))— перестановки длины min(k, s) и min (n-k,t) соответственно и Q— множество (неупорядоченное) элементов { i1, i2,i3 . . ., ik-s }. Если k £ s, то Q = Æ. Предполагается, что s³O и t³0.

Требуется найти перестановку p*Î Р, которой соответствует наименьшее значение функции F (p, n), заданной на Р рекуррентным соотношением

F (p, k) = Ф [F(p, k - 1), Qst (p, k)]

где F (p, 0)— известная не зависящая от p величина, а функция, стоящая в правой части этого соотношения, неубывающая по F (p, k—1).

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

1) Инициализация. Выбор начальной расстановки p. Определение функции F(p,n). Запомнить расстановку p* как оптимальную.

2) Пока существуют нерассмотренные варианты перестановки выполнять п.3-4.

3) Генерировать следующую расстановку p*. Вычислить F*(p*,n).

4) Если F*(p*,n)> F(p,n) запомнить расстановку p* как оптимальную.

       Задача о следующей перестановке (алгоритм Дейкстры) рассмотрена в [3].

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

с_ниж=1 и с_вер=n

для некоторого постоянного значения n(n>1). Кроме того известно, что упорядоченная последовательность значений с(1),с(2),...,с(n) является некоторой перестановкой значений от 1 до n, но не последней в алфавитном порядке: n, n-1, ...1. Внутренний блок должен преобразовать последовательность c(l), с (2), ..., с(n) в последовательность, являющуюся ее посредственным следующим по алфавиту преемником. Например, при n=9 последовательность

1 4 6 2 9 5 8 7 3

должна быть преобразована в последовательность

1 4 6 2 9 7 3 5 8

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

       с (k) сохраняется для 1 £k < i

       с (k) изменяется для k=i

       Значение i определяется как максимальное значение i(<n), такое, что c(i)<c(i+1).

После того как i найдено, необходимо отыскать в «хвосте», т. е. среди значений с(j) при i+l£j£n, новое значение с(i). Т.е. требуется найти такое значение j в интервале i+l£j£n, что с(j) есть наименьшее значение, удовлетворяющее условию

c(j)>c(i)

 После того как j найдено, с(i) должно получить свое новое значение, для чего используется операция «с: переставить(i, j)». Дополнительным преимуществом этой операции является то, что после ее выполнения вся последовательность продолжает оставаться перестановкой чисел от 1 до n; заключает всю цепочку действий переупорядочивание значений в хвосте последовательности, чтобы монотонно возрастали. Общая структура программы представляется в виде:

*  определение i;

*  определение j;

*  c: переставить (i, j);

* сортировка хвоста

Операция «с: переставить (i, j)» не нарушает монотонности значений функции в хвосте, и поэтому «сортировка хвоста» сводится к расположению значений в обратном порядке.

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

Переменные:

c : вектор;

i,j : целое ;

Начало:

       i := n -1;

       Пока (c[i]>=c[i+1]) i:=i-1;

       j:=n;

       Пока (c[j]<=c[i]) j:=j-1;

       c :переставить( i , j );

       i:=i+1; j:=n;

       Пока (i<j)

                   н.ц .

                              c :переставить( i , j );

                              i:=i+1;

                              j:=j-1;

                   к.ц.

Конец.

Методы планирования работы систем с одним обслуживающим прибором

Пусть конечный поток требований N={1,2,3,...,n}, поступающих на обслуживание в заданные моменты времени, обслуживается одним прибором. В каждый момент времени прибор обслуживает не более одного требования. Требование k,  поступает на обслуживание в момент времени dk>=0 и для обслуживания требует tk единиц времени. Порядок обслуживания может быть произвольным, либо регламентироваться заданными отношениями частичного порядка. При некоторых постановках задачи могут допускаться прерывания в обслуживании каждого отдельного требования. Необходимо так организовать процесс обслуживания, чтобы он в том или ином смысле был наилучшим.

Процесс обслуживания может быть описан заданием кусочно-постоянной, непрерывной слева функции s =s (t), принимающей при 0£ t£¥ одно из значений 0, 1, 2,..., n. Если s(t)=k¹0, то в момент времени t прибор обслуживает требование k; если s (t) = 0, то в момент времени t ни одно из требований не обслуживается. Эта функция называется расписанием.

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

· условие полноты: для любого 1 £k £n  существует 0 < t < ¥, такое, что s (t)=k; суммарная длина промежутков, на которых s (t) = k, равна tk;

· условие готовности к обслуживанию: s(t) ¹k для всех t<dk;

· условие упорядоченности: если по условию задачи требование i необходимо обслужить раньше требования j и s (t') == i, то s (t) ¹ j для всех t < t';

· условие непрерывности: если по условию задачи прерывания в обслуживании требований не допускаются и s {t') == s (t") = k ¹ 0, то s (t) == k для всех t' < t < t".

Расписания s =s (t), которые удовлетворяют перечисленным условиям, называются допустимыми.

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

При рассмотрении задач такого рода под допустимым расписанием будем понимать такое расписание s=s(t), которое удовлетворяет всем требованиям, вытекающим из постановки конкретно рассматриваемой задачи.

Каждому допустимому расписанию s = s (t) соответствует вектор  времен завершения обслуживания требований при этом расписании. Значение ,  , таковы что и s(t)¹k для всех t> .

Предполагается, что качество расписания s определяется вектором , т.е. каждому расписанию s ставится в соответствие значение некоторой скалярной функции F( ) вектора , определяемого расписанием s. Наиболее распространенным является следующий способ задания F( ). Для каждого требования  задается неубывающая кусочно-непрерывная функция jk(x), выражающая в количественном отношении «штраф», который необходимо «заплатить», если обслуживание этого требования завершится в момент времени х. В качестве F( ) выбирается одна из функций  или . Функции jk(x) называются функциями штрафа. Расписание, которое удовлетворяет всем условиям рассматриваемой задачи, называется оптимальным, если ему соответствует наименьшее значение F( ).

Если прерывания обслуживания каждого отдельного требования запрещены, то активное расписание однозначно определяется заданием последовательности p=(i1, i2,i3 . . ., in), в которой эти требования обслуживаются. Таким образом, решение задачи может быть получено в результате рассмотрения конечного числа расписаний, определяемых возможными последовательностями обслуживания требований. Такие расписания называются перестановочными. Если множество N не упорядочено, то число перестановочных расписаний n!.

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

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

Пусть требования i и j обслуживаются непосред­ственно друг за другом и их обслуживание начинается в момент времени t ³ 0. Если при этом первым обслужи­вается требование i, то суммарный штраф за обслужива­ние этих требований

Если первым обслуживается требование j, то суммарный штраф за обслуживание этих двух требований

Определим

Величина Rij ( t ) показывает, насколько изменяется суммарный штраф при переходе от последовательности, при которой требование i начинало обслуживаться в мо­мент времени t непосредственно перед требованием j, к последовательности, отличающейся от исходной транс­позицией элементов i и j.

Если Rij ( t )<0, то при решении вопроса, какое именно из двух последовательно обслуживаемых требова­ний i и j необходимо начать обслуживать в момент вре­мени t, предпочтение следует отдать требованию i. Ана­логично, если Rij { t )>0, то первым в момент времени t следует обслуживать требование j. Наконец, если Rij { t )=0, то порядок обслуживания этих требований безразличен.

Поскольку функции ji(x) и jj(x) предполагаются кусочно-непрерывными в интервале (0, ), то этот интервал может быть разбит на конечное число интерва­лов, в каждом из которых величина Rij ( t ) положительна. отрицательна или равна нулю.

Интервал (q1, q2) называется интервалом очередности типа i ® j, если Rij ( t )<0 для всех tÎ(q1, q2). Eсли Rij ( t )>0 для всех tÎ(q1, q2) интервал (q1, q2) называется интервалом очередности типа j ® i. При Rij ( t )=0 для всех tÎ(q1, q2) порядок обслуживания требований безразличен.

Величина Rij ( t ) по определению зависит от значений t , ti , tj и функций штрафа ji(x) и jj(x). В каждом конкретном случае в результате несложных преобразований могут быть выделены интервалы очередности.

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

Директивным сроком называется момент времени Dk>0, к которому необходимо или, во всяком случае, желательно завершить обслуживание требования . В общем случае не удастся построить такого расписания, при котором обслуживание каждого требования k завершается не позднее заданного директивного срока Dk. Появляется объективная необходимость в нарушении от­дельных директивных сроков, что сопряжено с определенными потерями. Эти потери, как правило, зависят от того, какие именно требования и на сколько задерживаются с обслуживанием. Иными словами, каждому требованию  отнесена неубывающая кусочно-непрерывная функция штрафа jk(x)=0 при х £ Dk и jk(x)>0 при х > Dk. Требуется определить расписание обслужива­ния п требований, при котором суммарный штраф наи­меньший.

       В [1] предлагается алгоритм конструирования оптимальной относительно FS(p) последовательности обслуживания требований, когда jk(x)=max(x-Dk,0), :

Упорядочим множество N всех требований по не­убыванию значений Dk. Обозначим полученную последовательность pD=(i1, i2,i3 . . ., in). Если при этом все требования обслуживаются в срок, то pD - оптимальная последовательность.

Упорядочим множество N всех требований по не­убыванию значений tk. Обозначим полученную последо­вательность pt=(j1, j2,j3 . . .,jn).Если при этом Dik < Dij . или , то pt - оптимальная последовательность.

Из множества N выберем требование Ln с tLn =  max (tk). Если Dk<max(tLn,DLn) для всех kÎN, то в оптимальной последовательности это требование мож­но обслуживать последним .

Среди требований множества Np выберем требова­ние Ln-р с DLn-р= mах Dk. Если tLn-р+ Dk>Stl  для всех kÎNp, то в оптимальной последовательности требования множества Np будут обслуживаться первыми в порядке неубывания значений Dk. В про­тивном случае обозначим Np через М.

Разобьем множество М на два подмножества М1 и М2 по следующему принципу: если для jÎM существует iÎM такое, что интервал (q1=0, q2=Stk) является интервалом очередности типа i ® j , to jÎM2, остальные требования принадле­жат множеству М1. Иными словами, множество M1 со­стоит из конкурентноспособных претендентов на первооче­редное обслуживание в оптимальной последовательности среди всех требований множества М.

Выберем произвольное требование L1ÎM1 и пред­положим, что в оптимальной последовательности это тре­бование обслуживается первым среди всех требований множества М. Уменьшим значение Dk для всех kÎM, k¹L1 на величину tL1 и перейдем к выполнению пп. 3—4, полагая N = М \ L1. Таким образом, в результате при­нятия гипотезы, что первым в оптимальной последователь­ности обслуживается требование L1, получаем множество М (L1)ÌM все еще неупорядоченных требований. Аналогичные рассуждения проводим относительно ос­тальных требований множества М1.

 Перейдем к последовательному рассмотрению ситуа­ций вида: требование L1 обслуживается первым и М (L1) — множество все еще неупорядоченных требований. Повто­ряем пп. 5, 6, полагая М =- М (L1) и принимая в качестве Dk значения исходных директивных сроков, уменьшенных на величину tL1. Затем перейдем к последовательному рассмотрению ситуаций вида: требования L1, L2, обслуживаются первыми в последовательности (L1, L2) и M(L1, L2) - множество все еще неупорядоченных требований и т.д.

       В результате получаем конечное множество последовательностей, среди которых выбираем последовательность p*, которой соответствует наименьшее значение FS(p). Эта последовательность является искомой.

Методы планирования работы систем с параллельными обслуживающими приборами

Пусть конечный поток требований N={1,2,3,...,n}, поступающих на обслуживание в заданные моменты времени, обслуживается M идентичными приборами. В каждый момент времени прибор обслуживает не более одного требования. Каждое требование может обслуживаться любым прибором. Требование k,  поступает на обслуживание в момент времени dk>=0 и для обслуживания требует tk единиц времени. При некоторых постановках задачи могут допускаться прерывания в обслуживании каждого отдельного требования. Необходимо так организовать процесс обслуживания, чтобы он в том или ином смысле был наилучшим.

Расписанием s =s (t)={s1(t),s2(t),...,sM(t)} называется совокупность M кусочно-постоянных, непрерывных слева функций sL=sL(t), каждая из которых задана на промежутке 0£ t<¥ и принимает значения 0, 1, 2,..., n, причем если sL(t)=k¹0 при некотором t=t’, то sH(t’)¹k для любых 1£L¹H£M. Выражение sL(t)=k¹0 означает, что в момент времени t=t’ прибор L обслуживает требование k. Ecли sL (t’) = 0, то в момент времени t=t’ прибор L свободен.

Расписание должно удовлетворять:

· условию полноты: суммарная длина промежутков, на которых функции sL(t) принимают значения sL(t)¹0, равна tk.

· условие готовности к обслуживанию: sL(t) ¹k для всех t<dk;

Будем говорить, что расписание s=s(t) допускает прерывания в процессе обслуживания требований, если существуют такие 1£ k£n, 1£L¹H£M и 0£t’<t<t’’<¥, что выполняется хотя бы одно из условий:

1)  sL(t’)= sL(t’’)=k, но sL(t) ¹k

2)  sL(t’)= sH(t’’)=k

       Содержательно, процесс обслуживания требований без прерываний удовлетворяет следующему условию. Каждое требование обслуживается только одним прибором. Если процесс некоторого требования k начинается в момент времени tk, то оно протекает непрерывно и завершается в момент времени tk+tk.

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

Каждому расписанию s соответствует вектор  времен завершения обслуживания требований при этом расписании. Значение ,  - наибольшее значение t, при котором .

       Качество расписания s характеризуется значением действительной кусочно-непрерывной монотонно возрастающей функции F( )=F(x1,x2,...,xn) при x= .

       Алгоритм построения расписаний      для систем с параллельными обслуживающими приборами аналогичен методу последовательного конструирования для систем с одним обслуживающим прибором. При этом следует учесть, что требование k может быть выполнено любым прибором L, если он свободен в данный момент времени.

 

 

Методы планирования работы систем с последовательными приборами. Одинаковые маршруты.

       Пусть конечный поток требований N={1,2,3,...,n}, поступающих на обслуживание, обслуживается M последовательными приборами. В каждый момент времени прибор обслуживает не более одного требования. Все требования поступают на обслуживание в момент времени d=0. Пусть ti1 - время обработки требования с номером i (i=1,2,3,...,m) первым обслуживающим прибором, ti2-вторым. Определить порядок обслуживания требований, при котором суммарная длительность их обработки будет минимальной.

       Рассмотрим частный случай поставленной задачи, когда M=2. Поскольку первый прибор может выполнять обслуживание без задержки требований, оптимизация заключается в оптимизации времени простоя второго обслуживающего прибора. Рассмотрев зависимость простоя второго прибора от порядка следования требований С.М. Джонсон вывел простой алгоритм нахождения оптимальной последовательности:

1)  Среди всех требований из N найти требования с наименьшим значением tij.

2)  Если i=1 то данное требование должно быть обслужено первым.

3)  Если i=2 то данное требование должно быть обслужено последним.

4)  Исключить требование i из списка требований.

5)  Повторять п. 1-4 до тех пор, пока имеется хотя бы одно требование, пока множество необслуженных требований не пусто.

Если М=3, то при решении рекомендуется использовать следующий эвристический алгоритм:

1)  Проверить выполнение следующих ограничений:

 

            min (ti1) > mах (ti2)           (1)

               i

            min (ti3) > mах (ti2)           (2)

               j

2)  Если одно из ограничений (1) или (2) выполняется, то можно построить оптимальное расписание. Для этого трехстолбцовая матрица трудоемкости преобразуется в двухстолбцовую путем попарного сложения элементов первого и второго столбцов, а также элементов второго и третьего столбцов. Элементы Vi1 и Vi2 новой матрицы определяется следующим образом: Vi1+i2; Vi2= i2+i3 для всех I=1,....,М. К полученной таким образом матрице применяется алгоритм Джонсона.

3)   Если ни одно из ограничений (1) и (2) не выполняется, то следует применить следующий эвристический алгоритм, позволяющий получить достаточно хорошее, но все-таки не оптимальное расписание. Он сводится к следующим действиям:

3.1)Выделить номер фазы "К" с наибольшей суммарной продолжительностью заданий, т.е. найти mах(t)

3.2) Если К=1, то требования следует обслуживать в порядке убывания величины (ti2+ti3).

3.3) Если К=3, то требования следует обслуживать в порядке возрастания величин (ti1+ti2).

3.4)  Если К=2, то следует исключить второй столбец и задания упорядочить на основе алгоритма С.Джонсона для двухфазной модели.

 

Методы планирования работы систем с последовательными приборами. Различные маршруты.

       Пусть имеется n требований и M обслуживающих приборов. Каждое требование обслуживается приборами в заданной специфической для него последовательности. Все требования поступают на обслуживание в момент времени d=0. Процесс обслуживания требования k не может включать повторных обращений к одним и тем же приборам. Каждый прибор обслуживает одновременно не более одного требования. Известны времена обслуживания tij - время обработки требования с номером i (i=1,2,3,...,m) прибором j. Прерывания в обслуживании каждого отдельного требования отдельным прибором не допускаются. Требуется определить порядок обслуживания требований, при котором суммарная длительность их обработки будет минимальной.

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

Принцип планирования сводится к следующему. Из пакета требований J1,...,Jм планировщик выбирает некоторую совокупность заданий J2,...Jw, которые будут выполняться совместно на основе разделения ресурсов системы между ними. Совокупность требований J2,...,Jw, выполняемых совместно, называется смесью требований. Смесь не является неизменной во времени. Первоначально она компонуется в момент поступления требований в систему. Затем, когда требование Jj будет обслужено, смесь может быть пополнена одним из требований, находящихся в пакете. Процесс продолжается до тех пор, пока не будут обслужены все требования из пакета. Стремясь обеспечить максимальную загрузку устройств, необходимо включить в смесь такое задание, которое в наибольшей степени займет свободные ресурсы устройств.

Планирование заданий основывается на использовании матрицы трудоемкости, в которой N столбцов определяет потребности в усройствах, а (N+1) столбец - в памяти.

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

1)  Распределить задания по потокам. Задание Ji принадлежит потоку Рj тогда и только тогда, когда tij>tдля всех  и k=j.

2)  Составить начальную смесь. Из потоков Р1,...,РN выбираем по одному заданию.

3)   Скорректировать смесь.По окончании обработки одного из требований Jw освобождается выделенное ему устройство. На место этого задания включаем задание из того же потока. Затем выполняем действия, аналогичные рассмотренным в пункте 2.

4)   Повторить пункт 3 для полной обработки всех заданий пакета.


Дата добавления: 2018-10-27; просмотров: 820; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!