автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели, методы и программные комплексы оптимального раскроя и комплектовки с учетом дополнительных ограничений

На правах рукописи

МАТЕМАТИЧЕСКИЕ МОДЕЛИ, МЕТОДЫ И ПРОГРАММНЫЕ КОМПЛЕКСЫ ОПТИМАЛЬНОГО РАСКРОЯ И КОМПЛЕКТОВКИ С УЧЕТОМ ДОПОЛНИТЕЛЬНЫХ ОГРАНИЧЕНИЙ

Специальность: 05.13.18— Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Петрозаводск - 2004

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ на кафедре прикладной математики и кибернетики

Официальные оппоненты:

доктор технических наук, профессор Мухачева Э.А.

доктор физико-математических наук, профессор Романовский И.В. доктор технических наук, профессор Савин И.К.

Ведущая организация:

Санкт-Петербургский институт информатики и автоматизации Российской Академии наук

в Лз. часов на заседании диссертационного совета Д.212.190.03 в Петрозаводском государственном университете по адресу: 185640, г. Петрозаводск, пр. Ленина, д. 33.

С диссертацией можно ознакомиться в Научной библиотеке Петрозаводского государственного университета.

Защита диссертации состоится в JS- часов на заседании д

Автореферат

Ученый секретарь диссертационного совета, кандидат технических н а у к , у

доцент

В.В. Поляков

Общая характеристика работы

Актуальность

Сложная социально-экономическая ситуация в России, обострение конкуренции среди промышленных предприятий и необходимость снижения себестоимости производимой продукции все настоятельнее требуют повышения эффективности производства, более рационального расходования имеющихся в его распоряжении финансовых и материальных средств и ресурсов, повышения производительности труда. Учитывая сложное финансовое положение многих предприятий и проблемы поиска инвестиций, часто не удается добиться повышения эффективности производства за счет экстенсивных факторов или расширения производства, его существенной реструктуризации и модернизации, освоения новой, более совершенной и конкурентоспособной продукции.

В значительной степени данные проблемы проявляются в перерабатывающих отраслях промышленности (лесной, деревообрабатывающей, целлюлозно-бумажной, металлургической, горноперера-батывающей и др.), где кроме общеэкономических присутствуют специфические, отраслевые проблемы: истощение наиболее продуктивных и качественных сырьевых баз, непропорционально высокий рост транспортных и топливно-энергетических расходов, повышение требовательности заказчиков к качеству производства и оформлению готовой продукции, снижение платежеспособного покупательского спроса, колебания цен на продукцию на внутреннем и внешнем рынках. В сложившихся условиях одним из наиболее эффективных способов решения вышеуказанных проблем является качественно новый уровень планирования и управления предприятием и его подразделениями с использованием современных организационных и информационно-аналитических методов, математического моделирования, современных автоматизированных систем управления технологическими процессами и интегрированных систем управления предприятиями, систем поддержки принятия решений. При этом повышение эффективности производства может достигаться за счет оптимизации производственных процессов, то есть за счет принятия рациональных управленческих решений, позволяющих повысить согласованность работы отдельных агрегатов, входящих в

состав технологической системы. В результате этого сокращается время простоя оборудования, достигается значительная экономия сырья и энергии, повышаются объемы и качество выпускаемой продукции при аналогичных трудовых и производственных затратах.

Исследование производственных технологических процессов в перерабатывающих отраслях промышленности показало, что многие из них связаны с раскроями и комплектовкой материалов. Являясь очень важными с точки зрения экономии используемых ресурсов и в то же время одними из наиболее сложных для решения, эти задачи способны обеспечить возможность оптимального планирования и управления производственными процессами, сократить расход сырья и переделов, снизить себестоимость продукции и, в конечном счете, привести к высокрму экономическому эффекту. Для решения данных задач можно эффективно использовать методы математического моделирования и оптимизации с применением компьютерных технологий.

Следует отметить, что использование классических методов решения задач раскроя и комплектовки, как правило, не применимо для оптимизации многих реальных производственных процессов из-за необходимости учета их специфических особенностей, в частности, связей между объектами и предметами раскроя и комплектовки, а также многочисленных дополнительных ограничений, обусловленных конкретными технологиями раскроя. Указанное обстоятельство требует разработки комплекса моделей, методов и программных систем для решения обобщенного класса задач раскроя и комплектовки с учетом дополнительных ограничений, что подтверждает актуальность выбранной темы диссертационного исследования.

Цели и задачи исследования

Основная цельдиссертационного исследования—разработ-

ка математических моделей, методов и комплексов программ для решения задач раскроя и комплектовки материалов в производственных системах.

В соответствии с поставленной целью в диссертации решаются следующие задачи:

1. Обоснование необходимости решения класса задач, связанных

с оптимизацией планирования раскроев и комплектовок при наличии дополнительных ограничений.

2. Постановка и исследование комплекса математических моделей обобщенной задачи раскроя и комплектовки материалов.

3. Разработка методов решения обобщенной задачи раскроя и комплектовки с учетом большой размерности.

4. Определение схем декомпозиции прикладных многокритериальных задач расчета объемного и объемно-календарного планов, разработка методов расчета динамических параметров формирования производственных планов раскроя и комплектовки.

5. Разработка комплекса программ для решения прикладных задач раскроя и комплектовки материалов.

6. Разработка рекомендаций по использованию предложенных моделей, методов и программных систем в организации планирования и управления производственными процессами, создании систем поддержки принятия решений.

Объектом исследования являются производственные технологические процессы, связанные с раскроями и комплектовкой материалов.

Предметом исследования — математические модели и методы решения задач раскроя и комплектовки.

Методы исследования

Теоретической и методологической основой исследования являются методы исследования операций и математического программирования. Системный анализ и методы оптимизации используются для анализа производственных процессов, построения математических моделей производственных процессов и разработки алгоритмов решения соответствующих экстремальных задач.

Методы линейного, динамического и дискретного программирования, теория двойственности, а также различные схемы декомпозиции задач используются для решения линейных и нелинейных задач сложной структуры и высокой размерности, элементы теории

вероятности и математической статистики — для идентификации параметров и исследования стохастических факторов.

Для разработки алгоритмов и программных комплексов использовались теория алгоритмов и структур данных, современные технологии проектирования программных систем, методы структурного и объектно-ориентированного программирования, проектирования баз данных. Для разработки программ использовались языки и системы программирования Fortran, C + +, Pascal, Delphi, Clipper и ORACLE.

Научная новизна

В диссертации предложены новые и модифицированы известные методы решения прикладных задач, названных обобщенными задачами раскроя, предложены принципы классификации исследуемых моделей, разработаны новые методы и схемы декомпозиции задач.

К числу результатов исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:

♦ Сформулирован и исследован класс задач оптимизации для моделирования процессов, содержащих операции раскроя и комплектовки материалов.

♦ Определен класс обобщенных задач раскроя, объединяющий рассматриваемые модели. Предложена классификация задач указанного класса.

♦ Разработаны схемы декомпозиции обобщенных задач раскроя и методы решения вспомогательных задач, связанных с ними.

♦ Разработаны методы расчета динамических параметров формирования производственных планов раскроя и комплектовки.

♦ Разработаны и протестированы эффективные методы и алгоритмы решения этих задач.

Практическая значимость и реализация результатов работы

Полученные в диссертации результаты использовались при выполнении госбюджетных и хоздоговорных научно-исследовательских

работ, выполненных под руководством и при личном участии автора на кафедре прикладной математики и кибернетики, в Центре ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 1981-2004 гг.

В работе приведены результаты вычислительных экспериментов, которые подтверждают применимость разработанных алгоритмов и программ для решения задач с размерностью, требуемой на практике. Представленные в работе математические модели, методы и алгоритмы решения, программные комплексы используются на ряде крупных предприятий (ОАО "Архангельский ЦБК", ОАО "Се-гежский ЦБК", ОАО "Кондопога", ОАО "Котласский ЦБК", ОАО "Карелэнерго", АХК "Кареллеспром" и др.). В результате эксплуатации программных систем на предприятиях повысилась эффективность управления производством, получен реальный экономический эффект. На основании результатов внедрения программных комплексов в промышленное производство разработаны рекомендации по использованию предложенных моделей и методов в организации планирования и управления производственными процессами, имеются акты внедрения программных систем в промышленную эксплуатацию и свидетельства о рационализаторских предложениях.

Рассмотренные в диссертации математические модели и методы решения задач обладают достаточной общностью и могут использоваться для планирования и управления производствами в других отраслях промышленности.

Полученные результаты применяются в учебном процессе, курсовых и дипломных работах студентов, исследованиях аспирантов, отражены в учебно-методической разработке "Исследование операций в планировании и управлении предприятием ЛПК" (СПб.: Изд-во СПбГЛТА, 2001).

Апробация работы

Основные результаты диссертационной работы докладывались автором на I съезде лесопромышленников Республики Карелия (Петрозаводск, 2004), Международной научно-технической конференции «Лесопромышленная логистика и информационные системы лесного комплекса» (Санкт-Петербург, 2003), Всероссийской научно-практической конференции «Проблемы лесопромышленных регионов» (Москва, 2002), IV Международном форуме «Лесопромышлен-

ный комплекс России XXI века» (Санкт-Петербург, 2002), 1-У Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 1994, 1996, 1998, 2000, 2002), Научно-практических конференциях АХК «Карел-леспром» (Петрозаводск, 1998-2003), Международной конференции «Новые технологии и устойчивое управление в лесах Северной Европы» (Петрозаводск, 2001); Республиканской научно-практической конференции «Устойчивое развитие региона: лесопромышленный комплекс» (Петрозаводск, 2000), Республиканской научно-практической конференции «Актуальные проблемы лесного комплекса» (Петрозаводск, 1999), XXV международной конференции «Экономическая наука: Теория, методология, направления развития» (Санкт-Петербург, 1998), Республиканской научно-практической конференции «Ресурсосберегающие технологии лесного комплекса» (Петрозаводск, 1998), Международной научно-технической конференции «Проблемы развития лесного комплекса Северо-Западного региона» (Петрозаводск, 1996), Всероссийской научно-практической конференции «Новые информационные технологии в образовании и управлении» (Петрозаводск, 1993) и других конференциях и семинарах.

Структура и объем работы

Диссертация состоит из введения, 5 глав основного материала, заключения, библиографического списка и 3 приложений. Основной материал изложен на 218 стр., включая 26 рисунков и 17 таблиц. Библиографический список включает 197 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации.

Публикации

Основные результаты диссертационной работы опубликованы в 75 печатных работах, в т. ч. 9 монографиях, 62 статьях и материалах Международных, Всероссийских и региональных конференций и семинаров, 3 учебных пособиях.

Содержание работы

Во введении обоснована актуальность темы диссертации, указаны цель и задачи исследования, обсуждены научная новизна и практическая значимость работы.

В первой главе вводятся задачи раскроя и комплектовки, определяются их содержание и классификация связанных с ними моделей. Следуя работам Л. В. Канторовича и В. А. Залгаллера, задача раскроя определяется как поиск наиболее выгодного способа размещения заготовок определенного набора деталей (предметов раскроя) на кусках материала (объектах раскроя). Ее конкретизация, построение математической модели и выбор метода решения связаны с уточнением понятий:

♦ объектов раскрояфу (»"€1..т);

♦ предметов раскроя Ф^ (.7 6 1 ..п);

♦ группы движений в, определяющей размещение предметов на объектах;

♦ схемы построения возможных (допустимых) способов размещения;

♦ целевых функций задачи — критериев эффективности при выборе способа размещения;

♦ дополнительных требований к решению задачи.

Формально раскрой или план раскроя объекта Ф — совокупность непересекающихся (за исключением границ) образов предметов раскроя Ф?' в 6 5 в фигуре объекта раскроя Ф:

ф]И > ф]'. с ф> * Ф8 е ==» )п 1пЦФ];) = 0.

