книги из ГПНТБ / Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями

А К А Д Е М И Я Н А У К К А З А Х С К О Й С С Р

И Н С Т И Т У Т Г О Р Н О Г О хГе л а

С. ЦОЙ, С. М. ЦХАЙ, Е. И. МАСТЯЕВА

СИНТЕЗ

ОПТИМАЛЬНЫХ

СЕТЕЙ В СИСТЕМЕ

УПРАВЛЕНИЯ

ГОРНЫМИ

ПРЕДПРИЯТИЯМИ

И з д а т е л ь с т в о « Н А У К А » К а з а х с к о й С С Р А Л М А- А Т А • 1 9 7 4

•ъS. Л£М«Л<

1 ЧлГ//.ТАКОГО «АЛА

.т•»

Z f'

УДК 519.9 + 519.95

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

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

Илл. 58, табл. 27, библ. 69.

ОТВЕТСТВЕННЫЙ РЕДАКТОР

Академик АН КазССР О. А. БАЙКОНУРОВ.

0376— 107 Ц м 405(07)—74 33— 74

Издательство «Наука» Казахской ССР. 1974 г.

П Р Е Д И С Л О В И«Е-

Бурное развитие экономики и техники сопровождается невиданным ростом научных исследований и внедрением полученных результатов в производство. Среди научных разработок оптимального управления народным хозяйст­ вом одно из важных мест занимает метод сетевого планиро­ вания и управления (СПУ).

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

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

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

Авторы выражают глубокую признательность академику АН КазССР О. А. Жаутыкову за ценные замечания и реко­ мендации при подготовке рукописи к изданию.

3

Г л а в а I

КРАТКИЙ КРИТИЧЕСКИЙ ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ОПТИМИЗАЦИИ СЕТЕВЫХ МОДЕЛЕЙ

§1. КЛАССИФИКАЦИЯ МЕТОДОВ СЕТЕВОГО ПЛАНИРОВАНИЯ

ИУПРАВЛЕНИЯ (СПУ)

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

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

Система сетевого планирования и управления — одна из новых форм научного метода планирования сложных работ, которые могут выполняться большим числом исполнителей.

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

4

многообразие существующих методов, необходима их клас­ сификация.

Анализ современного состояния теории СПУ в горном деле показывает, что все методы, обеспечивающие решение сетевых задач, можно объединить в четыре основные груп­ пы:

1)методы построения сетей;

2)методы анализа и оптимизации сетей по фактору вре­

мени;

3)методы решения оптимальных задач сетевого плани­ рования, минимизирующие стоимость всего проекта;

4)методы оптимального распределения ограниченных ресурсов во времени.

В связи с острой потребностью народного хозяйства, в том числе и горнорудной промышленности, в рациональных

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

Методы построения сетевых графов

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

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

Коротко остановимся на методах построения сетей.

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

Пусть дан перечень работ с объемами и сроком выполне­ ния (табл. 1.1).

Представим взаимосвязь указанных работ в виде ориен­ тированного графа без контуров (рис. 1.1). В сетевом графе,

5

на — конечное событие, называемое мажорантой. В нашем

Таблица 1.1

примере вершина 0 служит минорантой, а вершина 5 — ма­ жорантой. Если событие, изображаемое вершиной 5, насту­ пило, то анализируемый проект полностью выполнен.

Изображение проекта в виде ориентированного графа (рис. 1.1) является, пожалуй, самым распространенным спо­ собом и широко описано в литературе [27, 30, 48]. В горной промышленности также применяется метод линейно-стре­ лочных графиков со связями, разработанный под руковод­ ством В. Р. Именитова [25, 32]. Сущность его состоит в вы­ черчивании линейной диаграммы проекта в выбранном масштабе времени с одновременным нанесением технологи­ ческих взаимосвязей работ. Основное достоинство этого ме­ тода заключается в том, что для отыскания критических путей не нужно использовать специальные алгоритмы. Ра­ боты, составляющие критические пути, можно находить на графике визуально. Также легко определяются непо­ средственно на графике резервы времени работ. Линейно­ стрелочный график для нашего примера (рис. 1.1) вычерчен

6

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

На рисунке 1.2 работы представлены горизонтальными линиями, а взаимосвязь между ними — вертикальными ли­ ниями. Например, вертикальными линиями связаны работы

(0,1) и (1,3), (1,3), (3,4) и (3,5) и т. д.

У работ, обладающих резервом времени, на линейно­ стрелочном графике есть еще и наклонная штриховая ли­ ния. Например, работа (2,4) связана с работой (4,5) и имеет резерв времени, равный 1. На оси времени t он дан в виде горизонтальной проекции наклонной штриховой линии. На­ клонная штриховая линия означает, что после завершения работы (2,4) пройдет еще один месяц до того момента, как выполнится полностью работа (3,4) и начнется работа (4,5).

Для небольших проектов четкое представление о поряд­ ке следования работ может быть получено с помощью ли­ нейных диаграмм, которые составляются в системе коорди­ нат после построения исходного сетевого графа. Этот спо­ соб подробно описан в работе С. И. Зуховицкого и И. А. Радчик [27]. Линейная диаграмма строится следующим обра­ зом (рис. 1.3). Ось абсцисс является осью времени. На оси ординат отмечены номера событий. Каждая работа изобра­ жена в виде полоски — вытянутого прямоугольника. Длина прямоугольника соответствует продолжительности работы, а начало его расположения определяется технологическими взаимосвязями работ. Каждая полоска вычерчивается па­ раллельно оси абсцисс одна над другой, снизу вверх в по­ рядке возрастания номеров события j, а для работ, имеющих одно и то же j,— в порядке увеличения номеров событий i. Здесь i и j — начальное и конечное события работы (г, j).

Линейная диаграмма для рассматриваемого примера (рис. 1.1) дана на рисунке 1.3. Заштрихованные полоски — это работы критического пути, определяемого соединением непрерывно следуемых работ от нулевого события до ко­ нечного. Прямоугольники, нарисованные пунктирными ли­ ниями, показывают резервы времени соответствующих ра­ бот.

Диаграмму сети с учетом ранних и поздних сроков свер­ шения событий можно вычертить в системе координат с по­ мощью метода В. Максимова [25]. Горизонтальная проек­ ция отрезков при этом равна продолжительности работ. Описываемый пример (рис. 1.1) по методу Максимова пред­ ставлен на рисунках 1.4 и 1.5. На оси абсцисс отложено вре­ мя, на оси ординат — события работ. Работы показаны в виде прямых или дугообразных линий. Начало каждой ра­ боты фиксируется на оси времени t. На рисунке 1.4 начерче-

7.

Рис. 1.2.

на диаграмма с учетом ранних начал, т. е. считается, что все работы, обладающие резервом времени и не лежащие на критическом пути, начаты в наиболее ранний возможный срок. Например, работа (2,4) начата в момент t = 3, а рабо­

та (3,5) — в момент t = 5. На рисунке 1.5 начало работ ото­ двинуто на более поздний срок. Работа (2,4) начата в момент

9