В работе предложен, основанный на генетических методах, подход к решению проблем управления запасами, возникающих при производстве многокомпонентных вычислительных устройств. Показана возможность сравнительно легкой адаптации алгоритма к различным вариантам постановки задачи.
The approach for solving inventory control tasks was described. This approach based on genetic algorithm and it’s modifications. This method can be easy adapted for different problem statements.
Как правило, современные вычислительные устройства состоят из множества компонентов, производимых различными компаниями, зачастую расположенными в разных странах и даже на разных континентах. В этих условиях при проектировании производственных процессов нельзя не принимать во внимание проблемы формирования запасов компонентов, необходимых для сборки изделий. Иными словами, при производстве сложных вычислительных устройств, использующих в своей структуре множество компонентов от разных производителей, приходится решать логистические задачи управления запасам. Задача определение такого уровня запаса каждого из компонентов, а также времени и объемов его поставки на склад, при которых издержки, связанные с транспортировкой и хранением продукции, будут минимальны – это задача, которую приходится решать достаточно часто.
При решении задач управления запасами в каждом конкретном случае необходимо учитывать множество параметров, оказывающих непосредственное влияние на рассматриваемую систему. Это число номенклатур (компонентов изделия), характер потребления компонентов со склада, характер восполнения запаса, учет дефицита, задержка поставок и т.д. Наличие большого количества различных факторов, которые необходимо рассматривать при решении задач управления запасам, определяет их сложность. В частности, одним из основных факторов, усложняющих модель, является многономенклатурность. При большом числе номенклатур реализация сколько-нибудь сложных методик управления запасами оказывается невозможной, а стоимость информационной системы может перекрыть возможную экономию. Вместе с тем, согласно статистике, только 18% работ рассматривают многономенклатурные задачи. Вместе с тем, большинство практических задач являются многономенклатурными, поэтому в данной работе основное внимание уделено именно этому классу задач.
В общем случае можно сказать, что решение задачи управления запасами - это некий график (расписание) поставок товаров на склад, при котором издержки хранения, транспортировки товаров и др. минимальны. Таким образом, задачи управления запасами можно рассматривать как разновидность задач составления производственных расписаний.
В свою очередь, задачи проектирования расписаний тоже часто приходится решать при синтезе технологических и вычислительных процессов. Но задачи управления запасами и составления производственных расписаний тесно связаны, так как по сути являются звеньями одной производственной цепи: поставщик комплектующих – склад – цех производства продукции – склад. Поэтому тот факт, что задачи синтеза расписаний и задачи управления запасами схожи, позволяет использовать одни и те же методы их решения, а следовательно упрощает создание систем, способных решать эти задачи в комплексе.
Многочисленные работы в области решения задач синтеза расписаний показывают, что одними из наиболее перспективных способов являются генетические алгоритмы и методы на них основанные.
Исследование способов решения задач управления запасами генетическими методами обусловлено хорошими результатами, полученными с их помощью при решении сложных задач синтеза расписаний.
Точные методы решения могут быть использованы только для небольшого круга сравнительно простых задач управления запасами, поэтому на практике используют приближенные методы. Учитывая схожесть задач управления запасами и задач синтеза расписаний, а также хорошие результаты, показанные генетическими методами при решении задач синтеза расписаний, в данной работе рассматривается применение генетических методов для решения задач управления запасами.
В генетических методах при поиске экстремума оперируют совокупностью записей (хромосом). Каждая хромосома состоит из множества полей (генов) и содержит информацию о конкретном варианте расписания.При этом аллелями (значениями генов) являются значения искомых параметров расписания. С помощью генетических операторов выбора родителей, кроссовера, мутации и селекции имитируется улучшение приспособленности популяции хромосом к заданным условиям, т.е. осуществляется поиск окрестностей экстремальной точки.
При применении методов локальной оптимизации оперируют единственной хромосомой,
исследуя значения целевой функции в окрестностях текущей точки в пространстве
оптимизируемых параметров.
Одной из основных подзадач при применении генетических алгоритмов является отыскание способа размещения информации о расписании в хромосоме. Необходимо, чтобы каждая хромосома не только однозначно определяла свой вариант расписания, но и в результате действия над ней генетических операторов образовывались хромосомы, не требующие дополнительной коррекции. Для рассматриваемой задачи управления запасами существует достаточно простой способ представления информации о графике поставок в хромосоме. При этом применение генетических операторов не приводит к необходимости контролировать и корректировать результаты их действия.
Все результаты расчетов, приведенные в данной работе, получены с помощью специально разработанного программного комплекса с графическим интерфейсом, рассчитанного на решение класса задач управления запасами, в постановке, приведенной выше. В программном обеспечении реализован генетический алгоритм с усовершенствованиями, подробнее о которых будет сказано ниже.
В рассматриваемой задаче в качестве значений генов использовались численные величины, определяющие временные интервалы, на которые должно хватить завозимого товара (компонента вычислительного устройства). Задавшись уровнем гарантийного запаса можно однозначно определить моменты времени, в которые товар должен поступить на склад и соответственно моменты, когда товар необходимо заказывать, а также объем заказов.
В соответствие с классическим генетическим алгоритмом, на первом этапе формировалась популяция хромосом со случайными значениями генов. Значения генов (аллели) выбирались из множества {1…T} с равной вероятностью (T - количество дискретных интервалов времени на рассматриваемом временном отрезке). Это означает, что объем единовременной поставки товара на склад мог равняться как количеству, необходимому на один день продаж, так и количеству, необходимому на весь рассматриваемый период. На практике объем поставки колеблется c гораздо меньшей амплитудой, однако теоретически нельзя исключать вероятность того, что, например, выгоднее лишь один раз завезти весь необходимый товар на склад.
В процессе генетического поиска из хромосом постепенно вытесняются «плохие» значения генов и формируются хромосомы, соответствующие лучшим графикам поставок товаров, т.е. меньшему значению целевой функции – сумме расходов на доставку товаров и содержание запаса. Чтобы ускорить этот процесс применялся метод локальной оптимизации, оперирующий одной хромосомой. Помимо метода локальной оптимизации, для увеличения скорости поиска решения применялись динамически изменяемые вероятности появления новых значений генов в процессе мутации хромосом, а также при формировании новых хромосом взамен исключаемых из популяции.
Через некоторое время после начала работы генетического алгоритма включался механизм, определяющий количества значений генов в лучших хромосомах. Для каждого вероятного значения гена из множества {1…T} определялось количество его вхождений в группу лучших хромосом. Значения, встречающиеся чаще, получали большую вероятность появиться в результате мутации или в результате создания новой хромосомы.
Для компенсации отклонений фактического объема спроса от прогнозировавшегося и действительного времени исполнения заказа от ожидаемого, используется гарантийный запас. В разработанной программе уровень гарантийного запаса может быть задан как функция скорости «потребления» компонента изделия со склада. Например, можно указать, что в каждый момент времени гарантийный запас компонента на складе должен быть равен потребности в данном компоненте на период времени, равный удвоенному времени доставки этого компонента на склад. Возможно использование и более сложных формул вычисления гарантийного запаса.
В качестве тестовых задач использовались: однопродуктовая задача, взятая из литературы и многопродуктовая задача, полученная из первой путем добавления еще двух видов компонентов, составляющих изготавливаемую систему и изменения уровня потребления заготовок.
Решение однопродуктовой задачи сравнивалось с решением приведенном в источнике. График поставок, полученный с помощью генетического алгоритма, дает затраты равные 430.28 единиц, а график поставок, приведенный в литературе, – 457.17 единиц, что примерно на 6% хуже.
Решение многономенклатурной задачи управления запасами осуществлялось с помощью того же программного решения однономенклатурной задачи. На базе этого же программного комплекса решались многостадийные задачи синтеза производственных расписаний.Это подчеркивает, что применение алгоритмов, построенных на основе эволюционных методов, позволяет решать достаточно широкий круг задач при незначительных изменениях в программном обеспечении или же вообще без таковых.
Полученные результаты позволяют сделать вывод о перспективности применения генетических методов для решения задач управления запасами, возникающих как на этапе планирования, так и на этапе реализации производственных процессов. Основным преимуществом генетических методов можно назвать сравнительно простую (по сравнению с традиционными методами решения) адаптацию алгоритма к различным вариантам постановки задачи. С помощью одного и того же варианта алгоритма можно решать целый ряд схожих задач. Вероятностный характер исходных данных компенсируется наличием в системе гарантийного запаса, уровень которого можно менять в зависимости от величины спроса на товар, или, например, стабильности поставок. Кроме того, этот способ может быть дополнен подходом, суть которого заключается в постепенной корректировке исходного расписания в процессе его реализации в зависимости от степени отличия реальных параметров задачи от ранее прогнозируемых.