Объекты и предметы раскроя измеримы, что позволяет ввести меру дефекта плана раскроя ¡и(Ф \ и,б5 Ф^') > 0, называемую объемом потерь, и долю потерь как отношение их объема к объему израсходованного материала

Прикладные задачи, рассматриваемые в диссертации, делятся на следующие классы:

♦ единственного объектаФ,

♦ заданного количества объектов одного типоразмера ф,

♦ неизвестного количества объектов одного типоразмера ф,

• объектов некоторого множества типоразмеров Ф,- (1 € М = 1..т). Количество экземпляров объектов каждого вида может быть известным, произвольным или определяться границами.

Планы раскроя рассматриваемых в диссертации прикладных задач (в отличие от классических) связаны дополнительными ограничениями, включая:

• комплектность предметов, т. е. пропорциональность объемов их производства (с поправкой на ранее созданные запасы);

• комплектность расходования объектов раскроя;

• массовость производства, суть которого альтернатива: не выкраивать предметы данного вида или выкраивать их количество, не меньшее заданной нижней границы;

• соблюдение определенных границ доли потерь материала;

• дополнительные ограничения, связанные с весом или другими показателями выкраиваемых предметов;

• групповые требования к размещению предметов раскроя, обусловленные более сложными правилами технологии раскроя по сравнению с указанием группы движений (к примеру, симметрии, центровки или жесткости размещения);

• условия последовательности реализации процесса раскроя, примерами которых могут служить гильотинные резы или определенные требования к очередности выкраивания и форме остатка материала после каждого шага;

• взаимосвязи между используемыми технологиями раскроя;

• учет качества материала, составляющего объект и предметы, наряду с определенными условиями их соответствия.

Задача комплектовки определяется как поиск наиболее выгодного способа составления объектов комплектовки из определенного набора заготовок — предметов комплектовки. По своему физическому

содержанию операция комплектовки является обратной по отношению к операции раскроя. Цель задачи раскроя — поиск плана, обеспечивающего наибольший доход, задачи комплектовки, напротив, — минимизация затрат, связанных с комплектовкой.

Далее рассматриваются наиболее часто встречающиеся на практике прикладные задачи поиска оптимального плана раскроя и комплектовки одного объекта, среди которых задачи линейного и плоского раскроя преимущественно прямоугольных объектов на прямоугольные и круглые предметы, раскрои полосы и некоторых трехмерных объектов.

Задача раскроя единственного объекта является вспомогательной при исследовании задачи оптимизации состава планов раскроя и комплектовки, цель которой — определение минимального количества одинаковых или различных объектов раскроя для получения заготовок в требуемых количествах. Таким образом, в диссертации рассматриваются два основных класса взаимосвязанных моделей: формирования планов и оптимизации их состава.

Исследуется проблема критерия оптимальности в рассматриваемых задачах. Большинство из рассмотренных задач являются многокритериальными, что вызывает необходимость использования соответствующих средств их решения. Заключительные разделы главы посвящены идентификации моделей планирования и управления производством и исследованию связей задач комплекса математических моделей.

Вторая глава содержит описание разработанных автором методов решения задач рассматриваемого класса, среди которых особенности применения динамического, линейного, билинейного и дискретного программирования, методов декомпозиции и локальной оптимизации.

Предложены методы оценки и построения оптимальных планов раскроя и комплектовки на основе их декомпозиции и синтеза, разработаны и реализованы на практике следующие методы и алгоритмы решения прикладных задач линейного программирования (ЛП):

♦ метод формирования многоуровневой структуры множеств переменных и ограничений задачи, который позволяет в рамках одной программы решать различные варианты частично агрегированных задач;

• метод вариации весов переменных начального базисного плана, необходимый для установления приоритетов ограничений или приближения значений переменных или линейных форм к нижней или верхней границе;

• метод формирования списка "перспективных" столбцов, который существенно повышает эффективность поиска новых базисных элементов при многократном решении задач ЛП;

• метод интерактивного интерфейса с оператором, необходимый в случае невозможности формализации ряда условий задачи;

• методы решения последовательности задач.

Выявлена возможность использования средств билинейного программирования в качестве основы формирования предложенных автором гибких моделей распределения ресурсов и методов решения соответствующих оптимизационных задач. Установлена целесообразность применения методов декомпозиции и генерации столбцов для решения задач оптимизации раскроев и комплектовок. Введено понятие «степень блочности», необходимое для оценки сложности решения задач рассматриваемого класса.

Для поиска приближенных решений рассматриваемых прикладных задач с дискретными переменными предложены методы:

• агрегации управляемых факторов;

• вариации коэффициентов целевой функции.

Обоснована возможность оценки ожидаемой эффективности от использования новой технологии посредством усреднения двойственных оптимальных планов линейных задач распределения ресурсов и представления задач планирования и управления в виде взаимосвязанных комплексов моделей.

В третьей главе сформулирован класс задач раскроя и комплектовки, который сочетает многообразие приложений в области управления производством и возможность использования единого математического инструментария и алгоритмов решения.

Ослабление данного класса моделей приводит к задачам ЛП, для решения которых удается применить метод генерации столбцов, получая достаточно эффективные алгоритмы их решения. Восстановление снятых при этом условий дискретности или нелинейных связей является одной из проблем реализации этого метода, для решения которой используется метод ветвей и границ, усиленный методом вариации коэффициентов целевой функции.

Следующая задача — выбор очередности выполнения планов. Решение задачи объемного планирования (ОП) представляет собой набор планов раскроя, реализация которых в течение определенного срока (горизонта планирования) обеспечивает необходимые объемы выкраиваемых заготовок. Чем длительнее срок, тем больше номенклатура предметов раскроя и эффективность решения. Однако при этом планы раскроя объединяют продукцию разной срочности, что отражается на сроках выполнения заказов. Основной целью моделей и методов формирования объемно-календарного планирования (ОКП) является поиск компромиссного варианта.

Изучение особенностей этих задач приводит к обобщенной задаче оптимизации планов раскроя, в которой учитывается комплектность как объектов, так и предметов раскроя.

Для формулировки модели вводятся следующие индексные множества:

• М — видов предметов раскроя;

• С} — комплектов предметов (ф = М, если не требуется пропорциональность выработки);

••С — видов объектов раскроя;

• 5 — групп объектов раскроя (К = 5, если не требуется пропорциональность расходования);

• N — планов раскроя (и его частей Иъ, которые относятся к объекту

• Ь — дополнительных ограничений.

Параметры и неизвестные:

1. Для предмета раскроя « 6 М:

у,- — планируемая выработка (неизвестное значение);

— доход от выработки одного предмета; Щ, В\ — границы объема выработки; Л? — юличество ранее выработанных предметов; Щ — допустимый остаток к моменту завершения периода.

2. Для комплекта предметов д :

уч — планируемая выработка (неизвестное значение);

Сд — доход от выработки одного комплекта;

Ь^, Вд— границы объема выработки;

к,-д — кратность вхождения предмета ¡£Мв комплект д.

3. Для объекта раскроя к € К:

гк — планируемый расход (неизвестное значение);

сгк — затраты, связанные с расходованием одного объекта;

Вгк— границы объема расходования; Л£ — юличество ранее раскроенных объектов; #£ — допустимое количество некомплектных объектов.

4. Для группы объектов раскроя в е

XV, — планируемый расход (неизвестное значение); с™ — затраты, связанные с расходованием группы; Ьу, В™ — границы объема расходования; кратность объекта

5. Для плана раскроя ; из множества N, состоящего из непересекающихся подмножеств Nк, заданы:

X] — объем выработки (неизвестное значение):

с? — оценка плана (например, потери материала);

ац — кратность вхождения предмета г £ М.

6. Обозначим через ц> вектор, составленный из всех переменных х, у, г, V и ни. Левые части дополнительных ограничений I Е Ь чаще всего связывают переменные какой-либо одной из них, образуя группы ограничений Ьх, Ьу, Ьг, V и V". Относя прочие ограничения ко множеству Ь°, получим следующее разбиение Ь на части: Ь = Ь° и Ьх и V и Ьг и V и V". Для каждого определены:

Р1 — правая часть (или части) ограничения;

— тип ограничения (уравнение, произвольное нестрогое или двойное неравенство);

аи — коэффициенты линейной формы. При этом предполагается, что ац для каждого / £ Ьх — линейные формы от количества предметов в плане раскроя для всех столбцов < £ ^.

Основная математическая модель Р такова:

(1)

¿елг

гк= * е К,

(2)

г е м,

(3)

чед

(4)

лев

ац х} Р1, I е Ь

(5)

Щ < Уi < В?, г <= м,

• '

(6)

Ь"я<Уд<В"ч, деС},

(7)

К<*к<Вгк, к€К,

(8)

ч > о, з е N.

(10)

<бм де<з ¿елг «65

/11 \

(11)

X], у», гк, Ьд, V), — целые. (12)

Если оптимальный план может быть получен округлением нецелочисленных значений для решения Рд можно использовать метод генерации столбцов на основе вспомогательных задач оптимизации плана раскроя. Как правило, среди множителей цх, ... — весов линейных форм целевой функции (11) — не более двух, отличных от нуля.

Если субоптимальный план может быть получен округлением нецелочисленных значений ... , для решения Р можно ис-

пользовать метод генерации столбцов на основе вспомогательных задач оптимизации плана раскроя.

Рассмотренный класс задач составляют детерминированные модели. На практике с целью повышения уровня адекватности реальным производственным процессам предложено использовать подходы, которые позволяют в рамках данного класса задач учесть ряд стохастических факторов, включая случайный характер появления продукции пониженного качества или неопределенность сроков переналадки оборудования. Главу завершает исследование связей объемного и объемно-календарного планов производств, а также методы построения ОКП на основе рассчитанного ОП.

В четвертой главе рассматриваются прикладные задачи оптимизации планов раскроя, характерные для основных производств предприятий различных отраслей промышленности. Все задачи относятся к классу обобщенных задач планирования раскроев, для их решения применяются методы, представленные в главе 3.

В задаче планирования раскроев и распределения заявок между бумагоделательными машинами (БДМ) объектами раскроя являются съемы тамбуров продукции, а предметами — форматы продукции. Учет особенностей производства и сбыта бумаги —

главная цель задачи. Производительность каждой БДМ, а следовательно, выработка продукции ограничены, так же, как и потребность в каждом из форматов. Требуется составить планы раскроя, которые обеспечат выпуск заданного ассортимента и объемов продукции с минимальными отходами. Управляемые факторы в данной задаче — время, производительность БДМ и плотность вырабатываемой бумаги с учетом ожидаемого качества продукции.

Для постановки задачи расчета объемного плана введем следующие обозначения. Индексные множества: ф £ Ф — форматы рулонов; я" £ П плотности продукции; ф Е Ф — сорта продукции; 7 <Е Г типы продукции; q £ Q — агрегаты (БДМ); к £ К — объекты раскроя (марки продукции); s £ S — группы объектов (марки без учета качества); г £ М — предметы раскроя (конечная продукция); г £ R — выполняемые заказы и j £ N — планы раскроя.

Параметры и неизвестные задачи:

— продолжительность работы агрегата при выра-

ботке продукции плотности тг с минимальной и максимальной скоростью;

z¡, = Zq-хф -— объем выработки продукции марки к £ К;

— объем выработки конечной продукции —

остатки продукции;

планируемые объемы: т]г — отгрузки и т)'г недопоставки продукции; вГ1Гф.у — продуктовая структура поставки заказчику Г € Я;

— объем выработки плана раскрою

