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

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

ВОРОНОВ РОМАН ВЛАДИМИРОВИЧ

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

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

Диссертация выполнена на кафедре прикладной математики и кибернетики Петрозаводского государственного университета.

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

Кандидат экономических наук, доцент,

Заслуженный деятель науки РК В. А. Кузнецов

Официальные оппоненты: Доктор физико-математических наук,

профессор В. Ф. Горьковой

Кандидат технических наук И. М. Шабалина

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

Защита диссертации состоится "27"февраля 2004 года в 15 часов на заседании Диссертационного Совета Д 212.190.03 в Петрозаводском государственном университете по адресу: 185035, г. Петрозаводск, пр. Ленина, д. 33.

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

<¿1

Автореферат разослан "....."января 2004 года. Ученый секретарь диссертационного совета, ^ кандидат технических наук, доцент

В. В. Поляков

2004-4 27467

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

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

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

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

В настоящее время на всех предприятиях ЦБП уже созданы си-

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

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

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

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

Научная новизна заключается в следующем:

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

2. Построены математические модели распределения заказов между БДМ с учетом для каждого способа раскроя:

— максимального количества рулонов одного формата;

— минимальной разницы между длинами форматов;

— максимального общего количества рулонов;

— максимального количества разных форматов.

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

4. Построена математическая модель расчета объемно-календарного плана.

5. Разработаны численные методы поставленных задач оптимизации, в основе которых:

— генерация столбцов с использованием рекуррентного соотно-

шения для решения подзадач линейного раскроя;

— предварительное применение генератора столбцов, учитыва-

ющего описанные технологические ограничения;

— схема ветвей и границ, эвристики.

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

— приоритетного выполнения заказов;

— равномерного выполнения заказов.

7. Обоснованы интерактивные схемы построения плана с участием оператора.

8. Разработаны программные комплексы и базы данных, реализующие предложенные модели, методы и алгоритмы.

9. Программные системы апробированы на реальных данных и в настоящее время внедряются на производстве.

Личное участие автора. Все основные результаты работы получены лично автором.

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

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

При проектировании информационной системы была применена теория баз данных. При создании комплекса программ использованы средства программирования, такие как BorlandC+ + , C++Builder — для написания программы и InterBase — для создания базы данных.

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

Реализация работы. Автор диссертации с 2000 года участвует в разработке АСУ предприятий ЦБП: ОАО «Кондопога»и ОАО «Се-гежский ЦБК». Сотрудниками кафедры ПМиК совместно с отделами АСУ в рамках договорных работ была поставлена и решена задача распределения заказов между БДМ, реализован и внедрен в производство программный комплекс, который позволил эффективно применить математические методы в планировании производства.

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

Апробация работы: Результаты диссертационного исследования были представлены и обсуждались на Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск) в 2000,2002 гг, научно-практических конференциях ОАО «Кареллеспром», научных семинарах ПетрГУ, института прикладных математических исследований Карельского научного центра РАН и Карельского научно-исследовательский института лесопромышленного комплекса (КарНИИЛ ПК).

Программа планирования работы БДМ используется ОАО «Кон-допога».

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

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

1. Предварительное исследование и постановка задач.

2. Математические модели оптимизационных задач, связанных с планированием работы БДМ.

3. Численные методы решения рассматриваемых задач.

4. Комплекс программ, реализующих предложенные методы.

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

Структура и объем работы. Основная часть диссертационной работы состоит из введения, пяти глав и заключения. Представлен библиографический список использованной литературы и два приложения. Общий объем работы составляет 143 страниц сквозной нумерации, из них 113 страниц основного текста, включая 17 таблиц, и 2 приложения - 30 страниц. Список литературы содержит 99 наименований.

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

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

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

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

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

N — множество БДМ ЦБК;

Г — множество раскраиваемых форматов;

Р — дискретное множество стандартных плотностей бумаги;

Б — дискретное множество стандартных диаметров рулонов;

М — множество заказов.

Каждому заказу соответствуют:

^ — непустое множество допустимых форматов, подмножество Б, чаще всего состоит из одного элемента;

— непустое множество допустимых Б ДМ, подмножество ЛГ, иногда состоит из одного элемента;

— непустое множество плотностей бумаги, подмножество Р, часто состоит из одного элемента;

£)< — непустое множество диаметров рулона, подмножество /), на практике диаметр чаще всего описывается интервалом;

— минимальный объем заказа г (тонн);

— максимальный объем заказа (тонн).

Введем в рассмотрение множество каждый элемент

которого однозначно определяет набор БДМ-плотность-диаметр. Для <7 € 0 определяются:

Цд) — БДМ, соответствующая набору д, элемент N

