ПОИСК Статьи Рисунки Таблицы Декомпозиция и решение задачи из "Оперативно-календарное планирование" Аппроксимирующая функция (VII.30) позволяет разделить общую экстремальную комбинаторную задачу поиска оптимального варианта плана-графика ремонтов оборудования химического предприятия на п взаимосвязанных задач, каждая из которых относится к установкам, соответствующим дугам путей агрегированной сетевой модели. Критерием оптимальности при этом является максимум пропускной способности каждого пути на заданном горизонте планирования. [c.220] Декомпозиция задачи с использованием аппроксимирующей функции (VII.30) сопровождается определенными потерями в-оптимальности, которые, однако, можно уменьшить путем правильного выбора соответствующей последовательности (очередности) путей при решении задачи. Поскольку при оптимальном планировании. ремонтов оборудования поставлена цель получения максимума критерия (VII.20), выбор последовательности путей при упомянутом разделении общей задачи целесообразно провести на основании оценки вклада в критерий оптимальности потока в каждом из путей пути следует ранжировать в порядке уменьшения этого вклада. Такая последовательность и определит очередность задач по путям. [c.220] Результатом решения задачи (VI 1.32)—(VI 1.37) являются верхние границы Хи интегральных потоков в агрегированных дугах со 6 И а -они достижимы только в случае полного согласования всех ремонтов во всех дугах. Найденное решение дает возможность получить путевое разложение оценок интегрального потока в сети, которое и используется для вычисления вклада каждого потока в критерий оптимальности. [c.221] Таким образом, из множества путей сети За = 5 ) (1 = 1, 2,. . ., п) последовательно выбираются пути, обеспечивающие максимум произведения величины и стоимости потока в пути на множестве всех возможных путей, относящихся к рассматриваемому этапу расчета. Рассмотрим процедуру формирования последовательности (очередности) путей при решении задачи. [c.221] После выполнения всех этапов У = 1, 2,. . ., п получаем последовательность номеров путей ( S/ , которая и определяет их очередность при поиске оптимального плана-графика ремонта оборудования. [c.222] Степень аппроксимации критерия (VII.31) выражением (VII.44) обуславливается последовательностью, в которой будет осуществляться оптимизация по агрегированным дугам пути. [c.224] Дуги пути ранжируются в порядке возрастания величины полученных оценок веса A оптимизация начинается с дуг, обладающих минимальным весом. [c.225] Таким образом, чтобы решить общую задачу оптимизации плана-графика ремонтов на сетевой модели крупного предприятия, необходимо в определенной последовательности решить ряд взаимосвязанных комбинаторных задач оптимизации плана-графика ремонтов оборудования, соответствующего агрегированным подсетям модели предприятия. Каждой агрегированной дуге соответствует некоторая последовательно-параллельная подсеть либо совпадающая с исходной подсетью, либо полученная ее приведением (см. главу IV). Такая последовательно-параллельная подсеть подразделяется на два подмножества к первому относятся дуги, для оборудования которых на горизонте планирования намечены ремонты ко второму — дуги, оборудование которых на горизонте планирования не ремонтируется. Для первого подмножества будем пользоваться термином дуги с обслуживанием, для второго — дуги без обслуживания. [c.225] Полученная цифра достаточно убедительно свидетельствует о том, что прямой перебор вариантов не представляется возможным. Необходимо выбрать какой-то иной метод решения задачи. [c.226] Многие известные комбинаторные задачи, такие, как задача о коммивояжере, общая задача теории расписания [64] и т. д., сводятся к целочисленному линейному программированию. [c.226] Однако решение комбинаторной задачи посредством линейного программирования [64] возможно только в том случае, если каждой комбинации Г/ (/ = 1,2. у) удается поставить в соответствие точку 2-мерного пространства при некотором z, связанном с сущностью задачи. Например, если Q (Г) — некоторая линейная функция точки Г, причем Г — множество вариантов данной задачи, а Ь — выпуклый многогранник, состоящий из всевозможных комбинаций точек множества Г , то комбинаторная задача может бы ть сведена к задаче линейного программирования, заключающейся в максимизации Q (Г) на выпуклом многограннике Ь. Однако это возможно лишь при условии, что многогранник Ь удается задать с помощью системы равенств и неравенств, связывающих компоненты точки Г, т. е. если он может быть представлен как пересечение некоторого числа гиперплоскостей и полупространств точек Г. [c.226] Обращаясь к нашей задаче, видим, что сведение к линейному программированию не представляется возможным, поскольку функция Q (Г) не является линейной из-за ступенчатого характера функции пропускной способности в дугах подсети. Поэтому мы можем воспользоваться только приближенным методом решения комбинаторной задачи, основанным на эвристике, метода случайного поиска или комбинации случайного поиска и эвристических приемов [24]. [c.226] На рис. VII.1 Показано изменение интегральной пропускной способности AQ сети на горизонте планирования при изменении сроков проведения ремонта установки 1 (по оси абсцисс отложено число интервалов дискретности горизонта планирования). Из этого рисунка видно, что точки излома приращения интегральной пропускной способности сети соответствуют тем интервалам дискретности, в которых начало или конец ремонта установки 1 совпадает с концом ремонта какой-то установки. [c.227] Поскольку при оптимизации плана-графика ремонтов последовательно-параллельной ХТС критерием оптимальности является максимум интегральной пропускной способности сети, при переборе вариантов нет необходимости рассматривать все возможные сроки ремонта в дуге 1 (при неизменных сроках ремонта в других дугах) достаточно рассмотреть лишь даты остановки на ремонт, соответствующие точкам излома приращения интегральной пропускной способности A(J. Пример показывает,что число возможных вариантов пЛана-графика ремонта можно значительно сократить, рассматривая только зоны горизонта планирования, в которых обеспечивается максимальное совмещение ремонтов. [c.227] Однако, если ремонт -той установки начинается в точке В, то при совмещении его конца с концом более длительного ремонта возникают новые частичные совмещения этого ремонта с конечными этапами ремонтов, начатых ранее, например в момент В] Устанавливать начало ремонта в промежуточных точках интервала В[, 0 1) не следует, так как в крайних точках интервалов частичные совмещения обеспечиваются более полно. [c.229] Стремление ограничить число вариантов плана-графика при переборе не позволяет рассмотреть все возможные совмещения с учетом всех частичных. Однако можно построить все варианты полных совмещений, которые получаются в крайних точках интервалов (/),, В ). При полном совмещении ремонтов в левой части интервала каждый ремонт назначается на самую раннюю из допустимых дат. Например, на интервале 0, В ) ремонт установки 4 и все более короткие ремонты начинаются в момент В[, более длительные размещаются так, что их конец совмещается с концом ремонта установки 4. [c.229] Пусть время решения задачи на ЭВМ ограничено тем, что рассматривается не более 10 реализаций. В этом случае вероятность получения оптимального решения Р = 0,999 будет обеспечена при условии, что вероятность оптимального исхода каждого испытания составит р = 0,0001. А это значит, что среди общего числа вариантов 7 = 10 , рассмотренных в примере, приведенном в начале главы, должно быть не менее 10 вариантов, близких к оптимальному. [c.231] Одним из первых ограничений, введенных для уменьшения общего числа вариантов, является обусловленное практическими соображениями требование не начинать ремонт оборудования в субботние и воскресные дни горизонта планирования, независимо от продолжительности ремонта. Это требование связано с режимом работы предприятия. С подобным же обстоятельством связано другое ограничение на те дни недели, в которые могут быть начаты ремонты различной длительности оно позволяет минимизировать число субботних и воскресных дней во время простоя оборудования в ремонте. Эти ограничения значительно снижают размер поля допустимых дат. [c.231] Еще одним ограничением, также связанным с рабочей силой, является следующее требование чтобы не создавать пиков потребности в рабочей силе, не следует ремонтировать одновременно параллельные установки, если это позволяет общая длительность таких ремонтов на горизонте планирования. [c.231] По изложенным соображениям ремонты нескольких установок образуют своеобразные связки , обладающие весьма ограниченным числом допустимых дат при варьировании плана-графика. Для последовательных установок, образующих ниточные структуры технологических схем, требования к срокам, выдвигаемые при варьировании, прямо противоположны тем, которые предъявляются к параллельным установкам, т. е. если в установках нитки предстоит выполнить несколько ремонтов, все они (если это допустимо) как бы стремятся стянуться в одну дату, чтобы увеличить пропускную способность такой подсети. Такое стягивание алгоритм осуществляет не случайно, а целенаправленно случайный механизм определяет даты только первого ремонта и тех ремонтов, которые в силу несовпадения поля допустимых дат и первой найденной даты не могут быть с ней совмещены. [c.231] Вернуться к основной статье