Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

Г л а в а V

СИНТЕЗ ОПТИМАЛЬНОГО СЕТЕВОГО ГРАФА ПРИ ПЕРЕМЕННЫХ УРОВНЯХ НЕСКЛАДИРУЕМЫХ

РЕСУРСОВ

До сих пор мы рассматривали задачу синтеза и оптими­ зации сетевого графа при ограниченном объеме складируе­ мых ресурсов (денежные средства, материалы, сырье и энер­ гия). Однако на практике во многих производственных процессах используются нескладируемые ресурсы. Как уже указывалось, под нескладируемыми ресурсами подразуме­ ваются люди, оборудование, машины, станки и т. д. Если неизрасходованную часть складируемых ресурсов можно ре­ ализовать через некоторое время, то простои оборудования, машин, людей не восстанавливаются.

Ниже излагается синтез оптимального сетевого графа при ограниченном объеме нескладируемых ресурсов.

§ 1. Общие замечания

Предположим, что сетевая модель некоторого проекта задана ориентированным графом с полными контурами. Се­ тевая модель построена на языке «работа — связь». Работы в графе изображены в виде вершин i ( г = 1 , 2 , . . . , 2V), свя­ зи между работами — дугами иц .

Пусть для каждой работы i известен ее объем F*. Счита­ ем, что продолжительность выполнения работы обратно про­ порциональна интенсивности потребления ресурсов. Под интенсивностью понимается количество нескладируемых ре­ сурсов, используемых в единицу времени. Обозначим макси­ мальную интенсивность расходования ресурсов для i-й ра­ боты через pj. Очевидно, при такой интенсивности продол­ жительность работы будет наименьшей (обозначим ее через

87

Если обозначить через r t величину любой возможной ин­ тенсивности для работы i, то соблюдается условие

(Xz-CPi. (5.3)

Так как интенсивность потребления нескладируемых ресур­ сов меняется во времени при осуществлении данной работы, то ее продолжительность может быть определена по фор­ муле

где Vik — объем работы, выполняемой с постоянной интен­

Обозначим через R(t) переменный уровень нескладируе­ мых ресурсов, выделенных для осуществления работ проек­ та. Тогда суммарное значение интенсивностей всех работ, начатых в момент времени t, не должно превысить величи­ ны R{t). Ввиду того, что машины, оборудование, бригада и т. д. принимают целочисленное значение, функция /?(£) бу­ дет ступенчатой. Поэтому для большинства проектов ее мож­ но записать в виде

где ^k—1 и тА— соответственно начальный и конечный мо­ менты фиксированного отрезка времени;

Rk— постоянная фиксированная целочисленная величи­ на на каждом отрезке времени.

При решении задач % и t принимают целочисленные значения.

88

§2. Постановка задачи

Сучетом сделанных выше замечаний сформулируем за­ дачу синтеза сети. Требуется из данного графа с полными контурами выделить сетевой граф с минимальным значени­ ем длины критического пути посредством рационального подбора интенсивности использования ресурса на каждой работе при условии, что общий объем потребляемых ресур­ сов в любой момент времени t не превышает jR(f).

Как известно, в существующих постановках задач рас­ пределения нескладируемых ресурсов топология сети счи­ тается заданной, т. е. жестко зафиксированной. В предла­ гаемой постановке при решении отыскивается наилучшая топология, т. е. определяется оптимальный порядок следо­ вания работ каждого полного контура. Последнее сущест­ венно отличает рассматриваемую задачу синтеза сетевого графа проекта от общеизвестных постановок.

Предположим, что любая работа может выполняться с перерывами и на всех работах используется только один вид нескладируемых ресурсов.

§3. Алгоритм синтеза оптимального сетевого графа при переменных уровнях нескладируемых ресурсов

Предлагаемый алгоритм носит итерационный характер, при этом после каждой итерации число невыполненных ра­ бот уменьшается и на каждой последующей итерации рас­ сматривается новый допу­ стимый граф, в котором от­ сутствуют завершенные ра­ боты.

времени Att этих работ, т. е. в первую очередь ресурсы вы­ деляются для тех работ, которые имеют меньший резерв вре­ мени.

Распишем действия всех шагов алгоритма на конкрет­ ном примере. Пусть исходная сетевая модель анализируемо­ го проекта представлена графом с полными контурами на рисунке 5.1. Значения параметров Vi и р* приведены в таб­ лице 5.1, а на рисунке они указаны в прямоугольниках: сле­ в а — V it справа — р*. Причем последняя работа i = 12 яв­ ляется фиктивной.

Пусть функция (5.6) принимает постоянное значение Д( £ ) = ;1 0 при Ог£С£<С°о.

Сущность рассматриваемого алгоритма заключается в следующем. Определим совокупность работ, которые могут выполняться одновременно. По величине резерва времени выбранным работам назначаем определенное количество ресурсов r ^ p i . Далее устанавливаем промежуток времени 0 , в течение которого работы осуществляются с назначен­ ной интенсивностью. Для работ фронта вычисляем уже вы­ полненные объемы. Для тех работ, которые в промежуток времени 0 полностью не заканчиваются, находим время, не­ обходимое для завершения оставшегося объема. На этом действие одной итерации заканчивается, и все расчеты по­ вторяются заново для следующего фронта. На каждой ите­ рации анализируется новый фронт работ.

Итерация 1

Шаг 1. По формуле (5.2) вычисляем минимальную про­ должительность для всех работ графа (рис. 5.1) и применя­ ем алгоритм В. В результате получаем сетевой граф без кон­ туров с минимальным значением критического пути (рис.

90

В процессе синтеза по алгоритму В для всех работ графа G(Xl, U1) определяем ранние начала. В нашем случае ранние начала работ на графе (рис. 5.2) равны:

Шаг 2. Анализ результатов вычисления по алгоритму В. С помощью величин £? н и продолжительностей t i0 по­

строим временную линейную диаграмму D\ (рис. 5.3), где по оси абсцисс отложим время t, по оси ординат — номера ра-

Рис. 5.3.

бот. Расстояние между двумя соседними пунктирными ли­ ниями означает отрезок времени, в течение которого сум­ марная интенсивность использования ресурсов постоянна и равна сумме р* соответствующих работ.

91