WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

СОШКИН РОМАН ВЛАДИМИРОВИЧ

ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ ГОФРОПОЛОТНА И

МЕТОДЫ ИХ РЕШЕНИЯ

Специальность:

05.13.18 математическое моделирование, численные методы и

комплексы программ.

АВТОРЕФЕРАТ

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

Петрозаводск 2009

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

ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

доктор технических наук,

Научный руководитель:

профессор Кузнецов Владимир Алексеевич.

доктор технических наук,

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

профессор Колесников Геннадий Николаевич, кандидат физико-математических наук, доцент Печников Андрей Анатольевич.

Ведущая организация: Санкт-Петербургский государственный технологический университет растительных полимеров.

Защита диссертации состоится.................... 2009 года в........ часов на заседании Диссертационного Совета Д 212.190.03 при Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, д.

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

Автореферат разослан................. 2009 года.

Ученый секретарь диссертационного совета В.В. Поляков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

.

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





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

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

Действительно, если в 1980 году недельный план ОАО Архангельский ЦБК включал 10–12 изделий (из них до 60 % составляли стандартные ящики для упаковки рыбы), то в 1990 году 20–25 (причем доля ящиков для упаковки рыбы снизилась до 35 % ), в 1995 году это количество возросло до 60–80, в 2000 году до 120, а в настоящее время составляет 150–180 видов изделий. Аналогичная ситуация наблюдается и на других целлюлозно-бумажных комбинатах (ЦБК) и производствах бумажной и картонной тары.

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

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

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

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

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





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

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

Для достижения поставленной цели были сформулированы следующие задачи:

1. Исследовать технологии планирования и управления раскроями гофрополотна на различных производствах.

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

3. Исследовать математические задачи, полученные на основании расширенной модели.

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

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

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

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

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

Представлены принципы классификации исследуемых моделей.

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

• Сформулированы и исследованы задачи оптимизации для моделирования процессов раскроя гофрополотна.

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

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

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

Автором разработаны и выносятся на защиту следующие результаты:

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

2. Предложены методы решения этих задач.

3. Сформулирован класс задач ЛП с ограниченным количеством базисных переменных.

4. Разработаны методы решения задач ЛП с ОКБП. Дана классификация этих методов.

5. Все перечисленные методы реализованы в виде комплексов программных средств, используемых при разработке и создании АСУ планирования раскроев гофрополотна (далее ГП), внедренных на ряде промышленных предприятий.

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

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

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

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

1. ОАО Архангельский ЦБК, г. Новодвинск.

2. Филиал ОАО Архбум в г. Подольске.

3. ОАО Киевский картонно-бумажный комбинат, г. Обухов.

4. ООО Гранит, г. Павловский Посад.

5. ООО Ярославский картон, г. Ярославль.

6. ООО Вереск-1, г. Архангельск, г. Гатчина.

7. ЗАОр Народное предприятие Набережночелнинский картоннобумажный комбинат, г. Набережные Челны.

8. ОАО БумСнаб, г. Нижний Новгород.

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

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

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

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

Для разработки алгоритмов и программных комплексов использовались современные технологии проектирования программных систем и баз данных, методы структурного и объектно-ориентированного программирования. Для разработки использовались системы программирования Borland Delphi 4 – 7 и Microsoft Visual Studio.NET 2003, 2005, для проектирования баз данных использовались Paradox и Microsoft SQL Server 2000, 2005.

Апробация работы Основные результаты диссертационной работы докладывались автором на V-VIII Международных научно-технических конференциях Новые информационные технологии в ЦБП и энергетике (Петрозаводск, 2002, 2004, 2006, 2008), на Международной школе-конференции по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов (Ялта, Украина, 2006), на конференциях и семинарах ПетрГУ. На Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники Информационно-телекоммуникационные системы (Московская область, 2005) получен диплом первой степени.

На автоматизированную систему Управление гофропроизводством получено свидетельство об отраслевой регистрации разработки № в ФГНУ Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ.

Публикации Основные результаты диссертационной работы опубликованы в печатных работах, в том числе три в журналах, реферируемых ВАК.

