Методические указания по проведению лабораторных работ «Распределение ресурсов в сетевых канонических структурах» по курсу (стр. 1 из 3)
Нижегородский государственный университет
им. Н.И. Лобачевского
Факультет вычислительной математики и кибернетики
Кафедра информатики и автоматизации научных исследований
Методические указания по проведению лабораторных работ
«Распределение ресурсов в сетевых канонических структурах»
по курсу «Математические основы информатики»
специальность «Прикладная информатика»
Н.Новгород – 2001
УДК 519.8
Методические указания по проведению лабораторных работ «Распределение ресурсов в сетевых канонических структурах» по курсу «Математические основы информатики» для студентов факультета ВМК специальности «Прикладная информатика».
/Нижегородский государственный университет, 2001, 13 c.
В методических указаниях излагается материал по курсу «Математические основы информатики» к разделу «Дискретные оптимизационные модели». Дается содержательное описание объекта исследования, строится общая математическая модель, ставятся многокритериальные задачи принятия решений, проводится исследование математической модели, предлагаются алгоритмы решения поставленных оптимизационных задач. Приводится описание диалоговой программной системы «Распределение ресурсов в сетевых канонических структурах».
Методическое пособие подготовлено профессором М.Х. Прилуцким и аспирантом Е.А. Кумагиной.
Рецензент доцент, к.ф.-м.н. Таланов В.А.
Содержание
1. Содержательная постановка задачи....................................................................... 7
2. Математическая модель многоресурсного сетевого планирования................... 8
3. Исследование математической модели............................................................... 12
4. Постановка многокритериальных задач.............................................................. 14
5. Алгоритмы решения задач.................................................................................... 17
6. Диалоговая система планирования...................................................................... 20
7. Типовые сценарии принятия решений................................................................ 23
8. Пример.................................................................................................................... 25
9. Задания по лабораторной работе.......................................................................... 28
Литература..................................................................................................................... 29
1. Содержательная постановка задачи
Изготовление сложных изделий требует выполнения совокупности взаимозависимых работ, связи между которыми хорошо описываются с помощью канонических сетевых моделей – ориентированных взвешенных графов без петель и контуров, элементам которых поставлены в соответствие некоторые характеристики. При этом события (факт окончания или начала выполнения работ) соответствуют вершинам графа, а работы – дугам, ориентация которых соответствует технологии этого процесса.
Каноничность сетевой модели означает, что никакая работа не может начать выполняться до тех пор, пока не завершатся все ей предшествующие по технологии изготовления работы.
При описании предметной области мы будем пользоваться понятиями изделие – продукт трудовой деятельности, и работа – составная часть изделия. Принятие управленческих решений в дальнейшем мы будем отождествлять с распределением ресурсов, необходимых для выполнения работ.
Работы сетевых моделей мы будем характеризовать технологическими, организационными и ресурсными условиями.
К технологическим условиям относятся:
· условия взаимозависимости выполнения работ,
· условия, связанные с интенсивностями потребления работами ресурсов,
· условия, связанные с возможными длительностями выполнения работ.
К организационным условиям относятся:
· условия, связанные с моментами начала работ,
· условия, связанные с моментами окончания работ.
К ресурсным условиям относятся условия, связанные с расходованием ресурсов при выполнении работ.
Целью планирования является построение расписания выполнения заданного комплекса взаимозависимых работ таким образом, чтобы при заданных свойствах ресурсов и работ оптимизировать выбранную меру эффективности.
2. Математическая модель многоресурсного сетевого планирования
Исходные параметры математической модели
Пусть T={1,2,...,T0} – множество тактов планирования (период планирования).
P={1,2,…,k} – множество изделий.
Множество работ, составляющих изделие pÎP, обозначим J(p).
J=
={1,2,…,n} – множество всех работ, для удобства изложения будем считать, что работы имеют сквозную нумерацию по всем изделиям,Обозначим K(j) – множество работ, непосредственно предшествующих работе с номером j, jÎJ,
I={1,2,…,n} – множество различных ресурсов,
Обозначим Vit – количество ресурса i, которое в такт t поступит в систему, iÎI, tÎT.
Технологические параметры
rij – ресурсоемкость работы j по ресурсу i, iÎI, jÎJ. Это количество ресурсов необходимое для выполнения работы. Будем предполагать, что для выполнения работы требуется ресурс только одного вида.
mij, Mij – минимальная и максимальная интенсивности потребления работой j ресурса i, iÎI, jÎJ. Интенсивность выполнения работы - это количество ресурса, которое может потребить работа за один такт планирования.
t
, t 
– минимальная и максимальная длительности выполнения работы j, jÎJ. Длительность выполнения – это число тактов, в течении которых выполняется работа.Организационные параметры
qj– ранний срок возможного начала выполнения работы j, jÎJ.
Dj– директивный срок окончания выполнения работы j, jÎJD, где JD - множество работ, имеющих директивные сроки, JDÍ J.
Варьируемые параметры математической модели
x=(x1,...,xïJï) – вектор времен начала выполнения работ,
y=(y1,...,yïJï) – вектор времен окончания выполнения работ,
zijt– интенсивность потребления работой j ресурс i в такт t, iÎI, jÎJ, tÎT.
Ограничения математической модели
Технологические ограничения
Варьируемые параметры модели <xj, yj, zijt, iÎI, jÎJ, tÎT> определяют множество частично-целочисленных неотрицательных переменных:
(2.1)Взаимозависимость работ, определяющая каноничность сетевой модели, задается ограничениями:
(2.2)Ограничения на интенсивности потребления работами ресурсов и требования выполнения работ без перерывов:
(2.3)Ограничения на длительности выполнения работ:
(2.4)Полное использование необходимых ресурсов означает полное выполнение работы:
. (2.5)Организационные ограничения
Ограничения на сроки начала работ:
xj ³ qj, jÎJ. (2.6)
Ограничения на сроки окончания работ:
yj £ Dj, jÎJD. (2.7)
Ресурсные ограничения
Количество ресурса i, которое может быть использовано в такт t для изготовления изделий не превосходит количества ресурса, поступившего в систему:
. (2.8)Исходные параметры, варьируемые параметры и ограничения (2.1)-(2.8) представляют собой общую математическую модель процесса изготовления совокупности сложных изделий.
3. Исследование математической модели
Пусть
( 
) – минимальное (максимальное) количество тактов, за которое работа j потребит ресурс i. 
iÎI, jÎJ.
Здесь А – достаточно большое число, [а]- операция взятия целой части числа а.
Минимально возможная длительность работы j определяется следующим образом:
.Максимально возможная длительность работы j:
.Будем говорить, что математическая модель имеет технологически допустимое решение, если система (2.1)-(2.5) совместна.
Теорема1
Условия:
, jÎJ, 
*mij£rij , iÎI, jÎJ
являются необходимыми и достаточными для совместности системы (2.1)-(2.5).
Будем говорить, что математическая модель имеет организационно-технологически допустимое решение, если система (2.1)-(2.7) совместна.
Пусть Tj – максимальная суммарная продолжительность работ, начиная с работы j¢, для которой K(j¢)=Æ, и заканчивая работой j¢¢ j¢¢Î JD. Эта величина представляет собой величину критического пути.
Теорема 2.
Условия:
, jÎJ, *mij£rij , iÎI, jÎJ,