Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 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. Предлагаемые алгоритмы при их программной реализации на ЭВМ обеспечивают непрерывность процесса планирования с обхватом всего объема проектных работ в заданный период.

 

One of possible approaches of decision of task of the calendar planning with the using of heuristic algorithms is represented in the article.

 

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

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

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

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

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

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

 





Ответы на вопросы [_Задать вопроос_]

Информационно-управляющие комплексы и системы

Теленик С.Ф., Ролік О.І., Букасов М.М., Андросов С.А. Генетичні алгоритми вирішення задач управління ресурсами і навантаженням центрів оброблення даних

Богушевский В.С., Сухенко В.Ю., Сергеева Е.А., Жук С.В. Реализация модели управления конвертерной плавкой в системе принятия решений

Бень А.П., Терещенкова О.В. Применение комбинированных сетевых методов планирования в судоремонтной отрасли

Цмоць І. Г., Демида Б.А., Подольський М.Р. Методи проектування спеціалізованих комп’ютерних систем управління та обробки сигналів у реально-му час

Теленик С.Ф., РолікО.І., Букасов М.М., РимарР.В., Ролік К.О. Управління навантаженням і ресурсами центрів оброблення даних при виділених серверах

Селякова С. М. Структура інтелектуальної системи управління збиральною кампанією

Еременко А.П., Передерий В.И. Принятие решений в автоматизированных системах с учетом психофункциональных характеристик оператора на основе генетических алгоритмов

Львов М.С. Алгоритм перевірки правильності границь змінення змінних у послідовних програмах

Ляшенко Е.Н. Анализ пожарной опасности сосновых насаждений в зоне Нижне-днепровских песков – самой большой пустыни в Европе

Кучеров Д.П., Копылова З.Н. Принципы построения интеллектуального автору-левого

Касаткина Н.В., Танянский С.С., Филатов В.А. Методы хранения и обработки нечетких данных в среде реляционных систем

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Применение когнитивного подхода для решения задачи поддержки принятия управленческих решений при ликвидации лесных пожаров

Гончаренко А.В. Моделювання впливу ентропії суб’єктивних переваг на прийняття рішень стосовно ремонту суднової енергетичної установки

Фарионова Н.А. Системный подход построения алгоритмов и моделей систем поддержки принятия решений при возникновении нештатных ситуаций

Биленко М.С., Серов А.В., Рожков С.А., Буглов О.А. Многоканальная система контроля качества текстильных материалов

Мотылев K.И., Михайлов M.В., Паслен В.В. Обработка избыточной траекторной информации в измерительно-вычислительных системах

Гончаренко А.В. Вплив суб’єктивних переваг на показники роботи суднової енергетичної установки

Гульовата Х.Г., Цмоць І.Г., Пелешко Д.Д. Архітектура автоматизованої системи моніторингу і дослідження характеристик мінеральних вод

Соломаха А.В. Разработка метода упреждающей компенсации искажений статорного напряжения ад, вносимых выходными силовыми фильтрами

ПотапенкоЕ.М., Казурова А.Е. Высокоточное управление упругой электромеханической системой с нелинейным трением.

Кузьменко А.С., Коломіц Г.В., Сушенцев О.О. Результати розробки методу еквівалентування функціональних особливостей fuzzy-контролерів

Кравчук А. Ф., Ладанюк А.П., Прокопенко Ю.В. Алгоритм ситуационного управления процессом кристаллизации сахара в вакуум-аппарате периодического действия с механическим циркулятором

Абрамов Г.С., Иванов П.И., Купавский И.С., Павленко И.Г. Разработка навигационного комплекса для автоматического наведения на цель системы груз-управляемый парашют

Литвиненко В.И., Четырин С.П. Компенсация ошибок оператора в контуре управления следящей системы на основе синтезируемых вейвелет-сетей

Бардачев Ю.Н., Дидык А.А. Использование положений теории опасности в искусственных иммунных системах

Рожков С.О., Кузьміна Т.О., Валько П.М. Інформаційна база як основа для створення асортименту лляних виробів.

Ускач А.Ф., Становский А.Л., Носов П.С. Разработка модели автоматизированной системы управления учебным процессом

Мазурок Т.Л., Тодорцев Ю.К. Актуальные направления интеллектуализации системы управления процессом обучения.

Ускач А.Ф., Гогунский В.Д., Яковенко А.Е. Модели задачи распределения в теории расписания.

Сідлецький В.М., Ельперін І.В., Ладанюк А.П. Розробка алгоритмів підсистеми підтримки прийняття рішень для контролю якості роботи дифузійного відділення.

Пономаренко Л.А., Меликов А.З., Нагиев Ф.Н. Анализ системы обслуживания с различными уровнями пространственных и временных приоритетов.

Коршевнюк Л.О. Застосування комітетами експертів системи нечіткого логічного виводу із зваженою істинністю.. – С. 73 – 79.

Кирюшатова Т.Г., Григорова А.А Влияние направленности отдельных операторов и направленности всей группы на конечный результат выполнения поставленной задачи.

Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д деяких засобів паралельного програмування пакету МРІСН.

Ходаков В.Е., Граб М.В., Ляшенко Е.Н. Структура и принципы функционирования системы поддержки принятия решений при ликвидации лесных пожаров на базе новых геоинформационных технологий.

Сидорук М.В., Сидорук В.В. Информационные системы управления корпорацией в решении задач разработки бюджета.

Нагорный Ю.И. Решение задачи автоматизированного расчета надежности иасуп с использованием модифицированного метода вероятностной логики

Козак Ю.А. Колчин Р.В. Модель информационного обмена в автоматизированной системе управления запасами материальных ресурсов в двухуровневой логистической системе

Гожий А.П., Коваленко И.И. Системные технологии генерации и анализа сценариев

Вайсман В.А., Гогунский В.Д., Руденко С.В. Формирование структур организационного управления проектами

Бараненко Р.В., Шаганян С.М., Дячук М.В. Аналіз алгоритмів взаємних виключень критичних інтервалів процесів у розподілених системах

Бабенко Н.И., Бабичев С.А. Яблуновская Ю.А. Автоматизированная информационная система управления учебным заведением

Яковенко А.Е. Проектирование автоматизированных систем принятия решений в условиях адаптивного обучения с учетом требований болонского процесса

Бараненко Р.В Лінеаризація шкали і збільшення діапазону вимірювання ємностей резонансних вимірювачів

Головащенко Н.В. Математичні характеристики шумоподібно кодованих сиг-налів.

Шерстюк В.Г. Формальная модель гибридной сценарно-прецедентной СППР.

Шекета В.І. Застосування процедури Append при аналізі абстрактних типів даних модифікаційних запитів.

Цмоць І.Г. Алгоритми та матричні НВІС-структури пристроїв ділення для комп'-ютерних систем реального часу.

Бараненко Р.В., Козел В.Н., Дроздова Е.А., Плотников А.О. Оптимизация рабо-ты корпоративных компьютерных сетей.

Нестеренко С.А., Бадр Яароб, Шапорин Р.О. Метод расчета сетевых транзакций абонентов локальных компьютерных сетей.

Григорова А.А., Чёрный С. Г. Формирование современной информационно-аналитической системы для поддержки принятия решений.

Шаганян С.Н., Бараненко Р.В. Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ

Орлов В.В. Оценка мощности случайного сигнала на основе корреляционной пространственной обработки

Коджа Т.И., Гогунский В.Д. Эффективность применения методов нечеткой логики в тестировании.

Головащенко Н.В., Боярчук В.П. Аппаратурный состав для улучшения свойств трактов приёма – передачи информации в системах промышленной автоматики.