В различных отраслях современного производства все чаще встают вопросы оптимизации и планирования. Это приводит к необходимости решения таких задач, как оптимальный выбор оборудования, составление планов и расписаний, управление запасами, оптимизация раскроя материала и многие другие. Наряду с разработкой эффективных алгоритмов оптимизации для решения таких задач необходимо создать инструментальные средства, включающие данные алгоритмы, а также внедрить и применить такие системы в производственном процессе как на этапе подготовки производства, так и на этапе функционирования. Такие системы должны быть ориентированы на предметную область, под конкретные производственные условия, иметь удобный интерфейс и необходимый набор инструментов для выполнения производственных и исследовательских задач, в частности, функции настройки параметров алгоритма оптимизации, инструментарий для зада- ния параметров задачи, функции ввода-вывода данных и др.
В статье представлены инструментальные средства для решения задач из трех предметных областей: для оптимизации раскроя материала с динамическим портфелем заказов, для моделирования и оптимизации складской политики цепей поставок и для автоматизированного построения проектных расписаний.
Особенности задач и методы решения
В формализованной математической постановке задачи производственного планирования, как правило, представляют собой сложные задачи комбинаторной оптимизации, особенностями которых являются очень большое пространство поиска решений, cложные ограничения целевой функции и NP-полнота [1]. Поэтому на практике для решения таких задач применяют приближенные методы – эвристики, а в последнее время более перспективные и эффективные методы глобальной оптимизации – метаэвристики, которые решают вопрос выхода из локальных оптимумов и настроены на поиск глобального оптимума, а также позволяют работать в пространствах большой размерности с учетом cложных ограничений. На сегодняшний день эволюционные метаэвристики (ЭМ), а именно генетический алгоритм (ГА) и эволюционная стратегия (ЭС), нашли широкое применение для решения большого числа сложных задач оптимизации [2].
В случае применения ЭМ необходимо разработать отдельные операторы алгоритма, учитывающие особенности конкретной оптимизационной задачи и свойства целевой функции, а главное – ограничения целевой функции, обусловленные спецификой предметной области.
Можно выделить два основных подхода к разработке операторов ЭМ.
1. Разрабатываются простые операторы, которые, как правило, основаны на классических принципах (кроссинговер, рекомбинация, точечная или генная мутация и др.), а учет ограничений выносится в штрафные функции. Преимущества подхода: операторы легко описать и разработать. Недостаток: плохая сходимость и неудовлетворительное качество получаемого решения (зачастую алгоритм может не учесть отдельные ограничения).
2. Разрабатываются модифицированные операторы ЭМ, учитывающие ограничения во внутренней логике работы. Преимущества: хорошая сходимость и время работы алгоритма, а также качество получаемого решения. Недостаток: высокая интеллектуальная сложность алгоритма (операторы алгоритма труднее разработать и реализовать). Тем не менее данный подход предпочтительнее.
Во многих задачах целевую функцию сложно или невозможно представить в строгом аналитическом виде. В таких случаях метод имитационного моделирования является единственным подходом к построению моделей необходимого уровня детализации и адекватности реальным систе- мам [3]. Оптимизация на основе имитационного моделирования заключается в совместном использовании имитационной модели (ИМ) сложной системы и алгоритма оптимизации. С помощью ИМ рассчитываются значения отклика для различных комбинаций значений факторов, которые предлагает алгоритм оптимизации. Поисковый алгоритм оптимизации, в свою очередь, используя значения отклика, пытается улучшить решение. Для алгоритма оптимизации модель служит лишь механизмом преобразования входа в выход – концепция «черный ящик». Фактор случайности ИМ может вносить негативный эффект в работу ЭМ, приводя к блужданию поискового процесса, потере скорости сходимости алгоритма и попаданию в локальные оптимумы. В специальной литературе по данному вопросу отмечено, что основным является качество работы оператора селекции ЭМ при выборе особей в следующее поколение [4]. При этом один из основных подходов корректной оценки целевой функции – проведение серии прогонов ИМ для одной особи-решения.
Среда для оптимизации раскроя материала с динамическим портфелем заказов
При производстве мебели необходимо оклеивать дорогостоящей пленкой деревянные блоки прямоугольной формы. Пленка наклеивается на мембранно-вакуумном прессе, поверхность которого также является прямоугольником. Процесс оклейки состоит из двух этапов: сначала блоки укладываются на поверхность пресса с учетом направленности рисунка пленки, затем происходит запрессовка. На вход производственной системы поступают заказы на кухонные гарнитуры. Каждый блок является составляющей одного кухонного гарнитура. Размеры блоков и их количество определяются портфелем заказов. Заказы могут быть двух типов: срочные и обычные. На выходе системы необходимо формировать карты раскроя. Каждая карта раскроя представляет собой вариант укладки блоков на поверхность пресса. Гарнитур считается изготовленным, если все его блоки вошли в карты раскроя. При составлении очередной карты приоритет должны иметь блоки наиболее близкого к завершению гарнитура. Эта особенность вытекает из необходимости исключения простоев и чрезмерной загрузки оборудования.
Программная среда состоит из следующих компонентов: таблица текущих заказов, таблица невыполненных заказов, таблица выполненных заказов, блок оптимизации и модуль визуализации карт раскроя. Интерфейс и программные компоненты реализованы в среде Borland C++ Builder.
Исходная информация (портфель заказов) загружается в среду из файла, формируется таблица текущих заказов. Далее происходит сортировка блоков по типам пленки и для каждой группы блоков формируется таблица невыполненных заказов. Затем осуществляется запуск модуля оптимизации для составления карт раскроя из невыполненных заказов для каждого типа пленки. После того как данный модуль реализовал решение, блоки, вошедшие в карту раскроя, переводятся из невыполненных заказов в таблицу выполненных заказов. При этом формируется карта раскроя, которую пользователь может посмотреть на экране (рис. 1).
Модуль оптимизации основан на генетическом оптимизационном алгоритме в сочетании с алгоритмом укладки блоков [5].
Целевая функция имеет следующий вид: ЦФ = = Km + a1×Ku + a2×Kp, где Km – коэффициент использования материала (КИМ), , где Sбл – суммарная площадь всех блоков, уложенных на поверхность пресса, Sпр – площадь поверхности пресса; Ku – параметр, определяющий срочность заказов; Kp – параметр, определяющий приоритет заказов; a1, a2 – весовые коэффициенты, определяющие значимость производственных факторов.
Для получения карты раскроя необходимо определить номера блоков, которые нужно выбрать из портфеля заказов, а также их очередность при укладке на пресс. Поэтому каждому блоку в портфеле заказов, помимо идентификационного номера, присваивается порядковый номер, определяющий очередность его укладки. Задачи ГА – выбор блоков из портфеля заказов и определение комбинации значений порядковых номеров блоков, при которых достигается максимум заданного критерия. Для алгоритма укладки блоков исходными данными является набор порядковых номеров блоков, которые выдает ГА, а выходной величиной – значение целевой функции для полученной карты раскроя.
В среде предусмотрено задание пользователем значения желаемого КИМ. Если КИМ, полученный в результате раскроя, больше или равен этому значению, карта раскроя формируется автоматически. Если же это условие не выполняется, блоки остаются в числе невыполненных заказов и до- жидаются поступления новых заказов для реа- лизации лучших карт раскроя. После того как сформировались карты, их можно записать в файл, который используется на следующем этапе функционирования производственной системы.
Среда для моделирования и оптимизации складской политики цепей поставок
В последнее время управление складом в многоэшелонных цепях поставки играет важную роль в процессе управления сложной системой. Наиболее значимым является определение параметров заказа, а именно: что, когда и в каких количествах заказывать. В частности, на предприятиях данная задача решается с помощью аналитических расчетов, при которых используется упрощенная модель складской системы [6], а для определения оптимальной стратегии управления такой системой применяются аналитический метод и экспертный подход.
В реальных условиях многоэшелонная цепь – сложная система, потому что между эшелонами существуют взаимосвязи. Для разработки моделей таких систем хорошо подходит имитационное моделирование. Так, при решении задачи оптимизации складской политики строится имитационная модель складской системы, параметры которой оптимизируются [7].
Среда позволяет моделировать и оптимизировать складскую политику двухэшелонных цепей поставок объединенного типа. Структура цепи включает магазины, которые находятся в определенном радиусе от распределительного склада. Для магазинов поддерживается одинаковый ассортимент. В каждый магазин товар доставляется грузовиком из распределительного склада, причем грузовик не отправляется, пока вес товара в нем не превысит заданный минимальный вес. Также у грузовика есть ограничения на максимальный вес. Каждый товар характеризуется весом, поставщиком, стоимостью хранения в распределительном складе и магазине. Если количество товара становится меньше критического уровня, осуществляется заказ товара. Объем заказа фиксированный. Магазины отличаются частотой прихода покупателя, расстоянием до распределительного склада и стоимостью доставки. Считается, что у поставщика всегда есть товар. Поставщики характеризуются временем и стоимостью доставки товара на распределительный склад.
Среда включает блоки ввода исходных данных, имитационного моделирования, выбора параметров оптимизации и блок оптимизации на базе алгоритма эволюционной стратегии. Интерфейс и программные компоненты реализованы в среде Microsoft Visual C++.
Блок ввода исходных данных. В зависимости от выбранного количества магазинов, количества поставщиков и количества товаров создаются таблицы для задания данных по товарам, поставщикам и магазинам. Система осуществляет автоматическую проверку правильности ввода исходных данных, а именно: правильность формата данных, полноту данных для проведения той или иной операции, соответствие ограничениям предметной области и физическому смыслу.
Блок имитационного моделирования. Среда поддерживает автоматическое вычисление средних значений издержек (транспортировки, хранения и штрафов из-за дефицита), а также их среднеквадратических отклонений для заданного времени моделирования и числа прогонов модели. Можно вывести таблицу с процентом времени, которое каждый товар находился в дефиците, а также визуализировать работу системы в виде графиков инвентаризации.
Блок ввода оптимизируемых параметров. Критерием оптимизации являются суммарные затраты на интервале планирования, рассчитываемые по формуле W = WI + WS + WD, где WI – издержки хранения; WS – штрафы за дефицит товара на складе (процент дефицита преобразуется в штрафную функцию по графику арктангенс); WD – затраты на организацию поставок при соблюдении условия, что дефицит для каждого товара не превышает некое заранее заданное значение d (%).
В качестве оптимизируемых параметров используются параметры складской политики. Пользователю предлагается выбрать критические уровни и объемы заказов, подлежащие оптимизации с использованием алгоритма эволюционной стратегии. Существует возможность задания параметров оптимизации с помощью формул.
Блок оптимизации. В качестве оптимизационного алгоритма используется эволюционная стратегия типа (µ, λ) [2]. Пользователю предлагается задать параметры оптимизационного алгоритма: число родителей, число потомков, шаг мутации, критерий останова (максимальное число вычислений целевой функции), параметры для вычисления целевой функции (время моделирования, число прогонов имитационной модели).
Генерация начальной популяции для алгоритма ЭС реализуется по следующему алгоритму.
1. Вычисляется среднее значение издержек для заданного количества прогонов модели. Исходя из полученного значения рассчитывается коэффициент для преобразования процента дефицита в штрафную функцию.
2. Создаются λ особей. Каждый ген генерируется по нормальному закону с заданными параметрами.
3. Для значений генов проверяются следующие ограничения:
– если критический уровень склада меньше объема заказа магазина, то критический уровень приравнивается к объему заказа;
– если максимально возможный вес грузовика меньше минимально допустимого веса, то вес оптимизируемых объемов заказов меняется пропорционально их значениям;
– если объем заказа магазина весит больше максимального веса грузовика, то объем заказа уменьшается таким образом, чтобы его вес равнялся или был меньше максимально допустимого веса грузовика.
4. Вычисляются параметры, заданные в блоке выбора параметров оптимизации с помощью формул.
5. С помощью имитационной модели вычисляются суммарные издержки.
Затем выполняется алгоритм ЭС.
Среда поддерживает вывод графиков изменения шага мутации, среднего и минимального по популяции значения целевой функции в процессе оптимизации (рис. 2).
На выходе пользователь получает вектор оптимизированных параметров (в него входят все параметры складской политики), а также суммарные издержки хранения и транспортировки. Можно транслировать полученное решение в блок исходных данных и исследовать его с использованием имитационного моделирования.
Среда для автоматизированного построения проектных расписаний
Задачи составления расписаний возникают, например, на производстве, когда существует необходимость в упорядочении операций по исполнителям (станки, цеха) и по времени; при составлении расписаний движения транспорта; при планировании занятий в учебных заведениях; при планировании занятости персонала и т.д. [8].
Среда предназначена для построения расписаний проекта с учетом ресурсных ограничений и отношений предшествования. Исходными данными являются множество работ и множество типов возобновляемых ресурсов. Каждый тип ресурсов характеризуется величиной производительности (чем выше производительность, тем больше стоимость ресурса). Каждая работа может быть выполнена с использованием разных наборов ресурсов, поэтому стоимость и время выполнения работы могут меняться [9]. Во время обслуживания работы требуется некоторое количество единиц ресурса определенного типа. После завершения обслуживания работы освобожденные ресурсы в полном объеме могут быть мгновенно назначены на обслуживание других работ. Также между некоторыми работами заданы отношения предшествования. Необходимо определить моменты времени начала обслуживания каждой работы так, чтобы минимизировать время и стоимость выполнения проекта.
Программное средство состоит из следующих модулей: блок задания исходных данных, блок оптимизации и блок визуализации решения. Интерфейс и программные компоненты реализованы в среде Microsoft Visual C++.
Блок задания исходных данных. В зависимости от заданного пользователем количества работ в проекте и количества типов ресурсов создаются таблицы для задания данных по работам и ресурсам. Для ресурсов задаются следующие данные: номер типа ресурса, производительность ресурса, количество единиц ресурса данного типа, стоимость единицы ресурса. Для работ задаются номер работы, ее длительность и объем, требующиеся для выполнения работы ресурсы, предшественники.
Блок оптимизации. Для оптимизации рас- писания используется ГА со специально разработанными операторами скрещивания и мутации, которые обеспечивают получение решений, удовлетворяющих ограничениям задачи. Целевая функция вычисляет полное время выполнения проекта и общую стоимость проекта.
В данном окне (рис. 3) выбираются следующие параметры ГА.
· Число особей в популяции.
· Процент скрещивания. В зависимости от размерности задачи и сложности отношений предшествования эффективный процент скрещивания может меняться.
· Схема мутации. Предусмотрены три схемы мутации, которые отличаются друг от друга степенью применения блоков мутации (блок перестановки и блок изменения длительности работы). Блок перестановки меняет местами две различные работы, учитывая при этом ограничения предшествования. Блок изменения длительности изменяет длительность работы путем выбора другого ресурса, пригодного для выполнения данной работы. Таким образом, можно сократить время выполнения работы, увеличив при этом ее стоимость, или наоборот, сократить стоимость выполнения работы, увеличив ее длительность.
В окне также выводится график, отображающий изменение среднего и минимального значений целевой функции по популяции в процессе работы ГА.
Блок визуализации решения. Данное окно (рис. 4) предназначено для визуализации решения, полученного с применением ГА.
Здесь можно видеть полученную последовательность работ, а также время и стоимость выполнения проекта.
В заключение отметим, что в рамках данного направления, которое связано с разработкой программных средств для решения практических задач оптимизации и планирования производственной деятельности, можно выделить следующие направления развития:
– разработка эффективных оптимизационных алгоритмов;
– создание адекватных моделей производственных систем и процессов;
– включение различных постановок задач в рамках одного программного средства;
– создание набора инструментальных средств для реализации исследовательских задач;
– интеграция с другими программными системами.
Реализация метаэвристических оптимизационных алгоритмов, средств имитационного моделирования совместно с наличием широкого спектра функциональных возможностей позволят создавать эффективные системы оптимизации производственной деятельности.
Литература
1. Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
2. Glover F., Kochenberger G. Handbook of Metaheuristics. Kluwer, Boston, MA, 2003, 570 p.
3. Лоу А., Кельтон В. Имитационное моделирование. Классика СS. 3-е изд. СПб: BHV, 2004. 847 с.
4. Jin Y., Branke J. Evolutionary optimization in uncertain environments – a survey. IEEE Transactions on evolutionary computation, 2005, vol. 9, no. 3, pp. 303–317.
5. Афонин П.В. Система рационального раскроя материала с применением генетического оптимизационного алгоритма // Браславская школа-2000: тр. 4-й Междунар. летней школы-сем. по искусственному интеллекту для студентов и аспирантов. Беларусь, Минск: Изд-во БГУ, 2000. С. 125–128.
6. Стерлингова А.Н. Управление запасами в цепях поставок: учебник. М.: ИНФРА, 2008.
7. Захаров П.А. Управление запасами и организация поставок в условиях позаказного производства на основе гибридных систем // Интегрированные модели и мягкие вычисления в искусственном интеллекте: сб. тр. Междунар. науч.-практич. семинара. М.: Физматлит, 2001. С. 83–88.
8. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. М.: МГУ, 2011. 224 с.
9. Brucker P., Drexl A., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, models and methods. European Journal of Operational Research, 1999, vol. 112, pp. 3–41.
References
1. Gary M., Johnson D. Computers and Intractability: A Guide to the Theory of. NP-Completeness, 1979 (Russ. ed.:
Fridman A. Moscow, Mir Publ., 1982).
2. Glover F., Kochenberger G. Handbook of Metaheuristics. Kluwer Publ., Boston, MA, 2003, 570 p.
3. Law A.M., Kelton W.D. Simulation Modeling and Analysis. 3rd ed., McGraw-Hill Publ., 2000 (Russ. ed.: St. Peters-burg, BHhV Publ., 2004).
4. Jin Y., Branke J. Evolutionary optimization in uncertain environments – a survey. IEEE Transactions on Evolution-ary Computation. 2005, vol. 9, no. 3, pp. 303–317.
5. Afonin P.V. Reasonable material cutting system using genetic optimization algorithm. Trudy 4 Mezhdunar. letney
shkoly-seminara po iskusstvennomu intellektu dlya studentov i aspirantov (Braslavskaya shkola-2000) [Proc. 4th Int. Sum-mer School-Workshop on Artificial Intelligence for Students and Postgraduates]. Minsk, BGU Publ., 2000, pp.125–128 (in
Russ.).
6. Sterlingova A.N. Upravlenie zapasami v tsepyakh postavok [Stock Control in Supply Chains]. Textbook, Moscow,
INFRA Publ., 2008.
7. Zakharov P.A. Stock control and supply maintenance for order production based on hybrid systems. Integrirovannye
modeli i myagkie vychisleniya v iskusstvennom intellekte. Sbornik trudov Mezhdunar. nauchno-praktich. seminara [Integrat-ed Models and Soft Computing in Artificial Intelligence. Proc. of the Int. Science and Practice Workshop]. Moscow,
Fizmatlit Publ., 2001, pp. 83–88 (in Russ.).
8. Lazarev A.A., Gafarov E.R. Teoriya raspisany. Zadachi i algoritmy [The Theory of Scheduling. Problems and Algo-rithms]. Moscow, Moscow State Univ. Publ., 2011.
9. Brucker P., Drexl A., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, mod-els and methods. European Journ. of Operational Research. 1999, vol. 112, pp. 3–41.