Элементы теории графов и их технические приложения - 52 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

52
обслуживания разбираются задачи назначения приоритетов в обслуживании
поступающих заявок некоторыми устройствами, приборами и т.п. Существует
некоторое сходство формальных моделей этих видов задач.
Целенаправленную деятельность можно рассматривать как некоторый
протекающий во времени процесс, заключающийся в реализации (выполнении)
определенной совокупности работ
{
}
S
PPPS ,...,,
21
=
.
Выполнение работ стеснено целым рядом ограничений и условий, которые
можно разбить на две группы.
Ограничения
α . Эти ограничения описывают взаимную зависимость
выполнения работ. Каждой работе
SP
i
∈
можно поставить в соответствие некоторое
множество
S
i
⊂Π непосредственно предшествующих работ, без выполнения
которых нельзя начинать выполнение работы
i
P , а также ряд работ, не входящих во
множество
S , которое могут рассматриваться как внешние факторы, необходимые
для выполнения работы
i
P
. Например, возведение стен строящегося здания
возможно начать лишь после того, как сделан фундамент (работа из множества
S ), а
также при наличии кирпича и раствора, изготовление и транспортировка которых
могут и не входить в данный перечень работ.
Для описания некоторых других условий, входящих в ограничения
α , удобно
ход выполнения работ рассматривать в дискретном времени, приняв некоторую
величину
tΔ за единичный интервал времени (условный день, год и т.п.)
называемый шагом.
Некоторые работы могут быть выполнены целиком за один шаг, другие – за
несколько шагов. В ограничение
α
должно входить условие допустимости или
недопустимости прерывания работ.
Пусть
t - номер рассматриваемого шага ,...)2,1(
=
t . Обозначим через )(ty
i
долю
работы
i
P , выполняемую на шаге с номером t , которую назовем единичной
порцией работы
i
P . Обозначим через )(tS перечень работ, выполняемых на шаге с
номером
t . Пусть работа
i
P состоит из
m
единичных порций
i
y и прерывание этой
работы недопустимо. Условие недопустимости прерывания работы заключается в
том, что если эта работа начинается на шаге с номером
t , то единичные порции
i
y
должны входить в перечни работ
)1(),...,1(),(
−
+
+
mtStStS .
Ограничение
β . Они связаны с ограниченным объемом ресурса, который может
быть выделен на выполнение совокупности работ
S .
Обозначим через
)(tQ вектор ресурса, который может быть выделен на
выполнение работ на шаге с номером
t . Компонентами вектора )(tQ могут быть
величины
1
Q - сырье, материалы,
2
Q - оборудование,
3
Q - рабочая сила и т.п.
Обозначим через
[]
)(tyq
i
количество ресурса, которое необходимо затратить для
выполнения работы
)(ty
i
. В этих обозначениях ограничение
β
запишется в виде
[]
)()(
1
tQtyq
S
i
i
≤
∑
=
,
Mt ,...,2,1
=
, где
M
- общее число шагов.

Страницы