Содержание

1 ВВЕДЕНИЕ
1.1 Актуальность разработки компьютеризированной подсистемы планирования оптимальной загрузки оборудования
1.2 Цели и задачи работы
1.3 Научная новизна и практическая ценность
Анимированное представление процесса
2 ОБЗОР СУЩЕСТВУЮЩИХ ПОДСИСТЕМ
2.1 Модуль оперативно-календарного планирования в системе Omega Production
2.1.1 Исходные данные для оперативно-календарного планирования
2.1.2 Моделирование производственной программы
2.1.3 Мониторинг хода производства
2.2 Интегрированная система технологической подготовки, оперативного планирования и диспетчерского контроля «ФОБОС»
3 МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ОПЕРАТИВНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ
3.1 Генетические алгоритмы
3.2 Метод ветвей и границ
3.3 Основы теории расписаний
4 ПРЕДПОЛАГАЕМЫЕ РЕЗУЛЬТАТЫ
ВЫВОДЫ
Источники

1 ВВЕДЕНИЕ

вверх

      Как показывает опыт, задачи организационно-технологического управления наиболее трудно поддаются автоматизации. Для предприятий машиностроительной отрасли особенно актуальна проблема автоматизации оперативно-календарного планирования в гибких производственных системах (ГПС). Причиной этого является разнообразие парка оборудования и показное планирование, характерные для таких предприятий. ГПС - система, обладающая способностью быстро перестраиваться на обработку новых деталей в пределах, определяемых техническими возможностями оборудования и технологией обработки группы деталей. Таким образом, имеются значительные резервы для повышения эффективности за счет совершенствования системы оперативно-календарного планирования в ГПС.
      К настоящему времени на рынке программных продуктов присутствует значительное количество комплексных систем управления предприятием. Однако, в силу большого количества факторов, влияющих на процесс планирования конкретного производства, такие системы способны производить оптимизацию планов лишь по одному - двум критериям. С развитием современных математических методов (экспертные системы, генетические алгоритмы, нейронные сети) появилась возможность в автоматизированных системах планирования эвристических правил и знаний человека-оператора.
      Целью построения подсистемы является повышение эффективности работы механического цеха вследствие использования компьютеризированной подсистемы оперативно-календарного планирования, учитывающей текущую производственную ситуацию. Одним из существенных резервов повышения эффективности гибких станочных систем является сокращение непроизводственного времени в ГПС путем оптимизации расписания работ в течение оперативного срока планирования.
      Анализ структуры непроизводственного времени для ГПС механической обработки показал, что наиболее существенными составляющими потерь времени являются: время, затрачиваемое на операциях переналадок отдельных гибких производственных модулей (ГПМ) при поступлении партии деталей другого наименования на операцию, выполняемую данным ГПМ (так называемой партияоперации); время, затрачиваемое на транспортирование партий деталей к ГПМ; время простоев ГПМ из-за ожидания конца обработки партияоперации на предыдущей операции, осуществляемой на другом ГПМ.

1.1 Актуальность разработки компьютеризированной подсистемы планирования оптимальной загрузки оборудования

