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

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

РУБИНА ТАТЬЯНА БОРИСОВНА ' °

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ РАСКРОЙНО-ЗАГОТОВИТЕЛЬНОГО ПРОИЗВОДСТВА ПУТЕМ ОПТИМИЗАЦИИ РАСКРОЯ ДЛИННОМЕРНЫХ МАТЕРИАЛОВ

Специальность 05.13.07 - "Автоматизация технологических

процессов и производств (промышленность)"

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

Москва 2000

Работа выполнена а Московском Государственном Технологическом Университе «Станкии»

Научный руководитель: Научный консультант : Официальные оппоненты :

Ведущее предприятие :

член-корреспондент РАН Соломенцев Ю.М. доктор технических наук, профессор Горшков А.Ф. доктор технических наук, профессор, Слепцов В В. кандидат технических наук, доцент Кнауер И.Б. ЦНИТИ

Защита состоится июня 2000 года в_часов _минут на заседании

Диссертационного Совета К 063.42.04 при Московском Государственном Технологическом Университете "Станкии" по адресу: 101472, ГСП, Москва, К-55, Вадковский пер., д.3а.

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

С диссертацией можно ознакомиться в библиотеке МГТУ "Станкии"

Автореферат разослан О мая 2000 г.

ап I

Диссертационного Совета К 063.42.04

к.т.н. / Тарарин И М.

с- ну

кбьз-бн^о

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

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

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

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

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

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

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

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

• исследование применимости метода замещений (метода Горшкова) для решения задачи оптимального раскроя длинномерных материалов;

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

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

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

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

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

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

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

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

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

Практическая ценность:

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

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

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

Методы исследования: теория графов, численные методы, методы системного анализа и исследования операций, теория оптимизации.

Реализация работы: Научные результаты исследований были использованы

при выполнении работ по повышению эффективности работы заготовительного участка на московской фирме "Чудо-Окна", специализирующейся на изготовлении пластиковых окон. В результате внедрения алгоритма оптимального раскроя на производстве удалось повысить-коэффициент использования длинномерных материалов до 97%, что на 10-12% больше по сравнению с периодом до внедрения программы оптимизации.

Апробация работы. Результаты работы докладывались на заседании кафедры "Информационных технологий и вычислительных систем" МГТУ "Станкин", а также на следующих конференциях:

• IX Международная конференция-выставка "Информационные технологии в образовании" (Москва, 9-12 ноября, 1999 г.)

• Научно-техническая конференция "Метрологическое обеспечение эксплуатации и хранения технических объектов" (Москва, 8-9 декабря, 1999 г.)

• VII Международная конференция "Математика, компьютер, образование" (Дубна, 24-29 января, 2000 г.);

• II Всероссийская научно-техническая конференция "Компьютерные технологии в науке, проектировании и производстве" (Нижний Новгород, 3-4 февраля 2000 г.).

Публикации. По материалам диссертации опубликовано 5 работ. Структура и объем работы. Диссертация состоит из введения, 4 глав,

заключения, списка литературы ( _ наименований). Работа изложена на _

страницах машинописного текста, содержит _ рисунков, _ таблиц и _

приложений.

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

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

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

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

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

Изучением многих аспектов рационального раскроя, включая создание алгоритмического и программного обеспечения и методики внедрения, занимаются в различных научных и производственных учреждениях нашей страны, а также за рубежом. Это отражено в работах Ji.B. Канторовича, В.А. Залгаллера, Э.А. Мухачевой, Б.И. Тихомирова, В.Ф. Бабаева, A.C. Мухачевой, A.A. Петунина, А.Г. Тарновского, В.А.Габитова, Н.И. Соломещ и др.

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

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

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

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

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

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

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

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

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

• высокая скорость сходимости:

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

• использует векторы топологии в качестве ограничений.

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

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

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

Использование персональных компьютеров со стандартной операционной системой (Win 9х, Win NT) и дружеского интерфейса пользователя (стандарт Microsoft) на всех участках, в том числе на отрезном станке и сортировочном устройстве управления, -основа полной компьютеризации раскройно-заготовительного производства.

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

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

п

Тсjmax, . (i)

где Qj - коэффициенты, соответствующие заданным длинам раскроя, Xj"

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

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