Структура и объем работы Диссертация состоит из введения, 4 глав основного материала, заключения, библиографического списка и 1 приложения. Основной материал изложен на 118 стр., включая 5 рисунков и 2 таблицы. Библиографический список включает 87 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Для построения расширенной модели используются следующие обозначения:

M множество индексов заготовок для заказов (далее всегда i M );

M0 множество индексов заготовок для заказов, для которых разрешен поворот (M0 M );

i индекс заготовки, которая получается из заготовки с индексом i M0 путем поворота на 900 ;

ширина заготовки для заказа i M (измеряется в мм.);

Bendsi pi флаг необходимости дальнейшей переработки заготовки для заказа i M ;

объем заготовок на складе по заказу i M (измеряется в м2 );

множество индексов раскроев (далее всегда j N );

планируемая выработка гофрополотна в м2 в соответствии с раскроем j N (объем выработки раскроя);

множество индексов гофроагрегатов (далее всегда c C);

Wc множество допустимых различных форматов полотна на гофроагрегате c C;

Nc множество индексов раскроев допустимых для выпуска на гофроагрегате c C (Nc N );

Nt множество индексов раскроев допустимых для выпуска с использованием формата t Wc (Nt Nc N );

Aij нормативы выработки заготовок для заказов i M при раскрое единицы площади гофрополотна по схеме j N ;

количество заготовок для заказов i M в составе раскроя по схеме j N ;

доля потерь материала при раскрое по схеме j N ;

количество необрезных заготовок в раскрое j N ;

количество продольных ножей гофроагрегата c C;

KnBc количество продольных рилевочных ножей гофроагрегата d c, Dc минимальная и максимальная возможная производительность гофроагрегата c C в течение планируемого промежутка времени (в м2 );

ширина полотна формата t Wc (измеряется в мм.);

St минимально необходимая кромка для отреза с каждой стороны полотна формата Lt (измеряется в мм.);

St максимально разрешенная кромка для отреза с каждой стороны полотна формата Lt (измеряется в мм.);

gctj {0, 1} флаг выполнения раскроя j с использованием формата t гофроагрегата c;

Q множество индексов готовых изделий: комплектов картонных ящиков и изделия не входящие в комплекты (далее всегда q Q);

Mq M множество заготовок в составе комплекта ящика q Q;

кратность числа предметов с индексом i Mq в комплекте bq, Bq нижняя и верхняя границы требуемого количества в м2 комплекта q Q.

планируемый объем производства комплекта q Q (в м2 );

минимальный допустимый для кроя объем раскроя (в м2 );

K максимально разрешенное количество раскроев в оптимальном плане.

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

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

ограничения на объемы выпуска заготовок с учетом комплектности: (2) заготовки, для которых не важно направление гофры, (3) остальные заготовки.

ограничение на выработку комплектов.

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

учет производительности гофроагрегатов.

ограничение на объемы выпуска каждого из раскроев.

условие на допустимое количество раскроев в оптимальном плане.

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

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

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

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

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

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

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

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

1. Задачи ЛП с ограниченным количеством базисных переменных.

Чтобы сформулировать задачу ЛП с ограниченным количеством базисных переменных в общем виде, рассмотрим задачу ЛП P формирования оптимального плана раскроев с множеством M = 1..m ограничений, N = 1..n переменных, матрицей A (m n) ограничений и векторами b 0, c 0 и x соответствующей размерности Следуя содержанию задачи, коэффициенты матрицы Aij 0, следовательно, можно ограничиться случаем bi 0 для каждого i M.

Будем также считать, что ограничения задачи (12) совместны, x ее оптимальное решение, z = cx оптимальное значение целевой функции. Будем считать, что матрица ограничений этой задачи невырождена и имеет полный ранг. Каноническая форма этой задачи такова:

Множество переменных задачи (12) составляет N = N +M, базисных переменных N N, где |N | = m. Среди переменных множества присутствуют как переменные основной задачи Nx N (основные базисные столбцы), так и орты Ny M (дополнительные базисные столбцы), N = Nx + Ny. В силу предположения о невырожденности всех базисных решений задачи x[Nx ], y[Ny ] 0 для любого базисного множества N. Важная особенность целевая функция рассматриваемой задачи обязательно ограничена снизу.