вверх

      Равномерная работа и ритмичный выпуск продукции определяются многими условиями. К их числу принадлежат методы организации производства, своевременное проведение его технической подготовки, тесная увязка программы выпуска продукции с планом освоения новых изделий и освоения вновь вводимых мощностей. Большое значение для организации ритмичной работы имеют четко организованное материально-техническое снабжение и обеспечение кооперированных поставок, нормирование расхода и отпуска материалов цехам и на рабочие места, обоснованное определение резервных и оборотных запасов.
      Таким образом, созданы предпосылки для постепенного совершенствования системы оперативно-календарного планирования и ритмичного выпуска продукции каждым предприятием. Эти предпосылки должны быть в полной мере использованы в процессе планирования.
      На машиностроительном предприятии планирование работы механического цеха имеет наибольшую важность. Ведь средний коэффициент загрузки оборудования мелкосерийного и единичного производств составляет 0,45. Иначе говоря, более половины рабочего времени современное дорогостоящее оборудование стоит на производственных площадях мертвым капиталом, не принося прибыли и морально устаревая. Этот показатель одинаково справедлив в отношении предприятий в любой точке мира и неизбежно останется таковым, если не применять каких-то специальных методов, способствующих более полной загрузке оборудования.
      В производстве выбор последовательности (когда для каждого из заказов будет изготовлена единица комплекта, например, втулка) может оказать существенное влияние на конечный результат. Конечно, можно взять первую попавшуюся деталь и точить ее на станке несколько часов, а тем временем, в ожидании завершения операции, будет простаивать остальное оборудование, причем общее время простоя со временем будет расти как снежный ком. А можем изменить последовательность выполнения заказа и полностью или частично исключить простой станочного парка. Это принципиальный момент: хорошо известно, что потеря одного часа на критической операции влечет за собой потерю одного часа работы всей производственной системы.
      Одним из основных путей повышения коэффициента загрузки оборудования является составление производственного расписания его работы, контроль выполнения и оперативная коррекция расписания.
      Но эта задача является достаточно сложной, так как для оптимизации загрузки станков требуется учитывать значительное количество условий и ограничений. К основным ограничениям относятся: капитальные ремонты оборудования, длительности циклов обработки деталей, количество транспортных средств, применяемых для перевозки партияопераций между отдельными ГПМ, ГПМ и складом.

1.2 Цели и задачи работы

вверх

      Целью данной работы является повышение эффективности работы гибких производственных систем механообработки в машиностроении за счет составления локально оптимального расписания работы ГПС на уровне цеха.
      Основными задачами оптимизации расписания являются:

• последовательности запуска деталей в производство;
• обоснование выбранных критериев оптимизации;
• оценка адекватности модели.

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

1.3 Научная новизна и практическая ценность

вверх

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

2 ОБЗОР СУЩЕСТВУЮЩИХ ПОДСИСТЕМ

2.1 Модуль оперативно-календарного планирования в системе Omega Production

вверх

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

2.1.1 Исходные данные для оперативно-календарного планирования

      Исходными данными для расчета расписания производственных ресурсов являются:

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

2.1.2 Моделирование производственной программы

      В модуле оперативно-календарного планирования Omega Production также используется эвристический алгоритм формирования расписания. Управление качеством расписания при использовании эвристических алгоритмов производится через манипулирование параметрами алгоритма. Примеры таких параметров — загрузка оборудования, приоритет партий, точность определения производственных ресурсов и т.д. Для каждого параметра выделяется перечень возможных значений. Так, пример возможных значений для параметра «загрузка оборудования» — это равномерная загрузка, максимальный коэффициент загрузки и т.д.
      По результатам моделирования получается несколько вариантов производственной программы, которые нужно сравнить и выбрать наиболее соответствующий производственной ситуации вариант. Сравнение производится на основе численных оценок качества расписания. В системе используются следующие критерии оценки качества варианта расписания:

• задержка производства по расписанию по сравнению с установленными сроками выполнения заказов;
• величина времени межоперационного прослеживания изделий;
• коэффициент загрузки оборудования;
• длительность производственного цикла изделия/заказа;
• глобальный резерв времени (максимальное время, на которое может изменяться время выполнения операции без изменения сроков выпуска конечного изделия).

      После оценки и выбора наиболее подходящего варианта данные производственного расписания переносятся в действующую производственную программу.