р(д) — плотность рулона, соответствующая набору д, элемент Р;

¿(9) — диаметр рулона, соответствующий набору д, элемент Б.

В работе элементы множества 0 названы способами производства.

Множество О определим следующим образом:

<? = {?€ 0|Эг 6 М, М £ р(<7) е Р<, с1(д) в А}-

Введем обозначения: Ь '— формат (пшрина рулона бумаги), / е /' (см); ^я — длина тамбура БДМ ](4) (см);

V) — минимальный объем выработки БДМ у за период планирования (тонн);

V] — максимальный объем выработки бумаги БДМ у за период планирования (тонн).

Определим множества:

— множество заказов, для которых приемлем формат / и способ производства

FQi — множество приемлемых пар формат-способ производства для

Sq — совокупность раскроев тамбура БДМ с номером j(q) на множество форматов Fq, раскрой s G Sq определяется вектором A[Fq, s], где А/, = A[f, s] — количество рулонов длиной lf при раскрое тамбура по схеме раскроя s, множества Sq, q G Q, считаются дизъюнктными;

Sj — множества раскроев для каждой БДМ:

Введем переменные задачи:

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

— объем отгрузки выпущенной способом производства q бумаги формата заказчику

Основные соотношения модели имеют вид:

М1я = {г G М\М G Nu p(q) G Ри d{q) G Dit lf G Я};

заказа г:

FQi = {(f,q)\i G M/9};

(1)

(2)

(MeFQt

х, > 0, в € 5, уц„ > 0, г € М, / е 9 е <э. (4)

Неравенства (1) означают, что объемы отгрузки бумаги потребителям не могут превысить объемы ее выпуска. Неравенства (2) учитывают границы производительности БДМ, неравенства (3) соответствуют требованию выполнения заказов в установленном границами объеме.

Значительно сложнее задача объемно-календарного планирования (ОКП) производства бумаги. Для ее описания вводится множество смен работы комбината Т, при этом множество способов производства является подмножеством прямого произведения:

QcNxPxDxT.

Обозначим t(q) — элемент множества Т, соответствующий набору q. Появляются дополнительные обозначения:

— минимальный объем выработки БДМ ] в смену Ц

У^ — максимальный объем выработки БДМ з в смену £.

Ограничения (2) заменяются на неравенства

определяющие допустимые объемы выработки бумаги для каждой смены.

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

Пусть К — дискретное множество марок бумаги, выпускаемой комбинатом, к £ К, Для заказа г € М ставится в соответствие множество приемлемых марок продукции К^.

Каждый способ производства с индексом характеризуется:

7Гд — минимальной производительностью работы БДМ 2(я) (т/мин);

тГд — максимальной производительностью работы БДМ j(q) (т/мин);

г'дк — долей выпуска бумаги качества к при минимальной производительности БДМ ¿(з)»

r'q'k ~ Долей выпуска бумаги качества к при максимальной производительности Б ДМ j(q);

Cjt — минимальное время работы Б ДМ j(q) в смену t(q);

С"t — максимальное время работы Б ДМ j(q) в смену t(q).

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

Определяется множество заявок, для которых приемлемы формат /, способ производства q и качество к:

В качестве переменных возьмем:

т'а — время применения способа раскроя а при минимальной производительности;

т" — время применения способа раскроя в при максимальной производительности.

В таком случая ожидаемый объем производства бумаги качества к, для способа производства q & Q составит:

Введем переменные гл/9* — объемы отгрузки бумаги формата /. качества к € К, выработанной способом q Е Q для заказчика i € М. Исходной задаче соответствует линейная модель (6)—(9):

Mfqk = {i е Mfq\k е Ki).

»€S,

О 4

qZQ ,ke К,/ e Fq,

(6)

(7)

s€Sj

i e M,

(8)

(/,i)6FQi k&Ki

Г»> Т' , У^Чк > 0 s e Sq, i € M, / <E Fqt q € Q, к G K.

Пусть r = t^ + т" — время работы БДМ для выработки бумаги, разрезаемой по способу раскроя s, за которое вырабатывается х3 = п'дт'3 + тГд'т" тонн бумаги. В рамках данной модели предполагается, что при этом будет выработано xsк = r'qkir'qT's + г"ктт'д'т" тонн бумаги качества к. Таким образом, в рамках детерминированной модели (6)-(9) учитывается вероятностный характер качества бумаги.

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

X, > (10)

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