Цель данного исследования этой задачи с дополнительным условием которому соответствует оптимальное значение целевой функции z(k).

Полученную задачу обозначим Pk и будем называть задачей ЛП с ограниченным количеством базисных переменных основной матрицы. Задачу (12) или (13) будем называть базовой по отношению к данной задаче ОКБП, число k рангом базиса задачи. Следует оговорить некоторую условность в названии класса рассматриваемых задач ранг матрицы определяет лишь |Nx | количество основных столбцов матрицы ограничений, общее количество базисных переменных (основных столбцов Nx и Ny ), разумеется, всегда составляет m.

Отметим, что если |Nx | k, то решение Pk совпадает с решением P. Сложности возникают в случае |Nx | k, который рассматривается в соответствующем разделе диссертации.

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

Отметим некоторые особенности рассматриваемой задачи.

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

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

• Для любой задачи ЛП (12) или (13) имеется целое k0, такое, что рассматриваемая задача имеет допустимое решение только для k k0 . Таким образом, необходимо рассматривать подмножества Nx N для которых k0 |Nx | k, что принципиально противоречит концепции независимого множества матроида. В связи с этим необходима определенная, представленная далее, корректировка условий этой задачи.

Дополнив условия исходной задачи (12) требованием ограничения количества базисных (ненулевых) переменных решения этой задачи не более некоторого установленного значения k, получим задачу Pk. Оптимальное решение этой задачи обозначим x.

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

Обозначим M = N, J однородный матроид ранга k, множество элементов которого N, а семейство независимых множеств J = { A 2N ||A| k} определяет допустимые множества Nx. Множество баз данного матроида B составляют k-элементные подмножества N, множество циклов (k + 1)-элементные подмножества.

Введем также двойственный матроид по отношению к рассматриваемому M = N, J с семейством независимых множеств J = { A 2N ||A| k}. Независимые множества двойственного матроида (кроме баз) соответствуют недопустимым решениям задачи.

Множество Cn баз B каждого из этих матроидов составляют kэлементные подмножества N. Матроидная структура накладывается на множество допустимых решений задачи (13) с дополнительным условием (14).

Для некоторого k рассматриваемая задача может не иметь допустимого решения. Чтобы избавиться от этой проблемы, расширим множество столбцов задачи вектором b, которому сопоставим искусственную переменную w. Теперь задача обязательно имеет решение для каждого k. В случае выбора достаточно большого весового коэффициента G данная и исходная задачи эквивалентны.

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

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

Теорема 1 устанавливает связь задачи ОКБП с некоторой специально построенной задачей о покрытии, что указывает на NP сложность рассматриваемой задачи.

Теорема 2 показывает, что оптимальное решение задачи (13 14) эквивалентно решению задачи (15) для некоторого значения параметра G и устанавливает его оценку.

Теорема 3 устанавливает свойства целевой функции задачи (12) в случае фиксации значения одной из ее переменных и является основой для вывода в Теореме 4 свойства супермодулярности целевой функции zN как функции от множества столбцов базисных переменных, что и является обоснованием представленных далее алгоритмов решения задачи ОКБП.

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

В рамках исследования все алгоритмы решения задачи P являются:

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

В диссертации предложены следующие алгоритмы решения задач ЛП с ОКБП:

• Прямые переборные алгоритмы:

– последовательный анализ независимых множеств (алгоритм – последовательный анализ баз матроида (A2);

– перебор дополнений циклов двойственного матроида (A3).

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

• Прямые приближенные алгоритмы:

– приближенный алгоритм (A4), – жадный прямой алгоритм (A5).

На практике хороший результат показывает приближенный, не гарантирующий оптимальность полученного плана, алгоритм A4, аналогичный A2. На предварительном этапе этого алгоритма решением задачи (13) находится базисное решение N = Nx +Ny, а в процессе перебора множество N заменяется на существенно меньшее N N. Алгоритм A5 по своей сути, является незаконченным решением определенной разновидности симплексного метода. Специальным образом формируется базисное множество, далее следует выполнить определенное количество итераций симплексного метода, останавливаясь, (а) по мере завершения работы симкак только на следующем шаге |Nx | плексного метода, или (б) должно превысить k.

• Двойственные алгоритмы:

– алгоритм последовательного отсева (D1), – метод фронтального перебора (D2), – начальный шаг субоптимального алгоритма (D3).

Двойственными алгоритмами назовем методы, в которых базисные множества столбцов Nx пробных планов являются независимыми множествами двойственного однородного матроида ранга n k.

Если при исследовании прямых алгоритмов основой перебора является Nx =, то за основу двойственных логично принять Nx = Nx оптимальное решение задачи (12) без ОКБП. В алгоритме D1 после решения задачи (12) происходит последовательное исключение из базисного плана переменных с наихудшими оценками до тех пор, пока в плане не останется k переменных x.

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

3. Методы решения других задач оптимизации, основанные на использовании матроидов.

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

1. Задача ОКБП по критерию наименьшего суммарного перевыполнения заданий:

2. Задача ОКБП с ограниченным суммарным перевыполнением заданий:

3. Задача ОКБП с ограничениями размеров перевыполнения заданий:

4. Задача ОКБП по критерию наименьшего суммарного взвешенного перевыполнения заданий:

5. Минимаксная задача ОКБП:

6. Задача ОКБП с комбинированным критерием, например:

и произвольным дополнительным набором ограничений.

7. Задача ОКБП с критериями эффективности и ограничениями, подобными представленным, для некоторого подмножества M M дополнительных переменных.

Все перечисленные задачи могут иметь практическое приложение.

Поскольку все эти задачи без условия ОКБП сводятся к линейным задачам, представленная в диссертации теория может быть применена и к этим задачам.

4. Методы расчета оценок потерь материала.

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

Эти оценки важны в следующих случаях.

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

2. При оценке себестоимости изделия в зависимости от срочности его изготовления.

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

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

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

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

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

2. Если задача P не имеет решений, при расчете оценок следует исходить из пусть и недопустимого, но реально полученного плана, для чего необходимо решить задачу с правой частью где wi величина невыведенной искусственной переменной исходной задачи ЛП.

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

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

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

2. Модуль регистрации технологических карт и характеристик оборудования.

3. Модуль многодневного объемного планирования.

4. Модуль оперативного планирования работы технологических линий.

5. Модуль оперативного планирования работы гофроагрегатов.

6. Модуль учета выработки производства.

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

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

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

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

Как следствие, примерно на 80% сокращается количество ошибок, связанных с устаревшими данными в технологических картах или ручным вводом планов раскроя.

5. Сокращение времени, затрачиваемого на составление планов различных горизонтов времени. Например, составление трехдневного плана работы линий переработки сокращается в среднем с 5 часов 6. Появилась возможность оперативного пересчета планов в условиях динамически меняющегося списка заказов.

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

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

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

4. Установлена возможность использования представленных в диссертации алгоритмов для решения ряда других задач.

5. Все перечисленные методы реализованы в виде комплексов программных средств, используемых при разработке и создании АСУ планирования раскроев гофрополотна.

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

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

В приложении содержится копия свидетельства о регистрации разработки и акты о внедрении автоматизированной системы управления на:

ОАО Архангельский ЦБК, филиал ОАО Архбум в г. Подольске, ЗАОр Народное предприятие Набережночелнинский картонно-бумажный комбинат.

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

1. Сошкин Р.В. Математические модели и алгоритмы решения задач оптимального раскроя полосы / Р.В. Сошкин // Вестник Поморского университета. Сер. Естественные 2. Сошкин Р.В. Некоторые прикладные задачи раскроя и методы их решения / Р.В. Сошкин // Известия ОрелГТУ.

Сер. Фундаментальные и прикладные проблемы техники 3. Сошкин Р.В. О применении математических методов для повышения эффективности производства упаковки из гофрокартона / Р.В. Сошкин // Известия СанктПетербургской лесотехнической академии. 2007.

4. Власов Д.П. Новая реализация комплекса программ планирования производства гофротары / Д.П. Власов, В.А. Кузнецов, Р.В.

Сошкин // Новые информационные технологии в целлюлознобумажной промышленности и энергетике: Материалы VI Международной научно-технической конференции. Петрозаводск: Издво ПетрГУ, 2004. С.79–81 (вклад диссертанта 33%).

5. Кузнецов В.А. Модели раскроя в планировании и управлении производствами ЦБП / В.А. Кузнецов, Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VI Международной научно-технической конференции. Петрозаводск: Изд-во ПетрГУ, 2004. С.104– (вклад диссертанта 66%).

6. Сошкин Р.В. Особенности применения метода генерации столбцов при решении задачи раскроя гофрополотна / Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VI Международной научно-технической конференции. Петрозаводск: Изд-во ПетрГУ, 2004. С.122–124.

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

ГНИИ ИТТ Информика, 2005. С.73–74 (вклад диссертанта 8. Власов Д.П. Автоматизированная система управления производством гофротары / Д.П. Власов, В.А. Кузнецов, Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VII Международной научно-технической конференции. Петрозаводск: ПетрГУ, 2006.

С.50–53 (вклад диссертанта 50%).

9. Власов Д.П. Автоматизированная система оптимального планирования производства гофротары / Д.П. Власов, Р.В. Сошкин // Международная школа-конференция по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов. Тезисы докладов. М., 2006. С.12–13 (вклад диссертанта 50%).

10. Власов Д.П. Автоматизированная система оптимального планирования производства гофротары / Д.П. Власов, Р.В. Сошкин // Новые информационные технологии. Тезисы докладов XIV Международной студенческой школы-семинара М.: МИЭМ, 2006.

С.224–225 (вклад диссертанта 50%).

11. Власов Д.П. Автоматизированная система управления производством гофротары / Д.П. Власов, Р.В. Сошкин // Федеральная школа-конференция по инновационному малому предпринимательству в приоритетных направлениях науки и высоких технологий. Тезисы докладов. М., 2006. С.20–22 (вклад диссертанта 12. Власов Д.П. Свидетельство об отраслевой регистрации разработки №6562 / Д.П. Власов, Д.П. Косицын, В.А. Кузнецов, Р.В. Сошкин // ФГНУ Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ.

2006 (вклад диссертанта 25%).

Формат 60х84 1/16. Бумага офсетная.

Государственное образовательное учреждение высшего профессионального образования

ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Отпечатано в типографии Издательства Петрозаводского государственного университета 185910, Петрозаводск, пр. Ленина,

 
Похожие работы:

«Бабанин Дмитрий Владимирович МОДЕЛИ ОЦЕНКИ СТРУКТУРНЫХ РЕШЕНИЙ ПО ЗАЩИТЕ КОМПЬЮТЕРНЫХ СЕТЕЙ ОТ ВИРУСНЫХ АТАК Специальность 05.13.19 – Методы и системы защиты информации, информационная безопасность АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва - 2012 Работа выполнена на кафедре Вычислительные системы и сети ФГБОУ ВПО Московский государственный институт электроники и математики (технический университет) Научный руководитель : доктор...»

«БАКИН Евгений Александрович ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ СБОРА ИНФОРМАЦИИ В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ НА ОСНОВЕ ОПТИМИЗАЦИИ РАСПИСАНИЯ Специальность 05.13.01 Системный анализ, управление и обработка информации (в технике и технологиях) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2012 Работа выполнена на кафедре моделирования вычислительных и электронных систем в Федеральном государственном автономном образовательном учреждении...»

«Старченко Николай Викторович ИНДЕКС ФРАКТАЛЬНОСТИ И ЛОКАЛЬНЫЙ АНАЛИЗ ХАОТИЧЕСКИХ ВРЕМЕННЫХ РЯДОВ 05.13.18 – Математическое моделирование, численные методы и комплексы программ 01.01.03 – математическая физика диссертация на соискание ученой степени кандидата физико-математических наук Москва - 2005 Работа выполнена в Московском инженерно-физическом институте (государственном университете), Научный руководитель : доктор физико-математических наук, профессор Крянев Александр...»

«Зинин Михаил Владимирович Символьные алгоритмы и программы вычисления булевых базисов Грёбнера 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 Работа выполнена в Лаборатории информационных технологий Объединенного института ядерных исследований. Научный руководитель : доктор физико-математических наук, профессор Гердт...»

«Лаконцев Дмитрий Владимирович Анализ и оптимизация адаптивного централизованного управления в беспроводных широкополосных сетях передачи информации. Специальность 05.13.13 – Телекоммуникационные системы и компьютерные сети. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2007 Работа выполнена в Институте проблем передачи информации им. А.А. Харкевича РАН. Научный руководитель : доктор технических наук, профессор Вишневский Владимир...»

«Гультяева Татьяна Александровна ИССЛЕДОВАНИЕ ПОДХОДА К РЕШЕНИЮ ЗАДАЧИ КЛАССИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ПРЕДСТАВЛЕННЫХ СКРЫТЫМИ МАРКОВСКИМИ МОДЕЛЯМИ, С ИСПОЛЬЗОВАНИЕМ ИНИЦИИРОВАННЫХ ЭТИМИ МОДЕЛЯМИ ПРИЗНАКОВ Специальность 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Новосибирск – 2013 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального...»

«Токарева Юлия Сергеевна РАВНОВЕСИЕ В АРБИТРАЖНЫХ ПРОЦЕДУРАХ Специальность 05.13.18 математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Петрозаводск – 2008 г. Работа выполнена в Забайкальском государственном гуманитарно-педагогическом университете им. Н.Г. Чернышевского. Научный руководитель : доктор физико-математических наук, профессор Мазалов Владимир Викторович...»

«Есипов Денис Викторович МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ИНИЦИАЦИИ И РАСПРОСТРАНЕНИЯ ТРЕЩИН ГИДРОРАЗРЫВА ПЛАСТА 05.13.18 — Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск — 2011 Работа выполнена в Институте вычислительных технологий Сибирского отделения РАН. Научный руководитель : доктор...»

«Хаметов Дмитрий Владимирович АСИМПТОТИКА РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ УРАВНЕНИЯ ГАМИЛЬТОНА-ЯКОБИ-БЕЛЛМАНА, СООТВЕТСТВУЮЩЕГО УПРАВЛЯЕМЫМ ПРОЦЕССАМ С МАЛЫМИ СЛУЧАЙНЫМИ ВОЗМУЩЕНИЯМИ 05.13.01 системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико–математических наук Москва 2006 Работа выполнена на кафедре кибернетики Московского Государственного института электроники и математики (МИЭМ) Научный руководитель : доктор...»

«ФОКИН Василий Александрович МОДЕЛЬ СОГЛАСОВАНИЯ БИОМЕДИЦИНСКИХ ДАННЫХ И КОМПЛЕКС ПРОГРАММ ДЛЯ ИНТЕГРАЛЬНОЙ ОЦЕНКИ СОСТОЯНИЯ БИОСИСТЕМ 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Томск – 2009 Работа выполнена на кафедре медицинской и биологической кибернетики ГОУ ВПО Сибирский государственный медицинский университет. Научные консультанты: доктор...»

«Титов Ростислав Николаевич РАЗРАБОТКА СИСТЕМЫ ЭЛЕКТРОННОГО ДОКУМЕНТООБОРОТА ДЛЯ АВТОМАТИЗАЦИИ УПРАВЛЕНИЯ НАУЧНО-ТЕХНИЧЕСКИМИ ПРОЕКТАМИ (НА ПРИМЕРЕ ЕВРОПЕЙСКОЙ ОРГАНИЗАЦИИ ЯДЕРНЫХ ИССЛЕДОВАНИЙ) Специальность 05.13.01 - системный анализ, управление и обработка информации (в информационных системах) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2011 Работа выполнена в Европейской организации ядерных исследований и Национальном...»

«Величкин Андрей Сергеевич ОБРАЩЕНИЕ С ОТХОДАМИ ХИМИЧЕСКИХ ПРОИЗВОДСТВ ПРИ ПЕРЕРАБОТКЕ УРАНОВЫХ РУД – ИНФОРМАЦИОННАЯ ПОДДЕРЖКА 05.13.01 – Системный анализ, управление и обработка информации (химическая промышленность) АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Москва – 2010 Работа выполнена на кафедре Информационных технологий государственного образовательного учреждения высшего профессионального образования Московская государственная...»

«Ван Ефэн МЕТОДОЛОГИЯ СОВЕРШЕНСТВОВАНИЯ СИСТЕМ КРАТКОСРОЧНОГО ПРОГНОЗИРОВАНИЯ ЭЛЕКТРОПОТРЕБЛЕНИЯ Специальность: 05.13.06 – Автоматизация и управление технологическими процессами и производствами (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт - Петербург – 2013 Работа выполнена в Санкт-Петербургском государственном электротехническом университете ЛЭТИ им. В.И.Ульянова (Ленина), на кафедре систем автоматического управления...»

«Тютин Борис Викторович МЕТОДЫ АВТОМАТИЗАЦИИ РАСПРЕДЕЛЁННОГО ТЕСТИРОВАНИЯ РЕАКТИВНЫХ СИСТЕМ Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург - 2013 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Санкт-Петербургский государственный...»

«Миркаримова Бнбигуль Мирзажтевш АНАЛИЗ И ГЕОИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ ТЕРРИТОРИАЛЬНЫХ ПРОЦЕССОВ В СОСТАВЕ СИСТЕМЫ КОСМИЧЕСКОГО МОНИТОРИНГА 05.13.18 - Математическое моделирование численные методы и комплексы программ Автореферат диссертации на соискание ученой степени доктора технических наук Алматы, 2007 Работа выполнена а ДТП Институт космических исследований РГП ЦАФИ МОН РК, АО КАЗГЕОКОСМОС, ДТП Инстяпут проблем информатики управления РГП ЦФМИ МОН РК...»

«Шопырин Данил Геннадьевич Методы объектно-ориентированного проектирования и реализации программного обеспечения реактивных систем Специальность 05.13.13 – Телекоммуникационные системы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2005 2 Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики доктор технических наук, профессор Научный руководитель :...»

«Долженко Елена Николаевна АНАЛИТИЧЕСКАЯ СИСТЕМА КОМПЛЕКСНОЙ ОЦЕНКИ ЭКОЛОГИЧЕСКОЙ БЕЗОПАСНОСТИ ПРОМЫШЛЕННЫХ ПРЕДПРИЯТИЙ (на примере предприятий г. Норильска) 05.13.10 – управление в социальных и экономических системах АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Барнаул – 2007 Работа выполнена на кафедре экономики, менеджмента и организации производства ГОУ ВПО Норильский индустриальный институт Научный руководитель : кандидат технических...»

«ГОНЧАРОВ АНДРЕЙ ВИТАЛЬЕВИЧ МАТЕМАТИЧЕСКОЕ И АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННОГО ТРЕНАЖЕРНОГО КОМПЛЕКСА ДЛЯ ПОДГОТОВКИ ТЕХНОЛОГОВ ПО ТЕРМИЧЕСКОЙ ОБРАБОТКЕ СЫПУЧИХ ПРОДУКТОВ Специальность 05.13.06 –Автоматизация и управление технологическими процессами и производствами (образование) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва - 2012 Работа выполнена в ФГБОУ ВПО Московский государственный университет технологий и управления...»

«Паршков Олег Михайлович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ ПРИ РАСПРОСТРАНЕНИИ ЛАЗЕРНЫХ ИМПУЛЬСОВ В УСЛОВИЯХ ОДНОФОТОННОГО И ДВОЙНОГО РЕЗОНАНСОВ Специальности: 05.13.18 – Математическое моделирование, численные методы и комплексы программ 01.04.21 – Лазерная физика АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук Саратов 2008 2 Работа выполнена в ГОУ ВПО Саратовский государственный технический университет Научный...»

«Батурина Ольга Владимировна МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ДИНАМИЧЕСКИХ СИСТЕМ, ОПИСЫВАЕМЫХ ЛИНЕЙНЫМИ УРАВНЕНИЯМИ С УПРАВЛЯЕМЫМИ КОЭФФИЦИЕНТАМИ Специальность 05.13.01 Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт проблем...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.