2.1.3 Мониторинг хода производства

      Контроль хода производства при оперативно-календарном планировании осуществляется обычно с точностью до технологической операции — через отслеживание закрытия нарядов сменных заданий либо через отслеживание прохождения изделия в производстве на основании данных маршрутных листов. Для реализации мониторинга хода производства необходимо формирование директивных заданий по рабочим местам (сменных заданий и/или маршрутных листов) и ведение данных о фактическом ходе производства (по закрытию нарядов сменных заданий и/или внесению данных о выполнении технологических операций в маршрутные листы).
      Наряды сменных заданий формируются системой автоматически, на основании данных производственной программы. Наряду с формированием нарядов сменных заданий автоматически формируются сменные задания и маршрутные листы изделий. Исполнителем наряда сменного задания является работник из состава производственного персонала, которого предлагает система или назначает мастер.
      При закрытии нарядов сменных заданий указываются фактические сроки выполнения технологических операций над партиями изделий. Эта информация используется системой для представления фактического хода производства в составе производственной программы.
      Маршрутные листы, как и наряды сменных заданий, тоже формируются автоматически — на основании данных производственной программы. В них указываются плановая трудоемкость по производственным операциям и производственные ресурсы, которые задействованы при выполнении партия-операции. Рабочие, выполняющие операции, вносят в маршрутные листы информацию о фактическом выполнении операций с указанием времени начала и окончания, а также фактически задействованных производственных ресурсов.
      Цеха предприятия могут быть неоднородными по типу производства, то есть в рамках одного предприятия могут существовать цеха с массовым, серийным, мелкосерийным и единичным производством. Но это не является препятствием для оперативного учета в производстве для системы Omega Production, так как она позволяет гибко настроить систему учета для различных видов производства.
      В процессе производства может возникать отставание от графика работ, определенного производственной программой. Это отставание может быть обусловлено разными причинами: не всегда удается вовремя обеспечить производство требуемыми материалами и комплектующими, инструментом, учесть человеческий фактор, сбои в работе оборудования и т.п. И если не корректировать производственную программу, то увеличение отклонения фактических сроков выполнения операций от плановых приведет к невозможности использовать составленное расписание. Поэтому в модуле оперативно-календарного планирования реализован механизм корректировки производственного расписания, то есть производственная программа приводится в соответствие с фактическим ходом производства с заданной периодичностью.

2.2 Интегрированная система технологической подготовки, оперативного планирования и диспетчерского контроля «ФОБОС»

вверх

      Для решения задач оптимальной загрузки оборудования на единичных и мелкосерийных производствах в настоящее время успешно применяется система календарного планирования и диспетчерского контроля «ФОБОС», продвигаемая на рынке информационных технологий компанией ООО «Агентство индустриального развития».
      Система «ФОБОС» состоит из двух основных подсистем: «Внутрицеховой технологической подготовки производства» и «Оперативного календарного планирования и диспетчерского контроля».
      Модуль оперативного планирования и диспетчерского контроля системы «ФОБОС» обеспечивает компьютерную поддержку принятия оперативных решений на уровне цеха.
      Целью рассматриваемой системы «ФОБОС» является оперативное управление и диспетчерский контроль именно на цеховом уровне.
      Основные функции подсистемы:

• Формирование и коррекция оперативных производственных планов цеха с учетом имеющихся межоперационных заделов и текущего состояния станочной системы.
• Расчет производственного расписания загрузки оборудования по различным критериям (100 комбинаций из 14 критериев).
• Формирование сменно-суточных заданий на рабочие места цеха.
• Формирование оперативных маршрутных карт по всем партиям запуска с контролем их прохождения по рабочим местам.
• Составление и автоматическая коррекция планово-учетного графика изготовления комплектов деталей с контролем готовности каждой партии запуска.

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

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

      Распределение заданий на рабочие места и автоматизированный контроль за выполнением технологических операций осуществляется в системе «ФОБОС» на основании оформления традиционных рабочих нарядов. Последние выписываются компьютером в соответствии с текущим производственным расписанием.
      Диспетчер, в случае необходимости, может скорректировать расписание. Для этого в его распоряжении имеется широкий набор соответствующих эффективных вычислительных алгоритмов, позволяющих реализовать 100 комбинаций из 14 типичных производственных критериев.
      Производственное расписание наглядно описывается диаграммой Ганта, где каждой операции ставится в соответствие отрезок прямой, длина которого пропорциональна ее длительности. Эти отрезки, именуемые линиями Ганта, располагаются напротив инвентарных номеров основного технологического оборудования в последовательности, соответствующей производственному расписанию.
      В системе реализован принцип непрерывного имитационного моделирования движения материальных потоков. Встроенный таймер, синхронизированный с таймером компьютера, осуществляет в реальном времени сдвиг шкалы. В автоматическом режиме все линии Ганта на диаграмме через каждые 5 минут сдвигаются вместе с временной шкалой. При этом оборудование переводится в состояние, соответствующее рассчитанному производственному расписанию (от наладки к обработке, от обработки к ожиданию либо наладке на следующую операцию и т.п.). Таким образом, происходит процесс имитационного моделирования материальных потоков в реальном масштабе времени при условии, что отсутствуют сбои в работе оборудования.
      Следует, однако, заметить, что очень большая часть технологических операций выполняется на универсальном оборудовании. В таких случаях нормы времени на обработку соответствующих деталей вносятся технологом вручную (для этих целей в системе имеется удобный пользовательский интерфейс). Человек, как известно, может внести в систему и неточные данные. Именно с человеческим фактором, а также с качеством режущего инструмента связаны основные нарушения производственного расписания: на универсальном станке рабочий очень часто либо заканчивает операцию раньше запланированного срока, либо не укладывается в отведенный ему технологический норматив. Это может вызывать лавинообразный рост простоев на других рабочих местах. Дальнейшая работа цеха по такому расписанию возможна только при соответствующей компьютерной поддержке и надлежащем диспетчерском контроле.
      Детальное календарное планирование производства с указанием времен начала и конца каждой деталеоперации, выполняемой на конкретном рабочем месте, позволяет построить гистограмму реальной посменной и почасовой загрузки технологического оборудования.
      В настоящее время система «ФОБОС» внедрена на большом количестве заводов России и стран ближнего зарубежья, в Германии, Китае. Среди пользователей системы «ФОБОС» имеются такие машиностроительные предприятия как:

1. Машиностроительный завод МЕГОМ г. Витебск

2. Завод тяжелого станкостроения (АО Коломенский ЗТС) г. Коломна

3. Машиностроительный завод ММЗ (АО МетровагонМаш) г. Мытищи

4. Ремонтно-механический завод МАРС (АО Магнитогорский металлургический комбинат) г. Магнитогорск

5. Малаховский механический завод (ГлавУглеМаш) г. Малаховка

6. Гаврилов-Ямский машиностроительный завод «АГАТ» г. Ярославль и др.

      Недостатками рассмотренных систем являются:

• высокая стоимость покупки;

• проблемы внедрения из-за несоответствия конфигурации систем с поставленной задачей;

• затруднения сопровождения продукта в связи с территориальной отдаленностью.

3 МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ОПЕРАТИВНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ

3.1 Генетические алгоритмы