HcjXj^Lj, (2)

м

где J^j - коэффициенты, соответствующе длинам раскраиваемого материала.

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

п

ILaijXj^bi.t'i.z.....«. О)

м

Xj^Z О J -2,.... п,

где ¡2у - элементы матрицы коэффициентов, п - число допущенных к рассмотрению

раскроев, т - количество ограничений.

Существует множество методов решения задачи (1) при ограничениях (2-3),

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

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

отслеживающие текущее состояние упомянутых параметров. Это дает возможность:

• более точно выбирать дальнейшее направление вычислительного процесса;

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

• сокращать объемы вычислительных затрат при использовании вычислительной техники.

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

которого можно разбить на два непересекающихся множества ]/ — ^ У 2,'

Метод замещений - это точный метод решения задач на графах, использующий

Алгоритмы, построенные на базе метода замещений, имеют процедуры,

Двудольным называется граф

множество вершин

причем каждое ребро имеет вид

где

V, е ^, у2 е р.

Пусть

двудольный граф, содержащий множество

Эффективный кортеж пар замещений - это множество пар замещений, позволяющее из множества ребер Е выделить подмножество ребер Е' С1 Е ,

образующее искомый подграф , Е' )> удовлетворяющее заданным

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

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

Пусть задан двудольный граф , У2 , ]? содержащий счетное

множество ребер Е , разделенное на два подмножества ^ <И ^ , - /¡и ^ \ ^ а , каждое из которых не содержит подмножество Е' , удовлетворяющее заданным векторам топологии. Однако, подмножество Е' содержится в множестве Е и его элементы Е Е' распределены между

подмножествами Е° и Е \ Е°> Т0[Ла "а множествах Е° и Е \ Е° существует, по крайней мере, один эффективный кортеж пар замещений.

Изложенный принцип связывает существование эффективного кортежа пар

замещений с наличием подмножества ребер Е' ^ Е в двудольном графе при

Е' <£Е°»Е' Е°)-

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

I. На основе ограничений (2-3) формируются векторы топологии: вектор закрепленных

степеней {Щ ~ (¿^ ^п) первой доли графа, которая моделирует допустимые

длины раскроя и векторы допустимых степеней

Аттх = (Л1>А2>-~>Ап)'Апш. = (а1>а2>->ап) Д™ вт°р°й доли П5афа,

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

II. Формируется список ребер J? двудольного графа С (j^i ■> Vi i Е ]>

взвешенных по произведениям (1) и упорядоченных по убыванию их весов. Множеств ребер J? разделяется на два подмножества: первое подмножество содержащее

ребра максимального веса и второе подмножество]? \ ¡jf, содержащее ребра минимального веса.

III. Формируется дерево замещений (ДЗ) путем построения допустимых кортежей пар замещений с учетом условий (2-3) и векторов топологии. Конструирование подграфа в каждом узле дерева выполняется путем замещения одного из ребер первого

подмножества на одно из ребер второго подмножества, т.е. ребра gk £ являются

кандидатами на удаление, а ребра gk 6 \ Jjf - кандидаты на добавление в ДЗ.

При этом ребро, замещенное в узле-предке, не может стать замещающим в узлах-потомках, а заместившее ребро в узле-предке не должно замещаться в узлах-потомках.

IV. Среди допустимых кортежей пар замещений отыскивается эффективный кортеж,

доставляющий оптимум искомому подграфу G ^^^V^E' j по (1) и (2-3).

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

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

Ak = Ik*Jk'

где J к - множество ребер J к G подграфа (jk , инцидентных вершине со степенью большей или равной степени одной из вершин той же доли искомого подграфа, Jк -

множество ребер Jк G ]? \ подграфа (jk , со степенью меньшей или равной степени одной из вершин той же доли искомого подграфа;

Атт = (О, О, О, 0, 0), Атах = (2, 3, 2, 1,1), £ = (1, 1, 1, 1, 1)

О

Условие Х]

0 1 2 3 4

(5) + +

(6) + +

С) + + +

(В) + +

№ Ребро Вес (длина)

1 3-4 280

2 2-2 270

3 1-1 220

4 3-3 210

5 3-2 140