Соотношения задачи — уравнения баланса, которые связывают: (13) — продолжительности работы агрегатов и объемы выработки продукции определенной марки, (14) —производительности агрегатов и суммарные объемы раскроев, (15) — выпуск конечной продукции и суммарные объемы раскроев, (16) — объемы и продуктовую структуру отгрузки, (17) — запасы с объемами производства и отгрузки продукции.

Двусторонние ограничения связывают параметры задачи и переменные, включая: (18) — плановую продолжительность работы агрегатов, (19) — планируемый объем отгрузки продукции, (20) — остаток продукции на складах по завершении периода планирования.

(18)

я-еп

К<Чг + т/г<в?,

о <у'т<Щ, гея х, >0, з е ЛГ; >о, ?е<Э, я-еп.

(19)

(20) (21)

Целевая функция задачи отражает ущерб, связанный с недопоставкой продукции (первая сумма), потерями материала (вторая) и пониженным качеством продукции (третья):

(22)

Задача (13-22) является задачей ЛП большой размерности, для решения которой используются методы, предложенные в главе 3. Для решения гораздо более сложной задачи ОКП производства бумаги (картона) предложены эвристические алгоритмы поиска субоптимальных решений, получены оценки точности решений предложенных алгоритмов. Для решения данной задачи под руководством автора разработан программный комплекс, внедренный в промышленное производство в ОАО «Кондопога».

В задаче планирования производства цеха гофротары (ГТ)

предметы раскроя — прямоугольные заготовки деталей тарных ящиков или листы гофрокартона. Цель задачи — выработка запланированной продукции с минимальным расходом материала. Суммарная площадь требуемых изделий постоянна, поэтому экономия может обеспечиваться только за счет сокращения производственных потерь (отходов).

Рис. 1: Технология раскроя гофроагрегата

Для решения задачи моделируется сложный многоэтапный процесс, который включает поиск технически возможных, рациональных по затратам материала вариантов раскроя полотна гофроагре-гата (ГА) на прямоугольные заготовки различных размеров (рис. 1), определение сочетаний и объемов раскроев, обеспечивающих сбалансированное количество заготовок каждого комплекта конструкции ящика, расчет моментов запуска и чередования раскроев, выбор

устройств последующей обработки заготовок деталей с учетом производительности и времени переналадки оборудования, приоритетов и сроков выполнения заказов.

Математические модели, алгоритмы и программы разработаны для случая нескольких ГА с различной шириной гофрополотна, наличия вспомогательного и периферийного оборудования и др. Программный комплекс, разработанный автором, внедрен в цехе гофро-тары ОАО "Архангельский ЦБК".

Трехмерная задача размещения грузов возникает при составлении планов погрузки в транспортные средства (контейнеры, вагоны, трюмы теплоходов) продукции бумажного производства. Объектами раскроя в этой задаче является пространство внутри транспортных средств (ТС), которое в случае контейнера имеет форму параллелепипеда, вагона — закругленной сверху фигуры, трюма теплохода — многогранной невыпуклой области. Единицей продукции бумажного производства обычно является параллелепипед (кипа бумаги, картона или листовой целлюлозы, упаковка сложенных ящиков или мешков) или круговой цилиндр (рулон бумаги или картона) . Задачу усложняет наличие большого числа ограничений технологического характера, включая жесткость конструкции, условия погрузки и крепления последних единиц, балансировку груза, обеспечение удобства разгрузки. В отличие от предыдущих объекты раскроя в этой задаче дискретны.

Для решения задачи требуется решение ряда взаимосвязанных подзадач выбора ТС, уточнения объемов и построения схем погрузки продукции:

1. Определить наибольшую партию продукции, заданную номенклатурой и границами объемов, которую можно отгрузить, используя имеющиеся ТС.

2. Выбрать оптимальную по количеству или затратам часть имеющихся ТС, обеспечивающую доставку заданных объемов продукции.

3. Задача подобна предшествующей, но объемы продукции заданы границами.

4. В тех же условиях объемы продукции и количества ТС каждого вида заданы границами.

Решение этих подзадач, в свою очередь, основано на решении ряда вспомогательных:

• Поиск наиболее равномерного по весу, объему или по совокупности этих показателей распределения грузов между однотипными ТС.

• Поиск равномерного разбиения набора рулонов на вертикальные столбики.

• Размещение этих столбиков по площади ТС с учетом технологии погрузки: размеров и формы ворот, высоты у стенок и в центре вагона, карнизов трюмов, допустимых перемещений погрузчика, положения центра тяжести, жесткости размещения груза и ряда его динамических характеристик.

• Наглядное графическое отображение полученных схем погрузки.

В работе представлены математические модели и методы решения, вышеперечисленных задач, в частности, рассмотрена задача выбора планов с учетом групп объектов раскроя. Цель данной задачи — выбор способов заполнения каждого из ТС столбиками. рулонов с учетом вместимости, грузоподъемности и соответствия содержимого ТС структуре заказа.

Вводятся следующие обозначения и формулируется математическая модель:

— множество форматов продукции (предметов раскроя), — верхняя и нижняя границы количества планируемых к отгрузке рулонов формата I €

Ф — множество видов ТС, В^ — известное количество имеющихся, уч — неизвестное, необходимое для отгрузки, число ТС вида Я £ — грузоподъемность, с^ — оценка эксплуатацион-

ных расходов;

К — множество высот столбиков рулонов всех ТС Кя С К группа объектов раскроя, относящихся к

Л^ — множество конструкций столбиков рулонов, определяемых соответствующей высотой,

Л^ — высота, Wj — вес, х^ — неизвестное количество планируемых к погрузке столбиков конструкции

dqj

доля площади днища ТС q € Q, занятого столбиком j € Nq\

