Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 658.33

РЕШЕНИЕ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ

С ИСПОЛЬЗОВАНИЕМ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ

Кухаренко С.В., Балтовский А.А.

Введение.

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

Формирование основных направлений научно-технической политики в области планирования производства продукции в течении последних лет находится в центре внимания правительства Украины, о чем свидетельствуют государственные программы, которые сформулированы в рамках государственной научно-технической программы №7 „Перспективные информационные технологии, устройства комплексной автоматизации системы связи” (Постановление Верховного Совета Украины от 16.10.1992г.).

Анализ предшествующих публикаций.

В работе [1] авторы указывают, что для задач календарного планирования (КП), а также других задач, имеющих комбинаторную природу, характерен неполиномиальный рост времени решения с ростом размерности задачи. С этим связаны основные трудности построения систем КП реальных производств, имеющих как правило размерность выше средней. Проблема становится еще острее при переходе к КП единичных многономенклатурных производств. Это делает невозможным применение точных методов при решении задач КП реальных производств.

В работе [2] авторы отмечают, что для КП практическое применение находят в основном методы, базирующиеся на ограниченном переборе множества допустимых решений. Этим обусловлен интерес разработчиков систем КП к эвристическим методам решения задач, среди которых широко известен подход с использованием эвристик, называемых правилами предпочтения. Правила предпочтения устанавливают очередность технологических операций при возникновении конфликтов в процессе планирования. Они позволяют получать субоптимальные планы, существенно сокращая при этом объем необходимого перебора.

Из методов направленного перебора наибольшую известность получил метод ветвей и границ [3]. В этом методе задача КП разделяется на две части: 1 – довольно компактный алгоритм ветвления и выбора очередного претендента, 2 – определение метода оценки перспективных вершин и нахождение нижней границы. Использование метода ветвей и границ при составлении расписаний показало, что, несмотря на громоздкость решений, его можно использовать при удачном выборе способа задания оценок. Основная проблема состоит в определении взаимосвязи оценок и критерия качества.

Предпринималось довольно много попыток решить задачи КП методом
Монте-Карло. В этой области полученные результаты в основном дали возможность промоделировать различные способы задания правил выбора и их влияние на качество получаемых расписаний для разных производственных ситуаций.

На основе анализа работ [4-5] нами установлено, что все многообразие подходов и методов и безуспешность их использования в реальных производственных ситуациях приводят к необратимости использования эвристических методов решения. При этом под эвристикой понимается правило выбора претендента на включение в комбинацию на поле расписания в конфликтных ситуациях (функции предпочтения).

В настоящее время работы по исследованию функций предпочтения ведутся по следующим основным направлениям:

-   определение класса задач, в которых данная функция приоритета приводит к лучшим по сравнению с другими функциями результатам;

-   выявление функций приоритета, наиболее эффективных при решении данной задачи;

-   комбинированное их применение в сочетании с рандомизацией.

На основе анализа работ [1-5] приходим к выводу, что в практике используется большое разнообразие правил предпочтения, подходов к созданию новых и использованию уже известных эвристик, например, рандомизированные правила предпочтения, комбинированные правила предпочтения, и т.д. В виду отсутствия в настоящее время общего подхода, позволяющего решить задачу выбора наилучшего правила предпочтения для всего многообразия современных производств приходим к выводу, что удачная разработка новой эвристики или выбор уже известного правила предпочтения, наилучшим образом отвечающего характеру конкретного производства будет способствовать повышению качества системы КП в целом.

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

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

Анализ задачи.

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

Основная часть.

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

Разработанная нами схема системы календарного планирования включает восемь блоков:

Блок 1. Формирование и обновление исходных данных (номенклатура и показателя проекта плана, типовые модели проектируемых объектов, временные, стоимостные и ресурсные характеристики комплексов и отдельных работ, прочие нормативно-справочные данные) в режимах планирования и оперативного управления.

Блок 2. Подготовка (корректировка) массивов исходных данных, ввод в ЭВМ, первичная обработка и хранение нормативной и текущей информации.