вверх

       Одними из современных методов оптимизации, основанных на эвристических алгоритмах, являются генетические алгоритмы.
      
      Генетический алгоритм был получен в процессе обобщения и имитации в искусственных системах таких свойств живой природы, как естественный отбор, приспособляемость к изменяющимся условиям среды, наследование потомками жизненно важных свойств от родителей и т.д. Так как алгоритм в процессе поиска использует некоторую кодировку множества параметров вместо самих параметров, то он может эффективно применяться для решения задач дискретной оптимизации, определённых как на числовых множествах, так и на конечных множествах произвольной природы. Поскольку для работы алгоритма в качестве информации об оптимизируемой функции используются лишь её значения в рассматриваемых точках пространства поиска и не требуется вычислений ни производных, ни каких-либо иных характеристик, то данный алгоритм применим к широкому классу функций, в частности, не имеющих аналитического описания. Использование набора начальных точек позволяет применять для их формирования различные способы, зависящие от специфики решаемой задачи, в том числе возможно задание такого набора непосредственно человеком.
      Сила генетических алгоритмов в том, что этот метод очень гибок, и, будучи построенным в предположении, что об окружающей среде нам известен лишь минимум информации (как это часто бывает для сложных технических систем), алгоритм успешно справляется с широким кругом проблем, особенно в тех задачах, где не существует общеизвестных алгоритмов решения или высока степень априорной неопределенности.
      Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей - стрингов (хромосом). Затем ГА применяет множество простых операций к начальной популяции и генерирует новые популяции.
      ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация.
      Репродукция - процесс, в котором хромосомы копируются согласно их целевой функции (ЦФ). Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР), является искусственной версией натуральной селекции, «выживания сильнейших» по Дарвину.
      После выполнения ОР оператор кроссинговера (ОК) может выполниться в несколько шагов. На первом шаге выбираются члены нового репродуцированного множества хромосом. Далее каждая пара хромосом (стрингов) пересекается по следующему правилу: целая позиция k вдоль стринга выбирается случайно между l и длиной хромосомы минус единицу т.е. в интервале (1,L-1). Длина L хромосомы это число значащих цифр в его двоичном коде. Число k, выбранное случайно между первым и последним членами, называется точкой ОК или разделяющим знаком.
      Механизм ОР и ОК включает случайную генерацию чисел, копирование хромосом и частичный обмен информацией между хромосомами.
      Генерация ГА начинается с репродукции. Мы выбираем хромосомы для следующей генерации, вращая колесо рулетки, такое количество раз, которое соответствует мощности начальной популяции. Величину отношения Fi(x)/SumF(x) называют вероятностью выбора копий (хромосом) при ОР и обозначают Pi(OP). Здесь Fi(x) - значение ЦФ i-той хромосомы в популяции, SumF(x) - суммарное значение ЦФ всех хромосом в популяции. Величину Pi(OP) также называют нормализованной величиной. Ожидаемое число копий i-ой хромосомы после ОР определяют N=Pi(OP)*n. Здесь n - число анализируемых хромосом.
      Число копий хромосомы, переходящее в следующее положение, иногда определяют на основе выражения:
Ai=Fi(x)/СреднееFi(x) .
      Далее, согласно схеме классического ПГА, выполняется оператор мутации. Считают, что мутация - вторичный механизм в ГА.
      Понятие «схема» (схемата), согласно Холланду, есть шаблон, описывающий подмножество стрингов, имеющих подобные значения в некоторых позициях стринга. Для этого вводится новый алфавит {0,1,*}, где * - означает: не имеет значения 1 или 0. Для вычисления числа схем или их границы в популяции требуются точные значения о каждом стринге в популяции.
      Для количественной оценки схем введены 2 характеристики: порядок схемы - О(H); определенная длина схемы - L(H). Порядок схемы - число закрепленных позиций (в двоичном алфавите - число единиц и нулей), представленных в шаблоне.
      Предположим, что заданы шаг (временной) t, m примеров частичных схем H, содержащихся в популяции A(t). Все это записывают как m=m(H,t) - возможное различное число различных схем H в различное время t. В течение репродукции стринги копируются согласно их ЦФ или более точно: стринг A(i) получает выбор с вероятностью, определяемой Pi(OP). После сбора непересекающихся популяций размера n с перемещением из популяции A(t) мы ожидаем иметь m(H,t+1) представителей схемы H в популяции за время t+1. Это вычисляется уравнением:
       m(H,t+1)=m(H,t)*n*f(H)/sum[f(j)]      (3.1)