ij — число рулонов продукции формата t б М в столбце j € N. V (ÄVi-в х (V У^ dni -> min.

(23)

(24)

(25)

(26)

(27)

(28) (29)

Условие (24) означает ограничение объемов отгрузки, (25) — связывают неизвестные количества столбцов и вместимость ТС, (26) — вес груза и его грузоподъемность.

В работе представлены метод и алгоритмы решения данной задачи. Разработанный под руководством и при участии автора комплекс программ внедрен в ОАО «Кондопога», ОАО «Котласский ЦБК», внедряется в ОАО «Сегежский ЦБК». В результате эксплуатации системы повысилась объемная и весовая плотность загрузки ТС (следовательно, сократилась потребность в ТС), сократились неотгруженные остатки нестандартых видов продукции, появилась возможность расчета объемов продукции при заключении договора и формирования партии отгрузки в целях удобного размещения в ТС, снизилась трудоемкость, повысились оперативность и качество планирования.

В работе также рассмотрены особенности планирования погрузки водного транспорта, даны рекомендации по созданию программной системы для решения данной задачи.

В следующем разделе рассмотрена задача оптимизации планов раскроя круглой древесины, обеспечивающих требуемые ассортимент и количество пиломатериалов. Несмотря на большое количество имеющихся программных систем, данная задача остается весьма актуальной. В работе представлена математическая модель и предложен алгоритм решения задачи планирования выработки продукции с учетом сортировки древесины в условиях неопределенности распределения пиловочника по поставам. Разработан и проходит опытную эксплуатацию в ряде леспромхозов Республики Карелия программный комплекс, реализующий задачу планирования производства пиломатериалов.

В последнем разделе главы рассмотрена задача разработки горного массива, представленного в виде трехмерной фигуры. В ходе решения задачи необходимо определить, с какой стороны следует начинать разработку горного массива, т. е. в определении угла, который соответствует ориентации фронта разработки монолита — деления его на прямоугольные блоки определенных стандартных размеров. Задача усложняется наличием трещин в каменном монолите, параметры распределения которых позволяют оценить так называемую "блочность месторождения" облицовочного камня. Существуют различные инженерные методы оценки блоч-ности, включая статистические, гор но-геометрические, вероятностные, горно-тектонические и другие. В работе предложены математическая модель и алгоритм решения задачи раскроя монолита в котором используется схема ее декомпозиции.

В пятой главе исследуются прикладные задачи комплектовки, связанные с планированием и управлением производством промышленных предприятий.

В первом разделе рассмотрена задача планирования фанерного производства, которая описывает процесс комплектовки фанеры из листов шпона различной толщины в соответствии с технологией этого процесса. Разработаны математическая модель и метод решения задачи. В результате решения задачи получается оптимальный план комплектовки, который обеспечивает требуемые ассортимент и количество продукции из имеющихся запасов шпона. Разработанная программная система была внедрена на Архангельском ЦБК в 80-х годах прошлого столетия, в настоящее время

ведется модернизация программного комплекса для Новодвинского фанерного завода.

В следующем разделе рассматриваются две задачи оптимального выбора комплекта оборудования для выполнения одной

или ряда последовательных операций, определения его специализации и режимов работы. Цель первой из них — комплектовка необходимых производственных мощностей с наименьшими затратами на приобретение или эксплуатацию оборудования. Вторая задача предназначена для решения проблемы обеспечения сырьем лесопромышленного предприятия, распределения необходимого оборудования и определения очередности освоения лесосырьевых баз. Предметы и объекты комплектовки при этом неоднородны ввиду возможных различий технологий оборудования или породо-возрастного состава лесного фонда лесосырьевых баз. Для обеих задач разработаны математические модели и алгоритмы решения, которые реализованы в виде программного комплекса, проведены расчеты для предприятий ЛПК Республики Карелия.

В третьем разделе рассмотрена задача формирования поддонов, на которых необходимо разместить слои пачек листов гофрокартона или сложенных ящиков. Прочность конструкции обеспечивается чередованием слоев, связывающих пачки подобно кирпичной кладке. Слои могут несколько выходить за пределы площади поддона, иметь внутренние пустоты и неодинаковые размеры. Размеры кипы определяются наибольшими размерами слоев.

Цель задачи — поиск укладки наибольшей объемной плотности, при этом структура слоя может быть не гильотинным раскроем. Данная задача относится к числу трехмерных задач раскроя, для ее решения разработана оригинальная математическая модель и предложен метод решения. Программный комплекс, реализующий данную задачу, внедрен в промышленное производство в цехе гофрота-ры ОАО "Архангельский ЦБК".

В последнем разделе главы рассмотрена задача компоновки нестандартных съемов тамбуров Б ДМ. В связи с тем, что современные системы управления качеством обеспечивают непрерывный продольный и поперечный контроль параметров полотна БДМ или картоноделательной машины, это позволяет рассматривать более сложную задачу распределения форматов вдоль ширины тамбура, а рулонов конечной продукции с повышенным требованием ка-

чества — по длине полотна. Данная задача является одновременно задачей комплектовки и раскроя.

В работе представлена математическая модель и предложен метод решения данной задачи. Программный комплекс, реализующий данную задачу, разрабатывается по заказу компании "Метсо" (Финляндия).

Отмечено, что задачи, рассмотренные в главах 4 и 5, являются специальными случаями обобщенной задачи планирования раскроев и решаются предложенными в главе 3 методами. Более того, разработанная схема классификации позволяет сопоставить этим задачам соответствующие формулы, например:

— задача раскроя тамбура в наиболее об— задача планирования раскроев гофропо-лотна для одного гофроагрегата;

3. Р1+ /С}/(/Iх,/Л)/к — то же для нескольких;

4. Р1 + / М/ (цу,(.Р) / к/Б /х/ (Ьх,Ьу) — задача погрузки продукции предприятия ЦБП и т. д.

В заключении представлены основные научные и практические результаты работы:

1. Представлен и исследован класс задач планирования и управления производством, связанных с раскроями и комплектовкой материалов, выявлены свойства этих задач и характеризующие их признаки.

2. Сформулирована математическая модель (обобщенная задача оптимизации планов раскроя), объединяющая рассматриваемые задачи.

3. Представлена классификация прикладных задач выбора планов раскроя по отношению к признакам этой модели.

4. Выполнено исследование существующих и разработаны новые методы линейного и целочисленного программирования, необходимые для решения рассматриваемого класса прикладных оптимизационных задач.

5. Исследованы методы решения прикладных задач и математических моделей формирования объемного и объемно-календарного планов ряда производственных процессов. Разработаны схемы декомпозиции прикладных многокритериальных задач расчета взаимосвязанных объемного и объемно-календарного планов.

6. Предложены и реализованы методы расчета динамических параметров формирования производственных планов раскроя и комплектовки: очередности и сроков запуска и выполнения заказов, назначения и специализации оборудования и пр.

7. Разработанные математические модели и методы являются основой для создания АСУ производством ряда предприятий ЦБП

и ЛПК на основе задач оптимизации. Представленные математические модели, методы и алгоритмы реализованы в виде программных комплексов, внедренных в промышленное производство.

8. В результате работы создан ряд технологий и приемов, успешно используемых при обследовании производств, проектировании и реализации на всех этапах разработки, внедрения и практического использования программных систем на основе решения задач оптимизации.

9. Исследуемые в диссертации задачи носят достаточно общий характер и могут быть использованы в других отраслях промышленности.

Основное содержание диссертации опубликовано в следующих работах

1. Кузнецов В. А., Шалабин Г. В. Об одной однопродуктовой задаче оптимального управления процессом освоения проектной производственной мощности // Применение математики в экономике: Сб. Вып. 10. Л.: Изд-во ЛГУ, 1974. С. 35-44.

2. Прыгичев А. Н, Кузнецов В. А. Об одном методе решения задачи размещения с неоднородной целевой функцией // Применение

математики в экономике: Сб. Вып. 10. Л.: Изд-во ЛГУ, 1975. С. 34-42.

3. Кузнецов В. А., Шалабин Г. В. Определение оптимальной очередности ввода производственной мощности с учетом промежуточных пусковых комплексов // Применение математики в экономике: Сб. Вып. 12. Л.: Изд-во ЛГУ, 1977. С. 81-88:

4. Кузнецов В. А. Об одном методе решения транспортно-произ-водственной задачи специального вида // Применение математики в экономике: Сб. Вып. 11. Л.: Изд-во ЛГУ, 1977. С. 13-23.

5. Кузнецов В. А. Стохастическая задача оптимизации перевозки древесины // Вероятностные задачи прикладной математики: Сб. тр. Петрозаводск: Изд-во ПетрГУ, 1984. С. 37-45.

6. Кузнецов В. А., Поляков В. В., Кириллов В. М. О реализации оптимизационных моделей в АСУ ОДУ // Математическое обеспечение ЭВМ и систем управления: Сб. Петрозаводск: Изд-во ПетрГУ, 1985. С. 67-74.

7. Кузнецов В. А., Поляков В. В. О моделировании производственных процессов в ЦБП // Применение вычислительной техники в научных исследованиях и проектировании: Сб. тр. Карельского филиала АН СССР. Петрозаводск, 1986. С. 19-21.

8. Кузнецов В. А., Кириллов В. М. О математической подстановке и реализации задачи комплектовки фанеры // Математическое моделирование народного хозяйства: Межвуз. сб. Петрозаводск: Изд-во ПетрГУ, 1990. С. 28-33.

9. Кузнецов В. А., Поляков В. В. Опыт практического использования оптимизационных задач в управлении производством целлюлозы // Сб. науч. тр. ВНПО «Бумпром» Л., 1990. С. 35-43.

10. Кузнецов В. А., Поляков В. В., Коржов С. Т. О математических моделях раскроя бумажного полотна // Математическое моделирование народного хозяйства: Сб. Петрозаводск: Изд-во Петр-ГУ, 1990. С. 38-42.

11. Воронин А. В., Кузнецов В. А. Автоматизированная система планирования и управления производством гофротары // Труды ПетрГУ. Сер. Прикл. матем. и информ. Вып. 5 Петрозаводск: Изд-во ПетрГУ, 1996. С. 3-11.

12. Воронин А. В., Кузнецов В. А. Математические модели и программное обеспечение производства гофротары // Сборник науч. тр. КарНИИЛП. Петрозаводск: Изд-во ПетрГУ, 1997. С.25-28.

13. Кузнецов В. А., Шегельман И. Р., Булатов А. Ф. К вопросу выбора технологических процессов и их комплектования прогрессивными машинами и оборудованием // Проблемы освоения нетрадиционных видов древесного сырья: Сб. науч. тр. Петрозаводск: КарНИИЛП, 1997. С. 11-14.

14. Кузнецов В. А., Шегельман И. Р. Математическое моделирование при планировании и организации лесозаготовок. Петрозаводск: Изд-во КРИА, 1998. 125 с.

15. Кузнецов В. А., Шегельман И. Р. Применение математических методов и ПЭВМ на лесоразработках. СПб.: Изд-во СПб ЛТА, 1998. 68 с.

16. Воронин А. В., Кузнецов В. А. Оптимизационные модели в задачах планирования и управления предприятием бумажной промышленности: Матер, науч. конф. «Экономическая наука: Теория, методология, направления развития». СПб.: Изд-во СПбГУ, 1998. С. 256-259.

17. Шегельман И. Р., Кузнецов В. А. Экономико-математические методы исследования операций при организации лесозаготовок // Петрозаводск: Изд-во ПетрГУ, 1999. 64 с.

18. Кузнецов В. А. Задачи раскроя в целлюлозно-бумажной промышленности СПб: Изд-во СПб ЛТА, 2000. 132 с.

19. Воронин А. В., Кузнецов В. А. Прикладные оптимизационные задачи в целлюлозно-бумажной промышленности. Петрозаводск: Изд-во ПетрГУ, 2000. 152 с.

20. Воронин А. В., Кузнецов В. А. Математические модели и методы планирования и управления предприятием ЦБП. Петрозаводск: Изд-во ПетрГУ, 2000. 256 с.

21. Кузнецов В. А., Воронов Р. В. Оптимальное планирование распределения заказов производства бумаги между БДМ // Труды ПетрГУ. Сер. "Прикладная математика". Вып. 10. Петрозаводск: Изд-во ПетрГУ, 2000. С. 87-99.

22. Кузнецов В. А., Воронов Р. В. Практическая реализация алгоритмов построения объемного и объемно-календарного планов раскроя съема тамбуров // НИТ в ЦБП: Материалы V междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2002. С. 89-90.

23. Булатов А. Ф., Воронин А. В., Кузнецов В. А., Пладов В. Н., Шегельман И. Р. Оптимизация в планировании и управлении предприятиями регионального лесопромышленного комплекса. Петроза-

водск: Изд-во ПетрГУ, 2001. 218 с.

24. Воронин А. В., Кузнецов В. А., Патякин В. И., Шегельман И. Р., Базаров С. М. Исследование операций в планировании и управлении предприятием ЛПК: СПб.: Изд-во СПбЛТА, 2001. 48 с.

25. Шеков В. А., Кузнецов В. А. и др. К оценке блочности массива на основе модели трещиноватости // Геология и полезные ископаемые: сб. тр., Вып. 3. Петрозаводск: Изд-во Карельского научного центра РАН, 2001. С. 137-140.

26. Воронин А. В., Кузнецов В. А. Прикладные оптимизационные задачи для комплексных лесопромышленных предприятий // Актуальные проблемы лесопромышленных производств. Сб. науч. тр. КарНИИЛП. Петрозаводск, 2002, С. 42-46.

27. Воронин А. В., Кузнецов В. А. Использование прикладных оптимизационных задач для повышения эффективности управления интегрированными предприятиями лесопромышленного комплекса // Лесосечные, лесоскладские работы и транспорт леса: Межвуз. сб. научн. тр. СПб.: СПбГЛТА, 2002. С. 59-65.

28. Кузнецов В. А. Оптимальная комплектация лесопромышленного предприятия машинами и оборудованием // Проблемы лесопромышленных регионов: Матер. Всероссийской науч.-практ. кон-фер. Инст. предпр. и инвестиций. М., 2002. С. 19-20.

29. Кузнецов В. А. Цели и оценка экономического эффекта разработки системы планирования отгрузки продукции предприятия ЦБП // НИТ в ЦБП: Материалы V междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2002. С. 88-89.

30. Шегельман И. Р., Скрипник В. И., Пладов А. В., Кочанов А. Н., Кузнецов В. А. Моделирование движения лесовозных автопоездов // Петрозаводск: Изд-во ПетрГУ, 2003. 232 с.

31. Воронин А. В., Кузнецов В. А. Пути решения оптимизационных задач // Лесная промышленность. N 3. М., 2003. С. 14.

32. Воронин А. В., Кузнецов В. А., Шегельман И. Р. Системный подход к постановке и решению задач планирования и управления интегрированными предприятиями лесопромышленного комплекса // ПетрГУ. Петрозаводск, 2003. 46с, ил. Рус. Деп. в ВИНИТИ 29.05.2003. N 1059-В2003.

33. Воронин А. В., Кузнецов В. А., Шегельман И. Р. Постановка и решение задач оптимизации планирования и управления для вертикально-интегрированных лесопромышленных предприятий //

Материалы международной научно-технической конференции "Лесопромышленная логистика и информационные системы лесного комплекса". СПб: Изд-во СПб ЛТА, 2003. С. 26-29.

34. Кузнецов В. А. Обобщенная задача раскроя и ее приложения в ЦБП // Обозрение прикладной и промышленной математики, т. 10, вып. 1. М.: Изд-во "ОПиПМ", 2003. С. 178-180.

35. Кузнецов В. А. Планирование погрузки готовой продукции целлюлозно-бумажного комбината в транспортные средства // Известия высших учебных заведений "Лесной журнал". ХУ2-3. Архангельск: Изд-во АГТУ, 2003-С. 133-140.

36. Кузнецов В. А. Использование прикладных оптимизационных задач для повышения эффективности управления целлюлозно-бумажным производством // Целлюлоза. Бумага. Картон. N 5-6. М., 2003. С. 28-31.

37. Кузнецов В. А. Задачи раскроя и комплектовки материалов в моделировании производственных процессов // Известия высших учебных заведений "Лесной журнал". IV 1. Архангельск: Изд-во АГТУ, 2004. С. 111-116.

Подписано в печать 25.06.04. Формат 60 х 84 1/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,5. Усл. кр.-отт. 8. Тираж 100 экз. Изд.ном. 144. Петрозаводский государственный университет Типография Издательства Петрозаводского государственного университета 185640, Петрозаводск, пр. Ленина, 33

$15185

Введение.

Глава 1. Задачи раскроя и комплектовки в моделировании технологических процессов.

1.1 Терминология и обозначения.

1.2 Содержание моделей раскроя и комплектовки

1.3 Прикладные задачи поиска оптимального плана раскроя и комплектовки.

1.4 Задачи оптимизации состава планов раскроя и комплектовки

1.5 Критерии эффективности в рассматриваемых задачах

1.6 Краткая характеристика рассматриваемых задач

1.7 Идентификация моделей и их параметров.

1.8 Выводы.

Глава 2. Особенности применения математических методов при решении задач раскроя и комплектовки

2.1 Особенности применения динамического программирова ния.

2.2 Метод декомпозиции и синтеза планов раскроя и комплектовки

2.3 Особенности решения задач линейного программирования

2.4 Задачи ЛП специальной структуры.

2.5 Генерация столбцов в задачах раскроя и комплектовки

2.6 Дискретность и нелинейность связей в задачах оптими зации

2.7 Двойственные оценки и расчет эффективности технологий

2.8 Комплексы задач планирования производственного процесса

2.9 Выводы.

Глава 3. Задачи оптимизации планов раскроя и методы их решения.

3.1 Варианты задачи планирования раскроев.

3.2 Обобщенная модель оптмизации планов раскроя.

3.3 Использование модели в условиях стохастики производственного процесса.

3.4 Метод решения обобщенной задачи

3.5 Модели формирования объемно-календарного плана

3.6 Методы решения задачи ОКП

3.7 Выводы.

Глава 4. Прикладные задачи раскроя материалов.

4.1 Задача планирования раскроев и распределения заявок между Б ДМ.

4.2 Задача планирования производства гофротары.

4.3 Задача выбора транспортных средств и размещения продукции

4.4 Особенности планирования погрузки водного транспорта

4.5 Задача планирования производства пиломатериалов

4.6 Задача разработки горного массива.

4.7 Выводы.

Глава 5. Прикладные задачи комплектовки материалов

5.1 Задача планирования работы фанерного производства

5.2 Задача комплектовки оборудования производства щепы . 175 /ф 5.3 Комплектовка оборудования многофазного производства

5.4 Задача расчета оптимальных схем комплектовки поддонов

5.5 Задача компоновки нестандартных съемов тамбуров

5.6 Выводы.

В основу диссертационного исследования положен многолетний опыт разработки и применения математического моделирования, методов и комплексов программ для решения задач планирования производства, прежде всего, предприятий лесопромышленного комплекса (ЛПК) и целлюлозно-бумажной промышленности (ЦБП).

Диссертационная работа охватывает вопросы построения математических моделей планирования производственных процессов, разработки методов решения соответствующих оптимизационных задач и комплексов программ, в которых тесно переплетаются научные и прикладные проблемы.

Актуальность темы. Сложная социально-экономическая ситуация в России, обострение конкуренции среди промышленных предприятий и необходимость снижения себестоимости производимой продукции все настоятельнее требуют повышения эффективности производства, более рационального расходования имеющихся в его распоряжении финансовых и материальных средств и ресурсов, повышения производительности труда. Учитывая сложное финансовое положение многих предприятий и проблемы поиска инвестиций, часто не удается добиться повышения эффективности производства за счет экстенсивных факторов или расширения производства, его существенной реструктуризации и модернизации, освоения новой, более совершенной и конкурентоспособной продукции.

В значительной степени данные проблемы проявляются в перерабатывающих отраслях промышленности (лесной, деревообрабатывающей, целлюлозно-бумажной, металлургической, горноперерабатыва-ющей и др.), где кроме общеэкономических присутствуют специфические, отраслевые проблемы: истощение наиболее продуктивных и качественных сырьевых баз, непропорционально высокий рост транспортных и топливно-энергетических расходов, повышение требовательности заказчиков к качеству производства и оформлению готовой продукции, снижение платежеспособного покупательского спроса, колебания цен на продукцию на внутреннем и внешнем рынках. В сложившихся условиях, одним из наиболее эффективных способов решения вышеуказанных проблем заключается в качественно новом уровне планирования и управления предприятием и его подразделениями, используя современные организационные и информационно-аналитические методы, математическое моделирование, современные автоматизированные системы управления технологическими процессами и интегрированные системы управления предприятиями, системы поддержки принятия решений. При этом повышение эффективности производства может достигаться за счет оптимизации производственных процессов, то есть за счет принятия рациональных управленческих решений, позволяющих повысить согласованность работы отдельных агрегатов, входящих в состав технологической системы. В результате этого сокращается время простоя оборудования, достигается значительная экономия сырья и энергии, повышаются объемы и качество выпускаемой продукции при аналогичных трудовых и производственных затратах.

Исследование производственных технологических процессов в перерабатывающих отраслях промышленности показало, что многие из них связаны с раскроями и комплектовкой материалов. Являясь очень важными, с точки зрения экономии используемых ресурсов, и, в то же время, одними из наиболее сложных для решения, эти задачи способны обеспечить возможность оптимального планирования и управления производственными процессами, сократить расход сырья и переделов, снизить себестоимость продукции и, в конечном счете, принести высокий экономический эффект. Для решения данных задач можно эффективно использовать методы математического моделирования и оптимизации с применением компьютерных технологий.

Следует отметить, что использование классических методов решения задач раскроя и комплектовки, как правило, не применимо для оптимизации многих реальных производственных процессов из-за необходимости учета их специфических особенностей, в частности - связей между объектами и предметами раскроя и комплектовки, а также - многочисленных дополнительных ограничений, обусловленных конкретными технологиями раскроя. Указанное обстоятельство требует разработки комплекса моделей, методов и программных систем для решения обобщенного класса задач раскроя и комплектовки с учетом дополнительных ограничений, что подтверждает актуальность выбранной темы диссертационного исследования.

Основная цель диссертационного исследования — разработка математических моделей, методов и комплексов программ для решения задач раскроя и комплектовки материалов в производственных системах.

В соответствии с поставленной целью в диссертации решаются следующие задачи:

1. Обоснование необходимости решения класса задач, связанных с оптимизацией планирования раскроев и комплектовок при наличии дополнительных ограничений;

2. Постановка и исследование комплекса математических моделей обобщенной задачи раскроя и комплектовки материалов.

3. Разработка методов решения обобщенной задачи раскроя и комплектовки с учетом большой размерности.

4. Определение схем декомпозиции прикладных многокритериальных задач расчета объемного и объемно-календарного планов, разработка методов расчета динамических параметров формирования производственных планов раскроя и комплектовки.

5. Разработка комплекса программ для решения прикладных задач раскроя и комплектовки материалов.

6. Разработка рекомендаций по использованию предложенных моделей, методов и программных систем в организации планирования и управления производственными процессами, создании систем поддержки принятия решений.

Объектом исследования являются производственные технологические процессы, связанные с раскроями и комплектовкой материалов.

Предметом исследования — математические модели и методы решения задач раскроя и комплектовки.

Методы исследования. Теоретической и методологической основой исследования являются методы исследования операций и математического программирования. Системный анализ и методы оптимизации используются для анализа производственных процессов, построения математических моделей производственных процессов и разработки алгоритмов решения соответствующих экстремальных задач.

Методы линейного, динамического и дискретного программирования, теория двойственности, а также различные схемы декомпозиции задач используются для решения линейных и нелинейных задач сложной структуры и высокой размерности, элементы теории вероятности и математической статистики — для идентификации параметов и исследовании стохастических факторов.

Для разработки алгоритмов и программных комплексов использовались теория алгоритмов и структур данных, современные технологии проектирования программных систем, методы структурного и объектно-ориентированного программирования, проектирования баз данных. Для разработки программ использовались языки и системы программирования Fortran^ С++, Pascal, Delphi, Clipper и ORACLE.

Научная новизна. В диссертации предложены новые и модифицированы известные методы решения прикладных задач, названных обобщенными задачами раскроя, предложены принципы классификации исследуемых моделей, разработаны новые методы и схемы декомпозиции задач.

К числу результатов исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:

• Сформулирован и исследован класс задач оптимизации для моделирования процессов, содержащих операции раскроя и комплектовки материалов.

• Определен класс обобщенных задач раскроя, объединяющий рассматриваемые модели. Предложена классификация задач указанного класса.

• Разработаны схемы декомпозиции обобщенных задач раскроя и методы решения вспомогательных задач, связанных с ними;

• Разработаны методы расчета динамических параметров формирования производственных планов раскроя и комплектовки.

• Разработаны и протестированы эффективные методы и алгоритмы решения этих задач;

Практическая значимость и реализация результатов работы.

Полученные в диссертации результаты использовались при выполнении госбюджетных и хоздоговорных научно-исследовательских работ, выполненных под руководством и при личном участии автора на кафедре прикладной математики и кибернетики, в Центре ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 1981-2004г.г.

В работе приведены результаты вычислительных экспериментов, которые подтверждают применимость разработанных алгоритмов и программ для решения задач с размерностью, требуемой на практике. Представленные в работе математические модели, методы и алгоритмы решения, программные комплексы используются на ряде крупных предприятий (ОАО "Архангельский ЦБК", ОАО "Сегежский ЦБК", ОАО "Кондопога", ОАО "КотласскийЦБК", ОАО "Карелэнерго", АХК "Кареллеспром" и др.). В результате эксплуатации программных систем на предприятиях повысилась эффективность управления производством, получен реальный экономический эффект. На основании результатов внедрения программных комплексов в промышленное производство, разработаны рекомендации по использованию предложенных моделей и методов в организации планирования и управления производственными процессами.

Рассмотренные в диссертации математические модели и методы решения задач обладают достаточной общностью и могут использоваться для планирования и управления производствами в других отраслях промышленности.

Полученные результаты используются в учебном процессе, курсовых и дипломных работах студентов, исследованиях аспирантов, отражены в учебно-методической разработке "Исследование операций в планировании и управлении предприятием ЛПК" (С.-Петербург: Изд-во СПбГЛТА, 2001).

Апробация работы. Основные результаты диссертационной работы докладывались автором на I съезде лесопромышленников Республики Карелия (Петрозаводск, 2004), Международной научно-технической конференции «Лесопромышленная логистика и информационные системы лесного комплекса» (Санкт-Петербург, 2003), Всероссийской научно-практической конференции «Проблемы лесопромышленных регионов» (Москва, 2002), IV Международном форуме «Лесопромышленный комплекс России XXI века» (Санкт-Петербург, 2002), 1-У Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 1994, 1996, 1998, 2000, 2002), Научно-практических конференциях АХК «Кареллеспром» (Петрозаводск, 1998-2003), Международной конференции «Новые технологии и устойчивое управление в лесах Северной Европы» (Петрозаводск, 2001); Республиканской научно-практической конференции «Устойчивое развитие региона: лесопромышленный комплекс» (Петрозаводск, 2000 г.), Республиканской научно-практической конференции «Актуальные проблемы лесного комплекса» (Петрозаводск, 1999 г.), XXV международной конференции «Экономическая наука: Теория, методология, направления развития» (Санкт-Петербург,1998), Республиканской научно-практической конференции «Ресурсосберегающие технологии лесного комплекса» (Петрозаводск, 1998), Международной научно-технической конференции «Проблемы развития лесного комплекса Северо-западного региона» (Петрозаводск, 1996), Всероссийской научно-практической конференции «Новые информационные технологии в образовании и управлении» (Петрозаводск, 1993 г.) и других конференциях и семинарах.

Структура и объем работы. Диссертация состоит из введения, 5 глав основного материала, заключения, библиографического списка и 3 приложений. Основной материал изложен на 218 стр., включал 26 рисунков и 17 таблиц. Библиографический список включает 198 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации.

10. Основные результаты опубликованы в 88 работах автора, включая 10 научных и учебно-методических изданий.

Заключение

Исследования диссертации охватывают вопросы построения математических моделей комплектовки и раскроя с различными дополнительными ограничениями, связанные с задачами планирования и управления производством, разработки численных методов решения соответствующих оптимизационных задач, и комплексов програм, в которых тесно переплетаются фундаментальные научные и прикладные проблемы.

Прикладная часть диссертации содержит ряд задач, связанных между собой как областью приложения (предприятия ЦБП и ЛПК), так и используемыми для их постановки и решения математическими методами. Подведем основные итоги.

1. В работе представлен и исследован широкий класс прикладных задач планирования и управления производством, связанных с раскроями и комплектовкой материалов, выявлены свойства этих задач и характеризующие их признаки.

2. Сформулирована математическая модель (обобщенная задача оптимизации планов раскроя), которая объединяет значительную часть таких задач.

3. Представлена классификация прикладных задач выбора планов раскроя по отношению к признакам этой модели.

4. Выполнено исследование существующих и разработаны новые методы линейного и целочисленного программирования, необходимые для решения рассматриваемого класса прикладных оптимизационных задач.

5. Разработаны методы, которые позволяют в рамках представленного класса детерминированных моделей рассматривать задачи с учетом некоторых стохастических факторов.

6. В работе исследованы методы решения прикладных практически важных задач и математических моделей формирования объемного и объемно-календарного планов ряда производственных процессов.

7. Разработанные математические модели и методы являются основой для создания АСУ производством ряда предприятий ЦБП и ЛПК на базе задач оптимизации.

8. На основании накопленного опыта работы создан ряд технологий и приемов, успешно используемых при обследовании производств, проектировании, реализации на всех этапах разработки, внедрения и практическом использовании программных систем на основе решения задач оптимизации.

9. Исследуемые в диссертации задачи носят достаточно общий характер и могут быть использованы в других отраслях промышленности.

1. Андреев А. Е., Болотов А. А., Фролов А. Б. Задачи дискретной оптимизации и сложность алгоритмов. М.: МЭИ, 2000. 71 с.

2. Акоф Р., Сасиени Р. Основы исследования операций. М.: Мир, 1971. 534 с.

3. Базаров С. М., Воронин А. В., Кузнецов В. А., Патякин В. И., Шегельман И.Р. Исследование операций в планировании и управлении предприятием ЛПК. СПб: Изд-во СПбГЛТА, 2001. 48 с.

4. Беленький А. С. Исследование операций в транспортных системах. М.: Мир, 1992. 684 с.

5. Беллман Р. Динамическое программирование. М.: Мир, 1960. 424 с.

6. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Мир, 1965. 368 с.

7. Богданова Л. А., Кузнецов В. А. Оптимизация развития и размещения предприятий лесопильной промышленности в экономическом районе // Применение математики в экономике: Сб. Вып. 11. Ленинград: Изд-во ЛГУ, 1976. С. 24-29.

8. Богданова Л. А., Кузнецов В. А., Шалабин Г. В. Сетевая динамическая задача развития и размещения производства и методы ее решения // Применение математики в экономике: Сб. Вып. 12. Ленинград: Изд-во ЛГУ, 1977. С. 41-52.

9. Бугаев Ю. В. Применение векторной оптимизации на графах для моделирования раскроя лесоматериалов // Изв. вузов. Лес. ной журнал. 2001. N 3. С. 84-88.

10. Булатов А. Ф., Воронин А. В., Кузнецов В. А., Пладов В. Н., Ше-гельман И. Р. Оптимизация в планировании и управлении предприятиями регионального лесопромышленного комплекса. Петрозаводск: Изд-во ПетрГУ, 2001. 218 с.

11. Булатов А. Ф., Кузнецов В. А., Скрыпник В. И. Алгоритмы и программа оптимизации скорости и режимов движения предприятия ЦБП // Новые информационные технологии в ЦБП и энергетике. Материалы IV Международной конференции. Петрозаводск, 2000. С. 40-41.

12. Вагнер Г. Основы исследования операций: В 3 т. М.: Мир, 19721973.

13. Васильева Я. И. Картак В. М. Эвристический алгоритм упаковки гофров на листах. / Дискр. анализ и исслед. опер. (Материалы конференции) // Изд-во инст. математики. Новосибирск, 2000. С. 182.

14. Вентцель Е. С. Исследование операций. М.: Наука, 1980. 208 с.

15. Владимирова Н. Ю., Сигал И. X. Параметризация при решении некоторых классов задач дискретной оптимизации большой размерности. М.: ВЦ РАН, 2001. 78 с.

16. Воронин А. В., Кузнецов В. А. Пути решения оптимизационных задач // Лесная промышленность, N 3, М., 2003, С. 14.

17. Воронин А. В., Кузнецов В. А. Расчет ресурсов и планирование производства ЦБК: Отчет о НИР (заключит.). Петрозаводск: ПетрГУ, 1989. 49 с.

18. Воронин А. В., Кузнецов В. А. Прикладные оптимизационные задачи для комплексных лесопромышленных предприятий // Актуальные проблемы лесопромышленных производств. Сб. научных трудов КарНИИЛП. — Петрозаводск, 2002, С. 42-46.

19. Воронин А. В., Кузнецов В. А. Разработка экономико-математических моделей развития лесопромышленного комплекса // Лесосечные, лесоскладские работы и транспорт леса: Меж-вуз.- сб. научн. тр. — СПб.: СПбГЛТА, 2002, С. 32-35.

20. Воронин А. В., Кузнецов В. А. Использование прикладных оптимизационных задач для повышения эффективности управления интегрированными предприятиями лесопромышленного комплекса // Там же, С. 59-65.

21. Воронин А. В., Кузнецов В. А. Применение экономико-математических методов для решения задачи планирования производства гофротары // НИТ в ЦБП: Материалы II Междун. конф. Петрозаводск: Изд-во ПетрГУ, 1996. С. 34-36.

22. Воронин А. В., Кузнецов В. А. Автоматизированная система планирования и управления производством гофротары // Труды ПетрГУ. Сер. Прикл. матем. и информ. Вып. 5 Петрозаводск: Изд-во ПетрГУ, 1996. с .3-11.

23. Воронин А. В., Кузнецов В. А. Проблемы планирования и управления экономическим развитием ЛПК региона // Новые технологии и устойчивое управление в лесах Северной Европы: Тез. докл. межд. конф., Петрозаводск: Изд-во ПетрГУ, 2001. С. 2930.

24. Воронин А. В., Кузнецов В. А. Математические модели и программное обеспечение производства гофротары // Сборник на-учн. тр. КарНИИЛП. Петрозаводск: Изд-во ПетрГУ, 1997. с .25-28.

25. Воронин А. В., Кузнецов В. А. Оптимизационные модели в задачах планирования и управления предприятием бумажной промышленности: // Экономическая наука: Теория, методология, направления развития: Матер, научн. конф. СПб.: Изд-во СПб-ГУ, 1998. С. 256-259.

26. Воронин А. В., Кузнецов В. А. Прикладные оптимизационные задачи в целлюлозно-бумажной промышленности. Петрозаводск:, Изд-во ПетрГУ, 2000. 152 с.

27. Воронин А. В., Кузнецов В. А. Математические модели и методы планирования и управления предприятием ЦБП. Петрозаводск: Изд-во ПетрГУ, 2000. 256 с.

28. Воронин А. В., Кузнецов В. А. Модели и алгоритмы для предприятий ЛПК // Проблемы лесопромышленных регионов: Матер. Всероссийской научн.-практ. конфер. М.: Инст. предпр. и инвестиций. 2002. , С. 12-13.

29. Воронин А. В., Кузнецов А. В., Булатов А. Ф. Анализ классов задач и методов моделирования информационных потоков в лесопромышленных предприятиях // Лесопромышленный комплекс: Проблемы и решения: Сб. науч. трудов. Петрозаводск: КарНИИЛП, 1998. С. 16-20.

30. Воронин А. В., Кузнецов В. А., Булатов А. Ф. Методология оптимизации регионального ЛПК // Проблемы лесопромышленных регионов: Матер. Всероссийской научн.-практ. конфер. М.: Инст. предпр. и инвестиций. 2002. , С. 16-19.

31. Воронин А. В., Кузнецов В. А., Патякин В. И., Шегельман И. Р., Базаров С. М. Исследование операций в планировании и управлении предприятием ЛПК. Санкт-Петербург: Изд-во СПбЛТА, 2001. 48 с.

32. Воронин А. В., Кузнецов В. А., Печников А. А., Соколов Е. М. О подсистеме сбыта продукции АСУ целлюлозно-бумажного комбината // Математическое обеспечение ЭВМ и систем управления: Межвуз. сб. Петрозаводск: Изд-во ПетрГУ, 1985. С. 65-68.

33. ВоронинА. В.,Кузнецов В. А., Подкопаев Д. В. Командные задачи по программированию: организация, задачи и решения. Петрозаводск: Изд-во ПетрГУ, 1999. 92 с.

34. Воронин А. В.,Кузнецов В. А., Корзун Д. Ж. Командные задачи по программированию: организация, задачи и решения (выпуск 2). Петрозаводск: Изд-во ПетрГУ, 2000. 268 с.

35. Воронин А. В., Кузнецов В. А., Поляков В. В., Карпов А. В. Задачи оптимизации в АСУ ремонтным производством // НИТ в образовании и управлении: Всероссийская конференция. Петрозаводск: Изд-во ПетрГУ, 1993. С. 112-114.

36. Воронин А. В., Кузнецов В. А., Поляков В. В. О реализации программных средств для решения задач управления в интегрированных системах // Новые информационные технологии в ЦБП. Материалы II Междун. конференции. Петрозаводск, 1996. С.44-45.

37. Воронин А. В., Кузнецов В. А., Поляков В. В. Программные системы для обучения методам разработки математических моделей оптимизационных задач // НИТ в образовании и управлении: Тез. Всероссийской конференции. Петрозаводск, 1993. С. 62-64.

38. Воронин А. В., Кузнецов В. А., Рогов А. А. и др. Статистический анализ заказов РМЦ ЦБК // Новые информационные технологии в ЦБП и энергетике. Материалы IV Международной конференции. Петрозаводск, 2000. С. 43-46.

39. Воронин А. В., Кузнецов В. А., Тарасенко А. Ю. Система математических моделей для построения прогноза и оптимизациивыбора управления в АСУ ТП // Труды ПетрГУ, сер. Прикладная математика и информатика. Вып. 6 — Петрозаводск, 1997. С. 7-18.

40. Воронин А. В., Кузнецов В. А., Чернецкий В. И. и др. Математическое моделирование и программное обеспечение задач АСУ ЦБК: Отчет о НИР (заключит.). Петрозаводск: Изд-во Петр-ГУ, 1989. 164 с.

41. Воронин А. В., Кузнецов В. А., Шабаев Г. И. Автоматизированное управление сбытом продукции ЦБК в условиях рыночной экономики // Новые информационные технологии в ЦБП. Материалы I Междун. конференции. Петрозаводск, 1994. С. 6-8.

42. Воронин А. В., Кузнецов В. А., Шегельман И. Р. Постановка и решение задач оптимизации планирования и управления для вертикально-интегрированных лесопромышленных предприятий // Материалы международной научно-технической конференции

43. Лесопромышленная логистика и информационные системы лесного комплекса". СПб: Изд-во СПб ЛТА, 2003, С. 26-29.

44. Воронин А. В., Шегельман И. Р. Вертикально-интегрированные структуры управления в лесопромышленном комплексе. СПб: Изд-во СПб ЛТА, 2003. 160 с.

45. Воронов Р. В., Кузнецов В. А. Математические методы и модели бумажного производства // Новые информационные технологии в ЦБП и энергетике. Материалы IV Международной конференции. Петрозаводск, 2000. С. 51-52.

46. Вьюков И. Е. Автоматизация технологических процессов целлюлозно-бумажной промышленности: Учебное пособие для ВУЗов. М.: Лесная промышленность. 1978. 384с.

47. Вьюков И. Е., Зорин И. П. Автоматизация предприятия ЦБП. М.: Лесн. пром-ть, 1982. 288 с.

48. Вьюков И. Е., Зорин И. Ф., Петров В. П. АСОДУ предприятием ЦБП. М.: Лесная промышленность. 1978. 248с.

49. Вьюков И. Е., Зорин И. Ф., Петров В. П. Математические модели и управление технологическими процессами целлюлозно-бумажной промышленности М.: Лесная промышленность. 1975. 376 с.

50. Гасс С. Линейное программирование: методы и приложения. М.: Физматгиз, 1961. 303 с.

51. Гермейер Ю. Б. Игры с непротивоположными интересами. М.: Наука, 1976. 328 с.

52. Гимади Э. X., Залюбовский В. В., Севастьянов В. С. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками. // Дискрет, анализ и исслед. операций. Сер. 2. 2000. Т. 7, N1. С. 9-34.

53. Грибов А. А., Давыдова И. М., Романовский И. В. Техника цепных списков, ее программирование и использование в алгоритмахоптимизации. // Исследование операций и статистическое моделирование. Ленинград. Сб. трудов. Вып. 4. 1977. С. 127-166.

54. Давыдова И. М. Задачи размещения предпритяий. СПб.: Изд-во ЛГУ, 1978. 86 с.

55. Духовин Ю. И., Павлов Ю. Г., Марков В. А. Оптимальное планирование в лесной, целлюлозно-бумажной и деревообрабатывающей промышленности. М.: Лесн. пром-ть, 1984. 295 с.

56. Дудников Е. Е., Цодиков Ю. М. Типовые задачи оперативного управления непрерывным производством. М.: Энергия, 1979. 272 с.

57. Дюбин Г. П., Корбут А. А. Жадные алгоритмы для задачи о ранце: поведение в среднем // Сиб. журн. индустр. математики. 1999. т. 2, N 2. с. 68-93.

58. Едельштейн Ю. М., Сыпневская Л. А., Привалихин А. И. Оптимизация раскроя бревен на пиломатериалы и ее реализация на ЭВМ / Ю. М. Ельдештейн, // Изв. вузов. Лесной журнал. 1999. N 5. С. 62-66.

59. Еремин И. И. Двойственность в линейной оптимизации. Екатеринбург: ИМИМ. 2001, 179 с.

60. Жеребин В. М. Информационное обеспечение АСУ. М.: Наука, 1975. 200 с.

61. Зак Ю. А., Рейдман Р. В., Рувимский А. А. Методы оптимизации и их применение в целлюлозно-бумажной промышленности. М.: Лесная промышленность. 1973. 155 с.

62. Зорин И. Ф., Петров В. П., Рогульская С. А. Управление процессами целлюлозно-бумажного производства. М.: Лесная промышленность. 1981. 272 с.

63. Жадан В. Г. Численные методы линейного и нелинейного программирования. Вспомогательные функции в условной оптимизации. М.: ВЦ РАН, 2002. 156 с.

64. Информационные системы общего назначения (обзор) М.: Статистика. 1975. 471 с.

65. Исследование операций. / Под ред. Д. Моудера. В 2 т. М.: Мир. 1981.

66. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. Под ред. В. В. Шкурба. М.: Наука, 2000. 353 с.

67. Конвей Р. В., Максвелл В. Л., Милер Л. В. Теория расписаний. М.: Наука, 1975. 284 с.

68. Кузнецов В. А. Обощенная задача раскроя и ее приложения в ЦБП // Обозрение прикладной и промышленной математики, т.10, вып.1, М.: Изд-во "ОПиПМ", 2003, С. 178-180.

69. Кузнецов В. А. Планирование погрузки готовой продукции целлюлозно-бумажного комбината в транспортные средства // Известия высших учебных заведений "Лесной журнал", N 2-3, Архангельск: Изд-во АГТУ, 2003, С. 133-140.

70. Кузнецов В. А. Задачи раскроя и комплектовки материалов в моделировании производственных процессов // Известия высших учебных заведений "Лесной журнал", N 1, Архангельск: Изд-во АГТУ, 2004, С. 111-116.

71. Кузнецов В. А. Использование прикладных оптимизационных задач для повышения эффективности управления целлюлозно-бумажным производством // "Целлюлоза. Бумага. Картон.", N5-6. М.: 2003, С. 28-31.

72. Кузнецов В. А. Опыт применения оптимизационных моделей в задачах планирования и управления ЦБК // НИТ в ЦБП: Тез. II междунар. конф. Петрозаводск: Изд-во ПетрГУ, 1996. , С. 3334.

73. Кузнецов В. А. Задачи объемно-календарного планирования основного производства предприятия ЦБП // Новые информационные технологии в ЦБП и энергетике. Материалы IV Международной конференции. Петрозаводск, 2000. С. 32-33.

74. Кузнецов В. А. Система планирования и управления производством и отгрузкой бумаги и картона // НИТ в ЦБП: Материалы V междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2002. , С. 37-38.

75. Кузнецов В. А. Модели размещения предприятий большой размерности и методы их решения // Математические модели размещения производительных сил. Петрозаводск: Изд-во Карельского отделения АН СССР, 1980., С. 23-36.

76. Кузнецов В. А. Модели большой размерности и методы решения сетевых задач размещения предприятий // Моделирование развития народного хозяйства Карельской АССР. Петрозаводск: Изд-во Карельского отделения АН СССР, 1981., С. 46-58.

77. Кузнецов В. А. Анализ показателей работы лесотранспортных машин // Новые информационные технологии в ЦБП и энергетике. Материалы IV Международной конференции. Петрозаводск, 2002. С. 87-88.

78. Кузнецов В. А. Цели и оценка экономического эффекта разработки системы планирования отгрузки продукции предприятия ЦБП // НИТ в ЦБП: Материалы V междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2002. , С. 88-89.

79. Кузнецов В. А. Опыт разработки и создания систем планирования и управления технологическими процессами предприяий ЦБП // Проблемы лесопромышленных регионов: Матер. Всероссийской научн.-практ. конфер. М.: Инст. предпр. и инвестиций.2002. ,С. 10-11.

80. Кузнецов В. А. О взаимосвязях факторов с переменными оптимизационных задач на лесозаготовках // Ресурсосберегающие технологии лесного комплекса.: Тез. докл. республиканской научн.-практ. конфер. Петрозаводск: КарНИИЛП. 1998. , С. 9.

81. Кузнецов В. А. Стохастическая задача оптимизации перевозки древесины // Вероятностные задачи прикладной математики: Сб. тр. Петрозаводск, Изд-во ПетрГУ, 1984., с .37-45.

82. Кузнецов В. А. Опыт использования оптимизационных моделей для управления производственными процессами // Опыт и использование распределенных сетей управления производственными процессами: Тез. докл. ВНТС. Новокузнецк, 1986. С. 43-46.

83. Кузнецов В. А. Об одном методе решения транспортно-производственной задачи специального вида // Применение математики в экономике: Сб. Вып. 11. Ленинград: Изд-во ЛГУ, 1977. С. 13-23.

84. Кузнецов В. А., Азаров В. В. Программная система для решения задач линейной и сетевой оптимизации // Труды ПетрГУ. Сер. "Прикладная математика". Вып. 1. Петрозаводск: Изд-во Петр-ГУ, 1994. С. 51-56.

85. Кузнецов В. А., Воронов Р. В. Оптимальное планирование распределения заказов производства бумаги между БДМ // Труды ПетрГУ. Сер. "Прикладная математика". Вып.10. Петрозаводск: Изд-во ПетрГУ, 2000. С. 87-99.

86. Кузнецов В. А., Воронов Р. В. Практическая реализация алгоритмов построения объемного и объемно-календарного планов раскроя съема тамбуров // НИТ в ЦБП: Материалы V междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2002. С. 89-90.

87. Кузнецов В. А., Кириллов В. AÍ. О математической подстановке и реализации задачи комплектовки фанеры // Математическое моделирование народного хозяйства: Межвуз. сб. Петрозаводск: Изд-во ПетрГУ, 1990. С. 28-33.

88. Кузнецов В. А., Куприянов А. В. Задача планирования отгрузки бумаги ип картона и метод ее решения // Новые информационные технологии в ЦБП и энергетике. Материалы IV Международной конференции. Петрозаводск, 2000. С. 52-53.

89. Кузнецов В. А., Куприянов А. В. Особенности автоматизации планирования и управления погрузкой продукции предприятия ЦБП // НИТ в ЦБП: Материалы V междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2002. , С. 90-92.

90. Кузнецов В. АПатякин В. И., Шегельман И. Р. Оценка технологических процессов лесозаготовок с применением математических методов и ПЭВМ. СПб.: Изд-во JITA, 1998. 60 с.

91. Кузнецов В. А., Подкопаев Д. В. Классификация задач объемно-календарного планирования в производстве гофротары // Ресурсосберегающие технологии лесного комплекса.: Тез. докл. республиканской научн.-практ. конфер. Петрозаводск: КарНИИЛП. 1998. , С. 28.

92. Кузнецов В. А., Подкопаев Д. В., Шегельман Я. Р. Анализ технологических процессов производства щепы для ЦБК в лесопромышленном регионе // НИТ в ЦБП: Материалы III межд. конф. Петрозаводск: Изд-во ПетрГУ, 1998. , С. 43-44.

93. Кузнецов В. А., Поляков В. В. О моделировании производственных процессов в ЦБП // Применение вычислительной техники в научных исследованиях и проектировании: Сб. тр. Карельского филиала АН СССР. — Петрозаводск: 1986. С. 19-21.

94. Кузнецов В. А., Поляков В. В. О многоуровневой системе моделей распределения ресурсов АСУ ТП ЦБП // Создание и внедрение АСУ ТП: тез. докл. ВНТС. — Новгород: 1986. С. 19-21.

95. Кузнецов В. А., Поляков В. В. Опыт практического использования оптимизационных задач в управлении производством целлюлозы // Сб. научн. трудов ВНПО «Бумпром» — Ленинград: 1990. С. 35-43.

96. Кузнецов В. А., Поляков В. В., Кириллов В. М. О реализации оптимизационных моделей в АСУ ОДУ // Математическое обеспечение ЭВМ и систем управления: Сб. Петрозаводск: Изд-во ПетрГУ, 1985. С. 67-74.

97. Кузнецов В. А., Поляков В. В., Коржов С. Т. О математических моделях раскроя бумвжного полотна // Математическое моделирование народного хозяйства: Сб. Петрозаводск: Изд-во Петр-ГУ, 1990. С. 38-42.

98. Кузнецов В. А., Сущук М. А. Постановка и алгоритм решения задачи оценки лесных ресурсов Республики Карелия // Устойчивое развитие региона: лесопромышленный комплекс: матер, научн.-практ. конф. Петрозаводск.: КарНИИЛП. 2000. , С. 22.

99. Кузнецов В. А., Сущук М. А. Об экономической оценке лесных ресурсовв Республики Карелия // Современные проблемы лесного комплекса: Сб. научн. трудов. Петрозаводск.: КарНИИЛП. 2000. , С. 26-30.

100. Кузнецов В. А., ФоминА. А. Статистические и оптимизационные модели в военно-медицинской экспертизе // Труды ПетрГУ. Сер. "Прикладная математика". Вып. 4. Петрозаводск: Изд-во Петр-ГУ, 1995. С. 3-12.

101. Кузнецов В. А., Фомин А. А. О комплексе моделей исследования операций в военно-врачебной экспертизе. Деп. в ГЦНМБ N Д-26147. Петрозаводск: 1999. 13 с.

102. Кузнецов В. А., Фомин А. А., Касьянов О. Ю. Математические методы и использование ГИС-отображений состояния здоровья молодежи Карелии. // Деп. в ГЦНМБ N Д-26148. Петрозаводск: 1999., 15 с.

103. Кузнецов В. А., Шабаев Г. И. Некоторые подходы к оценке работы службы сбыта крупного предприятия // Труды ПетрГУ. Сер. "Прикладная математика". Вып. 1. Петрозаводск: Изд-во Петр-ГУ, 1994., С. 31-36.

104. Кузнецов В. А., Шалабин Г. В. Определение оптимальной очередности ввода производственной мощности с учетом промежуточных пусковых комплексов // Применение математики в экономике: Сб. Вып. 12. Ленинград: Изд-во ЛГУ, 1977. С. 81-88.

105. Кузнецов В. А., Шалабин Г. В. Об. одной задаче распределения капитальных вложений // Применение математики в экономике: Сб. Вып.9. Ленинград: Изд-во ЛГУ, 1974. С. 68-84.

106. Кузнецов В. А., Шалабин Г. В. Об одной однопродуктовой задаче оптимального управления процессом освоения проектной производственной мощности // Применение математики в экономике: Сб. Вып.Ю. Ленинград: Изд-во ЛГУ, 1974. С. 35-44.

107. Кузнецов В. А., ШегельманИ. Р. Математическое моделирование при планировании и организации лесозаготовок. Петрозаводск: Изд-во КРИА, 1998. 125 с.

108. Кузнецов В. А., Шегельман И. Р. Применение математических методов и ПЭВМ на лесоразработках. СПб: Изд-во СПб ЛТА, 1998. 68 с.

109. Кузнецов В. А., Шегельман И. Р. Некоторые приложения транспортной задачи к планированию процессов на лесозаготовках // Современные проблемы лесного комплекса: Сб. научн. трудов. Петрозаводск.: КарНИИЛП. 2000. С. 11-19.

110. Кузнецов В. А., Черноусов В. В., Шах Ю. М. Задача регулирования производительности основных отделов производства сульфатной беленой целлюлозы Сб. тр. ВНИИБ "Автоматизация и механизация производственных процессов в ЦБП" СПб. 1986., С. 54-57.

111. Куликов В. В., Кузнецов В. А., ФоминА. С., Чернов О. Э. Военно-медицинская экспертиза. Системное математическое моделирование. Петрозаводск.: Изд-во ПетрГУ, 1998. 120 с.

112. Лэсдон С. Оптимизация больших систем М.: Изд-во Мир, 1976. 584 с.

113. Исследование операций., // Современное состояние. / под. ред. Д. Моудера т. 1-2, М.: Изд-во Мир, 1989.

114. Мазурин А. Р. Система оптимизации раскроя листового материала T-FLEX / Раскрой // Новые пром. технологии. 2002. N3/4. С. 70-71.

115. Методологические положения оптимального отраслевого планирования в промышленности. Новосибирск: Наука, 1972. 175 с.

116. Мухачева Э.А, Картак В.М. Костригин Е.В. Гибридные методы решения классической задачи одномернонго раскроя. / Дискр. анализ и исслед. опер. (Материалы конференции) // Новосибирск. Изд-во института математики. 2000. С. 193.

117. Мухачева Э. А, Валева А. Ф. Метод динамического перебора в задаче двухмерной упаковки. Информационные технологии. 2000 JV 3 С. 21-25.

118. Мухачева Э. А, Валева А. Ф., Гареев И. Р. Применение метода динамического перебора к решению задач раскроя-упаковки. / Дискр. анализ и исслед. опер. (Материалы конференции) // Новосибирск. Изд-во института математики. 2000. С. 183-187.

119. Мухачева Э.А, Картак В.М. Оптимальная упаковка N-мерных прямоугольных объектов в полу бесконечную область. / Дискр. анализ и исслед. опер. (Материалы конференции) // Новосибирск. Изд-во института математики. 2000. С. 192.

120. Мухачева Э.А, Мухачева А.С, Чиглинцев В.А. Генетические алгоритмы для решения задач прямоугольного раскроя-упаковки. / Дискр. анализ и исслед. опер. (Материалы конференции) // Новосибирск. Изд-во института математики. 2000. С. 194.

121. Мухачева Э. А, Мухачева А. С, Чиглинцев В. А. Генетический алгоритм блочной структуры в задачах двухмерной упаковки. // Информационные технологии 1999 N 12. С. 13—18

122. Нейман Ф, Моргенштейн О. Теория, игр и экономическое поведение. М.: Наука, 1970. 707 с.

123. Непенин Ю. Н. Технология целлюлозы: В 2 т. М.: Лесная промышленность, 1990.

124. Норенков И. П. Эвристки и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. N 1 С. 2-7.

125. Норенков И. П., Косачевский И. Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации. // Информационные технологии. 1999. N 2 С. 2-87.

126. Ope О. Теория графов. М.: Мир, 1968. 368 с.

127. Оуэн Г. Теория игр. М.: Изд-во Мир, 1971. 228 с.

128. Обхерден А., Энглерт Л., Швензон X. и др. Целлюлоза. Бумага. М.: Лесная промышленность. 1980. 211 с.

129. Первозванский А. А. Математические модели в управлении производством. М.: Наука, 1975. 616 с.

130. Пижурин А. А. Оптимизация оперативно-календарного планирования и управления лесопильно-деревообрабатывающими предприятиями в условиях нечеткой производственной среды // Лесн. вестн. 1998. N 1. С. 100-104.

131. Плискин JI. Г. Билинейные модели оптимизации производства. М.: Советское радио, 1979. 201 с.

132. Проблемы оптимизации дискретных систем : Сб. науч. ст. под ред. М. К. Чиркова. // СПб.: Изд-во НИИХ, 2001. 128 с.

133. Прыгичев А. Н.} Кузнецов В. А. Об одном методе решения задачи размещения с неоднородной целевой функцией // Применение математики в экономике: Сб. Вып. 10. Ленинград: Изд-во ЛГУ, 1975. С. 34-42.