6 2-1 135

7 4-1 48

8 4-0 0

9 1-0 0

Оптимальное решение:х1=0, х2=2, хЗ=4, х4=1, К=598 598! 350

Рис . 1 Пример решения задачи раскроя методом замещений

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

В третьей главе рассматриваются методы построения комплексной модели раскроя и применения ее для повышения эффективности раскройно-заготовительного производства.

Деятельность производственного предприятия может быть отражена различными типами потоков. Для описания производственной системы заготовительного участка целесообразно выделить материальные и информационные потоки. Тогда производственный процесс можно представить как совокупность материальных и информационных потоков. Схема прохождения потоков по участкам цеха показана на схеме (рис. 2).

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

Раскрой на станке происходите динамическом режиме:

• Измеряется длинномерный профиль, поступающий на станок в данное время

• Информация о его длине поступает на компьютер станка

• Производится обсчет оптимального расположения заготовок на профиле

• Раскрой заготовок на станке

• Отправка информации о произведенном раскрое на центральный компьютер

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

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

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

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

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

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

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

На следующий участок

Сортировочное устройство

Информационные потоки Материальные потоки

Рис.2. Схема информационных и материальных потоков.

Имеется набор длин такие, что /■ С / и Ь, такие что Ь{ с1, при этом

р

1-1 < ¿у. Необходимо установить такое соответствие между 1кЬ, что Бк — ^ \ ,

/=1

- допуск И J"[ Sj. =0,/, €/и5 = и^ =0 (1) к

Задача считается решенной, когда 1 = 0, а V/;- £ 5" и при этом

удовлетворяет условию (1).

LjZSk<Lj-ö (2)

Т.о. для решения задачи требуется набор Sk , такой, что условие (2) выполняет Если же таких Sk - нет, то выбираем такое Sk , что Lj < Sk < Lj — 8 — CLk , где CLk = min возможное решение. Математическая реализация.

Сортировка /(-, где /j > 1г > ••■ >ln,Lj • произвольное, по условию Lj => /(

/=1 (=1

/>

Если а) 2// >Ь]~8 и = Ашп =>Р = Р + 1

/=1

ъ, £/, Т>Ц-8*Ь,-8- < = 1

1=1

Если р = п - оптимальный вариант, Iр - исключается из этой .¡-ой выборки, и печатаются

все /у = / и р + 1 - элемент становится р-ым и снова переходим к условию (а). При этом если р = п =>

с) > ■ = 8

- оптимальный вариант (3) "У > Ь^ — - не может быть.

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

1)

2) ¿у-5</(

V

3) I/, > Ц

1.

желаемое решение

2) ЬI — § < ^ - при этом ^ ^ = ШаХ - возможное решение

3) ^^ > Ху - нежелательно

В случае, когда ^^ /( > //. — а) 1 = п - это единственно возможное решение б)Ып, но !3, что ^+/,. <1у , т.е. < ¡к , где выбирается I

оставшихся длин.

у

в) ¡#п и 3 1к .такое что — > р = р+ 1, > LJ

1=1

г) р = р-1 элемент I п - исключается из выборки j, и I ^ становится I п -ым элементом.

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

р-1

Если р = п, то ' - есть решение для выборки j. ;=1

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

На производственной фирме по производству окон из ПВХ и алюминия внедрена и дейсвует подсистема оптимизации раскроя длинномерных профилей, интегрированная в автоматизированную информационную систему предприятия, которая включает в себя подсистемы управления, конструкторкско-технологической подготовки производства и контроля (рис.3). Программа реализована под стандартные операционные системы семейства Windows на языке С++ (с использованием пакета Visual Studio 6.0). Система организована по принципу клиент-сервер. К системе подключаются 10-15 пользователей одновременно, теоретически система позволяет работать одновременно до 100 пользователей. Создание блока раскроя и его'объединение с другими модулями является частью работы по созданию глобальной системы управления производством по схеме ОФИС-ЦЕХ-СКЛАД-ОФИС.

Передача данных между филиалами может осуществляться 2 способами:

• по удаленному доступу через коммутируемую телефонную линию, когда 2 домена ОФИС и СКЛАД объединены между собой в сеть посредством модема.

