Список сокращений
АРМ АСУ БП
Б ДМ
ГА ГК ГП ГТ ДП
кдм кя
КарНИИЛПК-
КЯ
ЛП
ЛПК
ОДУ
окп оп
ПетрГУ
СЦЛП
ТП
ТП
ТС
ЦБП
ЦБК
ЦЛП
автоматизированное рабочее место;
автоматизированная система управления;
билинейное программирование;
бумагоделательная машина;
гофроагрегат;
гофрокартон;
гофрополотно;
гофротара;
динамическое программирование;
картоноделательная машина;
картонный ящик;
Карельский НИИ лесопромышенного комплекса;
критерий эффективности;
линейное программирование;
лесопромышенный комплекс;
¦ оперативно-диспетчерское управление; объемно-календарное планирование; объемное планирование;
¦ Петрозаводский государственный университет; смешанное целочисленное ЛП; технологическая линия; технологический процесс;
транспортное средство;
• целлюлозно-бумажная промышленность; целлюлозно-бумажный комбинат;
• целочисленное ЛП.
Введение
В основу диссертационного исследования положен многолетний опыт разработки и применения математического моделирования, методов и комплексов программ для решения задач планирования про- изводства, прежде всего, предприятий лесопромышленного комплекса, (ЛПК) и целлюлозно-бумажной промышленности (ЦБП).
Диссертационная работа охватывает вопросы построения математических моделей планирования производственных процессов, разработки методов решения соответствующих оптимизационных задач и комплексов программ, в которых тесно переплетаются научные и прикладные проблемы.
Актуальность темы. Сложная социально-экономическая ситуация в России, обострение конкуренции среди промышленных предприятий и необходимость снижения себестоимости производимой продукции все настоятельнее требуют повышения эффективности производства, более рационального расходования имеющихся в его распоряжении финансовых и материальных средств и ресурсов, повышения производительности труда. Учитывая сложное финансовое положение многих предприятий и проблемы поиска инвестиций, часто не удается добиться повышения эффективности производства за счет экстенсивных факторов или расширения производства, его существенной реструктуризации и модернизации, освоения новой, более совершенной и конкурентоспособной продукции.
В значительной степени данные проблемы проявляются в перерабатывающих отраслях промышленности (лесной, деревообрабатыва- ющей, целлюлозно-бумажной, металлургической, горноперерабатыва-ющей и др.), где кроме общеэкономических присутствуют специфические, отраслевые проблемы: истощение наиболее продуктивных и каче-
6
ственных сырьевых баз, непропорционально высокий рост транспортных и топливно-энергетических расходов, повышение требовательности заказчиков к качеству производства и оформлению готовой продукции, снижение платежеспособного покупательского спроса, колебания цен на продукцию на внутреннем и внешнем рынках. В сложившихся условиях, одним из наиболее эффективных способов решения вышеуказанных проблем заключается в качественно новом уровне планиро-вания и управления предприятием и его подразделениями, используя современные организационные и информационно-аналитические методы, математическое моделирование, современные автоматизированные системы управления технологическими процессами и интегрированные системы управления предприятиями, системы поддержки принятия решений. При этом повышение эффективности производства может до-
(0 стигаться за счет оптимизации производственных процессов, то есть за
счет принятия рациональных управленческих решений, позволяющих повысить согласованность работы отдельных агрегатов, входящих в состав технологической системы. В результате этого сокращается время простоя оборудования, достигается значительная экономия сырья и энергии, повышаются объемы и качество выпускаемой продукции при аналогичных трудовых и производственных затратах.
Исследование производственных технологических процессов в пе-
& рерабатывающих отраслях промышленности показало, что многие из
них связаны с раскроями и комплектовкой материалов. Являясь очень важными, с точки зрения экономии используемых ресурсов, и, в то же время, одними из наиболее сложных для решения, эти задачи способны обеспечить возможность оптимального планирования и управления производственными процессами, сократить расход сырья и переделов, снизить себестоимость продукции и, в конечном счете, принести высо-
W кий экономический эффект. Для решения данных задач можно эффек-
тивно использовать методы математического моделирования и опти-
мизации с применением компьютерных технологии.
Следует отметить, что использование классических методов решения задач раскроя и комплектовки, как правило, не применимо для оптимизации многих реальных производственных процессов из-за необходимости учета их специфических особенностей, в частности - связей между объектами и предметами раскроя и комплектовки, а также - многочисленных дополнительных ограничений, обусловленных конкретными технологиями раскроя. Указанное обстоятельство требует разработки комплекса моделей, методов и программных систем для решения обобщенного класса задач раскроя и комплектовки с учетом дополнительных ограничений, что подтверждает актуальность выбранной темы диссертационного исследования.
Основная цель диссертационного исследования — разработка математических моделей, методов и комплексов программ для решения задач раскроя и комплектовки материалов в производственных системах.
В соответствии с поставленной целью в диссертации решаются следующие задачи:
1. Обоснование необходимости решения класса задач, связанных с оптимизацией планирования раскроев и комплектовок при наличии дополнительных ограничений;
2. Постановка и исследование комплекса математических моделей обобщенной задачи раскроя и комплектовки материалов.
3. Разработка методов решения обобщенной задачи раскроя и комплектовки с учетом большой размерности.
4. Определение схем декомпозиции прикладных многокритериальных задач расчета объемного и объемно-календарного планов, разработка методов расчета динамических параметров формирования производственных планов раскроя и комплектовки.
5. Разработка комплекса программ для решения прикладных задач
раскроя и комплектовки материалов.
6. Разработка рекомендаций по использованию предложенных моделей, методов и программных систем в организации планирования и управления производственными процессами, создании систем поддержки принятия решений.
Объектом исследования являются производственные техноло- гические процессы, связанные с раскроями и комплектовкой материалов.
Предметом исследования — математические модели и методы решения задач раскроя и комплектовки.
Методы исследования. Теоретической и методологической основой исследования являются методы исследования операций и математического программирования. Системный анализ и методы оптимиза- ции используются для анализа производственных процессов, построения математических моделей производственных процессов и разработки алгоритмов решения соответствующих экстремальных задач.
Методы линейного, динамического и дискретного программирования, теория двойственности, а также различные схемы декомпозиции задач используются для решения линейных и нелинейных задач сложной структуры и высокой размерности, элементы теории вероятности и математической статистики — для идентификации параметов и исследовании стохастических факторов.
Для разработки алгоритмов и программных комплексов использовались теория алгоритмов и структур данных, современные технологии проектирования программных систем, методы структурного и объектно-ориентированного программирования, проектирования баз данных. Для разработки программ использовались языки и системы программирования Fortran, C++, Pascal, Delphi, Clipper и ORACLE.
Научная новизна. В диссертации предложены новые и модифицированы известные методы решения прикладных задач, названных
10
обобщенными задачами раскроя, предложены принципы классификации исследуемых моделей, разработаны новые методы и схемы декомпозиции задач.
К числу результатов исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:
• Сформулирован и исследован класс задач оптимизации для моделирования процессов, содержащих операции раскроя и комплектовки материалов.
• Определен класс обобщенных задач раскроя, объединяющий рассматриваемые модели. Предложена классификация задач указанного класса.
• Разработаны схемы декомпозиции обобщенных задач раскроя и методы решения вспомогательных задач, связанных с ними;
• Разработаны методы расчета динамических параметров формирования производственных планов раскроя и комплектовки.
• Разработаны и протестированы эффективные методы и алгоритмы решения этих задач;
Практическая значимость и реализация результатов работы.
Полученные в диссертации результаты использовались при выполнении госбюджетных и хоздоговорных научно-исследовательских работ, выполненных под руководством и при личном участии автора на кафедре прикладной математики и кибернетики, в Центре ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 1981-2004г.г.
В работе приведены результаты вычислительных экспериментов, которые подтверждают применимость разработанных алгоритмов и программ для решения задач с размерностью, требуемой на практике. Представленные в работе математические модели, методы и алгоритмы решения, программные комплексы используются на ряде крупных
11
предприятий (ОАО "Архангельский ЦБК", ОАО "Сегежский ЦБК", ОАО "Кондопога", ОАО "Котласский ЦБК", ОАО "Карелэнерго", АХК "Кареллеспром" и др.). В результате эксплуатации программных систем на предприятиях повысилась эффективность управления производством, получен реальный экономический эффект. На основании результатов внедрения программных комплексов в промышленное производство, разработаны рекомендации по использованию предложенных моделей и методов в организации планирования и управления производственными процессами.
Рассмотренные в диссертации математические модели и методы решения задач обладают достаточной общностью и могут использоваться для планирования и управления производствами в других отраслях промышленности.
Полученные результаты используются в учебном процессе, кур-совых и дипломных работах студентов, исследованиях аспирантов, отражены в учебно-методической разработке "Исследование операций в планировании и управлении предприятием ЛПК" (С.-Петербург: Изд-во СПбГЛТА, 2001).
Апробация работы. Основные результаты диссертационной
работы докладывались автором на I съезде лесопромышленников Республики Карелия (Петрозаводск, 2004), Международной научно-техни- ческой конференции «Лесопромышленная логистика и информационные системы лесного комплекса» (Санкт-Петербург, 2003), Всероссийской научно-практической конференции «Проблемы лесопромышленных регионов» (Москва, 2002), IV Международном форуме «Лесопромышленный комплекс России XXI века» (Санкт-Петербург, 2002), I-V Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 1994, 1996, 1998, 2000, 2002), Научно-практических конференциях АХК «Кареллеспром» (Петрозаводск, 1998-2003), Международной конференции «Но-
12
вые технологии и устойчивое управление в лесах Северной Европы» (Петрозаводск, 2001); Республиканской научно-практической конференции «Устойчивое развитие региона: лесопромышленный комплекс» (Петрозаводск, 2000 г.), Республиканской научно-практической конференции «Актуальные проблемы лесного комплекса» (Петрозаводск, 1999 г.), XXV международной конференции «Экономическая наука: Теория, методология, направления развития» (Санкт-Петербург,1998), Республиканской научно-практической конференции «Ресурсосберегающие технологии лесного комплекса» (Петрозаводск, 1998), Международной научно-технической конференции «Проблемы развития лесного комплекса Северо-западного региона» (Петрозаводск, 1996), Всероссийской научно-практической конференции «Новые информационные технологии в образовании и управлении» (Петрозаводск, 1993 г.) и других конференциях и семинарах.
Структура и объем работы. Диссертация состоит из введения, 5 глав основного материала, заключения, библиографического списка и 3 приложений. Основной материал изложен на 218 стр., включая 26 рисунков и 17 таблиц. Библиографический список включает 198 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации.
Публикации. Основные результаты диссертационной работы опубликованы в 77 печатных работах, в т.ч. 6 монографиях, 67 статьях и материалах Международных, Всероссийских и региональных конференций и семинаров, 4 учебных пособиях.
Содержание работы
Во введении обоснована актуальность темы диссертации, указаны цель и задачи исследования, обсуждены научная новизна и практическая значимость работы.
В начале первой главы представлена терминология, необходимая для описания математических моделей и методов решения соответ-
13
ствующих оптимизационных задач. Вводятся задачи раскроя и комплектовки, устанавливается их содержание, приводится классификация связанных с ними моделей. Исследование наиболее часто встречающихся на практике задач выявляет основные особенности рассматриваемого в последующих главах класса моделей — большое количество разнообразных дополнительных ограничений и возможность декомпозиции планов раскроя.
Рассматривается проблема критерия оптимальности. Практически все прикладные задачи являются многокритериальными, что вызывает необходимость использования соответствующих средств их решения. Заключительные разделы главы посвящены идентификации моделей планирования и управления производством и исследованию связей задач комплекса математических моделей. Первую главу диссертации, как и последующие, завершают выводы.
Вторая глава содержит описание разработанных автором методов и технических приемов решения задач раскроя и комплектовки. Эти задачи весьма неоднородны не только по своему назначению и месту в планировании и управлении производством, но и по структуре используемой модели, переменным, связям между ними, критериям эффективности и целевым функциям. Ввиду сложности- прикладных задач этого класса, большая их часть реализуется комплексом взаимосвязанных моделей.
Решение большого количества весьма разнообразных по форме и содержанию оптимизационных задач требует использования определенного набора средств, инструментария постановщика модели и разработчика алгоритмов. Содержание главы посвящено особенностям применения методов линейного, дискретного, динамического программирования (ДП), методов декомпозиции и эвристик в решении рассматриваемых экстремальных задач.
В третьей главе конструируется класс задач раскроя и ком-
14
плектовки, который удачно сочетает многообразие приложений в области управления производством и возможность использования единого математического инструментария алгоритмов решения.
Для этого исследуются прикладные задачи и выделяются два класса взаимосвязанных моделей: формирования планов и оптимизации их состава. Изучение особенностей этих задач приводит к обобщенной задаче оптимизации планов раскроя, для решения которой уда-Щ> ется применить эффективный метод генерации столбцов. Задача носит
достаточно общий характер, на практике встречаются ее частные случаи, признаки которых позволяют классифицировать широкий класс моделей оптимизации планов, достаточно полно представляющих большое количество прикладных задач раскроя и комплектовки.
Исследуемый класс задач составляют детерминирование модели. Их практическую значимость и адекватность ситуации управления можно повысить, используя представленные в следующем разделе приемы, которые позволяют в рамках данного класса задач учесть некоторые стохастические факторы, включая случайный характер появления продукции пониженного качества или неопределенность сроков переналадки оборудования. Главу завершает исследование связей объемного (ОП) и объемно-календарного планов (ОКП) производств, а также методы построения ОКП на основе рассчитанного ОП.
В четвертой и пятой главах рассматриваются прикладные за-дачи оптимизации планов раскроя и комплектовки, среди которых расчет планов и распределение заявок с учетом режимов работы группы бумагоделательных машин, формирование ОП и ОКП производства го-фротары, оптимизация погрузки продукции предприятия ЦБП в транспортные средства (ТС), выбор оборудования для заготовки и транспортировки древесины и технологической щепы, комплектовка оборудова-ния лесозаготовительного предприятия и другие. Эти задачи являются частными случаями обобщенной модели, представленной в 3 главе, они
15
охватывают разные аспекты управления предприятиями и характерны для комплексной системы управления производством предприятий различных отраслей промышленности.
В заключении представлены основные результаты работы.
Диссертацию завершают библиографический список из 197 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации.
Автор благодарит за поддержку и полезные советы при подготовке и оформлении диссертации, проф. Чернецкого В. И. — основателя научной школы прикладной математики ПетрГУ, доц. СПбГУ Шала-бина Г. В., проф. И.Р.Шегельмана, доц. Воронина А. В.
Глава 1. Задачи раскроя и комплектовки в моделировании технологических процессов
Прикладные задачи расчета оптимального плана раскроя или комплектовки материалов чрезвычайно разнообразны, поскольку эти технологические операции часто являются основными в различных про-* мышленных производствах. В главе приводятся постановка и исследо-
вание особенностей прикладных моделей планирования и управления предприятиями, связанных с этими операциями и принципы их классификации.
Прежде всего, учитывая наличие расхождений в общепринятой терминологии, вводятся обозначения, используемые в диссертации при ^ описании моделей и алгоритмов.
Далее представлены определения задач поиска оптимальных планов раскроя и комплектовки, а также классификация рассматриваемых в диссертации моделей. Исследованы наиболее часто встречающиеся классы таких задач, установлена их основная особенность — наличие дополнительных ограничений.
Модели и методы решения задач комплектовки во многом сходны с моделями и методами решения задач раскроя, что позволяет рассма-(6- тривать эти классы задач совместно, под общим названием «задачи
раскроя».
В оптимизационых задачах важен критерий эффективности (КЭ), который, будучи формализацией целей управления, определяет оптимальное решение и основанные на нем управления, достоверные данные и параметры. Поэтому далее рассматриваются возможные КЭ и условия их выбора, проблемы идентификации моделей и их параметров 0&; и краткая характеристика рассматриваемых в диссертации задач.
16
17 1.1. Терминология и обозначения
В дисертационной работе используется терминология работ [151, 156, 157], при описании ТП — работа Первозванского А. А. [151], математических обозначений — книга Романовского И. В. [156].
Вектор а[Р] определим как отображение произвольного конечного индексного множества а : Р —> R1. Общепринятое определение век-т тора как функции натурального аргумента а = (ai,...,an) является
частным случаем данного, что позволяет рассматривать части вектора а[Р'], Р' С Р, не заботясь о нумерации элементов. Индексное множество может не указываться, если это не приводит к неоднозначности, вектор-строка и вектор-столбец не различаются.
Индекс компоненты вектора а,- может быть указан в скобках (a[i]). Верхние индексы используются либо для перечисления элементов по-v- следовательности, либо для выделения некоторых индексных множеств
в громоздких обозначениях. Скалярное произведение a b определяется для векторов а[Р], Ь[Р] с одинаковым индексным множеством, например, а Ъ = а[Р] Ь[Р] = ЕреР ар Ьр.
Сравнение векторов выполняется покомпонентно, векторные нуль О = (0, 0, ...,, 0) и единицу 1 = (1, 1, ..., 1) удобно использовать для записи условия неотрицательности х > 0 или вычисления суммы компонент вектора 1 а = Т,реР ар. Чтобы упростить описание громоздких
б*
математических моделей, индексная переменная будет связана с определенным индексным множеством (г ? М, j ? N, s ? S и т. п.).
Использование свертки по ближнему индексу при перемножении матриц и векторов позволяет реже применять операцию транспонирования матрицы. К примеру, в качестве задачи линейного программирования (ЛП) в дальнейшем будет рассматриваться задача Р:
^ z = c[N]x[N] ->max(mm); A[M,N]x[N] • Ь[М}; x[N] > О
или: сх —> max(min); Ах • 6; х > 0; |