134. Романовский И. В. Алгоритмы решения экстремальных задач. М.: Наука , 1977. 352 с.

135. Романовский И. В. Субоптимальные решения. Петрозаводск: Изд-во ПетрГУ, 1998. 96 с.

136. Рувимский А. А., Зак Ю. А., Рейдман Р. М. Математические модели и алгоритмы в системах управления картонно-бумажным производством. М.: Лесная промышленность, 1971. 231 с.

137. Сафонова М. Р. Система планирования работы бумажного производства и оптимизации раскроя полотна: // Целлюлоза. Бумага. Картон. 1999 N9-10. С. 33-35.

138. Сервах В. В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискрет, анализ и исслед. операций. Сер. 2. 2000. т. 7, N1. С. 75-82.

139. Сигал И. X. Приближенные методы и-алгоритмы в дискретной оптимизации. М.: МИИТ, 2000. 106 с.

140. Скопин И. И., Сафонова М. Р., Дятлова Е. П. Задача диагностики узкого места в интегрированной системе управления сульфатной беленой целлюлозы. М.: Наука, 1984. 38 с.

141. Соболев И. В. Оптимизация раскроев пиломатериалов. М.: Лесн. пром-сть, 1976. 154 с.

142. Танаев В. С., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975. 256 с.

143. Тьюаринсон С. Разреженные матрицы. М.: Наука, 1975. 272 с.