• т.к. связь не всегда бывает качественной предусмотрен второй вариант - с использованием Internet-технологии по электронной почте.

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

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

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

Накопитель

Клиент 3

Клиент N

Рис.3 Информационные связи между элементами технологической среды

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

Преимуществом данного блока перед подобными системами является его полная автономность - возможность системы работать на любом компьютере с операционной системой Windows (Wind 9х, WinNT) без установки других программных компонент. Легко подключается практически к любой СУБД (Paradox, InterBase, SQLServer, FoxPro и др.). Подсистема оптимизации раскроя может работать автономно: в случае необходимости при работе на локальном компьютере данные для оптимизации могут вводиться с клавиатуры.

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

Подсистема автоматизированного раскроя длинномерных профилей внедрена и действует на фирме "Чудо-окна". По статистике за последние 20 месяцев процент использования материала составил в среднем 97%, что приблизительно на 10-12% больше, чем за такой же промежуток времени до внедрения программы оптимизации раскроя.

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

ОБЩИЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ.

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

2. Проведенные экспериментальные и теоретические исследования выявили возможность применения метода замещений для решения задачи линейного целочисленного раскроя.

3. Сформулирован принцип парных реберных замещений для двудольных графов. На

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

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

5. Разработан алгоритм решения задачи линейного целочисленного раскроя, позволяющий генерировать оптимальные раскройные карты в режиме реального времени для большого количества размеров заготовок (1500-2000 типоразмеров).

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

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

8. Повышение эффективности раскройно-заготовительного производства достигнуто за счет

• уменьшения отходов длинномерных материалов (на 10-12%),

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

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

• снижения вероятности ошибок ввода данных (человеческий фактор) за счет отсутствия дублирования ввода данных; информация вводится единожды.

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

1. Т. Б. Рубина. Применение метода замещений для решения задачи составления расписания учебных занятий // Сборник трудов участников конференции "Информационные технологии в образовании". М.: МИФИ, 1999, Часть III, с. 163165.

2. Т.Б. Рубина. Внедрение оптимального раскроя на производстве // Тезисы докладов научно-технической конференции "Метрологическое обеспечение эксплуатации и хранения технических объектов", М., 1999, с. 99-100.

3. Т.Б. Рубина. Оптимизация раскроя длинномерных профилей методом замещений // Международная конференция "Математика, компьютер, образование" М.: Прогресс-Традиция, 1999, с .279

4. Т.Б. Рубина. Повышение эффективности использования производственных ресурсов за счет внедрения автоматизированной подсистемы раскроя длинномерных профилей // Тезисы докладов II Всероссийской научно-технической конференции "Компьютерные технологии в науке, проектировании и производстве". - Нижний Новгород, 2000, ч.1, с.31

5. Т.Б. Рубина. Применение принципа парных замещений при решении задач раскроя (в печати)

ВВЕДЕНИЕ.

ГЛАВА 1. Задачи исследования в общей проблеме оптимального раскроя материалов.

1.1. Раскрой длинномерных материалов.

1.2. Факторы, влияющие на модель раскроя.

1.3 Сложность задачи раскроя.

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

1.5. Методы решения задач линейного целочисленного раскроя.

1.6. Программное обеспечение для решения задач раскроя.

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

1.8. Технологическая среда раскройно-заготовительного производства.

1.9. Выводы по главе 1.

ГЛАВА 2. Исследование метода замещений и его применениедля решения задачи раскроя.

2.1. Технологическая постановка задачи раскроя.

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

2.3. Выбор метода решения.

2.4. Сущность метода замещений.

2.5. Основные определения.

2.6. Принцип парных замещений для двудольных графов.

2.7. Метод решения.

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

2.9. Построение дерева замещений.

2.10. Алгоритм решения оптимизационной задачи с помощью метода замещений.

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

2.12. Вычислительная схема решения задачи раскроя.

2.13. Пример решения задачи раскроя.

2.14. Выводы по главе 2.

ГЛАВА 3. Оптимизация управления процессом раскроя.

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

3.2. Потоки в раскройно-заготовительной производственной системе.

3.3. Статический раскрой.

3.5. Динамический раскрой.

3.6. Временная диаграмма.

3.7. Сортировочное устройство.