где f(H) - есть средняя ЦФ стрингов, представленных схемой H за время t.
      Если обозначить среднюю ЦФ всей популяции как f`=sum[f(j)]/n, тогда
       m(H,t+1)=m(H,t)*f(H)/f`       (3.2)
       Правило репродукции Холланда: схема с ЦФ выше средней «живет», копируется и с ниже средней ЦФ «умирает».
       Предположим, что схема H остается с выше средней ЦФ с величиной c*f`, где c - константа. Тогда выражение (3.2) можно модифицировать так
       m(H,t+1)=m(H,t)*(f`+c*f`)/f`=(1+c)*m(H,t)       (3.3)
       Некоторые исследователи считают, что репродукция может привести к экспоненциальному уменьшению или увеличению схем, особенно если выполнять генерации параллельно.
      Отметим, что если мы только копируем старые структуры без обмена, поисковое пространство не увеличивается и процесс затухает. Потому и используется ОК. Он создает новые структуры и увеличивает или уменьшает число схем в популяции.
      Очевидно, что нижняя граница вероятности выживания схемы после применения ОК может быть вычислена для любой схемы. Так как схема выживает, когда точка ОК попадает вне «определенной длины», то вероятность выживания для простого ОК запишется
       P(s)=1-L(H)/(L-1)       (3.4)
       Если ОК выполняется посредством случайного выбора, например, с вероятностью P(ОК), то вероятность выживания схемы определится
       P(s)=1-P(ОК)*L(H)/(L-1)       (3.5)
       Допуская независимость репродукции (ОР) и ОК, получим:
       m(H,t+1)=m(H,t)*f(H)/f`*[1-P(ОК)*L(H)/(l-L)]       (3.6)
       Из выражения (3.6) следует, что схемы с выше средней ЦФ и короткой L(H) имеют возможность экспоненциального роста в новой популяции. Рассмотрим влияние мутации на возможности выживания.
      ОМ есть случайная альтернативная перестановка элементов в стринге с вероятностью Р(ОМ). Для того, чтобы схема H выжила, все специфические позиции должны выжить. Следовательно, единственная хромосома выживает с вероятностью (1-P(ОМ)) и частная схема выживает, когда каждая из l(H) закрепленных позиций схемы выживает.
      Тогда мы ожидаем, что частная схема H получает ожидаемое число копий в следующей генерации после ОР, ОК ОМ
       m(H,t+1) > m(H,t)*f(H)/f`*[1-Р(ОК)*l(H)/(l-1)-l(H)*P(ОМ)]      (3.7)
       Это выражение называется «схема теорем» или фундаментальная теорема ГА.
       Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ, нет или он расплывчатый, или каждый раз зависит от конкретной задачи.
      Основная теорема ГА, приведенная Холландом, показывает ассимптотическое число схем «выживающих» при реализации ПГА на каждой итерации. Очевидно,что это число, конечно приблизительное и меняется в зависимости от вероятности применения ГА. Особенно сильное влияние на число «выживающих» и «умирающих» схем при реализации ПГА оказывает значение целевой функции отдельной хромосомы и всей популяции.
      Во многих проблемах имеются специальные знания, позволяющие построить аппроксимационную модель. При использовании ГА это может уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.

3.2 Метод ветвей и границ

вверх

      Метод ветвей и границ — один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
      Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
      Алгоритм решения:
       Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X₀. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и F_max = F(X₀).
      Если же среди компонент плана X₀ имеются дробные числа, то X₀ не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X₀)>=F(X) для всякого последующего плана X.
      Предполагая, что найденный оптимальный план X₀ не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X₀ дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу + 1. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования:

       Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:
       1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
       2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
       3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.
      Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).
       4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).
      Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану X₀ задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.
      Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:
       1. Находят решение задачи линейного программирования (1)-(3).
       2. Составляют дополнительные ограничения для одной из пере-менных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
      3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
     4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
       Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.

3.3 Основы теории расписаний