144. Тютюкин В. К. Нахождение оптимальных планов в многооперационных системах обработки изделий методом «ветвей и границ» // Применение математики в экономике: Сб. Вып. 6. Ленинград: Изд-во ЛГУ, 1970. С. 29-45.

145. Уздемир А. П. Обобщенная задача календарного планирования дискретного производства: // Автоматика и телемеханика. 1999. N 4. С. 103-110.

146. Финкельштейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с.

147. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 520 с.

148. Чернецкий В. И. Математическое моделирование динамических систем. Петрозаводск: Изд-во ПетрГУ, 1996. 432 с.

149. Чернецкий В. И. Математическое моделирование стохастических систем. Петрозаводск: Изд-во ПетрГУ, 1994. 488 с.

150. Чернова Г. В. Задача об определении порядка запуска деталей, обеспечивающего минимум пролеживания деталей // Применение математики в экономике: Сб. Вып. 5. Ленинград: Изд-во ЛГУ, 1969. С. 147-158.

151. Шалабин Г. В., Кузнецов В. А. Динамические модели распределения капиталовложений. // Оптимизация долгосрочного плана группы взаимосвязанных отраслей экономического района. JL: Изд-во ЛГУ, 1975. С. 60-80.

152. Шеков В. В., Кузнецов В. А., Киль А. В, Шеков М. В. К оценке блочности массива на основе модели трещиноватости //Геология и полезные ископаемые Карелии: Труды Карельского научного центра РАН, вып. 3 — Петрозаводск: Изд-во КНЦ РАН, 2001. С. 137-140.

