Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 3

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

Текст из файла (страница 3)

Если работысвязаны отношением Ti  Tj ,то работа Ti должна быть завершена раньше,чем начнется выполнение работы Tj.[τji] – матрица времен выполнения работ на процессорах, элемент которой τjiзадает время выполнения работы j на процессоре i;R={R1(Tj),…, Rs(Tj)} – набор, i-ая компонента которого задает количестворесурса типа Ri необходимое для выполнения задания Tj.Расписание может задаваться одним из трех способов:Временная диаграмма – для каждой работы задано время началавыполнения s’(Tj) и процессор на котором она выполняется.Привязка работ к процессорам и порядковый номер выполнения задания напроцессоре. Работа не может начаться выполняться, если не выполнены всеработы на процессоре с меньшими порядковыми номерами, завершены всеее предшественники, выполняющиеся на других процессорах и достаточноколичества требуемых дополнительных типов ресурсов. Привязка - всюдуопределенная на множестве работ функция, которая задает распределениеработ по процессорам.

Порядок задает ограничения на последовательностьвыполненияработиявляетсяотношениемчастичногопорядка,удовлетворяющим условиям ацикличности и транзитивности. Отношениепорядка на множестве, работ распределенных на один и тот же процессор,является отношением полного порядка.8Привязка работ к процессорам и приоритет работы. Работа может начатьвыполняться, если завершены все ее предшественники (работа готова квыполнению), в очереди готовых работ нет работ с большим приоритетом,на процессоре не выполняется никакая другая работа и достаточноколичества требуемых дополнительных типов ресурсов. Частным случаемявляются списочные расписания: существует единый упорядоченныйсписок работ и не задается привязка работ к процессорам.Задачи построения расписаний можно разделить на классы в соответствии соследующими характеристиками:1.Тип процессоров.2.Тип отношения частичного порядка на множестве работ.3.Времена выполнения работ.4.Способ задания директивных интервалов работ.5.Модель вычислений.6.Мера оценки эффективности расписания.Тип процессоров.

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

Наиболее часторассматриваются следующие отношения порядка:пустое,лес,произвольное.Времена выполнения работ могут быть:равными,различными,равными 1 или 2.Директивные интервалы работ могут быть:9f- общий директивный интервал для всей системы работ,[sj,fj) – индивидуальные директивные интервалы для каждой работы,[0,fj) – индивидуальные директивные интервалы с общей левой границей,rj – требуемая частота выполнения работы.Модельвычисленийхарактеризуетсядисциплинойобслуживанияработиучитываемыми временными задержками при вычислении времени выполнениярасписания.

Дисциплина обслуживания работ может быть:без прерываний – работа не может быть прервана до полного завершения,с прерываниями – разрешается прерывать работу и запускать ее впоследующем. При этом предполагается, что общее время требуемое длявыполнения работы остается неизменным.Временные задержки:учитываются временные задержки начала выполнения работ, определяемыелишь отношением частичного порядка в расписании и ограниченнымчислом процессоров;учитываются временные задержки начала выполнения работ, связанные сполучением доступа к разделяемым ресурсам (каналам обмена, общейпамяти….) и работой системного программного обеспечения.

В этом случаеполучение точного значения времени выполнения расписания возможнолишь с использованием имитационных моделей.Мера оценки эффективности расписания:время выполнения расписания,число используемых процессоров для выполнения множества работ за времяне превышающее заданные директивный срок,максимальное число совместимых работ (для задач в которых задаютсяиндивидуальные директивные сроки работ),критерии, основанные на использовании функций штрафа за нарушениедирективных сроков работ (используются при построении расписаний длясистем мягкого реального времени).В таблице приведены известные из работ [1-17] функции штрафа.

