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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

53
В задачу иногда вводится предложение, что единичная порция работы )(ty
i
либо выполняется полностью, если на нее выделен необходимый ресурс, либо не
выполняется совсем, если ресурс выделен не полностью. Более сложная задача
получается, когда доля выполненной работы зависит от количества выделенного
ресурса.
Задача на составление расписания сводится к тому, чтобы для каждого шага
t
назвать перечень работ
{
}
e
tt
PPtS ,...,)(
1
= , которые должны выполняться в течение
этого шага, и также долю
)(ty
i
каждой из этих работ с учетом всех ограничений,
накладываемых на порядок выполнения работ и на выделяемые ресурсы.
Если число работ велико, то число вариантов расписания может быть
огромным. Выбор конкретного варианта расписания связан с понятием
директивного срока. Если перечень работ и ресурс на их выполнение заданы, то
наилучшим (оптимальным) вариантом
расписания следует считать тот, при котором
время выполнения всего перечня будет минимальным. Этот срок и принято
называть директивным.
Пусть имеется сложная программа работ
{
}
S
PPS ,...,
1
=
, в которой действуют
ограничения
α
, определяющие очередность выполнения отдельных работ, так и
ограничения β на выделяемые ресурсы. На практике обычно ограничения
α
связывают между собой не все работы, а действуют внутри некоторых независимых
групп работ. Сами же такие группы между собой жесткими ограничениями не
связаны.
В таких случаях программу работ S можно представить в виде некоторого
разбиения
{}
m
RRm ,...,
1
= , элементы которого m
R
∈
представляют собой
некоторые самостоятельные подпрограммы, обладающие тем свойством, что между
ними отсутствуют жесткие ограничения очередности, так что каждая подпрограмма
m
R
∈ может выполняться почти независимо от выполнения других подпрограмм.
Однако внутри каждой подпрограммы
{
}
r
iii
PPR ,...,
1
=
порядок выполнения работ
подчинен жестким ограничениям
α
.
Таким образом, задачу на составление расписания можно разбить на две
самостоятельные задачи.
Особенности задач первого типа состоят в том, что жесткие ограничения
α
в
таких задачах в значительной степени предопределяют порядок выполнения
отдельных работ и число возможных вариантов расписания здесь не очень велико.
Однако варианты всегда возможны и среди них могут найтись такие, при которых
окажется минимальным время выполнения подпрограммы, наиболее рациональное
распределение ресурсов и т.п. Для решения задач этого типа широко
применяются
методы сетевого планирования и управления (СПУ).
В задачах второго типа ограничения на очередность выполнения отдельных
работ незначительны, что не означает, что порядок выполнения работ здесь
безразличен. От порядка выполнения работ зависит распределение ресурса по
шагам. На переход от одной работы к другой тратится время, может потребоваться
переквалификация персонала, переналадка или
замена оборудования и т.п. Поэтому
и здесь стоит задача составления расписания работ в определенном смысле

Страницы