Application of genetic algorithms to the production and selling problems.pdf В настоящее время развитие различных научных и производственных отраслейневозможно без применения средств вычислительной техники и современных ин-теллектуальных информационных технологий. Это обусловлено тем, что многиесовременные задачи просто не могут быть решены классическими методами из-заочень большой сложности математических моделей, их описывающих [1, 2].Задачи составления производственных планов являются комбинаторными за-дачами большой размерности. От их решения зависит эффективность производст-ва. Однако из-за их сложности (задачи реальной размерности относятся к NP-полным) решения, как правило, принимаются интуитивно человеком с использо-ванием различных эвристик. Реальное производство представляет собой систему сэволюцией и, как любая действительно сложная система, характеризуется множе-ством подсистем с высокой степенью неопределенности. Следовательно, решениезадачи планирования производства не может быть найдено при использованиикакого-либо единого подхода для всех подсистем.В данной работе показывается применение генетических алгоритмов для ре-шения такой важной управленческой задачи на промышленном предприятии, какпланирование производства и сбыта готовой продукции. Задача является сложнойи многогранной, основные этапы планирования представлены на рис. 1.Система управления производственным предприятием должна отвечать сле-дующим требованиям и обеспечивать следующую функциональную полноту [3]:- обеспечение планирования продаж, которое оценивает (обычно в единицахготового изделия), какими должны быть объем и динамика продаж, чтобы былвыполнен установленный бизнес-план;- обеспечение планирования производства, которое утверждает план произ-водства всех видов готовых изделий и их характеристики;- обеспечение индивидуальной программы производства для каждого вида из-делия в рамках выпускаемой линии продукции, при составлении которой следуетучитывать все технологические ограничения;- обеспечение планирования потребности в материалах на основе производст-венной программы для каждого вида готового изделия;- определение требуемого расписания закупки и/или внутреннего производст-ва всех материалов и комплектующих этого изделия и соответственно их сборку;СистемапланированияресурсамипредприятияОбщий портфельзаказов (номен-клатура выпуска)ПланированиепроизводстваПроизводственныемощностиТекущий план выпускаЗапасыРассогласованиеУкрупненноерасписаниедля всегопредприятияРасписаниедля всегопредприятияЧастныепроизводственныеусловия цеховОптимизациявыпуска продукцииРасписаниедля цехаДетализированноерасписание дляукрупненных цеховПерсоналМатрицы Поточные линии ПродукцияСтоимистьПоказатели качестваСроки выполненияРис. 1. Схема «Основные этапы планированияна промышленном предприятии»- обеспечение планирования производственных мощностей, которое преобра-зует план производства в конечные единицы загрузки рабочих мощностей (стан-ков, рабочих, лабораторий и т.д.);- обеспечение планирования потребности в финансах.В постановках таких проблем обычно рассматривается задача поиска опти-мального решения, при котором время, необходимое для производства всех изде-лий в требуемом объеме, будет минимально, все сроки по договорам выполнены,и запасы на складе не превышают определенного значения.Такие задачи, как правило, имеют множество различных разнородных пара-метров и ограничений. Самый простой способ найти оптимальное решение - пе-ребрать все возможные значения параметров. При этом не нужно делать никакихпредположений о свойствах целевой функции, а задать ее можно просто с помо-щью таблицы. Однако в нашей задаче потребуется перебрать огромное количест-во комбинаций, что приводит к значительным затратам вычислительных и вре-менных ресурсов. Таким образом, возникает необходимость в каком-либо новомметоде оптимизации, пригодном для практики. Покажем, каким образом можноприменить эволюционные механизмы к данной задаче.1. Постановка задачиТребуется составить план производства и план сбыта продукции на календар-ный месяц с учетом всех ограничений в условиях динамически изменяющегосясписка заказов. Целевая функция T - время, необходимое для производства всехизделий в требуемом объеме, будет выглядеть следующим образом:1 2 max( , ,..., ,..., ) min j LT T = T T T→ , (1)где jT - суммарное время работы j-й производственной линии за выбранный пе-риод (месяц); L - количество производственных линий.1Dj jkkT T==Σ, (2)где jkT - суммарное время работы j-й производственной линии за k-е сутки,jkT R ≤ ; D - количество рабочих дней в текущем месяце; R - рабочее время про-изводственных линий (часов в сутках), остальное время отводится на профилак-тическое обслуживание и ремонтные работы.1Nijkjki ijxT hMP==Σ + , (3)где ijk x - переменная, объем производства изделий i-й номенклатуры на j-й линииза k-е сутки, ijkx b ≥ ; b - минимальный размер партии производства, обусловлен-ный технологическими ограничениями и требованиями к качеству продукции, ijP- объем производства изделий i-й номенклатуры на j-й линии за единицу времени(производительность линии); в случае, когда ijP равняется нулю, производствоизделий i-й номенклатуры на j-й линии невозможно; N - количество номенкла-турных позиций; h - дополнительные временные издержки, возникающие на ли-нии при смене производственной номенклатуры и типа сырья; M - количество та-ких мероприятий в сутках по подготовке линии к производству изделий другойноменклатуры.Размер складских запасов на конец k-х суток1Nk ikiV V==Σ, (4)где ikV - остатки продукции i-й номенклатуры на складе на конец k-х суток,kV W ≤ ; W - максимально допустимый размер складских запасов, i0 V - остаткипродукции i-й номенклатуры на складе на начало месяца, должно быть задано.( 1)1Lik i k ijk ikjV V x y −== +Σ − ; (5)1 1 1 1D N D Nik ik ik i k iy c C= = = =ΣΣ =ΣΣ +, (6)где ik y - переменная, объем отгруженной продукции i-й номенклатуры за k-есутки, ik y ≥cik ,1Nikiy Z=Σ ≤ ; Z - максимально возможная суточная отгрузка сосклада, обусловленная, прежде всего, ограниченными возможностями трудовыхресурсов; ikc - объем продукции i-й номенклатуры, который обязательно долженбыть отгружен за k-е сутки, в противном случае будет нарушение сроков поставокпо договорам и невыполнение плана продаж; i C - объем продукции i-й номенк-латуры, который дополнительно требуется произвести и отгрузить в течение ка-лендарного месяца, продукция реализуется через торговый дом, сроки поставокпо этим позициям гибкие. Значение i C рассчитывает плановый отдел на основа-нии предварительных заказов на текущий и последующий месяцы, а также марке-тинговых исследований.На рассматриваемом предприятии работают одновременно 5 производствен-ных линий (L = 5), рабочих дней в месяце 30 (D = 30), на профилактические иремонтные работы отводится 4 ч в сутки, т.е. рабочее время линий 20 ч (R = 20).Производительность линий задана в табл. 1. Минимальный размер партии произ-водства 8 т (b = 8). На подготовку линии к производству изделий другой номенк-латуры и замену сырья уходит примерно 15 мин или четверть часа (h = 0,25).Максимально допустимый размер складских запасов 800 т (W = 800), максималь-ный объем продукции, который могут отгрузить работники со склада, 100 т(Z = 100). В среднем в месяц предприятие отгружает 2,3 - 2,5 т готовой продук-ции. Требуется найти оптимальные значения объемов производства ijk x (i= 1,N;j = 1, L ; k= 1,D) и сбыта продукции ik y (i= 1,N; k= 1,D).Т а б л и ц а 1Матрица производительности линийПроизводительность (кг/ч)Наименование Линия 1 Линия 2 Линия 3 Линия 4 Линия 5Изделие 1 650 1150 1150 1200Изделие 2 650 1160 1160 600Изделие 3 1160 1160 600Изделие 4 590 600Изделие 5 700Изделие 6 600 600Изделие 7 520 600Изделие 8 630 1100 1100 1150Изделие 9 650 1100 1100 1150Изделие 10 600 1150 1150 600Изделие 11 1050 1050 1250Изделие 12 645 600Изделие 13 1100 1100 1100Изделие 14 600 1000 1000Изделие 15 600 1150 1150 600Изделие 16 1000 1000Изделие 17 1150 1150Изделие 18 600Изделие 19 1100Изделие 20 1100В качестве дополнительных параметров необходимо учесть остатки на складена начало месяца по каждой номенклатурной позиции Vik, перечень имеющихсязаказов cik, в том числе предварительных Ci.2. Генетический алгоритм и его программная реализацияДля решения такого класса задач достаточно результативным инструментомявляются генетические алгоритмы (ГА). Это семейство алгоритмов, которые по-зволяют найти приемлемое решение в аналитически сложно решаемых задачахчерез последовательный подбор и комбинирование исходных параметров с ис-пользованием механизмов, напоминающих биологическую эволюцию [4].Рассмотрим принцип работы генетического алгоритма. На начальном этапедля поставленной задачи необходимо создать массив кодов, позволяющий зако-дировать любое допустимое решение последовательностью символов. Решение,закодированное таким образом, называется организмом, в котором каждый пара-метр - хромосома. Элементарная единица в хромосоме называется геном. Алго-ритм как итерационный набор эволюций содержит основные операторы-модули:формирование начальной популяции, размножения, мутации и селекции. Рас-смотрим принципы работы и назначение каждого из операторов. Так, операторформирования начальной популяции задает многомерные вектора-организмы наоснове параметров исходных данных.Существует три основных принципа формирования начальной популяции:- генерируется полная популяция, накрывающая все множество решений вданной области с заданным шагом, аналогично сетке;- из множества допустимых решений случайным образом выбирается подмно-жество;- комбинация этих двух способов.После генерации начальной популяции к ней применяются генетические опе-раторы, и новые поколения решений создаются до тех пор, пока не сработает кри-терий останова.Критерий останова генетического алгоритма основан на наблюдении за эво-люцией получаемых решений - если в течение фиксированного числа S поколе-ний наилучшее решение не меняется, или в популяции в течение S поколений непоявилось ни одного решения (или их появилось слишком мало), которое прошлоотбор, то эволюционные изменения в популяции затухают. Алгоритм также за-вершает свою работу при достижении определенного числа поколений.Среди операторов размножения традиционно выделяют следующие:- кроссовер, при котором производится скрещивание генетического материаладвух различных решений-«родителей» для получения решений-«потомков»;- различные виды оператора мутации, который преобразует исходную хромо-сому в набор новых решений, как правило, случайным образом.Мутации создают в популяции изменчивость. Лучшие решения, отбираемыекаким-либо механизмом, допускаются к кроссоверу и дают решения-потомки. Се-лекция, которая также опирается на значения целевой функции приспособленно-сти решений, отсеивает малоперспективные организмы. Под витальностью будемпонимать жизненную силу организма, определяемую значениями функции целиили функцией приспособленности.Отсев, как правило, является стохастичным, и в популяции остается некото-рый небольшой процент «неприспособленных» решений. Некоторое количестворешений с «плохой» витальностью должно переходить в следующее поколение,так как, несмотря на свою малую пригодность, такие решения могут содержатьэлементы, необходимые для генерации оптимальных решений. Генетические ал-горитмы лучше других методов оптимизации приспособлены для решения такихзадач, так как не требуется начинать всю вычислительную процедуру сначала, аможно задействовать другой алгоритм определения витальности и продолжатьэволюцию имеющейся популяции решений в изменившихся условиях. Такие ре-шения в новых условиях могут стать очень ценными векторами из пространствадопустимых решений и ускорить нахождение оптимума.Генетический алгоритм для решения задачи реализован в виде программногомодуля, который позволяет сохранять введенную задачу и решение в файле, реа-лизует процедуры генетических преобразований. Интерфейс программного моду-ля также позволяет регулировать численность популяции, процент мутантов вкаждом поколении и другие параметры эволюционного поиска.В качестве организма рассматривался набор хромосом, каждая из которых от-вечала за хранение исходной информации в следующем виде:1 … k … 30D=30 - количество рабочихдней в текущем месяце1 2 …201 2 …201 2 …20N = 20 - количество видовизделий1 1 0 0 0 0 0 1 1 0 0 0 0 0 11 указывает на выпускпродукции в k-е суткиj-линия(1,...,L)L=5 -кол-волиний xijk - объем выпускаемой продукции i-го видана j-й производственной линией за k-е суткиyik - объем отгруженной продукции i-го видаза k-е суткиПродукция со всех произ-водственных линийПоскольку размерность задачи очень высока, имеется большое количество до-полнительных ограничений, применение классических методов становится за-труднительным.Здесь организм как набор хромосом, как способ кодирования решений пред-ставляет собой два массива: трехмерный массив Производственные линии . Ра-бочие дни месяца . Перечень номенклатуры изделий, в ячейках которого задаютсязначения xijk - возможные объемы производства; двумерный массив Рабочие днимесяца . Перечень номенклатуры изделий, в ячейках которого задаются значенияyik - возможные объемы суточной отгрузки продукции (рис. 2).Дополнительно специально разработанным алгоритмом автоматически рас-считывается матрица загрузки каждой производственной линии и соответственновременные издержки, возникающие на линии при смене производственной но-менклатуры и типа сырья.Такой «хромосомный» вид представления позволяет легко не только пробо-вать различные методы генерации начальной популяции, но и сопоставлять их сзадачами линейного программирования.Приспособленность решения определяется по заданной целевой функции. Вы-численное значение целевой функции приспособленности становится витально-стью организма. Дополнительные процедуры, реализующие стохастический вы-бор данного решения для участия в турнире, преобразуют значение целевойфункции данного организма в вероятность его выбора для кроссовера или перехо-да в следующее поколение.Интерфейс программного модуля составлен так, что позволяет указывать вседопустимые пороговые значения параметров перед запуском алгоритма.30xijkОбъемпроизводстваyikОбъемспросаДниИзделия120ik130Рис. 2. Пространство «хромосом»-решений для задачи планирования производстваи сбыта готовой продукцииГенетические операторы реализованы в виде отдельных DLL-модулей, что по-зволяет без изменения основного программного кода модифицировать новые реа-лизации операторов мутации и кроссовера. Так, оператор мутации имеется вдвух реализациях:- в виде одноточечного оператора, который изменяет случайно выбранный генв допустимых пределах для этого гена;- в виде двухточечного оператора, меняющего местами два случайно выбран-ных гена.Оператор кроссовера выполняет операцию обмена участка хромосом крест-накрест в случайно выбранной точке. Выбор хромосом для участия в турнире ор-ганизован по принципу «рулетки» на основе датчика случайных чисел с равно-мерным распределением. Оператор селекции выполняет функции отбора наилуч-ших полученных решений на данном этапе эволюции.После генерации каждого следующего поколения проверяется критерий остано-ва, подсчитывается лучшее, среднее и худшее значения в данной популяции. Есликритерий останова не выполнен, к новому поколению снова применяются генети-ческие операторы, если критерий останова выполнен - поиск прекращается.3. Тестирование алгоритмаАлгоритм тестировался на примерах задач различной размерности, различны-ми неоднородными параметрами и с разными объемами начальной популяции,где критерием останова являлось сохранение лучшего решения подряд в 5 поко-лениях.Наиболее приемлемыми получились параметры алгоритма с численностью по-пуляции 10 организмов, для изделий оптимальный размер партий производствасоставил порядка 16 т.Результаты работы алгоритма для задачи с 6 хромосомами в каждом организмес общим числом параметров 4000.Число поколений 8 8 10 15 16 18 22 25Перебрано решений 240 312 321 415 564 356 660 405Средний объем перебора составил - 409, эффективность работы алгоритма -3,98.Отобранные генетическим алгоритмом календарные планы производства пре-доставлялись технологу и менеджеру производства для согласования графика вы-пускаемой и отгружаемой продукции. Полученные решения хорошо согласова-лись с мнениями специалистов компании, что, несомненно, способствовало ре-шению такой важной управленческой задачи на промышленном предприятии, какпланирование производства и сбыта готовой продукции.ЗаключениеПредложенный вариант решения задачи планирования производства и сбытаготовой продукции, основанный на генетических алгоритмах, показал свою эф-фективность. Превосходство генетических алгоритмов состоит в том, что они ра-ботают при достаточно сложном рельефе функции приспособленности, причемрезультаты его работы представлены целой «популяцией» решений, имеют мень-ше шансов сойтись к локальному оптимуму и робастно функционируют на много-экстремальном ландшафте исходного пространства.

Скачать электронную версию публикации