вверх

      Качество функционирования современного производства во многом определяется решениями, принимаемыми на этапах календарного планирования и оперативного управления. Особенно это актуально в связи с созданием современных автоматизированных производств – гибких производственных систем (ГПС). Системы оперативно – календарного планирования современных производств строятся в том числе и на достижениях так называемой «теории расписаний».
    Теория расписаний – это наука, занимающаяся исследованиями детерминированных обслуживающих систем на предмет оптимизации расписаний их функционирования.
    Примеры таких систем:

• цех, участок, на станках которых осуществляется обработка деталей;

• ВУЗ, где преподаватели обучают студентов и т.д.

    В любом случае имеется конечное множество требований (деталей, преподавателей и т.д.) N={1,2,...,n} и конечное множество приборов (станков, групп студентов и т.д.) M={1,2,...,m}.
    Предполагается, что i – е требование на каждой стадии его обслуживания q (например, на каждой операции технологического процесса) может быть обслужено любым из приборов L є M(но не более, чем одним одновременно). Предполагается также, что каждый прибор одновременно может обслуживать не более одного требования. В теории расписаний рассматриваются различные системы обслуживания:
    В теории расписаний рассматриваются различные системы обслуживания:

• системы поточного типа, в которых каждое требование i є N сначала обслуживается приборами первой группы , затем второй группы и т.д. пока не будет обслужено приборами последней r – ой группы;