Функции штрафаопределены для работ i= <s'i, si, fi, ti> и имеют вид Fi = Fi(s', s, f, t), гдеs' – время старта работы;[s, f) – директивный интервал работы;t – время выполнения работы.В таблице:10f' = s' + t – время завершения работы; c1, c2 - константы, не зависящие от конкретной работы.Название штрафной функцииМатематическое представление:Fi =Отставание [1,2,3,11,13,14,15]max{0, f'i – fi}Смещение [1,2,4,5,6,11,13,14]f'i – fiЗавершение [2, 4,5,6,7,14]f'iДискретное запаздывание[1,4,15]1, если f'i > fi, иначе 0Отклонение [5]|fi' – fi|Опережение [5,13]max{0, fi – fi'}Непопадание [7]0, если (si', fi')  (si, fi), иначе 1Простых элементов [8,9]U * (U + 1) / 2, гдеU = max(fi' – fi,0) + max(si' – si,0)Красильщика [11]fi' + constiДлительность [13]fi' – si'«Жесткие сроки» [12]-c1, если fi' ≤ fi, иначе c2(fi'/fi – 1)Крепкие сроки [12]-c1, если fi' ≤ fi, иначе c2Мягкие сроки [12]-c1, если fi' ≤ fi, иначе (c2-c1)fi'/fi – c2Неубывающая кусочнонеперывная (общий вид) [15]0, если fi' ≤ fi, иначе E = φ, где φ > 0, φ –неубывающая кусочно-непрерывная функцияСтупенчатая [15]0, если fi' ≤ fi, иначе ai, где ai > 0, ai – некотораяконстанта для i-й работыДлительность прохождения(Flow time) [16, 17]f'i – siФункция специального вида (1)[1]φ(fi') + αi, где φ(fi') не убывает в полуинтрвале(0, f], α1 ≥ α2 ≥ … ≥ αnФункция специального вида (2)[1]αi * φ(fi'), где φ(fi') не убывает в полуинтрвале(0, f], α1 ≥ α2 ≥ … ≥ αnФункция специального вида (3)[1]φ(fi' + αi), где φ(fi') не убывает в полуинтрвале(0, f], α1 ≥ α2 ≥ … ≥ αnФункция специального вида (4)[1]aiui(fi'), ui(fi') = 0, если fi' ≤ f, иначе ui(fi') = 1; ai>011Название штрафной функцииМатематическое представление:Fi =Произвольная неубывающая [1]Произвольная неубывающая функция В таблице приведены критерии оценки качества расписаний построенные на основефункций штрафа.Название критерияМатематическое представлениеМаксимум [1,4,5,6,11,13,14,15]max Fi, i = 1..nВзвешенный максимум [2,14]max wiFi, I = 1..nСумма [9,10,13,14,15,16]nFii=1Взвешенная сумма [8,10,11]nw Fiii=1Средняя сумма [13]1 n Fin i=1Взвешенная средняя сумма [14]1 n wi Fin i=11.

Танаев В.С., Гордон В.С., Шафранский Я.М.. Теория расписаний. Одностадийные системы. Москва"Наука", главная редакция физико-математической литературы 1984.2. Щепин. Е.В. Теория расписаний // Школа Яндекса по анализу данных, 2007(http://www.mi.ras.ru/~scepin/1-sched.pdf)3. Лазарев А.А., Гафаров Е.Ф. Теория расписаний. Минимизация суммарного запаздывания для одногоприбора // Вычислительный центр им. А.А. Дородницына Российской академии наук, 2006 [PDF](http://aspirantura.mipt.ru/zastchita/avtoreferats/fupm/f_3hygnb)4. Кононов А.В. Задачи теории расписаний на одной машине с длительностями работ,пропорциональными произвольной функции // Дискретный анализ и исследование операций.

Июль- сентябрь 1998. Серия 1. Том 5, № 3, c. 17-37.5. Алексеева Е.В. Теория принятия решений. Лекция 10 [PDF] (http://math.nsc.ru/LBRT/k5/lec10.pdf)6. Алексеева Е.В. Теория принятия решений. Лекция 11 [PDF] (http://math.nsc.ru/LBRT/k5/lec11.pdf)7. Сафонова Т.Е.. О минимизации числа элементов работ, не попавших в свои директивные интервалы[PDF] (http://www.mathnet.ru/php/getFT.phtml?jrnid=znsl&paperid=3165&what=fullt).128.

Сафонова Т.Е. Реализация алгоритма построения оптимального расписания с началом в заданноминтервале [PDF] (http://www.mathnet.ru/php/getFT.phtml?jrnid=znsl&paperid=3166&what=fullt)9. Шахабзян. К.В. Упорядочение структурного множества работ, минимизирующее суммарный штраф[PDF] (http://www.mathnet.ru/php/getFT.phtml?jrnid=znsl&paperid=3169&what=fullt)10. Шахабзян. К.В. О задачах теории расписаний типа n|1|| ci(t) [PDF](http://www.mathnet.ru/php/getFT.phtml?jrnid=znsl&paperid=3328&what=fullt)11.

Лукьянова А.П., Лесин В.М. Теория расписаний [ZIP] (http://rain.ifmo.ru/cat/data/vis/scheduletheory/schedule-theory-2003/shedule.zip)12. Павлова Е. Управление транзакциями в СУБД реального времени [HTML](http://meta.math.spbu.ru/~katya/publications/programmirovanie2000)13. Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Методы исследования операций при принятиирешений. // Тамбов.

Издательство ТГТУ. 2004. [PDF](http://window.edu.ru/window_catalog/files/r37969/tstu2005-016.pdf)14. Коффман Э.Г. Теория расписаний и вычислительные машины. Москва "Наука", главная редакцияфизико-математической литературы 1984.15.

Танаев В.С., Шкурба В.В. Введение в теорию расисаний. Издательство "Наука", главная редакцияфизико-математической литературы. Москва. 1975.16. A.W. Krings. Survivable Systems and Networks, Lecture 24 2001 CS404/504. [PDF](http://www2.cs.uidaho.edu/~krings/CS448/Notes.2004/2004-24-ssn.pdf)17. Nikhil Bansal. Algorithms for Flow Time Scheduling. School of Computer Science, Computer ScienceDepartment, Carnegie Mellon University, Pittsburgh, PA 15213, December 2003 [PDF](http://www.research.ibm.com/people/n/nikhil/papers/thesis.pdf)1.4 Задачи, возникающие при проектировании вычислительных системреального времени1.4.1.

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

Характеристики

Список файлов лекций