Блок 3. Алгоритмы календарного планирования (проверка совместимости ограничений; расчет (перерасчет) календарного плана на планируемый период по заданному критерию оптимизации; формирование календарного плана и представление основных показателей для анализа руководству.

Блок 4. Логика (Утверждается ли план руководством? Если „Да”, то переход к блоку 6, если „Нет”, то к блоку 5).

Блок 5. Логика (Изменение ограничений по представлению руководства. Если „Да”, то переход к блоку 2.

Блок 6. Формирование и печать текущих и оперативных календарных планов, диспетчерских документов и доведение их до соответствующих уровней руководства и ответственных исполнителей.

Блок 7. Реализация комплексов работ, информация о фактическом состоянии проектируемых объектов.

Блок 8. Логика (Имеются ли отклонения от плана? Если „Да”, то переход к блоку 1, если „Нет” - к блоку 7).

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

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

В качестве исходных данных задаются:

-   плановый период;

-   номенклатура объектов;

-   соответствующие технологическое модели;

-  временные и стоимостные оценки этих моделей в натуральных единицах или относительных процентах от общей продолжительности;

-   стоимости объекта как детерминированные, неотрицательные величины.

Математическая модель задачи имеет вид:

,

где  - весовой коэффициент относительной ценности сглаживания ресурса  - го вида;  - график использования ресурсов  - го вида в текущий момент  реализации календарного плана .

Ограничения модели:

1.                           Исходный план должен включать все множества работ проектируемых объектов организации в планируемый период

, ,

где  -  – тый объект тематического плана;  - работа, принадлежащая множеству работ технологической модели  – го объекта.

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

,

где  - заданное директивное время наступления ;  - подмножество событий, время наступления которых задано директивно.

3.                           Технологические временные ограничения, соответствующие топологии технологических моделей. Технологически допустимым календарным планом назовем вектор , компоненты которого удовлетворяют ограничениям:

 ; ,

где , - соответственно время начала и продолжительность выполнения работы.

Вектор  содержит  компонент ( – число работ в моделях всех объектов, т.е. число элементов множества ).

4.                           Ресурсные ограничения. В каждый момент планового периода число проектировщиков по каждой из специальностей данной организации не должно превышать имеющегося в наличии:

,    .

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

, ,

где  - количество ресурсов вида , необходимое в каждый момент времени  для выполнения работы , определяемое по формуле

,

где  – общая стоимость всех работ объекта ;  – относительный процент стоимости работы  от общей стоимости объекта;  – средняя для планового периода выработка единицы ресурса  - ой специальности.

Множество работ объекта  разбито на непересекающиеся подмножества  таким образом, чтобы выполнялись условия:

, ,  .

Фиктивные работы, а также работы типа «ожидание», не требующие ресурсов, принадлежат подмножеству .

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

; ,

где  – плановое задание по стоимости проектных работ, выполняемых в  - том отчетном периоде ;  - время начала отчетного периода;  - время окончания отчетного периода.

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

Если  - сметная стоимость работ каждого раздела проекта, то и стоимость всего проекта  будет

.

Для того, чтобы плановые задания по сметной стоимости проектных работ и номенклатур объектов тематического плана не находились в противоречии, необходимо выполнение условия

.

Полученные результаты.

Для решения задачи календарного планирования с использованием ЭВМ могут быть использованы приведенные ниже комплексы эвристических алгоритмов.

Первый комплекс. Основан на „методе ветвлений” и состоит в следующем. Множество всех работ   планируемого периода разбивается на  подмножеств
( – число отчетных периодов в планируемом). Каждое подмножество  включает в себя работы, которые будут выполняться полностью или частично в s – том отчетном периоде. Декомпозиция задачи на подзадачи, соответствующее отчетным периодам, позволяет учесть плановые ограничения на сметную стоимость проектных работ и производить пересчет отдельных вариантов планов в процессе оперативного управления не на весь планируемый период, а на ближайший. Этот комплекс включает два этапа, первый из которых предназначен для стадии формирования и анализа годового тематического плана работ проектной организации.

Алгоритм первого этапа согласовывает время выполнения отдельных проектов с директивными сроками и одновременно производит распределение проектных работ по кварталам и месяцам с целью оптимизации суммарной загрузки трудоресурсов по критерию равномерности. Качество декомпозиции задачи календарного планирования процесса проектирования на первом этапе алгоритма оценивается следующим критерием:

,

где  - суммарное количество ресурсов времени (человеко-дней), необходимое для выполнения работ  - го отчетного периода ресурсами  - го вида:

 , ,

где  - средняя трудоемкость  - го вида ресурсов в  - том отчетном периоде:

, , .

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

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

Последовательность действий для включения объекта в план следующая:

-   моделирование начала выполнения объекта;

-   определение загруженности каждого вида трудоресурсов при выполнении работ по заданному объекту;

-   суммирование одноименных трудоресурсов при выполнении работ по всем объектам;

-   вычисление критерия оптимальности.

Начало выполнения объекта определяется по формуле

,

где  и  - соответственно ранний и поздний сроки начала проектирования объекта;  - случайная величина, различно распределенная на отрезке 0,1 для объектов с различными приоритетами.

Так, для первого приоритета e распределена с плотностью ; для второго приоритета принято распределение случайной величины с плотностью

Для третьего и четвертого приоритетов  распределена на заданном отрезке равномерно

Выводы.

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

2. Предлагаемые алгоритмы при их программной реализации на ЭВМ обеспечивают непрерывность процесса планирования с обхватом всего объема проектных работ в заданный период.

1.                  Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы календарного планирования. – К.: Техника, 1980. – С. 20-25.

2.                  Первин Ю.А., Португал В.М., Семенов А.И. Планирование мелкосерийного производства в АСУП. – М.: Наука, 1973. – С. 16-32.

3.                  Перовская Е.И. Об одном алгоритме решения задачи календарного планирования // Вычислительные процессы и структуры. – Л.: Машиностроение, 1982.
С. 84-92.

4.                  Джостон Д.Ж. Экономические методы. – М.: Статистика, 1980. – 444 с.

5.                  Математические вопросы кибернетики / Под ред. С.В. Яблонского. – М.: Наука. – Вып. 4, 1992. – 239 с.

6.                  Бирин Ю.Н., Звягинцева О.Л., Клевицкий Г.С. и др. Микро-ЭВМ в управлении строительством. – М.: Строиздат, 1989. – 296 с.