3.8. Технологическая схема измерения и раскроя профиля.

3.9. Выводы по главе 3.

ГЛАВА 4. Комплексная автоматизация работы раскройно-заготовительноно производства.

4.1. Интегрированная автоматизированная система управления производством «Чудо-Окна».

4.2. Обеспечение ИАСУ.

4.2.1. Техническое обеспечение.

4.2.2. Математическое обеспечение.

4.2.3. Информационное обеспечение.

4.2.4. Архитектура системы.

4.2.5. Программное обеспечение.

4.2.6. Лингвистическое обеспечение.

4.3. Подсистема оптимизации раскроя длинномерных материалов.

4.4. Описание функционирования ИАСУ на реальном производстве.

4.5. Рекомендации по внедрению оптимального раскроя на производстве.

4.6. Требования к персоналу.

4.7. Методика внедрения подсистемы оптимального раскроя.

4.8. Выводы по главе 4.

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

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

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

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

Цель работы: Сокращение отходов длинномерных материалов и повышение эффективности проектирования автоматизированных систем управления раскройно-заготовительным производством.

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

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

• исследование применимости метода замещений (метода Горшкова) для решения задачи оптимального раскроя длинномерных материалов;

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

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

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

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

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

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

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

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

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

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

Практическая ценность:

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

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

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

Методы исследования: теория графов, численные методы, методы системного анализа и исследования операций, теория оптимизации.

Реализация работы: Научные результаты исследований были использованы при выполнении работ по повышению эффективности работы заготовительного участка на московской фирме "Чудо-Окна", специализирующейся на изготовлении пластиковых окон. В результате внедрения алгоритма оптимального раскроя на производстве удалось повысить коэффициент использования длинномерных материалов до 97%, что на 10-12% больше по сравнению с периодом до внедрения программы оптимизации.

Результаты работы докладывались на заседании кафедры "Информационных технологий и вычислительных систем" МГТУ "Станкин", а также на следующих конференциях:

• IX Международная конференция-выставка "Информационные технологии в образовании" (Москва, 9-12 ноября, 1999 г.)

• Научно-техническая конференция "Метрологическое обеспечение эксплуатации и хранения технических объектов" (Москва, 8-9 декабря, 1999 г.)

• VII Международная конференция "Математика, компьютер, образование" (Дубна, 24-29 января, 2000 г.);

• II Всероссийская научно-техническая конференция "Компьютерные технологии в науке, проектировании и производстве" (Нижний Новгород, 3-4 февраля 2000 г.).

4.8. Выводы по главе 4.

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

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

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

3. Программное обеспечение реализовано на языке С++ с использованием пакетов Inprise С++ Builder 4.0 и Visual Studio 6.0, в качестве СУБД использована Inprise InterBase 5.0, однако без принципиальных изменений по желанию заказчика можно использовать любую другую промышленную СУБД.

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

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

ЗАКЛЮЧЕНИЕ.

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

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

2. Проведенные экспериментальные и теоретические исследования выявили возможность применения метода замещений для решения задачи линейного целочисленного раскроя.

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

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

5. Разработан алгоритм решения задачи линейного целочисленного раскроя, позволяющий генерировать оптимальные раскройные карты в режиме реального времени для большого количества размеров заготовок (1500-2000 типоразмеров).

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

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

8. Повышение эффективности раскройно-заготовительного производства достигнуто за счет

• уменьшения отходов длинномерных материалов (на 10-12%),

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

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

• снижения вероятности ошибок ввода данных (человеческий фактор) за счет отсутствия дублирования ввода данных; информация вводится единожды.

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

1. Т.Б. Рубина. Применение метода замещений для решения задачи составления расписания учебных занятий // Сборник трудов участников конференции "Информационные технологии в образовании". М.: МИФИ, 1999, Часть III, с. 163-165.

2. Т.Б. Рубина. Внедрение оптимального раскроя на производстве // Тезисы докладов научно-технической конференции "Метрологическое обеспечение эксплуатации и хранения технических объектов", М., 1999, с. 99-100.

1. Аверьянова Н.К., Бухвалов A.B. Опыт внедрения программы линейного раскроя в судостроении // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез. докл. всесоюз. конф., Уфа, 1987, с.2-3

