Методические указания по проведению лабораторных работ «Распределение ресурсов в сетевых канонических структурах» по курсу (стр. 2 из 3)
Tj£Dj, jÎJD (3.5)
являются необходимыми и достаточными для совместности системы (2.1)-(2.7).
Будем говорить, что математическая модель имеет организационно-ресурсно-технологически допустимое решение, если система (2.1)-(2.8) совместна.
Теорема 3.
Проблема существования организационно-ресурсно-технологически допустимого решения относится к классу NP-полных.
Доказательство заключается в постановке в рамках общей модели задачи Джонсона для m (m>2) станков.
Доказательства теорем приведены в [1].
4. Постановка многокритериальных задач
В рамках построенной общей математической модели ставятся различные оптимизационные задачи. Постановка задачи определяется двумя факторами: множеством допустимых решений и критерием (или группой критериев) оптимальности. Множество допустимых решений задается системой ограничений, которая выбирается из вышеописанных условий (2.1)-(2.8). Среди ограничений задачи обязательно должны присутствовать технологические ограничения и могут присутствовать ограничения организационного или (и) ресурсного типа. Вместо ограничений организационного и ресурсного типа могут вводиться соответствующие критерии оптимальности.
Первым типом оптимизационных задач являются задачи, в которых допускаются нарушения организационных ограничений. При этом на систему обслуживания накладываются штрафные санкции. Определим для каждой работы jÍJD функцию штрафа, связанную с выполнением ее после директивного срока:
fj(yj, Dj)=
, jÎJD.Таким образом, определяется группа частных критериев, связанных с нарушениями директивных сроков выполнения работ fj(yj,Dj)®min, jÍJD.
В качестве обобщенного функционала можно рассматривать аддитивную свертку частных критериев.
F=
®min. (4.1)Функционал F определяет количество тактов нарушения сроков выполнения для работ, имеющих директивные сроки. Минимизация функционала F отражает стремление своевременно завершать выполнение работ. Постановка задач этого типа включает исходные параметры, варьируемые параметры, ограничения (2.1)-(2.5), (2.8), критерий (4.1).
Другой тип оптимизационных задач связан с возможностью нарушения ресурсных ограничений. Введем частные критерии оптимальности для условий ресурсного типа.
git(
,Vit)®min iÎI, tÎT.Здесь
– количество i-го ресурса, необходимое для выполнения работ в такт t, Vit – количество i-го ресурса, которое поступает в систему в такт t. Функция git( 
,Vit) определяет для каждого ресурса i функцию штрафа, связанную с неиспользованием или с недостатком его в такт t.git(
,Vit)= 
iÎI, tÎT.git – параметр, определяющий штрафные санкции, связанные с неиспользованием 1% ресурса i в такт t.
dit – параметр, определяющий штрафные санкции, связанные с недостатком 1% ресурса i в такт t.
В качестве обобщенного функционала выберем следующий:
Ф=
®min. (4.2)Функционал Ф определяет максимальные штрафные санкции за неравномерность расходования ресурсов по тактам планирования.
Постановка задач этого типа включает исходные параметры, варьируемые параметры, ограничения (2.1)-(2.7), критерий (4.2).
В случае, когда разрешаются нарушения и организационных и ресурсных ограничений, задача планирования ставится как бикритериальная задача с ограничениями (2.1)-(2.6) и критериями (4.1), (4.2).
Предлагаемый алгоритм основан на идеологии «жадных алгоритмов» (аналог метода градиента для непрерывных задач): выбранная из фронта работ очередная работа включается в строящееся расписание, причем для ее выполнения используются все доступные к данному моменту времени ресурсы в максимально возможном объеме.
На подготовительном этапе каждой работе j, используя технологические ограничения, присваивается длительность tj, jÎJ, тем самым осуществляется переход к сетевым моделям, для которых можно провести расчет временных характеристик: найти моменты раннего начала выполнения работы, раннего окончания выполнения работы, позднего начала и позднего окончания выполнения работ.
, jÎJ. 
, jÎJ. 
, jÎJ. 
, jÎJ.Затем каждой работе ставится в соответствие величина
- резерв времени работы j, jÎJ.Пусть t0 – произвольный такт планирования, t0ÎT. Назовем «фронтом работ» множество F(t0) – множество работ, любая из которых может выполняться, начиная с такта t0, t0ÎT.
Для выбора очередной работы из фронта работ перейдем от множества F(t0) к вектору p(t0), компоненты которого и будут определять порядок выполнения работ. Существует несколько способов определения вектора p(t0).
Пусть F(t0)={j1,j2,...,jk}. Тогда p(t0)=(p1,p2,...,pk), pl¹pq, pl, pqÎF(t0), где pq – номер работы, выполняемой q-ой по порядку. Упорядочим работы множества F(t0) по неубыванию резервов времени и перенумеруем их. Это первый способ получения вектора p(t0).
Используя полученную перестановку построим матрицу Р=÷çpij÷çk´k. Элемент этой матрицы pij определяет резерв времени, который будет иметь работа i, если она будет включена в строящееся расписание j-ой по порядку. В матрице Р ищется произвольная незаполненная ячейка
и начальная перестановка преобразуется таким образом, чтобы работа i0 выполнялась j0-ой по порядку. Строится новое расписание, рассчитываются новые резервы времени, и заполняются соответствующие элементы матрицы. Процедура повторяется, пока не будут заполнены все элементы матрицы P.Введем переменные xij , которые имеют следующую содержательную интерпретацию:
i,j= 
.Для нахождения порядка выполнения работ, при котором суммарный временной резерв минимален, следует решить следующую задачу:
, j= . 
, i= .x
Î{0,1}, i,j= . 
.Построенная задача является задачей о назначениях и может быть решена известными алгоритмами (например, алгоритмом Куна). По полученному решению X* находится искомый вектор p, определяющий порядок выполнения работ из фронта работ.
Таким образом, предлагаются два алгоритма упорядочения работ из фронта работ. Использование упорядочения по неубыванию резервов времени работ более быстрый результат расчета. При использовании второго алгоритма результат расчета может быть лучше, но этот алгоритм требует больших временных затрат.
6. Диалоговая система планирования
Для решения задач сетевого планирования создана диалоговая программная система. Эта программная система позволяет вводить, редактировать, хранить данные, необходимые для решения конкретной прикладной задачи, получать решение задачи планирования.
Данные, необходимые для решения задачи объединяются в одном проекте. Под проектом понимается информация трех типов: общие характеристики проекта, данные о работах, данные о ресурсах.
Общие характеристики проекта включают в себя наименование проекта, дату начала периода планирования, длительность периода планирования, режим планирования (месяцы/ дни).
Информация о изделиях включает в себя наименование и список составляющих его работ. Для каждой работы указывается тип необходимого ресурса, ресурсоемкость, минимальная и максимальная интенсивность, директивный срок, список предшествующих работ. Корректировка данных о работах производится на листе «Работы».
Информация о ресурсах включает в себя наименование, количество ресурса, текущую, начальную и максимальную перегрузку, приращение перегрузки. Корректировка данных о ресурсах производится на листе «Ресурсы».
Справочная информация доступна в двух видах: в виде краткой выпадающей подсказки при фиксировании курсора на элементе и в виде подробной информации в отдельном окне при нажатии клавиши «F1».