Планирование и оптимизация: от Вергилия до... APS-системы

Автор: Илья Маляренко КИС Каждый раз, когда мы произносим \"лучше\" или \"самый\", в наших словах звучит скрытое упоминание о задаче оптимизации: выборе из нескольких решений того, которое наиполнейшим образом соответствует предъявляемым требованиям. С задачами поиска наиболее привлекательного решения в условиях различных ограничений мы сталкиваемся постоянно: ищем наикратчайший путь от станции метро до работы с учетом различных факторов (шумности улицы, чистоты и качества дорожного покрытия); выбираем информационную систему для внедрения на предприятии, изучая такие характеристики, как стоимость владения, длительность и трудоемкость внедрения, наличие соответствующих людских ресурсов, адекватность ее возможностей задачам компании; оформляем кредит на покупку бытовой техники, выбирая из множества предложений банков то, которое отвечает нашим возможностям по первому взносу и ежемесячным платежам. Ключевым ресурсом любого производства является время, присутствующее в задаче оптимизированного планирования в различных ипостасях. Одним из первых исторических упоминаний о задаче оптимизации является поэма Вергилия \"Энеида\", в которой королеве Дидо (приблизительно VII век до н. э.) после ее бегства из Тира на северное побережье Африки от злонамеренных родственников приходится бороться с кознями местного властителя. На просьбу Дидо продать ей участок земли у моря тот милостиво соглашается продать пятачок земли, который можно опоясать шкурой одного вола. Находясь в ситуации сложного выбора: возвращения домой, где ждет неминуемая смерть от рук брата, или подчинения прихотям местного властителя, Дидо придумывает способ, который поверг бы в изумление неискушенного политика. Она разрезала шкуру вола на тонкие полоски, сплела из них длинный канат и решила задачу поиска участка с максимальной площадью поверхности в условиях постоянной длины каната с учетом формы примыкающего морского побережья в виде прямой. Как известно, такой фигурой является полукруг. По легенде, на месте участка королевы Дидо был основан один из крупнейших средиземноморских торговых, культурных и военных центров - Карфаген. Задача планирования имеет не менее удивительную историю. Считается, что ее появление связано с формированием крупных централизованных образований, городов, в которых было необходимо координировать работу большого числа людей: строительных рабочих при возведении огромных зданий и сооружений, военных при проведении боевых операций, пожарных при тушении пожаров, жрецов во время богослужений и т. д. Наиболее остро в то время стояла задача оперативного планирования действий крупных армейских подразделений: войсковых операций, транспортировки войск, обеспечения продовольствием и амуницией, доставки завоеванных ценностей. В самых общих словах задача планирования может быть сформулирована следующим образом: как с учетом временных факторов наилучшим образом распорядиться имеющимися ресурсами (людьми, орудиями труда, материалами, информацией и пр.), чтобы достигнуть поставленных целей? Одним из интереснейших изобретений армейской мысли, впервые воплощенным в жизнь еще в персидской армии, стала идея синхронизации скорости перемещения отдельных воинских подразделений за счет применения походного и строевого шага. В этом случае скорость движения всех воинов приблизительно одинаковая, колонна не растягивается по маршу и не сжимается на отдельных участках пути. Для того чтобы синхронизировать движение отдельных фаланг и когорт, применялись походные барабаны и другие \"ритмоводители\". Сколь бы интересным ни был составленный план, практическую ценность он представляет только в том случае, если его можно выполнить. На современных предприятиях также имеется проблема синхронизации как отдельных подразделений, так и производственных линий внутри них. Для повышения ритмичности производства применяются конвейеры, карточки канбан, средства автоматизированного синхронного планирования, при этом ритм всего процесса определяется самой медленной технологической цепочкой. Важным аспектом планирования является анализ материальных потоков. Изучив успехи и неудачи военных операций, римские полководцы пришли к выводу, что одной из основных проблем, замедляющих перемещение армии, являются подводы с продовольствием, идущие в конце колонны. В связи с этим устав обязал легионеров носить с собой на марше запас еды в заплечном мешке, что позволяло осуществлять быстрые маневры в условиях, когда поставки продовольствия не успевали за перемещениями войск. Иллюстрация работы генетического алгоритма Стоит ли удивляться, что в очередной раз задача оптимизации планирования встала перед выходцем из того же Карфагена, полководцем Ганнибалом, в конце концов проигравшим Риму во Второй Пунической войне благодаря использованию Фабием Максимом тактики \"выжженной земли\", нарушившей планы поставок и обеспечения продовольствием войск Ганнибала, находящихся на Пиренейском полуострове. В новом ракурсе, отличном от принятого в современных учебниках, воспринимается и победа в Отечественной войне 1812 г., когда запланированно нарушив систему снабжения 300-тысячной Наполеоновской армии Кутузову удалось втянуть войска неприятеля в глубь территории России, уничтожив предварительно местные источники пополнения запасов продовольствия. Задача производственного планирования в современной формулировке и масштабах появилась впервые, по-видимому, в венецианском Арсенале, который начал работу в VIII веке. К XVI веку Арсенал, занимающийся производством амуниции и кораблей, обеспечивал Венеции военно-техническое господство в Средиземноморском регионе. Каждый корабль выполнял универсальные функции: был военным и гражданским судном одновременно, реализуя заповеди политики меркантилизма. В доках Арсенала находился стратегический резерв Венеции - около 100 кораблей, готовых отправиться в любую точку Средиземноморья по решению Совета дожей. В период расцвета на верфях Арсенала трудилось до 16 000 работников. Территория Арсенала составляла 32 из 670 га площади Венеции и по праву называлась сердцем города. Любая система автоматизированного планирования является системой поддержки принятия решений и не может полностью заменить планировщика. Уже в то время применялись современные идеи разделения труда, универсальные взаимозаменяемые детали, цеховая форма организации производства с разделением маршрута на отдельные технологические операции, выполняющиеся на разных участках. Финальная сборка была отделена от подготовительного участка и выполнялась специальными рабочими на поточной линии. Существовали особые подразделения, занимавшиеся, как бы мы сейчас сказали, научно-исследовательскими и опытно-конструкторскими работами в области кораблестроения и конструирования нового вооружения (именно здесь впервые была реализована идея корабельной артиллерии). Арсенал имел в своем распоряжении склады, обеспечивавшие поставки всех необходимых материалов по первому требованию, на стратегические виды сырья (лес, пенька) распространялась государственная монополия. В Арсенале работали, говоря современным языком, менеджеры проектов, контролировавшие производственный процесс и осуществлявшие взаимодействие с управленцами из органов власти. До 10% бюджета Венецианской республики шло на поддержание первой в мире фабрики, которая являлась гарантом политической и финансовой стабильности государства. Решение задачи оптимизированного планирования Итак, мы выяснили, что проблема планирования представляет собой вопрос распределения работ между имеющимся ресурсами с учетом различных ограничений. При производственном планировании в качестве ресурсов в первую очередь рассматриваются машины, затем персонал, сырье и технологическая оснастка. С точки зрения оптимизации все решения, получаемые в результате выработки планов, можно разделить на следующие: - оптимальные по всем критериям; - оптимизированные по одному/нескольким критериям; - приемлемые по всем ограничениям. Процесс построения производственного расписания, отражающего, в какой момент времени на каком ресурсе будет выполняться та или иная задача, складывается из двух подзадач: нахождения приемлемых расписаний и последующего выделения из приемлемых расписаний лучших. Исходя из каких критериев можно выбрать лучшее расписание? Этот вопрос напрямую перекликается с вопросом о том, каким образом можно улучшить существующую на предприятии ситуацию. Ключевой ресурс любого производства - время, присутствующее в задаче оптимизированного планирования в различных ипостасях. Во-первых, одним из наиболее важных проявлений времени, за которое следует бороться, является дата выхода заказа из производства. Для большинства заказов рассчитанные даты выхода должны быть максимально приближены к датам обещанной отгрузки заказов клиентам. Второе проявление времени - длительность технологического цикла. У любого изделия есть минимально возможный технологический цикл, продолжительность которого равна сумме длительностей отдельных операций. Реальный технологический цикл всегда включает межоперационные простои. Чем меньше доля межоперационных простоев в длительности цикла, тем лучше. Идеология кайдзен предполагает, что внутренним движителем всех процессов улучшения является стремление к достижению измеримых и понятных целей, выраженных в терминах KPI. Помимо межоперационных простоев на длительность цикла влияет количество транспортировок полуфабрикатов и количество переналадок. Уменьшение затрат времени на эти этапы всегда благотворно сказывается на качестве производственных планов. Анализируя возможности оптимизации, следует иметь в виду, что скорость обслуживания клиента (еще одно проявление времени) может быть увеличена за счет поддержания запасов складов полуфабрикатов и готовой продукции на складах. Тем не менее время, в какой бы оно форме ни выражалось, всегда имеет определенную цену для предприятия. Поэтому стратегии оптимизации должны учитывать множество факторов, влияющих на конечный результат, выраженный в виде производственного расписания. Впервые проблема планирования ресурсов была сформулирована в строгой математической форме в виде задачи целочисленного линейного программирования для одной машины, дискретной оси времени и нескольких независимых работ. В такой формулировке время фигурирует в виде плановых периодов, единственная независимая переменная равна 1, если выполнение задачи запланировано с заданного периода, в противном случае переменная равна 0. Минимизируемая целевая функция - итоговая разница между временем завершения всех операций и обещанной датой отгрузки (makespan). Учитываемые ограничения: невозможность одновременно на одной машине производить сразу несколько операций, необходимость выполнить все операции и уложиться в отведенные сроки. Существенным недостатком такой формулировки является невозможность решать типовые задачи для нескольких машин и технологических маршрутов с множеством последовательных операций в режиме реального времени, так как для этого нужно проводить длительный поиск глобального оптимума из всего множества потенциальных решений. Большинство планировщиков в процессе составления расписаний используют эвристические правила. Наиболее простым и известным является правило Смита: наилучший результат при планировании на одной машине достигается при последовательном назначении работ с наименьшей длительностью. Эвристические правила называют правилами разрешения конфликтов планирования, или правилами диспетчеризации. Современные экспертные системы планирования производства строятся на базе формализованных в виде математических функций правил диспетчеризации, используемых специалистами по планированию. Упрощенная схема работы таких систем представлена ниже. 1. Создать очередь выполнения операций для каждого из ресурсов (с использованием правил отбора операций). a. Включить все операции, которые можно выполнить на текущий момент (учитывая ограничения по последовательности выполнения операций в маршрутах). 2. Как только освобождается любая машина: - обновить очередь выполнения операций; - проранжировать операции в очереди; - запустить на выполнение операцию с наивысшим рангом. В промышленных системах, построенных на методах эвристического программирования, данная схема выглядит значительно сложнее, так как могут использоваться сразу несколько операций разрешения конфликтов планирования, в том числе специализированные правила выбора машин для операций, а также правила выбора операций из \"назначаемой\" группы на текущем шаге планирования. Следует отметить, что системы, основанные на эвристических алгоритмах и методах локального поиска, позволяют найти оптимизированное, но не оптимальное производственное расписание. К современным методам оптимизации и локального поиска, не гарантирующим нахождение глобального оптимума, относятся: - генетические алгоритмы; - метод роящихся частиц (Particle Swarm); - метод моделирования отжига (Simulated Annealing); - табуированный поиск (Tabu search). Эволюционные и генетические алгоритмы. Еще со времен Ламарка развитие живого мира рассматривается как процесс постоянного совершенствования (приспособления) особей под влиянием среды. Моделируя отбор лучших планов, как процесс эволюции в популяции особей, можно получить решение задачи оптимизации, задав начальные условия эволюционного процесса, населив виртуальную вселенную существами - носителями информации и указав цель эволюционного процесса. Схема взаимодействия различных подразделений в процессе использования ими APS-системы Генетические алгоритмы, предложенные в начале 70-х годов, являются одним из самых распространенных вариантов реализации эволюционных алгоритмов. Генетические алгоритмы используют аналогию между естественным отбором и процессом выбора наилучшего решения из множества возможных. Носителями решений являются особи, в \"хромосомах\" которых закодированы те или иные существенные параметры. Ключевой момент здесь - возможность задать функции оценки приспособленности особей (fitness function), ответственной за \"половой отбор\" (эволюционная аналогия задачи оптимизации: наиболее привлекательная самка выбирает самого статусного самца). Схема работы генетических алгоритмов выглядит следующим образом. 1. Задается способ кодирования параметров задачи в \"хромосомах\". 2. Создается исходная популяция (начальное решение). 3. Рассчитывается функция приспособленности каждой особи. 4. Для наиболее приспособленных особей производится \"скрещивание\" и рождение новых особей, содержащих признаки обоих родителей. При этом передача признаков осуществляется в соответствии с одним из выбранных способов \"обмена участков хромосом\". Наименее приспособленные особи \"отмирают\" и заменяются новорожденными. 5. Осуществляется мутация некоторой части особей добавлением в процесс поиска элемента случайности. 6. Шаги 2-5 итерационно повторяются заданное число раз. 7. Из оставшейся популяции выбираются лучшие особи, \"хромосомы\" декодируются, а получаемое таким образом решение соответствует локальному оптимуму. В современных условиях локальный поиск на базе генетических алгоритмов реализуется достаточно просто. Основную сложность таит в себе выбор того, какие параметры и в каком виде будут закодированы в \"хромосомах\". В качестве функции оценки приспособленности особей могут использоваться простые, знакомые со школы математические функции. Планирование не может быть эффективным, если рассматривает предприятие как обособленную от рынка производственную структуру. Преимуществом генетических алгоритмов перед другими является простота их реализации, относительно высокая скорость работы, параллельный поиск решения сразу несколькими особями, позволяющий избежать попадания в \"ловушку\" локальных оптимумов (нахождения первого попавшегося, но не самого удачного оптимума). Недостаток - сложность выбора схемы кодирования, возможность вырождения популяции, сложность описания ограничений планирования. Метод роящихся частиц (particle swarm). Это наиболее простой и, что удивительно, один из самых молодых методов эволюционного программирования, появившийся в середине 90-х годов. Группа исследователей, занимавшихся этологией птиц и рыб, их социальной организацией, пришла к выводу о возможности решения задач оптимизации с помощью моделирования поведения групп животных. В основу метода положен тот факт, что при формировании стаи птицы стремятся к некоторому центру \"притяжения\", постепенно замедляя скорость полета. В реализации данного алгоритма многомерное пространство поиска населяется роем частиц (элементарных решений). Координаты частицы в пространстве однозначно определяют решение задачи оптимизации. Помимо координат каждая из частиц описывается скоростью перемещения и ускорением. В процессе перемещения частицы осуществляют \"прочесывание\" пространства решений и тем самым находят текущий оптимум, к которому на следующем шаге устремляются остальные частицы. Для введения случайной составляющей в процесс поиска могут быть включены \"сумасшедшие\" частицы, закон движения которых отличается от закона движения остальных. Схема работы алгоритма выглядит следующим образом. 1. Создается исходная \"случайная\" популяция частиц. 2. Для каждой частицы рассчитывается целевая функция. 3. Лучшая частица с точки зрения целевой функции объявляется \"центром притяжения\". 4. Векторы скоростей всех частиц устремляются к этому \"центру\", при этом чем дальше частица находится от него, тем большим ускорением она обладает. 5. Осуществляется расчет новых координат частиц в пространстве решений. 6. Шаги 2-5 повторяются заданное число раз. 7. Последний \"центр тяжести\" объявляется найденным оптимальным решением. Этот алгоритм благодаря своей простоте (менее десяти строк кода) и скорости считается очень перспективным для задач планирования. Табуированный поиск (Tabu Search). Данная процедура представляет собой вариацию известного метода градиентного спуска с памятью. В процессе поиска ведется список табуированных (запрещенных для перехода) позиций (из числа уже посещенных и рассчитанных). Критические параметры алгоритма - глубина списка запретов, определение текущего состояния, размер области вокруг текущего состояния. В процессе поиска осуществляются операции аспирации (включение в запрещенный список состояний вокруг текущего состояния) и диверсификации, которая добавляет фактор случайности в процесс поиска. Моделирование отжига (Simulated Annealing). Метод, разработанный в 80-х годах, основан на аналогии с физическим процессом охлаждения металла и переходом его в состояние с минимальной энергией кристаллической решетки. Изначально он использовался для моделирования поведения системы атомов при разных температурах, но впоследствии был расширен для решения комбинаторных задач. Схема применения метода достаточно проста. 1. Задается начальное условие. 2. Выбираются соседние состояния и определяется вероятность перехода в каждое из этих состояний, которая зависит от их \"энергии\". 3. Уменьшается температура (от нее зависит вероятность перехода в новое состояние). 4. Шаги 2-3 повторяются заданное число раз. Планирование на современном предприятии Программные продукты, реализующие вышеописанные алгоритмы оптимизации для составления детальных производственных расписаний, относятся к классу APS-систем (Advanced Planning & Scheduling). Это относительно молодое направление корпоративных информационных систем, возникшее в конце 80-х годов и снискавшее среди менеджеров по логистике и планированию западных предприятий заслуженное уважение. Большинство APS-систем являются инструментами имитационного моделирования производственной деятельности и применяются для поддержки принятия решений в области операционного менеджмента промышленных предприятий. Подобное планирование предполагает последовательное решение ряда задач анализа имеющихся возможностей, формулирования производственной программы, составления технологического расписания, контроля хода его выполнения. Работа APS-систем начинается с описания производственного процесса в виде информационной модели. Данная модель может быть создана как непосредственно в APS-системе, так и во внешних средствах технологической подготовки производства. Информационная модель процесса включает описание рабочих центров и технологических операций, технологические маршруты, спецификации и рецептуры изделий, а также некоторые другие параметры. Подготовкой нормативно-справочной информации занимаются специалисты-технологи. Виды диаграмм Ганта, применяемые в APS-системах Следующий шаг процесса планирования - формулирование производственной программы. Портфель заказов определяется на основании данных прогноза продаж и/или реальных клиентских заказов. В случае, если планирование осуществляется по определенным периодам, необходимо согласование возможностей производства, служб материально-технического снабжения и сбыта. Данный этап осуществляется с применением APS-системы, которая позволяет ответить на вопросы: сколько производственных заказов мы сможем выполнить в течение периода планирования, какие для этого необходимы ресурсы: люди, производственные мощности, сырье и материалы, насколько загружены производственные мощности, нужно ли прибегать к услугам субподрядчиков? При использовании модели планирования со скользящим горизонтом, когда заказы принимаются в произвольный момент времени, встраиваясь в уже сформулированную производственную программу, и отгружаются клиентам по мере выполнения, необходим несколько иной подход к формированию планов. В этом случае для каждого клиентского заказа APS-система позволяет рассчитать ожидаемую дату изготовления с учетом имеющейся загрузки оборудования, наличия сырья на складе и возможностей персонала. Для решения данной задачи применяется инструмент поддержки принятия решений, который отвечает на вопросы: когда заказ будет отгружен клиенту, какие ресурсы для этого нужны, как новый заказ повлияет на дату отгрузки остальных? После формирования портфеля заказов полученный план используется службой материально-технического снабжения для оценки потребности в сырье и материалах, для формирования заявок на их закупку. На этом этапе APS-система позволяет сформировать рекомендации по закупкам, которые ответят специалистам службы снабжения на вопрос, какие материалы, в каком количестве и когда закупать. В дальнейшем эта информация будет использована для составления производственного расписания с учетом ожидаемых поставок материалов и сырья на склад. Следующим шагом в планировании производства является составление детального расписания, которое позволит ответить на вопрос, какая операция, в какой момент времени должна выполняться на данной единице оборудования, а также на сопутствующие вопросы: когда и на каком оборудовании будут осуществляться переналадки? Помимо решения вышеназванной задачи APS-система на основании введенных в нее данных о целях и стратегиях оптимизации позволяет получить оптимизированное производственное расписание, примиряющее конфликтующие между собой потребности различных подразделений. Одни заинтересованы в своевременной отгрузке заказа, другие - в повышении производительности оборудования, третьи - в уменьшении складских запасов. Производственное расписание в виде нарядов на работы передается в цех, где начинается его исполнение . Важный момент здесь - соблюдение указанной в сформированном APS-системой расписании последовательности работ. В процессе исполнения плана накапливаются отклонения хода производственного процесса (поломки оборудования, брак, отсутствие каких-либо компонентов на складе), которые нарушают изначальную схему работ. В связи с этим для контроля процессов и оперативного их перепланирования необходим механизм обратной связи с технологическими подразделениями, который реализуется в системах класса APS. Данный механизм позволяет ответить на вопрос, как изменилось расписание по сравнению с первоначальным из-за поломок, брака и других факторов. Анализ основной деятельности предприятия предполагает использование простых и емких ключевых показателей эффективности (КПЭ) для диагностики ситуации на предприятии. Современные APS-системы позволяют оценить множество обобщенных и отраслевых ключевых показателей такого рода по имеющемуся производственному расписанию. Данный инструмент предназначен в первую очередь для топ-менеджеров, руководителей технологических подразделений и планово-диспетчерских служб. Что важно знать специалисту, выбирающему систему оперативного планирования? Каковы наиболее важные факторы выбора системы оперативного производственного планирования для создания механизма поддержки принятия решений специалистов планово-диспетчерских бюро, отделов сбыта и материально-технического снабжения?