153. Шегельман И. Р., Кузнецов В. А. Экономико-математические методы исследования операций при организации лесозаготовок. Петрозаводск: Изд-во ПетрГУ, 1999. 64 с.

154. Шегельман Я. Р., Скрипник В. П., Пладов А. В., Кочанов А. Н., Кузнецов В. А. Моделирование движения лесовозных автопоездов. Петрозаводск: Изд-во ПетрГУ, 2003. 232 с.

155. Шеков В. А., Кузнецов В. А. и др. К оценке блочности массива на основе модели трещиноватости // Геология и полезные ископаемые: сб. трудов, Вып. 3. Петрозаводск: изд-во КНЦ РАН, 2001. С. 137-140.

156. Шитов Ф. А. Технология ЦБП. М.: Лесная промышленность, 1966. 268 с.

157. Шкурба В. В. Некоторые вопросы автоматизированного управления предприятиями. М.: Кибернетика, N 3, 1967. С. 66-77.

158. Шмелев В. В. Точные штрафные функционалы в задачах календарного планирования // Автоматика и телемеханика. 1999. N 9. С. 107-114.

159. Шмелев В. В. Мультипликативный метод точных нештрафных функционалов для задач календарного планирования // Автоматика и телемеханика. 2000. N 8. с. 147-155.