• системы с различными порядками (маршрутами) прохождения приборов требованиями и т.д.

    В частности, в последних системах с последовательными приборами для каждого требования i є N задается своя, специфическая для этого требования последовательность Lⁱ=(Lⁱ₁,Lⁱ₂,...,Lⁱ_n) его обслуживания приборами. Требование i сначала обслуживается прибором Lⁱ₁, затем Lⁱ₂ и т.д. пока не будет обслужено прибором Lⁱ_n. Последовательности обслуживания могут быть различными для разных требований и могут содержать повторение приборов.
    В любом случае, если требование i на стадии q должно или может быть обслужено прибором L=Lⁱ_q, то предполагается заданной длительность t_iL>=0 его обслуживания прибором. Запись t_iL=0, как привило, означает, что по условию задачи требование i на стадии q прибором L не обслуживается.
    Наряду с величинами t_iL могут быть заданы также: момент d_i>=0 поступления требования i в систему; директивный срок D_i>0, к которому необходимо завершить обслуживание требования.
    Процесс функционирования обслуживающей системы может быть описан путем задания расписания (календарного плана, временного графика и т.п.).
    Расписание – некоторая совокупность указаний относительно того, какие именно требования какими именно приборами обслуживаются в каждый момент времени.
    Расписание рассматривается как совокупность {S₁(t),S₂(t),...,S_m(t)} кусочно–постоянных непрерывных слева функций, каждая из которых задана на интервале 0≤t≤∞ и принимает значения 0, 1, …, n.
    Если S_L(t^')=i≠0 (здесь i – номер требования), то в момент времени t^' прибор L є M обслуживает требование i є N. Если S_L(t^')=0, то в момент времени t^' прибор L простаивает.
    При задании расписания должны соблюдаться все условия и ограничение, вытекающие из постановки рассматриваемой задачи, т.е. расписание должно быть допустимым.
    Пример. На рис.1 приведен график расписания S_i(t), i є N обслуживания требований N={1,2,3,4} приборами M={1,2,3} при различных маршрутах обслуживания требований. Все длительности обслуживания равны «1».


Рис.1. График расписания обслуживания требований N = {1, 2, 3, 4} приборами M = {1, 2, 3}

     Здесь L¹=(1,2), т.е. первое требование обслуживается первым и вторым приборами, L²=(3,2) – второе требование обслуживается третьим и вторым приборами, L³=(2,1,2,3) – третье требование обслуживается вторым, первым, снова вторым и третьим приборами, L⁴=(2,3,1) - четвертое требование обслуживается вторым, третьим и первым приборами. d₁=1 – момент поступления требования 1 в систему, d₂=d₃=0 – моменты поступления требований 2 и 3 в систему, d₄=2 – момент поступления требования 4 в систему. D₁=4 – директивный срок завершения обслуживания требования 1, D₂=2 – директивный срок завершения обслуживания требования 2, D₃=6 – директивный срок завершения обслуживания требования 3, D₄=5 – директивный срок завершения обслуживания требования 4.
    Прибор 1 во временном интервале (1,2] обслуживает требование 1, в интервале (2,3] - требование 3, в интервале (4,5] - требование 4. Прибор 2 в интервале (0,5] без простоев обслуживает требования 3, 2, 4, 1, 3 и т.д. Это расписание допустимо, т.е. каждый прибор одновременно обслуживает не более одного требования и i – е требование обслуживается одновременно не более, чем одним прибором.
    Если существует несколько допустимых расписаний, то естественно необходимо выбрать лучшее из них. В теории расписаний качество расписания во многих случаях оценивают следующим образом. Каждое (допустимое) расписание S однозначно определяет вектор моментов завершения обслуживания требований. Задается некоторая действительная неубывающая по каждой из переменных функция F(x)=F(x₁,x₂,...,x_n). Качество расписания S оценивается значением этой функции при . Из двух расписаний лучшим считается то, которому соответствует меньшее значение F(x). Расписание, которому соответствует наименьшее значение F(x) (среди всех допустимых расписаний), называется оптимальным.
    В частности, при построении оптимального по быстродействию расписания . В этом случае , где .
    При построении расписания с наименьшим суммарным временем обслуживания , при этом .
    При построении расписания с наименьшим временем смещения моментов завершения обслуживания требований i относительно сроков D_i функция . При этом , где .
    Оптимальное расписание может быть найдено в результате перебора конечного множества возможных вариантов. Основная трудность при этом состоит в том, что число таких вариантов очень велико и растет, по меньшей мере, экспоненциально с ростом размерности задачи. Известны так называемые эвристические алгоритмы формирования расписаний, алгоритмы на основе методов линейного и динамического программирования. Задачи составления расписаний для некоторых сложных систем обслуживания до сих пор не решены (NP – трудные задачи).

4 ПРЕДПОЛАГАЕМЫЕ РЕЗУЛЬТАТЫ

вверх

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

ВЫВОДЫ

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

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

3. Целью разрабатываемой подсистемы является повышение эффективности работы гибких производственных систем механообработки в машиностроении за счет составления локально оптимального расписания работы ГПС на уровне цеха. Для достижения поставленной цели были определены следующие задачи: определение последовательности запуска деталей в производство; обоснование выбранных критериев оптимизации; оценка адекватности модели.

4. Оптимизация работы ГПМ на цеховом уровне за счет составления оптимального расписания работы по выбранному критерию позволит произвести повышение эффективности работы ГПС механообработки, что приведет к ускорению производственного процесса.

Источники

1. Н.М. Султан-заде P.P. Загидуллин Повышение производительности ГПС путем оптимизации расписаний - М., СТИН. 1996. № 12.

2. P.P. Загидуллин Комплексная математическая модель оперативно-календарного планирования в гибких комплексах механической обработки - М., Автоматизация и современные технологии. 1999. № 9.

3. В.С. Танаев, В.В. Шкурба Введение в теорию расписаний, М. «Наука», 1975.

4. О.М. Калин, С.Л.Ямпольский, Л.В.Песков Моделирование гибких производственных систем. – К: Техника, 1991.

5. Копосов В.Н. Математическое моделирование процессов в машиностроении/ Курс лекций
   URL: http://elib.ispu.ru/library/lessons/Koposov/index.html
   

6. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning - Addison-Wesley, 1989.

7. В.М. Кутрейчик Генетические алгоритмы. – Таганрог: Изд. ТРТУ, 1998.