2. Автоматизированное производство и проектирование в машиностроении. / Под ред. Ю.М. Соломенцева, В.Г. Митрофанова. -М.: Машиностроение, 1986. 256 с.

3. Алгоритмы и программы решения задач на графах и сетях. -Новосибирск: Наука, Сиб.отд., 1990 513 с.

4. Бабаев В.Ф. Оптимальный раскрой металла с помощью ЭВМ в условиях единичного и мелкосерийного производства // Технология машиностроения, 1966, № 12, с. 43-46

5. Бабаев В.Ф. Оптимальный раскрой материалов с помощью ЭВМ. М.: Машиностроение, 1982 - 167 с.

6. Балакшин Б.С. Теория и практика технологии машиностроения: В 2 кн. -М.: Машиностроение, 1982-Кн. 1 239 с. Кн.2 - 367 с.

7. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. - 366 с.

8. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд./Пер.с анл. М., Издательство Бином, СПб, Невский диалект, 1998 г. - 560 с.

9. Бэллман Р. Динамическое программирование. М.: Изд. Иностр.литер., 1960.-400 с.

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

11. Булавский В.А., Яковлева H.A. О решении задач оптимального раскроя материалов на ЭВМ В кн. Математические методы в технико-экономических расчетах: Материалы научного совещания, т.4, Москва, 4-8 апреля 1960 г, М.: Изд-во АН СССР, 1961, с.83-87

12. Волков В.А. Анализ использования материальных ресурсов, М.: Экономика, 1965 113 с.

13. Габитов В.А., Мухачева A.C., Федорова H.H. Предоптимаизационный выбор алгоритма решения задачи линейного целочисленного раскроя // В кн.: Принятие решений в условиях неопределенности, Уфа, 1996, с. 17-22

14. Горанский Г.К., Бендерева Э.И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М.: Машиностроение, 1981.-456 с.

15. Горшков А.Ф. Об одном методе отыскания экстремальных суграфов //Сибирский математический журнал АН СССР, 1985. Т.26, № 1, с.44-48.

16. Горшков А.Ф. Метод отыскания экстремальных подграфов на двудольных графах // Техническая кибернетика, 1986, № 4, с. 136-142.

17. Горшков А.Ф., Соломенцев Ю.М. Отыскание экстремальных каркасов с предписанными степенями вершин методом замещений. //ДАН, 1996. Т.347, № 4, с.443-445.

18. Горшков А.Ф., Соломенцев Ю.М. Применимость реберных замещений в классе комбинаторных задач на графах. //ДАН, 1994. Т.337, № 2, с.151-153.

19. Горшков А.Ф., Соломенцев Ю.М. Применимость вершинных замещений в классе задач о к-вершинных подграфах //ДАН, 1994. Т. 336, №2, с. 157-160

20. Грабер М. Введение в SQL. Пер. с англ. - М., Издательство «ЛОРИ», 1996, 379 с.

21. Грешилов A.A. Как принять наилучшее решение в реальных условиях -М.: Радио и связь, 1991. 320с.

22. Григорчук Т.И., Соломещ Н.И. О приближенном подходе к решению одномерной задачи упаковки в контейнеры случайной емкости // Применение ЭВМ в решении научно-технических и народнохозяйственных задач: Тез.докл., Уфа, 1989, с.68

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

24. Данциг Дж. Линейное программирование, его обобщения и применения, М.: Прогресс, 1966 600с.

25. Елманова Н.З. Borland C++Builder 3.0. Архитектура «клиент/сервер», многозвенные системы и Internet-приложения М.: Диалог-МИФИ, 1998-240с.

26. Емеличев В.А., Ковалев М.Н., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981.-341 с.

27. Ереклинцев В.В., Фридман Д.С., Розенфельд В.Х. Оптимизация раскроя проката. М.: Металлургия, 1984. - 159 с.

28. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969.543с.

29. Ибатулина С.М. Распараллеливание алгоритмов решения задач раскроя // Управление сложными техническими системами, № 8, Уфа, 1985, с.112-118

30. Канторович JI.B. Математические методы организации и планирования производства, Ленинград, Издательство ЛГУ, 1939, 68 с.

31. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М: Изд-во АН ССР, 1959, 348 с.

32. Канторович Л.В., Романовский И.В. Генерирование столбцов в симплекс-методе // Экономика и мат.методы, 1985, т.21, вып.1, с. 128138

33. Каримова Л.М., Мухачева Э.А., Никулыпина Л.М. Принципы конструирования в проблемно-ориентированных пакетах В кн. Методология разработки АСУ: Тез.Всесоюз. науч.-техн. конф., Калинин, 1980, с.70-71

34. Картак В.М. Комбинированные методы для получения оптимального целочисленного раскроя в задачах одномерного раскроя // Принятие решений в условиях неопределенности: Межвузовский сборник Уфа: УГАТУ, 1996, с.40-46

35. Кацев С.Б. Решение оДной обобщенной задачи о разбиении множеств // Кибернетика, 1977, № 5, с.115-120

36. Кацев С.Б., Романовский И.В. Две задачи целочисленного программирования. Задача о распределении заданий // Алгол-процедуры, JL, Изд-во ЛГУ, 1975, вып. 13, с.18-23

37. Красильников Я.И. Рациональный раскрой металла, М.-Свердловск: Машгиз, 1961 -46 с.

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

39. Ковалев М.М. Новые приложения метода частичных порядков // Кибернетика, 1985, № 2, с. 11-16

40. Ковалев М.М., Тарновский А.Г. Серии эвристических алгоритмов раскроя и анализ их эффективности // Математическое обеспечение рационального раскроя в системах автоматизированного проектирвания: Тез. докл. всесоюз. конф., Уфа, 1988, с. 85-86

41. Ковалев М.М., Тарновский А.Г. Сравнительный анализ САПР раскроя на ПЭВМ // Международный симпозиум INFO-89, Минск, 1989, т.2., ч.1, с.276-281

42. Колоколов A.A. Регулярные отсечения при решении задач целочисленной оптимизации // Управляемы системы, Новосибирск, 1981, вып. 21, с. 18-25

43. Компьютерно-интегрированные производства и CALS-технологии в машиностроении: Учеб. пособие / Под. редакцией Черпакова Б.И., М.: ГУП "ВИМИ", 1999, 512 с.

44. Липатов Е.П. Теория графов и ее применения. М.: Знание, 1986, 32 с.

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

46. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике. Физике, химии: Пер. с англ. М., Мир, 1998-653 с.

47. Математика в современном мире, М.: Знание, 1969 72 с.

48. Математическая энциклопедия / Гл. ред. И.М. Виноградов М.: Советская энциклопедия, 1984. - т.4, с. 868-870

49. Математическое обеспечение расчетов линейного и прямоугольного раскроя // Материалы всесоюзного семинара. Уфа, 1981 - 179 с.

50. Математическое обеспечение рационального раскроя в системах автоматизированного проектирвания // Материалы Всесоюзной конференции, Уфа, 1988 159 с.

51. Михалевич В., Кукса А. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. -М.: Наука, 1983. 208 с.

52. Мухачева Э.А., Рубинштейн ГШ. Математическое программирование: Учеб.пособие для экон. и инж.-техн. спец. Вузов / АН СССР, Сибирское отд-ние, Ин-т математики, 2-е изд., перераб. и доп. Новосибирск: Наука, Сибирское отд-ние, 1987. - 271 с.

53. Мухачева Э.А. Дополнительные вопросы математического программирования. Курс лекций. Уфа, 1972, 63с.

54. Мухачева Э.А. Рациональный раскрой промышленных материалов, М., Машиностроение, 1984. 176 с.

55. Мухачева Э.А., Мухачева A.C., Картак В.М., Белов Г.Н. Задачи линейной упаковки: вычислительные эксперименты // Международная Сибирская конференция по исследованию операций, Новосибирск, 1998, с.67

56. Мухачева A.C., Житников В.П. Метод оценок для решения задач линейной и прямоугольной упаковки // Международная научная конференция , Уфа, 1998, с.40

57. Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем. Диссертация на соискание степени канд. физ.-мат. наук, Уфа, 1999 117 с.