160. Юдин Д. Б., ЮдинА. Д. Экстремальные модели в экономике. М.: Экономика 1979. 360 с.

161. Balas Е. An Additive Algorithm for Solving Linear Programm Prolems with Zero-One Variables., // Oper. Research, 1962. v.10, N. 4, 517-546 pp.

162. Bartels R. H., Golub G. H. The Simplex Method of Linear Programming using LU decomposition, // Communications ACM, v. 12, 1969. pp. 266-268, 275-278.

163. Benders J. F. Partitioning Procedures for Solving Mixed Variable Programming Problems, // Numerische Mathematik v. 4, 1962. pp. 238-252.

164. Chenn C. S., Le S. M., Shen Q. S. An analitical model for the container loading problem // European Journal of Operations Research, v. 16. 1980. pp. 68-76.

165. Golemanov L. Banchevsky Z., Atanasov V. A methodology for modeling and coordination of industrial production and energy complexes. // Helsinki, 1989. 79 p.

166. Dantzig G. B. Linear Progamming and Extantions. Princeton Uniercity Pres, 1963. 462 p.

167. Dantzig G. B., Van Slyke R.M. Generalized Upper Bounding Techniques, // Journal Computer and System Science, v. 1, 1967. pp. 213-226.

168. Dantzig G., Wolfe P. The Decompozition Principle for Linear Programming // Operations Research, v. 8, 1960. pp. 101-111.

169. Dickhoff H. A Tipology of Cutting and Parcking Problems // European Journal of Operations Research, v. 44, 1995. pp. 145-159.

170. Garñnkel R. S., Nemhauser G. L. A Survey of Integer Programming emphazing Computation and Relations among Models // «Mathematical Programming» New-York London, Academic Press, 1973. 528 p.

171. Geofrion A. M., Marsten R. E. Integer Programming Algorithms: a Fraimework and the State-of-Art-Survay // Management Sei., 1972. v.18, N. 4, 465-491 pp.

172. Gilmore R. C., Gomory R. E. Many Stage Cutting Stock Problems of Two and More Dimensions // Journal ORSA., 1965. v.16, N. 4, 94-120 pp.

173. Kuznetsov V., Tarasenko A. Application of mathematical modelling in the system Damatic Xdi // Prod, of Intern. Conf. "Forest sector development problems" Petrozavodsk. 1998. 24-25 pp.