— имеющийся на складе объем запаса продукции форматом /, плотностью р, диаметром рулона d, качеством к. Введем переменные Z{Vdk

— объемы поставки продукции со склада плотностью р € Р, диаметром рулона d, качества к £ К, выполняемые для заказчика i 6 М. Пусть MfPdk множество заказов, для которых приемлем формат /, плотность р, диаметр рулона d, качество к. Тогда неравенство, соответствующее ограничению на объемы отгрузки бумаги со склада имеет вид:

^Sfpdk, / е F, ре Р, de d, к е К. (И)

Тогда общий объем продукции, поступившей заказчику г, равен:

В некоторые смены БДМ находится на ППР или простаивает по другим причинам. В эти периоды невозможен выпуск бумаги и это необходимо учитывать при планировании производства. Если в смену t € Т БДМ j простаивает, например, в связи с плановым ремонтом, то необходимо из множества Q удалить те элементы q, для которых t(q) — t. Это позволит не рассматривать в модели способы производства, относящиеся к таким сменам.

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

Обозначим Rq — максимальное количество ножей ПРС БДМ j(q). Тогда число рулонов в плане раскроя ограничено сверху величиной Rq — 1:

Y, Af» ^ R4 - 1. «е Sq, q € Q. (13)

/eF,

Предъявляемое на производстве требование ограниченить снизу разницу между длинами форматов в одной раскладке приводит к появлению неравенства:

fi,beF.:a(Ah.-Ah.) = l. (14)

где 6 — наименьшее допустимое значение (обычно 3 см).

Управление потоком продукции затруднительно, если количество различных форматов превышает определенное число (3-5). Пусть Т — максимальное количество различных форматов в одном раскрое. Для учета этого ограничения в модель необходимо добавить неравенство:

]Г <г{А/а) < ï, s£Sq,qeQ. (15)

/6F,

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

Л/, < aî/, fe F„ seS. (16)

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

• Минимизация отходов сырья в виде обрезной кромки.

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

где д — индекс множества 5,, для которого в € 5,. Критерий оптимальности в этом случав — минимум целевой функции:

г(х) = с„х, —> пап. (17)

«65

• Минимизация объемов перевыпуска продукции. Критерий оптимальности — минимум функции

*(») = ]С И"«/ ~чктЬ' (18)

í6Q^€F

где ич} — дополнительные переменные ограничений (1):

53 = УИч + «»/. 9 € С?, / е (19)

»65, 4 «6М/,

• Минимизация объемов срезаемой с рулона бумаги для получения нужного диаметра.

Пусть тт.-/, — доля среза рулона диаметра с?(д) формата / до ближайшего подходящего диаметра заказа i. Критерий оптимальности — минимум целевой функции:

2(У) = 2 £ X 7rifяУifч —> т1п- (20)

• Минимизация объема выпуска редко востребованных форматов.

Пусть V» — дополнительные переменные ограничений (3):