58. Пономарева К.В, Кузьмин Л.Г. Информационное обеспечение АСУ: Учеб. для сред.спец.учеб. заведений. 2-е изд, перераб. и доп. - М.: Высш.шк., 1991.-222 с.

59. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М: Мир, 1980. 476 с.

60. Романовский И.В. Программа решения задачи линейного раскроя. -Оптимальное планирование, Новосибирск, 1969, вып. 12

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

62. САПР. Системы автоматизированного проектирования: Учеб.пособие для техн. вузов. В 9 кн. Кн.1. Принципы построения и структура / И.П. Норенков; Под ред. И.П. Норенкова. Мн. Выш.шк., 1987 - 123 с.

63. САПР. Системы автоматизированного проектирования: Учеб.пособие для техн. вузов. В 9 кн. Кн.2. Технические средства и операционные системы / Д.М. Жук, В.А. Мартынюк, П.А. Сомов; Под ред. И.П. Норенкова. Мн. Выш.шк., 1988 - 155 с.

64. САПР. Системы автоматизированного проектирования: Учеб.пособие для техн. вузов. В 9 кн. Кн.З. Информационное и прикладное программное обеспечение / В.Г. Федорчук, В.М. Черненький; Под ред. И.П. Норенкова. Мн. Выш.шк., 1988 - 157 с.

65. Соломенцев Ю.М. Конструкторско-технологическая информатика и автоматизация производства.- М.: Станкин, 1992.-127с.

66. Соломенцев Ю.М., Павлов B.B. Моделирование технологической среды машиностроения. -М.: Станкин, 1994. 104 с.

67. Соломещ Н.И. Задачи линейного целочисленного раскроя материала случайной длины. Дис. канд. физ.-мат. наук, Уфа, 1989 106 с. (На правах рукописи)

68. Справочник по математике для экономистов / В.Е. Барбаумов, В.И. Ермаков, H.H. Кривенцова и др.; Под ред. В.И. Ермакова. 2-е изд., перераб. и доп. - М.: Высш. шк., 1997. - 384 с.

69. Страуструп Б. Язык программирования С++. Часть первая. Пер. с англ.- Киев: «Диасофт», 1993. 264 с.

70. Страуструп Б. Язык программирования С++. Часть вторая. Пер. с англ.- Киев: «Диасофт», 1993. 296 с.

71. Стриер JI.M. Производственные запасы и эффективность машиностроительного производства. М.: Машиностроение, 1980. -72с.

72. Сурков К.А., Сурков Д.А., Вальвачев А.Н. Программирование в среде С++ Builder Мн.: ООО «Попури», 1998 - 576 с.

73. Танаев B.C., Поварич М.П. Синтез граф-схем алгоритмов выбора решений. Минск: Наука, 1974 - 112 с.

74. Тарновский А.Г. САПР "Раскрой" промышленная система раскроя материалов на ПЭВМ / Методы решения экстремальных задач и смежные вопросы, Минск, ИТК АН БССР, 1990, с. 142-158

75. Тарновский А.Г. Проблемы оптимизации технологического процесса раскроя промышленных материалов в станкостроении / КТИ-87 -Тезисы докл. всесоюз. научн. конф., М., 1987, с.61-63

76. Теллес М. Рейсдорф К. Borland С++ Builder: библиотека программиста- СПб: Питер Ком, 1998. 512 с.

77. Тихомиров Б.И. Экономия материалов путем оптимального раскроя (Обзорная информация), М., 1968. 53 с.103

78. Шамис В.А. С++ Builder 3.0 Техника визуального программирования. -М.: "Нолидж", 1998, 512 с.

79. Шенбот И.М., Алиев В.М. Проектирование вычислительных систем распределенных АСУ ТП М.: Энергоатомиздат, 1989 - 88 с.

80. Шклярский Л.Ф., Даниленко Ю.И., Малованов Б.К., и др. Совершенствование структуры управления машиностроительным предприятием в условиях АСУ М.: Машиностроение, 1991 - 271 с.

81. Энциклопедия кибернетики Харьков, 1974 - т.1. 608 с.

82. Янг М. Visual С++6. Полное руководство: В 2 т.: Пер. с англ. Киев: Издательская группа BHV, 1999. Т.1. - 544 е., Т2. - 560с.104