+ = В{, г е М,

о <vi<Bi-bг, ¡ем.

Тогда критерий оптимальности — максимум целевой функции: г(ь) = ^ Vi —► шах, (21)

где М' С М — множество, соответствующее редко востребованным форматам.

• Максимизация объема выполненного в срок производственного задания.

Пусть и^ — искусственные переменные ограничений (3): (/,</)€*•(?,

Тогда критерий оптимальности — минимум целевой функции:

г(ю) = ^ ю* —► т1п. (22)

«6 м

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

В этом случае необходимо минимизировать функцию

<У) = Ц £ Ц ¡С

»60/6^, к€К> ¿6М/,ц

П11П,

(23)

где К' С К — подмножество марок пониженного качества бумаги.

Минимизация числа применяемых раскроев. Критерий оптимальности — минимум целевой функции:

г(х) = —► шш.

«€5

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

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

Рассматриваемые методы являются основой алгоритмов решения задач объемного и объемно-календарного планирования распределения заказов между БДМ.

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

1. Решение задачи (1)-(3) с любой из описанных целевых функций (17)-(24) затруднено из-за огромного числа вариантов раскроев тамбура. Мощность множеств 5? исчисляется десятками и сотнями миллионов единиц.

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

г* = £ с/А/ —> тах, /ег

(25)

(26)

/ег

о < Л/ < (if, feF, (28)

Х>/<Дд> (29)

/6F

Л/ > 0, целые, (30)

где:

с/ — стоимость рулона вида /, / G F, определяется через значения двойственных переменных задачи;

Ад — максимально возможная длина остатка бумажного полотна;

А, — число рулонов вида /, неизвестные задачи, / G F.

Для решения задачи (25)-(30) методом динамического программирования введем в рассмотрение функцию:

!к к к \

CtX, = ^ г f » (31)

t=l 1=1 1=1 J

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

Теорема 1 Значения функции <p(y,k,z) связаны между собой рекуррентным соотношением:

, „ . Г если Ч- < min(d,z), целое

^ —оо, иначе,

V(y,k,z) = max {c*s + <р{у - Д, А: - 1,z - ä) | (32)

0 < i < min(d, [z/h\)}. В качестве решения задачи интересует

min ^(y.lFl.ß,), y=L„~Aq L,

где |F| — число элементов множества F. Оптимальное решение этой задачи (26)—(30) представляет собой раскрой с наибольшей оценкой переменных х,, для улучшения текущего базисного плана.

Теорема 2 Если для всех решения г* задач (25)-(30) выполнено соотношение

то текущее базисное решение задачи (1)-(4) оптимально.

2. Опишем другой подход к решению задачи распределения заказов между БДМ. Процесс состоит из двух этапов. На первом этапе генерируются все возможные варианты раскроя бумажного полотна, удовлетворяющие требуемым ограничениям (13)—(16). Полученные в результате генерации столбцы, соответствующие способам раскроя, составят матрицу ограничений неравенств (1). Второй этап состоит из решения задачи линейного программирования.

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

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

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

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

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

Пусть множество заказов М разбито на ц непересекающихся непустых подмножеств:

Будем считать, что заказ i имеет срочность к, если г 6 М*. Введем обозначения:

М'к = U Mi,

Sk = {s е S|fc = min{ I |г е Mt, Ats > 0}}.

Потребуем, чтобы время выполнения заказов срочности 1 было наименьшим, а также для каждого к = был минимальным промежуток времени между моментами завершения выполнения заказов множеств и М'к. Допускается совместная выработка бумаги для заказов разной срочности. Показано, что для решения поставленной

задачи необходимо искать лексикографический минимум:

екх' —у min>

где

е* = (0....0,1,0, ...,0). к

Для учета нижних границ (10) применяется алгоритм, основанный на ветвлении задачи.

Пусть — задача поиска оптимального плана БДМ на допустимом множестве раскроев S', xf — решение этой задачи. Шаги алгоритма:

Шаг О. So = S, к = 0.

Шаг 1. Присвоим S* = Sk-

Если допустимое множество задачи ö[S*] пусто, то при к = 0 исходная задача (1)-(3) не имеет решения, завершение алгоритма; при к > 0 переход на Шаг 4.

Иначе — переход на Шаг 2.

Шаг 2. Если выполнены условия:

1) V« € 5* х?» > 0 => >

2) *(*?')<«.

то задача (17), (1)—(3) решена. Иначе - переход на Шаг 3.

Шаг 3: Обозначим 5 = {а£*|а:?* < Р, з € Я* П Если 5 = 0, то переход на Шаг 4. Иначе, пусть в' = аг§тт{х,|в € 5}

5а = 5ЛК), 5*+1 = {"'}, к = к + 1

переход на Шаг 1. Шаг 4. к = к — 1, переход на Шаг 3.

Показана сходимость описанного алгоритма. Параметр определяется пользователем эмпирически. Предложено решение задачи составления плана работы БДМ с минимальным количеством раскладок методом подбора значения параметра

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

— планирования сбыта продукции (по номенклатуре, объемам, а в

дальнейшем, по срокам работы);

— планирования производства на уровне распределения заказов меж-

ду БДМ, выбора способа раскроя (раскладки), плотности и, возможно, скорости работы машины;

— управления запасами (прогнозирование поступления и отгрузки

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

— учета качества продукции.

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

невостребованной бумаги.

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

В приложении 1 содержится акт о внедрении комплекса программ объемного планирования выпуска бумаги на ОАО «Кондопога».

В приложении 2 помещены тексты программ.

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

1. Лазарев А. В., Воронов Р. В. О некоторых свойствах решения задачи определения графика проведения ППР СТО // Труды Петрозаводского государственного университета. Сер. «Прикладная математика и информатика». Вып. 7. Петрозаводск: Изд-во ПетрГУ, 1998. С.155-170.

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

3. Кузнецов В. А., Воронов Р., В. Задача оптимального планирования бумажного производства // Труды Петрозаводского государственного университета. Сер. «Прикладная математика и информатика». Вып. 7. Петрозаводск: Изд-во ПетрГУ, 1998. С. 179-188.

4. Кузнецов В. А., Воронов Р. В. Задача определения планов раскроя и распределения заявок с учетом режимов работы группы БДМ // в книге «Задачи раскроя в целлюлозно-бумажной промышленности». СПб: СпбЛТА, 2000, С. 83-96.

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

ЛР ИД №02969 от 06.10.2000 Гигиенический сертификат №10КЦ.34.953.П.00136.03.99 от 05.03.99 г. Подписано в печать 20.11.2004. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. 1,3 уч.-изд.л. 7 усл.кр.-отт. Тираж 100 экз. Изд. №8.

Петрозаводский государственный университет Типография Издательства Петрозаводского государственного университета 185640, Петрозаводск, пр. Ленина, 33

РНБ Русский фонд

2004-4 27467

Введение.

Глава 1. Описание объекта исследования

1.1 Краткие сведения о технологии бумажного производства

1.2 Особенности планирования производства бумаги.

1.3 Проблемы автоматизации бумажного производства

Глава 2. Постановка и исследование задачи планирования загрузки БДМ

2.1 Терминология и основные обозначения

2.2 Математические модели объемного и объемно-календарного плана

2.3 Некоторые дополнительные ограничения задачи.

2.4 Целевые функции

Глава 3. Методы решения задач планирования

3.1 Задачи линейного и плоского раскроя и методы их решения

3.2 Линейная оптимизация и метод генерации столбцов

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

3.4 Использование декомпозиции при решении задачи объемного планирования

3.5 Локальная оптимизация, ослабление задачи

Глава 4. Алгоритмы решения задач объемного и объемнокалендарного планирования

4.1 Использование метода генерации столбцов.

4.2 Универсальный генератор планов раскроев.

4.3 Методы сокращения объема вычислений при решении задач

4.4 Методы решения задач объемно-календарного планирования с дополнительными ограничениями.

Глава 5. Техническая реализация алгоритмов и программ

5.1 Программные средства реализации.

5.2 Описание базы данных.

5.3 Описание функций программного комплекса.

Объектом диссертационного исследования служит задача согласования планирования производства и сбыта бумаги или картона крупного предприятия целлюлозно-бумажной промышленности (ЦБП). Эта задача изучалась сотрудниками кафедры прикладной математики и кибернетики (ПМиК) Петрозаводского государственного университета (ПетрГУ) с участием автора диссертации в рамках договора с целлюлозно-бумажным комбинатом (ЦБК) ОАО «Кондопога» на разработку автоматизированной системы распределения заказов на выпуск бумаги между бумагоделательными машинами (БДМ).

В основе разработанной системы оптимизационная модель задачи планирования работы группы БДМ с учетом основных технологических особенностей ЦБК.

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

Актуальность темы

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

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

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

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

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

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

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

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

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

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

• постановка задач расчета оптимального объемного и объемно-календарного планов работы БДМ;

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

• написание комплекса программ, реализующих предложенные алгоритмы, их тестирование и внедрение.

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

Основу рассматриваемой разработки составляет хорошо изученная многими авторами задача раскроя тамбура бумажного полотна [8]. Решение этой задачи средствами динамического программирования не представляет принципиальных или вычислительных трудностей. Однако, в вариантах, представленных в [8], [47], [65], [78] не учитывается множество технологических особенностей процесса производства и сбыта бумаги. Начиная от стандартной учебной задачи линейного раскроя [39], задача постепенно усложнялась, включая такие факторы, как выбор плотности, производительность и ожидаемое качество продукции Б ДМ в различных режимах работы. В итоге получена математическая модель задачи, которая связывает работу отдела сбыта, отслеживающего выполнение заказов, и производственного отдела предприятия ЦБП, обеспечивающего выработку необходимой продукции. При этом решается основной вопрос — загрузка оборудования и распределение работ между различными БДМ с учетом плотности, марки и качества продукции, объемов выработки и планов раскроя. Основная особенность данной работы — комплексный учет широкого ряда факторов, связанных с организацией производства бумаги: выбора БДМ, распределение заказов между различными машинами, их специализация по плотности и пр. Планирование осуществляется в условиях стохастического характера качества продукции. Увязка перечисленных факторов является важнейшей целью разработки.

Сложность задачи распределения заказов между БДМ с учетом их спецификаций, производственных возможностей оборудования размеров, тамбура и возможных планов раскроя обусловлена ее комбинаторными особенностями: планирование выработки десятка форматов на 3-4 машинах допускает тысячи вариантов планов раскроя и еще больше — их комбинаций, дающих нужные объемы продукции.

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

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

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

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

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

При проектировании информационной системы была применена теория баз данных. При создании комплекса программ использованы средства программирования, такие как BorlandC+-Ь, C++Builder — для написания программы и InterBase — для создания базы данных.

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

Научная новизна заключается в следующем:

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

2. построены математические модели распределения заказов между БДМ с учетом ограничений для каждого способа раскроя: максимального числа вхождений каждого формата; минимальной разницы между длинами форматов; общего числа форматов; максимального числа разных форматов; максимального числа форматов одного вида;

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

4. построена математическая модель расчета объемно-календарного плана;

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

6. применены методы сокращения объема вычислений, позволяющие эффективно решать рассматриваемые задачи большой размерности;

7. предложено четыре новых метода определения порядка выполнения заказов: два метода приоритетного выполнения заказов; два метода равномерного выполнения заказов;

8. предложены два метода интерактивного построения плана с участием оператора;

9. разработаны программные комплексы и базы данных, реализующие предложенные модели, методы и алгоритмы;

10. программные системы апробированы на реальных данных и в настоящее время внедряются на производстве.

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

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

Реализация результатов работы

Автор диссертации с 2000 года участвует в разработке АСУ предприятий ЦБП: ОАО «Кондопога» и ОАО «Сегежский ЦБК». Сотрудниками кафедры ПМиК совместно с отделами АСУ в рамках договорных работ была поставлена и решена задачи распределения заказов между БДМ, реализован и внедрен в производство программный комплекс, который позволил эффективно применить математические методы в управлении производством.

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

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

Результаты диссертационного исследования были представлены и обсуждались на Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (г.Петрозаводск) в 2000, 2002 гг, научно-практических конференциях ОАО «Кареллес-пром», научных семинарах ПетрГУ, института прикладных математических исследований Карельского научного центра РАН и Карельского научно-исследовательский института лесопромышленного комплекса (КарНИИЛПК).

Программа планирования работы БДМ используется на ОАО «Кондопога».

Публикации

Результаты диссертации опубликованы в 5 печатных работах.

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

1. предварительное исследование и постановка задач;

2. математические модели оптимизационных задач, связанных с планированием работы БДМ;

3. численные методы решения рассматриваемых задач;

4. комплекс программ, реализующих предложенные методы;

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

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

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

Выводы

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

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

2. планирования производства на уровне распределения заказов между БДМ, выбора способа раскроя, плотности и, возможно, скорости работы машины;

3. управления запасами (прогнозирование поступления и отгрузки продукции различных форматов, плотностей и марок);

4. учета качества продукции.

Заключение

При моделировании распределения заказов между БДМ были получены следующие результаты:

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

2. В рамках математических моделей распределения заказов между БДМ учтен ряд технологических особенностей.

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

4. Проведено исследование рассмотренных оптимизационных задач.

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

6. Предложены методы определения порядка выполнения заказов.

7. Предложены методы интерактивного построения плана с участием оператора.

8. Разработаны программные комплексы и базы данных, реализующие предложенные модели, методы и алгоритмы.

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

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

2. Разработка программы согласованного планирования планово-профилактических ремонтов и графика работы комплекса БДМ.

1. Авербах И. Л. Оптимизация в блочных задачах с целочисленными переменными/ Авербах И. JL, Цурков В. И. — М.: Наука: Физмат-лит, 1995.101. П 12

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

3. Акулич И. JI. Математическое программирование в примерах и задачах: Учеб.пособие для студентов экон.спец.вузов. -2.изд.,испр.и доп. — М.: Высш.шк., 1993.

4. Асанов М. О. Дискретная оптимизация: Учеб. пособие. — Екатеринбург, 1998.

5. Асанов М. О. Методы дискретной оптимизации: Учеб. пособие. — Екатеринбург, 1992.

6. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы, М.: Вильяме. 2003.

7. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

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

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

10. Белоусов А. И. Лекции по дискретной математике: Учеб.пособие/ Белоусов А. И., Мартынов Б. В., Щетинин А. Н.; Под ред. А. И. Бе-лоусова. — М.: Изд-во МГТУ им.Н.Э.Баумана, 1994.

11. Берж К. Теория графов и её применение. М.: Издательство иностранной литературы, 1962.

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

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

14. Вероятностные методы дискретной математики: Тр. третьей Пет-розав. конф.,12-15 мая 1992 г.,Петрозаводск,Россия/ Под ред.

15. B. Ф. Колчина и др. М.: "ТВП"; Утрехт: "VSP", 1993.

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

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

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

19. Вотяков А. А. Математические основы "административно-командного метода": Алгоритмы решения массовых задач линейного программирования. -М., 1994.

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

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

22. Геворкян Г. А. Механические модели и алгоритмы решения задач математического программирования: Диссертация на соискание ученой степени д-ра физ.-мат.наук в форме науч.докл.: 01.02.04:05.13.16. — Ереван, 1994.

23. Гермогенова Т. А. Диффузионный предел некоторых разностных схем метода дискретных ординат. — М., 1994.

24. Гимади 3. X. Дискретные экстремальные задачи принятия решений: Учеб. пособие. — Новосибирск, 1991.

25. Гольдштейн А. Л. Исследование операции: многокритериальные задачи: Конспект лекций. — Пермь, 1995.

26. Громова Н. Б. Методы исследования операций в моделировании организационно-экономических задач: Учеб.пособие для студентов инж.спец.целевой интенсивной подготовки специалистов в вузах/ Громова Н. Б., Минько Э. В., Прохоров В. И. — М.: Изд-во МАИ, 1992.

27. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

28. Данзангийн Ганхуяг Некоторые специальные задачи математического программирования и их редукция к выпукло-вогнутым и частично целочисленным задачам: Автореферат диссертации на соискание ученой степени канд. физ.-мат.наук: 05.13.16. — Иркутск, 1995.

29. Дискретная математика и математические вопросы кибернетики// Под редакцией Яблонского С. В. и Лупанова О. Б., М.: Наука, 1974.

30. Дискретные системы и их программное обеспечение: Межвуз. сб./ Под ред. М. К. Чиркова, С. П. Маслова. — Л.: Изд-во ЛГУ, 1990.

31. Дискретный анализ: Сб.ст./ Отв.ред.А.Д.Коршунов. — Новосибирск, 1994.

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

33. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985.

34. Емиличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.

35. Ершов А. П. Введение в теоретическое программирование. М.: Наука, 1977.

36. Исследование операций и математическое программирование. — Кишинев, 1992.

37. Исследование операций и статистическое моделирование/ Санкт-Петербург.гос.ун-т; Под ред. И. В. Романовского Вып. 6. 1994.

38. Исследование операций (модели, системы, решения): Сб./ Рос.АН,ВЦ; Отв.ред. Ю. П. Иванилов. — М., 1994.

39. Канторович JI. В., Залгаллер В. А. Рациональный раскрой промышленных материалов. — Новосибирск: Наука , 1972.

40. Карманов В. Г. Математическое программирование. — М.: Физмат-лит, 2001.

41. Коган Д. И. Дискретные многокритериальные задачи распределительного типа: Учеб. пособие/ Коган Д.И. — Н.-Новгород, 1991.

42. Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании: Автореферат диссертации на соискание ученой степени д-ра физ.-мат. наук: 01.01.09. — Иркутск, 1995.

43. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности/ Хачатуров В.Р., Веселовский В.Е., Злотов А.В. и др. — М.: Наука, 2000.

44. Комбинаторные модели и методы: Сб. ст./ Рос. АН. ВЦ; Отв. ред. Н.А.Соколов. М.: ВЦ РАН, 1995.

45. Комбинаторные модели и методы/ Рос.АН, ВЦ Вып. 2. 1997.

46. Кнут Д. Искусство программирования для ЭВМ, т.1-3, М.: Мир1977.

47. Коржов С. Т. Математическое моделирование и программное обеспечение оптимального технологического функционирования системы бумагоделательных машин : Автореферат диссертации на соискание ученой степени канд.техн.наук: 05.13.16. — Петрозаводск, 1996.

48. Красовская М. А. Методы и алгоритмы нелинейного программирования в АСУ: Учеб.пособие. — М.: Изд-во МАИ, 1994.

49. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978.

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

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

52. Кузнецов В. А., Воронов Р. В. Задача оптимального планирования бумажного производства j j Труды Петрозаводского государственного университета. Сер. "Прикладная математика и информатика". Вып. 7. Петрозаводск: Изд-во ПетрГУ, 1998., С. 179-188.

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

54. Кузнецов В. А., Воронов Р. В. Задачи раскроя в целлюлозно-бумажной промышленности // Задача определения планов раскроя и распределения заявок с учетом режимов работы группы БДМ. СПб: СпбЛТА, 2000, С. 83-96.

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

56. Кук В., Вейз Г. Компьютерная математика. М.: Наука, 1990.

57. Лавров С. С., Гончарова Л. И. Автоматическая обработка данных, хранение информации в памяти ЭВМ. М.: Наука, 1971.

58. Лаврушин В. И. Методы и алгоритмы решения некоторых задач дискретной математики: Автореферат диссертации на соискание ученой степени канд.физ-мат. наук: 01.01.09. — Саратов, 1993.

59. Лебедева Л. А. Модели целочисленного программирования: Учеб.пособие. — Норильск, 1994.

60. Летова Т. А. Задачи линейного и целочисленного программирования: Учеб.пособие — М.: Изд-во МАИ, 1996.

61. Линейное программирование: Учеб.-метод.пособие/ Афанасьев М. Ю., Оревков Ю. П., Павлова Л. С. и др; Под ред. Ю. Н. Черемных. — М.: Изд-во Моск. ун-та, 1992.

62. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

63. Лэсдон Л. С. Оптимизация больших систем. М.: Изд-во Наука, 1975.

64. Малиновский Ю. Г. Элементы математического программирования: Учеб.пособие. — Челябинск: Изд-во ЧГТУ, 1995.

65. Математические методы исследования операций в примерах и задачах: Учеб.пособие для студентов всех спец./ Карандаев И. С., Ма-лыхин В. И., Гатауллин Т. М. и др. — М., 1993.

66. Меламед И. И. Бикритериальные задачи дискретного программирования с MINSUM-MAXSUM критериями. — М.: ВЦ РАН, 2000.

67. Меламед И. И. Некоторые задачи дискретного программирования с двумя и тремя критериями —М.: ВЦ РАН, 1998.

68. Методы комбинаторной оптимизации: Сб./ Рос.АН, ВЦ; Отв.ред. Н. А. Соколов. М.: ВЦ РАН, 1997.

69. Методы решения задач нелинейного и дискретного программирования: Сб. науч. тр./ АН УССР, Ин-т кибернетики им. В. М. Глушкова, Науч. совет АН УССР по пробл. "Кибернетика"; Редкол.: В. С. Ми-халевич (отв. ред.) и др. -Киев, 1991.

70. Миронова И. В. Языковые и программные средства постановки задач в системах линейного программирования: Автореферат диссертации на соискание ученой степени канд.физ.-мат.наук:05.13.11. — М., 1992.

71. Моргунов И. Б. Основы дискретной оптимизации некоторых задач упорядочения: На прим.учеб.процесса. — М., 1994.

72. Морз Ф. М.} Кимбелл Д. Е. Методы исследования операций. М.: Изд-во Наука, 1956.

73. Нефедов В. Н. Дискретные задачи оптимизации: Учеб. пособие. — М.: Изд-во МАИ, 1993.

74. Нуриев Р. М. Дискретная математика Ч. 1. 1994.

75. Ope О. Теория графов.//М.: Изд-во Мир, 1968. 368 с.

76. Петрунин С. В. Исследование операций Ч. 1: Методы оптимизации. 1994.

77. Пярнпуу А. А. Вопросы алгоритмизации в некоторых прикладных задачах/ Пярнпуу А. А., Хохлюк В. И. — М., 1994.

78. Рогов А. А., Чернецкий В. И. Об одном методе расчета оптимального графика планово-профилактических работ (ППР) бумагоделательных машин ЦБК // Математическое моделирование народнохозяйственных процессов: Межвузовский сборник./ Петрозаводск, 1990.

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

80. Романовский И. В. Дискретный анализ. СПб: Невский диалект, 1999.

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

82. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.

83. Системное программирование и модели исследования операций: Сб.тр. Фак.вычислит.математики и кибернетики МГУ/ Под ред. JI. Н. Королева, П. С. Краснощекова. — М.: Изд-во Моск.ун-та, 1993.

84. Станевичюс А.-И. А. Барьерно-ньютоновские методы решения задач линейного программирования с двусторонними ограничениями/ Станевичюс А.-И. А., Щербак J1. В. — М.: ВЦ РАН, 1994.

85. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. — М.: Изд-во Наука, 1986.

86. Тимофеев Е. К. Целочисленное программирование: Учеб.пособие для студентов экон.спец./ Тимофеев Е. К., Бессарабов Н. И. — Новочеркасск, 1994.

87. Уздемир А. П. Динамические целостные задачи оптимизации в экономике. — М.: Издат.фирма "Физ.-мат.лит.", 1995.

88. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

89. Унгуряну М. М. Автоматизация процессов повышения эффективности программирования на основе методов дискретной многокритериальной оптимизации: Автореферат диссертации на соискание ученой степени канд.физ.-мат.наук: 01.01.11. — Н.Новгород, 1992.

90. Харари Ф. Теория графов. М.: Мир, 1973.

91. Хахулин Г. Ф. Постановки и методы решения задач дискретного программирования: Учеб. пособие. — М.: Изд-во МАИ, 1992.

92. Цурков В. И. Декомпозиция в динамических задачах с перекрестными связями Ч. 1, 2. -1994.

93. Чернецкий В. И. Математическое моделирование стохастических систем. — Петрозаводск, 1994.

94. Чирков А. Ю. О выделении полиномиальных подклассов в задаче целочисленного линейного программирования: Автореферат диссертации на соискание ученой степени канд.физ.-мат.наук: 05.13.17. — Н. Новгород, 1993.

95. Шевченко В. Н. Качественные вопросы целочисленного программирования. — М.: Наука, 1995.

96. Ширяев В. И. Исследование операций и численные методы оптимизации: Учеб. пособие. — Челябинск: Изд-во ЧГТУ, 1993.

97. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.1. СПРАВКАоб использовании результатов диссертационных исследований Воронова Р. В.