Математическое обеспечение автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов на базе дискретных моделей тема диссертации и автореферата по ВАК РФ 05.13.06, доктор технических наук Верхотуров, Михаил Александрович

• Верхотуров, Михаил Александрович
• доктор технических наук
• 2000

Оглавление диссертации доктор технических наук Верхотуров, Михаил Александрович

Введение.

Глава 1. Анализ проблемы автоматизации задач раскроя - упаковки, решаемых в процессе управления современным производством.

1.1 Автоматизированные системы и их интеграция в структуре управления современным производством.

1.1.1 Классификация автоматизированных систем (АС).

1.1.2 Требования к ИСУ и ее роль в структуре современного производства.

1.1.3 Типовой состав функциональных подсистем современной ИСУ

1.2 Этапы развития ИСУ.!.

1.2.1 Классификация ИСУ.

1.2.2 От автоматизации отдельных функций к методологии CSRP.

1.2.3 MRP - системы.

1.2.4 MRP II - системы.

1.2.5 ERP - системы.

1.2.6 CSRP - системы.

1.3 Задачи раскроя - упаковки - основа эффективной работы промышленного производства.

1.4 Выводы по первой главе.

Глава 2. Методология создания автоматизированных систем нерегулярного размещения ГО, функционирующих в составе ИСУ.

2.1 Многообразие задач раскроя - упаковки.

2.1.1 Классификация задач Р-У.

2.1.2 Задачи генерации и планирования раскроя-упаковки.

2.2 Основные определения и постановка задачи размещения ГО.

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

2.2.2 Общая постановка задачи оптимизации размещения ГО.

2.2.3 Целевая функция в задачах размещения ГО.

2.3 Задачи размещения и ИСУ.

2.3.1 Задачи САПР и АСР ГО.

2.3.2 Задачи АСУП и АСР ГО.

2.3.3 Задачи АС ТПП и АСР ГО.

2.4 Структура автоматизированной системы размещения ГО.

2.4.1 Препроцессорный блок АСР ГО.

2.4.2 Оптимизационное ядро АСР ГО.

2.4.3 Постпроцессорный блок АСР ГО.

2.5 Выводы по второй главе.

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

3.1 Методы решения задач упаковки ГО.

3.1 1 Классификация методов решения задач нерегулярного размещения ГО.

3.1.2 Точные методы решения задачи нерегулярного размещения ГО.

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

3.2 Применение эвристических методов локального поиска для задачи нерегулярного размещения ГО.

3.2.1 Алгоритм поиска с запретами (Tabu Search - TS).

3.2.2 Генетический алгоритм {Genetic Algorithm - GA).

3.2.3 Алгоритм муравьиной колонии {Ant Colonies - AC).

3.2.4 Метод моделирование отжига {SimulatedAnnealing- SA) и его модификации.

3.2.5 Гибридизация методов локального поиска для задач нерегулярного размещения ГО.

3.3 Применение метода последовательного уточнения оценок для решения задач нерегулярного размещения ГО.

3.3.1 Метод последовательного уточнения оценок.

3.3.2 "Жадный" алгоритм и метод SVC.

3.3.3 Алгоритм с возвратом и его модификации.

3.4 Выводы по третьей главе.

Глава 4. Методы и алгоритмы построения годографа функции плотного размещения на базе дискретно-логического представления информации и цепного кодирования.

4.1 Постановка задачи построения годографа.

4.2 Анализ существующих способов построения годографа.

4.2.1 Способы построения 2D годографа.

4.2.2 Способы построения 3D годографа.

4.3 Метод построения годографа на основе дискретно-логического представления информации и цепного кодирования.

4.4 Построение 2D годографа на основе ДЛПИ и ЦК.

4.4.1 Классифицирующие характеристики.

4.4.2 Структура элемента графической информации.

4.4.3 Способы построения годографа.

4.4.4 Алгоритм первоначального занесения объекта в область.

4.4.5 Алгоритмы построения годографа для случая "8-МПК-МАТК".

4.4.6 Алгоритм построения годографа для случая "4-ПК-МПР".

4.4.7 Алгоритмы изменения границы области.

4.4.8 Алгоритм построения частей несвязного годографа.

4.5 Построения 3D годографа на основе ДЛПИ и ЦК.

4.5.1 Классифицирующие характеристики.

4.5.2 Структура элемента графической информации.

4.5.3 Способы построения годографа.

4.6 Выводы по четвертой главе.

Глава 5. Методы и алгоритмы аппроксимации цепными кодами объектов с линейно-заданными границами.

5.1 Аппроксимация 2D ГО.

5.1.1 Аналитические способы представления информации.

5.1.2 Дискретные способы задания контуров ГО.

5.2 Аппроксимация 3D ГО.

5.3 Выводы по пятой главе.

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

6.1 Комплекс программных средств "Cut-CAD" современная ресурсосберегающая технология раскроя - упаковки.

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

6.3 Примеры практического применения разработанного математического и программного обеспечения.

6.3.1 Расчет подетальных норм расхода материала.

6.3.2 Проектирование карт раскроя листового анизотропного материала

6.4 Выводы по шестой главе.

Введение диссертации (часть автореферата) на тему «Математическое обеспечение автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов на базе дискретных моделей»

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

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

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

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

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

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

Текущий этап развития экономики России определяется переходом промышленных предприятий к функционированию в условиях рыночной экономики и характеризуется серьезными финансовыми проблемами и жесткой конкуренцией, как со стороны отечественных, так и зарубежных товаропроизводителей. Имея ограниченные ресурсы, предприятия должны действовать быстро и эффективно, проникать на мировые рынки, использовать новые технологии, совершенствовать организационную 9 структуру, товарные, финансовые и информационные потоки, внутренний и внешний документооборот. Ключ к разрешению этих проблем лежит в сквозной автоматизации, заключающейся в разработке и использовании интегрированных систем управления, базирующихся на современных методологиях планирования и управления различного вида ресурсами {MRP, MRPII, CRP, FRP, ERP, CSRP и т.д.), отражающих необходимость дальнейшей автоматизации управления различными процессами, происходящими как внутри сферы производства, так и при его взаимодействии с потребителем.

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

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

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

- исследованием и разработкой методов решения задач двумерного нерегулярного размещения занимаются несколько коллективов и отдельных авторов, это: Харьковская школа Р-У академика Стояна Ю.Г.; Институт алгоритмов и научных вычислений Германии (Ленгауэр Т.); Миленковик В., Даниэльс К. (США); Доусланд К.,

10

Доусланд В.(Великобритания); и ряд ученых в различных странах мира;

- исследование и разработка методов решения задач трехмерного нерегулярного размещения является новым научным направлением в классе задач раскроя - упаковки, которым занимается несколько авторских коллективов: Иконен И., Билес В. и др., Баллинг Р., Ландон М. и др., Зукман С., Каган И., Coca М. (США); Дикинсон и Кнопф (Канада); Такаюки Осогами (Япония). Активно работы в этом направлении развернулись во второй половине 90-х годов в связи с развитием одного из практических приложений этих задач -быстрого прототипирования.

Несмотря на заметное продвижение в области решения задач раскроя -упаковки:

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

- профессиональные укладчики при ручном размещении при решении задач нерегулярного размещения часто получают результаты лучшие, чем сгенерированные на ЭВМ;

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

11 работе в составе АСР, в связи с тем, что эта задача является некорректно поставленной;

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

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

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

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

12

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

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

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

2. Разработать теоретические основы оптимизации нерегулярного размещения двух- и трехмерных геометрических объектов на базе дискретных методов локального поиска, направленные на создание гибкого математического обеспечения АСР ГО.

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

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

13

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

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

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

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

Результаты, выносимые на защиту:

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

14 регламентирующий взаимодействие АСР ГО с различными подсистемами ИСУ.

2. Теоретические основы оптимизации нерегулярного размещения двух- и трехмерных геометрических объектов, базирующиеся на адаптации и интеграции методов дискретной оптимизации: "Поиска с запретами" (TS), "Моделирования отжига" (SA), "Генетических алгоритмов" (GA), "Муравьиной колонии" (АС), "Объективно -обусловленных оценок Л.В.Канторовича" (SVC) и на построении годографа функции плотного размещения, позволяющие разрабатывать инвариантное различным подсистемам в составе ИСУ математическое обеспечение оптимизационного ядра АСР ГО.

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

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

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

15 обеспечения на ряде предприятий различных отраслей промышленности.

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

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

2. Разработано эффективное математическое обеспечение оптимизационного ядра АСР ГО, включающее класс годограф -ориентированных алгоритмов решения задач нерегулярного размещения двух- и трехмерных геометрических объектов, основанных на применении следующих метаэвристических методов локального поиска: "Поиска с запретами" (TS), "Моделирования отжига" (SA), "Генетических алгоритмов" (GA), "Муравьиной колонии" (АС). Это позволяет получать допустимые и близкие к оптимальным решения задач нерегулярного размещения ГО.

3. Разработаны и исследованы метод и ряд комбинаторных детерминированных алгоритмов решения задач нерегулярного размещения двух- и трехмерных геометрических объектов на базе объективно - обусловленных оценок Л.В.Канторовича. Разработаны

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

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

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

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

17 метода оценок комбинаторные методы и алгоритмы оптимизации позволяют создать комплекс программных средств, быстро генерирующих высокоэкономичные карты раскроя - упаковки. Все это дало возможность применить полученные результаты для разработки соответствующего программного обеспечения, которое может быть использовано в составе различных подсистем ИСУ: АСУП, САПР и АСТПП, а также для создания на этой основе автономного комплекса программных средств. На базе проведенных исследований разработан работающий в среде Microsoft Windows 95/98 комплекс программных средств для решения задач Р-У - "Cut-CAD", который на практике показал высокую эффективность за счет быстрой адаптации к условиям работы производств различного вида в разнообразных отраслях промышленности, хорошей совместимости с различными подсистемами, функционирующими в составе ИСУ, уменьшения времени проектирования карт Р-У (в 5-10 раз) и экономии материала (до 5%).

Основание для выполнения исследований.

Работы в данном направлении проводились автором в Уфимском авиационном институте в 1989-1992 годах в рамках поисковых НИР по заказам Уральского филиала НИИД ("Рациональный раскрой материала с учетом ориентации волокон") и НПО БУММАШ ("Система автоматизированного нормирования и расхода материала с обеспечением его рационального раскроя"). В дальнейшем работы были продолжены в рамках выполнения хоздоговорных научно-исследовательских работ с Уфимским производственным объединением "Гидравлика" по темам №ИФ-ВК 01-92-ОГ (1992-1993 г.г.), №ИФ-ВК-07-95-ОГ (1995-1996 г.г.) и №ИФ-ВК-09-97-ХГ (1997-1999 г.г.); с ОАО "Уралхиммаш" и ОАО "Белебеевский опытный механический завод".

В 1998-1999 г.г. работа была поддержана государственным грантом по фундаментальным исследованиям в области технических наук (направление

18

Информационные технологии в проектировании изделий и технологических процессов их изготовления", раздел "Проблемы управления и контроля технологических процессов изготовления деталей и изделий авиакосмической техники", конкурсный центр МАТИ) по теме "Информационные технологии раскроя-упаковки одно и двухмерных объектов" №ИФ-ВК-04-98-ГУ.

Внедрение результатов;

- на НПО БУММАШ г. Ижевск (алгоритмы и программы дискретно-логической аппроксимации исходных плоских контуров; методы, алгоритмы и программы формализации плотного движения объектов на базе дискретно-логического представления информации; методы, алгоритмы и программы решения задачи оптимизации размещения дискретно - аппроксимированных деталей на листовом изотропном материале);

- в Уральском филиале НИИД г. Уфа (алгоритмы и программы формализации исходных данных об объектах раскроя; методы, алгоритмы и программы решения задачи оптимизации размещения линейно - аппроксимированных деталей на листовом анизотропном материале; алгоритмы и процедуры подготовки управляющих программ для оборудования с ЧПУ);

- в Акционерном обществе «Химмаш», г. Екатеринбург (методы и алгоритмы рационального размещения геометрических объектов на плоском материале в составе программного комплекса проектирования раскроя-упаковки «Cut-CAD», что позволило автоматизировать процесс проектирования карт раскроя и увеличить коэффициент использования листового и рулонного материала);

- на Уфимском унитарном агрегатном производственном объединении «Гидравлика», г. Уфа (методы, алгоритмы и программы

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

- в Акционерном обществе Белебеевский опытный механический завод, г. Белебей (подсистема препроцессорной подготовки информации, включающая алгоритмы и программы аппроксимации исходных данных об объектах раскроя - упаковки; алгоритм моделирования процесса плотного движения объектов в области размещения на основе их дискретно-логического представления и цепного кодирования; методы и алгоритмы автоматизированного нерегулярного размещения деталей сложных геометрических форм; интегрированная оболочка САПР раскроя - упаковки "Cut-CAD for Windows");

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

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

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

- Республиканская научно-техническая конференция "Применение САПР в машиностроении", Свердловск, 1989 г.;

20

- 8-ая поволжская межзональная конференция "Актуальные вопросы начертательной геометрии и инженерной графики", Йошкар-Ола, 1990 г.;

- Республиканская научно-техническая конференция "Автоматизация проектирования в энергетике и электротехнике", Иваново, 1990 г.;

- Всесоюзная научно-техническая конференция "Теория и методы создания интеллектуальных САПР в машиностроении и приборостроении", Минск, 1992 г.;

- Международная научно-методическая конференция "Проблемы качества высшего образования", Уфа, 1993 г.;

- Региональная научно-техническая конференция "Математическое программирование и приложения", Екатеринбург, 1993, 1995, 1997, 1999 гг.;

- Межрегиональная научно-методическая конференция "Актуальные вопросы современной инженерной графики", Уфа, 1994 г.;

- Сибирский конгресс "Прикладная и индустриальная математика", Новосибирск, 1994, 1996, 1998 гг.;

- Международный семинар НАИ-УГАТУ "Актуальные проблемы авиадвигателестроения", Уфа, 1994 г.;

- Международная научно-техническая конференция "Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении", Казань, 1995 г.;

- Всероссийская научно-техническая конференция "Роль геометрии в искусственном интеллекте и системах автоматизированного проектирования", Улан-Удэ, 1996 г.;

- Международная конференция "Комплексный анализ, дифференциальные уравнения и смежные вопросы", Уфа, 1996 г.;

- 14 международная конференция "Исследование операций", Ванкувер, Канада, 1996 г.;

21

- Всероссийская конференция по математическому программированию "Проблемы оптимизации и экономические приложения", Омск, 1997 г.;

- Международная конференция "Технология машиностроения", София, Болгария, 1997 г.;

- Международный конгресс по исследованию операций. EURO-XVI, Брюссель, Бельгия, 1998 г.;

- Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности, Уфа, 2000 г.

Публикации.

По теме диссертации опубликованы 53 работы, в том числе 1 монография (в соавторстве), 26 статей, 24 тезисов докладов, а также 2 научно-технических отчета.

Структура работы.

Диссертация состоит из введения, шести глав, выводов, списка литературы и приложения. Объем основной части диссертации составляет 324 страницы, кроме того, работа содержит 69 рисунков и 12 таблиц, расположенных на 44 страницах. Библиографический список включает 300 наименований.

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Верхотуров, Михаил Александрович

Основные выводы и результаты

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

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

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

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

288

2.1. На основе анализа применения методов дискретной оптимизации для решения задач нерегулярного размещения ГО выделен и разработан класс годограф - ориентированных алгоритмов, основанных на использовании следующих метаэвристических методов локального поиска: "поиска с запретами" (TS), "генетических алгоритмов" (GA), "моделирования отжига" (SA), "муравьиной колонии" (АС).

2.2. Для решения задач нерегулярного размещения геометрических объектов разработан метод последовательного уточнения оценок (SVC'), который основывается на физическом смысле двойственных переменных Л.В.Канторовича, Разработаны два способа подсчета оценок для несвязной и многосвязной видов непокрытой геометрическими объектами области размещения. Для первого из этих способов разработано два варианта подсчета оценок. Разработаны алгоритмы нерегулярного размещения ГО, основанные на методе последовательного уточнения оценок и его комбинациях с "жадным" алгоритмом и алгоритмом с возвратом.

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

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

289 вычислительной технике затруднительна в связи с тем, что данная задача является некорректно поставленной. В связи с этим разработан способ моделирования годографа на основе ДЛПИ и ЦК. На базе предложенного способа разработан метод построения годографа для двухмерного и трехмерного пространства. Выделены классифицирующие характеристики, влияющие на возможные способы построения годографа. Разработана структура элемента графической информации, позволяющая реализовать способ моделирования годографа на основе ДЛПИ и ЦК. Разработаны алгоритмы: построения годографа для различных случаев реализации ДЛПИ и ЦК; изменения области Р-У при занесении ГО в данную область и удалении ГО из неё; построения частей несвязного годографа. Разработаны структура решения задачи, методы и алгоритмы аппроксимации двух- и трехмерных ГО цепными кодами. Основными преимуществами применения дискретно - логического представления информации и цепного кодирования являются: корректность поставленной задачи построения годографа -небольшие изменения в исходных данных не влекут за собой изменения результатов решения; быстрота и надежность выполнения базовых логических операций; выбор шага дискретной сетки дает возможность манипулирования точностью получаемых результатов.

4 На базе разработанных методологии и математического обеспечения создан комплекс программных средств "Cut-CAD", позволяющий в автономном режиме решать задачи Р-У любого вида (плоских и пространственных геометрических объектов сложной формы). Он может быть использован как при автоматизации деятельности промышленных и проектных организаций, связанных с решением задач Р-У, так и при проведении научно-исследовательских работ по рассматриваемой проблематике. Для проверки качества

290 разработанных методов и алгоритмов проведен вычислительный эксперимент, а также произведено сравнение решений с результатами, полученными другими методами. Эксперимент показал высокую эффективность созданных автором методов и алгоритмов за счет уменьшения времени проектирования карт Р-У (в 5-10 раз) и экономии материала (до 5%). Результаты выполненных исследований внедрены на ряде предприятий и организаций различных отраслей промышленности, а в частности: на НПО БУММАШ (г.Ижевск) ("Система автоматизированного нормирования и расхода материала с обеспечением его рационального раскроя"); в Уральском филиале НИИД (г.Уфа) ("Рациональный раскрой материала с учетом ориентации волокон"); в Акционерном обществе «Химмаш» (г.Екатеринбург) ("САПР раскроя для рационального размещения заготовок на плоском материале в машиностроении"); на Уфимском унитарном агрегатном производственном объединении «Гидравлика» (г.Уфа); в Акционерном обществе "Белебеевский опытный механический завод" (г.Белебей) ("АРМ технолога раскройно-заготовительного производства"). Произведенные внедрения показали быструю адаптируемость разработанного программного обеспечения к условиям конкретных промышленных и проектных предприятий, а также позволили получить результаты, удовлетворяющие потребностям современного производства.

Список литературы диссертационного исследования доктор технических наук Верхотуров, Михаил Александрович, 2000 год

1. Автоматизированная система технологической подготовки производства в машиностроении / под ред. Г.К.Горанского. М.: Машиностроение, 1976. - 240с.

2. Автоматизация проектно-конструкторских работ и технологической подготовки производства в машиностроении, Т1, Т2/ под ред. О.И.Семенкова.- Минск: Вышэйшая школа, 1977. 312с.

3. Автоматизация технологической подготовки заготовительного производства / под общей ред. Г.П.Гырдымова. Ленинград: Машиностроение, 1990. - 350с.

4. Александров В.В. и др. Информационное обеспечение ИПК.- М.: Машиностроение, 1986.- 283с.

5. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. - 247с.

6. Алиев Т.М. Автоматизация информационных процессов в интегрированных АСУ промышленным производством. -М.: Машиностроение, 1981.-315с.

7. Аммерал Л. Интерактивная трехмерная машинная графика. -М:сол Систем, 1992.-314с.

8. Арефьев И.Б. Интегрированная АСУ в машиностроении. -М.: Машиностроение, 1988.-290с.

9. Артамонов Е.И. Проблемы разработки систем автоматизированного проектирования//Приборы и системы управления, 1981.-N2.-С. 12-23

10. Ю.Ахо А. и др. Построение и анализ вычислительных алгоритмов. -М.:Мир,1979.-536с.

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

12. Бабаев Ф. В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978, С.2-72.

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

14. Бадаев Ю.И., Залевский В.И. Аппроксимация плоских кривых ломаной линией //Прикладная геометрия и инженерная графика. Киев: Буд1вельник, 1976.21.-С. 105-108.

15. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Воронеж: ВГТУ, 1995.-54с.

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

17. П.Белякова Л.Б., Орехова О.М., Дмитриевская О.В. Алгоритм рационального раскроя полос на фигурные заготовки. -Труды ОНТИ ПТНИИ Волго-Вятского совнархоза, 1964, 1.-С. 53-65.

18. Белякова Л.Б. Об оптимальном раскрое листового материала. -В кн.: Автоматизация технологического проектирования при помощи ЭЦВМ. М.: Машиностроение, 1968.-С.21-32.

19. Белякова Л.Б. Вопросы оптимального расположения конгруэнтных фигур на плоскости: Автореф.дис.канд.физ.-мат.наук.-Горький:ГГУ,1970.-13с.

20. Бикмухаметов А.И., Липовецкий А. И. Реализация аппроксимационного подхода при оптимизации раскроя// САПР в кузнечно-штамповочном производстве: Тез. докл. научно-технической конференции. -Свердловск, 1988.-С. 22-23.

21. Бункин В. А., Курицкий Б.Я., Сокуренко Ю.А. Справочник по оптимизационным задачам в АСУ.-JI.: Машиностроение, 1984, 263с.

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

23. Валеева А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя//Труды междун. сибир. конф. по прикл. и индустр. математике, СО РАН, т.2, 1995.-С.47-57.

24. Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу (Обзор). -В кн.: Дискретные задачи оптимизации. Управляемые системы, Новосибирск, 1984, №25.-С.17-37.

25. Вайсбруд Р.А. Вопросы развития работ по созданию систем автоматизации проектирования процессов кузнечно-штамповочного про изводства// Кузнечно-штамповочное производство. 1985. N8.-С.39-47.

26. Вермишев Ю.Х. Основы автоматизации проектирования .-М: Радио и связь, 1988.-280с.

27. Верхотуров М.А., Болотовская Т.К. Некоторые аспекты проблемы построения рационального плана нерегулярного раскроя на заготовки сложных форм//Принятие решений в условиях неопределенности.-Уфа:УАИ,1990.-С.117-120.

28. Верхотуров М.А., Драган Т.М. Подсистема первоначальной (входной) обработки информации в САПР технологической подготовки раскроя// Применение САПР в машиностроении: Тез. докл. Всесоюзной конференции. Свердловск:УПИ, 1989.-С. 12-13.

29. Верхотуров М.А. Аппроксимация К-угольника М-угольником // Актуальные вопросы начертательной геометрии и инженерной графики: Тез. докл. межзональной конференции.-Иошкар-Ола:МарПИ, 1990,2.-С.51-52.

30. Верхотуров М.А. Способ раскроя изотропного материала на фигурные заготовки//Автоматизация проектирования в энергетике и электротехнике: Тез.докл. республиканской научно-технической конференции.-Иваново:ИЭИ,1991.-С.22-23.

31. Верхотуров М.А. Нерегулярная укладка геометрических объектов на базе дискретного представления информации в автоматизированных системах управления: Автореф.дисс. канд.техн.наук. -Уфа:УАИ, 1992.-16с.

32. Верхотуров М.А., Карамова JI.M., Мухачева Э.А., Тарасова Т.Д. Комплексная система рационального раскроя в условиях штамповочного производства// Обработка металлов давлением, N5.т.4.-Познань: 1993.-С.40-42.

33. Верхотуров М.А., Брусиловский Д.П. Использование в учебном процессе подсистемы фигурного раскроя САПР "Раскрой"// Проблемы качества высшего образования: Тезисы международной науч. метод, конференции. -Уфа: 1993.-С.34.302

34. Верхотуров М.А., Брусиловский Д.П. Система классификации геометрических объектов// Актуальные вопросы современной инженерной графики: Тезисы межрегиональной научно метод, конференция. - Уфа: 1994.-С.59.

35. Верхотуров М.А., Мартынов В.В. Анализ состояния работ в области фигурного раскроя промышленных материалов// Актуальные проблемы авиадвигателестроения: Сб. трудов международного семинара НАИ-УГАТУ. Уфа: 1994.-С. 108-113.

36. Верхотуров М.А. Дискретно логическое представление информации для синтеза и анализа двухмерных и трехмерных сцен// Актуальные вопросы современной инженерной графики: Тезисы межрегиональной науч.-метод. конференции.-Уфа: 1994.-С.64.

37. Верхотуров М.А., Мухачева Э.А., Ибатуллина С.М О рациональном распределении ресурсов// Экономика и управление.№3.-Уфа:1994.-С.ЗЗ-40.

38. Верхотуров М.А., Мухачева Э.А., Шабрина Л.И. Многообразие задач раскроя и упаковки. Деп.в ВИНИТИ, №3023-В94.-М:1994.-8с.

39. Верхотуров М.А., Мухачева Э.А. Интегрированная система рационального раскроя// Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении: Тезисы международной н.-т. конференции.-Казань:1995.-С.61-63. .

40. Верхотуров М.А., Верхотурова Г.Н. О способе представления информации для решения некоторых прикладных задач нелинейного303программирования// Математическое программирование и приложения: Тезисы межрегиональной конференция. Екатеринбург: 1995.-С.58.

41. Верхотуров М.А., Сергеева О.Ю. Применение метода оценок для решения некоторых задач нелинейного программирования// Математическое программирование и приложения: Тезисы межрегиональной конференции. Екатеринбург: 1995.-С.59-60.

42. Верхотуров М.А., Верхотурова Г.Н., Сергеева О.Ю. О решении некоторых прикладных задач нелинейного программирования// Методы оптимизации и их приложения: Тезисы 10-ой Байкальской школы-семинара.-Иркутск: 1995 .С.51.

43. Верхотуров М.А., Мухачёва Э.А. Метод оценок для решения задач раскроя упаковки// Принятие решений в условиях неопределенности: Межвузовский сборник научных трудов. - Уфа: 1996.-С.22-24.

44. Верхотуров М.А., Мухачева Э.А. Интегрированная система рационального раскроя в условиях единичного и мелкосерийного производства// Кузнечно-штамповочное производство". №5.-М: 1996.-С.24-27.

45. Верхотуров М.А. Математическое моделирование нерегулярной упаковки двух и трёхмерных геометрических объектов// Комплексный анализ, дифференциальные уравнения и смежные вопросы: Сб. трудов международной конференции. Уфа: 1996.-С.37-44.

46. Верхотуров М.А., Верхотурова Г.Н., Мухачёва Э.А. Об использовании оценок в задачах трёхмерной упаковки/7 Прикладная и индустриальная математика: Тезисы второго сибирского конгресса. Новосибирск: 1996. .-С.139.

47. Верхотуров М.А., Верхотурова Г.Н. Дискретно-логическое представление информации для синтеза и анализа двухмерных и трёхмерных динамических сцен// Прикладная и индустриальная математика: Тезисы второго сибирского конгресса. Новосибирск: 1996.-С.183-184.

48. Верхотуров М.А., Мухачёва Э.А. Метод оценок для решения задач раскроя упаковки// Исследование операций: Тезисы 14 международной конференции. - Ванкувер: 1996.-С.24.

49. Верхотуров М.А., Мухачёва Э.А. Объективно обусловленные оценки Л.В.Канторовича в задачах оптимального раскроя// Прикладная и индустриальная математика: Сб. Трудов Сибирского конгресса. -Новосибирск: 1997.-С.75-79.305

50. Верхотуров М.А., Верхотурова Г.Н. Об одном решении задачи трехмерной упаковки сложных геометрических объектов// Математическое программирование и приложения: Тезисы всероссийской конференции. Екатеринбург: 1997.-С.57-58.

51. Верхотуров М.А., Верхотурова Г.Н., Брусиловский Д.П. Методы и алгоритмы нерегулярной двухмерной упаковки объектов сложной геометрической формы: Деп. в ВИНИТИ, №682-В97.- М: 1997, 58с.

52. Верхотуров М.А., Верхотурова Г.Н. Метод псевдо оценок в задачах трехмерной упаковки// Проблемы оптимизации и экономические приложения: Тезисы конференции по математическому программированию, Омск: 1997.-С.40.

53. Верхотуров М.А., Мухачёва Э.А., Мартынов В.В. О методах решения задач фигурного раскроя в условиях единичного производства // Технология машиностроения: Сб. трудов международной конференции, Болгария, София, 1997.-С.З-9.

54. Верхотуров М.А., Мухачёва Э.А., Мартынов В.В. Методы рационального периодического размещения заготовок в штамповочном производстве// Технология машиностроения: Сб. трудов международной конференции, Болгария, София, 1997.-С. 10-17.

55. Верхотуров М.А., Верхотурова Г.Н. Некоторые особенности подсчета оценок в задачах трехмерной упаковки// Принятие решений в условиях неопределенности: Межвузовский сборник. Уфа: УГАТУ, 1997.-С.284-295.

56. Верхотуров М.А. Комбинаторные методы и алгоритмы для решения задач упаковки объектов сложных геометрических форм// Принятие решений в условиях неопределенности: Межвузовский сборник. Уфа: УГАТУ, 1997.- С.270-284.

57. Верхотуров М.А., Мухачёва Э.А., Мартынов В.В. Основные модели и методы задач раскроя упаковки// Межвузовский сборник научных статей306

58. УГАТУ, Уфа: УГАТУ,1997.-С.59-67.

59. Верхотуров М.А., Тархова JI.M. О применении остовного описания объектов для реализации компьютерной технологии фигурного раскроя // Вычислительная техника и новые информационные технологии: Межвузовский научный сборник. Уфа: УГАТУ, 1997.-С.88-93.

60. Верхотуров М.А., Верхотурова Г.Н. Особенности подсчета оценок в задачах трехмерной упаковки// Исследование операций: Тезисы международного конгресса EURO-XVI, Брюссель, 1998.-С.120.

61. Верхотуров М.А., Сергеева О.Ю. Некоторые комбинаторные алгоритмы для задач упаковки// Исследование операций: Тезисы международного конгресса EURO-XVI, Брюссель, 1998.-С.45.

62. Верхотуров М.А., Дьяконов Д.Б., Тархова J1.M. Об одном способе построения остова произвольного многоугольника// Прикладная и индустриальная математика: Тезисы третьего сибирского конгресса. Новосибирск: 1998.-С.60-61.

63. Верхотуров М.А., Мухачева Э.А., Сергеева О.Ю. Моделирование плотной упаковки геометрических объектов// Проблемы математики и теории управления. Межвузовский научный сборник, Уфа, 1998.-С.301-315.

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

65. Верхотуров М.А., Верхотурова Г.Н., Нугуманов А.Ш. Упаковка плоских геометрических объектов: постановка задачи и методы решения// Математическое программирование и приложения: Тезисы всероссийской конференции, Екатеринбург, 1999.-С.62-63.

66. Верхотуров М.А. О методе решения задачи нерегулярной упаковки плоских геометрических объектов// Вычислительная техника и новые информационные технологии: Межвузовский сборник научных трудов. -Уфа, 1999.-С.75-83.

67. Верхотуров М.А., Кардакова О.В., Логинов Е.В., Нугуманов А.Ш. О применении метода "simulated annealing" для решения задач нерегулярной упаковки// Интеллектуальное управление в сложных системах: Тезисы всероссийской конференции, Уфа, 1999.-С.19.

68. Верхотуров М.А. Классификация и методы решения задач упаковки геометрических объектов: Отчет по НИР (УГАТУ), ГР №01980010234.-М.: ВНТИЦ, 1999.-С.112-119, 133-135.

69. Вирт Н. Алгоритмы и структуры данных. -М: Мир, 1989, 360с.

70. Гавриш А.П., Ефремов А.И. Автоматизация технологической подготовки машиностроительного производства. Киев: Техника, 1982.- 215с.

71. Галактионова Н.Р. О программном обеспечении задач регулярного раскроя сложных форм//Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез.докл. Всесоюзной конференции.-У фа, 1987 .-С .44-45.308

72. Гамберг В.Я.,Липовецкий А.И., Петунии А. А. Автоматизация проектирования раскройных карт в условиях индивидуального производства//Кузнечно-штамповочное производство, 1982.-N3-C.26-27.

73. Гардан И., Люка М. Машинная графика и автоматизация конструирования.-М. Мир, 1987.-272с.

74. Герман К.Г., Мухачева Э.А. Принцип организации АСТП рационального раскроя материала в условиях гибкого автоматизированного производства .- Журн. Авиационная промышленность, 1979.№5-С.57-66.

75. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М. Мир, 1985. - 509с.

76. Гиль Н.И., Ещенко В.Г. Способ построения годографа вектор-функции плотного размещения для одного класса геометрических объектов-Харьков, 1977.-8с.-(Препринт/АН УССР, Ин-т пробл. машиностроения:63).

77. Гиль Н.И., Комяк В.М. Об одном подходе к построению годографа вектор функции плотного размещения плоских геометрических объектов, устойчивого к вычислительной погрешности.-Харьков, 1991.-23с.-(Препринт/АН УССР, Ин-т пробл. машиностроения:350).309

78. Гиль Н.И., Комяк В.М. Об одном способе формализации ограничений в задачах геометрического проектирования в R.- Харьков, 1992.-21с.-(Препринт/АН Украины, Ин-т пробл. машиностроения: 358).

79. Гиль Н.И., Черноморец А.А. Метод построения поверхности 0- уровня Ф-функции. Харьков, 1992.-29с.-(Препринт/АН Украины, Ин-т пробл. машиностроения: 359).

80. Гиль Н.И. Математическое моделирование нерегулярного размещения плоских геометрических объектов в системах автоматизации проектирования (теоретические основы, методы, приложения): Автореф.дис.докт.техн.наук.-Минск,1990.-32с.

81. Глушко А.Г., Рвачев B.J1. Об одной задаче оптимального раскроя. Журн. Кибернетика, 1967Д.-С.23.

82. Глушков В.М. Основы безбумажной информатики.2-е изд. М:Наука, 1987.-552с.

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

84. Грибов А. Б. Алгоритмы решения задачи плоского раскроя. -Кибернетика, 1973, N6.-C.33-42.

85. Гривачевский А.Г. Автоматизация проектирования технологической подготовки холодно штамповочного производства// Кузнечно-штамповочное производство, 1985. - N8. - С.28-30.

86. Громов Г.Р. Национальные информационные ресурсы: проблемы промышленной эксплуатации. М: Наука, 1984.- 240с.310

87. Гэри М.П., Джонсон Д.С. Вычислительные машины и трудноразрешимые задачи. М.; Мир, 1982. - 416с.

88. Данилевский Ю.Г. и др. Информационная технология в промышленности.-JI.Машиностроение. Ленингр. отд-ие, 1988.-283с.

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

90. Джамп Д. AutoCAD. Программирование.-М.:Радио и связь, 1992.- 336с.

91. Долгопольский Б.С., Бритарев К.Ф., Арцишевский Ю.Ю. Система автоматизированного проектирования на ЭВМ процессов холодной листовой штамповки// Кузнечно-штамповочное производство, 1979.-N6.-С.13-14.

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

93. Жак С.В. О методах решения задач, сочетающих эвристику и случайный выбор// Кибернетика, 1972.-N1.-C.119-121.

94. Загоруйко Н.Г. и др. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985.-213с,

95. Залгаллер В.А. Раскрой линейных материалов. Л.: Егоровец,-220с.

96. Залгаллер В.А. Рациональный раскрой как средство экономии материалов// Использование методов оптимизации в текущем управлении производством: Материалы Всесоюзной конференции, М.: 1980.-С.44-47.

97. Залгаллер В.А. Об одном необходимом признаке плотнейшего расположения фигур. Успехи матем. наук,1953.8.4.-С.23.311

98. Зангвил У.И. Нелинейное программирование. Единый подход.-М: Советское радио, 1973.-311с.

99. Зиндер Е. 3. Соотнесение и использование стандартов организации жизненных циклов систем// Системы управления базами данных, №3,1997.-С.41-46.

100. Зиндер Е. 3. Новое Системное Проектирование: информационные технологии и бизнес реинжиниринг //Часть 1 - СУБД №4, 1995 //. Часть 2 - бизнес - реинжиниринг//СУБД №1, 1996 //. Часть 3 - методы Нового Системного Проектирования//СУБД №2, 1996.

101. Иванов А.Н., Золотарев С.В. Построение АСУ ТП на базе концепции открытых систем// Мир ПК, №1,1998.-С.85-93.

102. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика.-М.:Радио и связь, 1995.-223 с.

103. Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования: Автореф.дисс. канд.техн.наук. Иошкар-Ола:МарПИ, 1993.-16с.

104. Ивлев К., Попова Т., Чекаленко Ю. Автоматизация процессов логистики// КомпьютерПресс, №11, 1997, С.245-250.

105. Ивлев К., Попова Т., Павлов JI. Реорганизация АСУ промышленных предприятий// КомпьютерПресс, №7, 1997, С.236-244.

106. Каневский М.В. Рациональный раскрой заготовок// Машиностроитель, 1982. -N5.-C.77-89.

107. Канторович J1.B. Математические методы в организации и планировании производства.-JL:ЛГУ, 1939.-60с.

108. Канторович Л.В. Методы рационального раскроя металла// Производственно техн. бюллетень. - М.-1942.-35с.

109. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование.-М:Экономика,1968.-96с.312

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

111. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов.- Новосибирск.: Наука СО, 1971.-320с.

112. Канторович Л.В.,Залгаллер В.А. Расчет рационального раскроя промышленных материалов.- Л.:Лениздат,1951.-199с.

113. Карасик Е.Б. Новый подход к решению задачи фигурного раскроя.-Баку, 1988.-18с.-Рукопись деп. в АзНИИНТИ, 12.05.88, N1032-Аз.

114. Кацев С.Б. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, №5 .-С. 139-141.

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

116. Колесников С.Н. Из истории автоматизации методологий управления предприятия// Открытые системы, №4, 1999, С.44-50.

117. Коллинз Г., Блэй Дж. Структурные методы разработки систем: от стратегического планирования до тестирования. -М: Финансы и статистика, 1986.-264с.

118. Компьютер и задачи выбора/Автор предисл.Ю.И.Журавлев.-М:Наука,1989.-208с.(Серия "Кибернетика неограниченные возможности и возможные ограничения").

119. Комяк В.М. Об одном подходе к построению допустимых вариантов размещения неориентированных объектов в заданной области. -Харьков, 1988.-19с.-(Препринт/АН УССР, Ин-т пробл. машиностроения: 270).

120. Комяк В.М. Математическое и компьютерное моделирование нерегулярного размещения плоских геометрических объектов в областях произвольной пространственной формы: Автореф.дисс. докт.техн.наук. -Харьков:ИПМаш,1996.-43с.

121. Корн Г., Корн Т.Справочник по математике.-М.:Наука,1984.-634с.313

122. Корницкая М. Н. Автоматизация проектирования карт фигурного нерегулярного раскроя в условиях единичного производства на основе апроксимационного подхода. -Дисс. на соискание ученой степени кандидата технических наук. Свердловск, 1993.- 202 с.

123. Корпоративная информационная система // Компьютер Пресс, №7, 1997.-С.216-222.

124. Кофман А. Введение в прикладную комбинаторику. М. : Наука, 1975.-187с.

125. Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982.-384с.

126. Кочетов Ю.А. Вероятностные алгоритмы локального поиска для задач дискретной оптимизации// Сибирская конференция по исследованию операций, 1998.-С.21-24.

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

128. Курицкий Б.Я. Оптимизация вокруг нас. Л.: Машиностроение, 1989.-144с.

129. Курс начертательной геометрии на базе ЭВМ. А.М.Тевлин, Г.С.Иванов, Л.Г. Нартова и др./Под ред.А.М.Тевлина.-М.:Высшая шк.,1983.-175с.

130. Левитин С.И., Самойлович Я.Б., Деречей Е.Г. Пути экономии цветных металлов. -М: Цветиздат, 1933.-65с.

131. Липаев В. В., Филинов Е. Н. Формирование и применение профилей открытых информационных систем// Открытые системы №5, 1997.-С.27-34.

132. Липовецкий А.И. К оптимизации свободного размещения прямоугольников. В кн.: автоматизация проектирования в машиностроении, Минск, 1985.-С.80-87.

133. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы314оптимального раскроя : Препринт. Свердловск : УрО АН СССР, 1988.-50с.

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

135. Магас С.Л. Методы решения экстремальных задач размещения многоугольных геометрических объектов в полосе. Автореф. Дис. . канд. физ.- мат. наук.- М., 1984.-16с.

136. Мартин Дж. Планирование развития автоматизированных систем.-М: Финансы и статистика, 1984.-196с.

137. Мартынов В.В. Аппроксимация плоского контура многоугольником при решении задач оптимизации размещения деталей обводообразующей оснастки//Начертательная геометрия и машинная графика в практике решения инженерных задач.-Омск:ОмПИ: 1988.-С.73-78.

138. Мартынов В.В. Об одном алгоритме определения областей допустимых размещений геометрических объектов /Принятие решений в условиях неопределенности//Межвузовский научный сборник. Уфа: УГАТУ, 1996.-С.10-17.

139. Математическое обеспечение расчетов линейного и прямоугольного раскроя: Материалы Всесоюзного семинара 22-27 июня 1980г.Уфа: У АИД 981.-179с.

140. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Материалы Всесоюзной конференции 15-17 июня 1987.Уфа: УАИ, 1988.-159с.

141. Моденов П.С., Пархоменко А.С. Геометрические преобразования. М: МГУ, 1961. -232с.

142. Мухачева Э.А. Поиск рационального решения в двухкритериальной задаче гильотинного раскроя. Новосибирск: Оптимизация 33, Новосибирск, СО АН СССР, 1983.-С.56-63.

143. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. М.: Машиностроение, 1984.-176с.315

144. Мухачёва Э.А., Ибатуллина С.М. Оптимизация раскроя материала в заданном ассортиментном отношении. Оптимизация 34 (51), Новосибирск, СО АН СССР, 1984.-С. 122-128.

145. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука СО, 1987.-272с.

146. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя упаковки геометрических объектов. - УГАТУ, Уфа: 1998.-217с.

147. Новожилова М.В. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств. Харьков, 1988.- 48с. - (Препринт /АН УССР. Ин-т пробл. Машиностроения: №292).

148. Норенков И.П. Введение в автоматизированное проектирование тех нических устройств и систем.-М.:Высш.шк., 1986.-304с.

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

150. Ойхман Е.Г., Попов Э.В. Реинжиниринг бизнеса. М.: Финансы и статистика, 1997.-157с.

151. Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.:Радио и связь, 1986.-400с.

152. Панкратов А.В., Пономоренко Л.Д. Линейная невыпуклая модель и метод локальной оптимизации в задачах упаковки выпуклых многогранников.-Харьков, 1987.-28с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №269).

153. Панкратов А. В., Пономаренко Л.Д. Оптимизационная задача упаковки многогранников (линейная модель и метод решения)// Автоматизированные системы управления и приборы автоматики.-1987.-Вып. 83.-С.14-19.

154. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. -М.:Мир,1985.-432с.316

155. Пономаренко Л.Д., Туранов И.Н. Оптимальная упаковка параллелепипедов: модель, метод и алгоритм. Харьков, 1984.-51с,-(депон. в ВИНИТИ, №4075-84).

156. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение.-М.Мир, 1989.-478с.

157. Пустыльник Г.М. Растровый метод реализации геометрических моделей на ЭВМ//Управляющие системы и машины,-Киев:Наук.думка,1986.1.-С.110-112.

158. Рвачев В.Л. Теория R-функций и некоторые ее приложения. Киев: Наук, думка, 1982.-5 50с.

159. Рвачев В.Л. Геометрические приложения алгебры логики.- Киев: Техника, 1967.-212с.

160. Рвачев В.Л., Стоян Ю.Г. К вопросу об оптимальном раскрое материалов.- В кн.: Вопросы теоретической кибернетики. Изд. Ин-та кибернетики АН УССР, Киев, 1965.-С.30-42.

161. Рвачев В.Л., Стоян Ю.Г. Алгоритм построения неравенств, которым удовлетворяют параметры размещения непересекающихся тел.-Кибернетика, 1966, 5.-С.43-53.

162. Рвачев В.Л., Стоян Ю.Г. К задаче об оптимальном размещении круговых выкроек. Кибернетика, 1965, 4.-С.66-78.

163. Реклейтис Т. Оптимизация в технике. -М.: Мир, 1986.т.1-349с., т.2-320с.

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

165. Роджерс Д. Алгоритмические основы машинной графики /Пер.с англ.-М. Мир, 1989.-512с.

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

167. Савлов С.Ф. Построение нерегулярных укладок неориентированных многоугольников// Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Материалы Всесоюзной конференции.- Уфа, 1988.-С.118-120.

168. Сеа Ж. Оптимизация. Теория и алгоритмы. М. :-Мир, 1973 .-312с.

169. Сергеева О.Ю. Численные методы плотной упаковки плоских геометрических объектов на базе интерпретации оценок J1.B. Канторовича. Дисс. на соискание ученой степени кандидата физ.- мат. наук. - Уфа, 1998.-143с.

170. Системы автоматизированного управления // Открытые системы, №2, 1998.-С.26-53.

171. Скатерной В.А. Оптимизация раскроя материалов в легкой промышленности. М.: Легпромбытиздат, 1989.-144с.

172. Смирнов С.В. и др. Управление машиностроительным предприятием.-М.:Высш.шк.,1989.-240с.

173. Стоян Ю.Г. Об оптимальном размещении геометрических объектов: Автореф.дис.докт.техн.наук.-М. МАИ, 1970.-Збс.

174. Стоян Ю.Г. Размещение геометрических объектов. Киев, Наукова думка, 1975.-217с.

175. Стоян Ю.Г., Винарский В.Я. Устойчивость и методы регуляризации преобразований геометрической информации.- Харьков, 1983.-44с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №184).

176. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наук, думка, 1976. -247с.

177. Стоян Ю.Г., Новожилова М.В. Метод поиска локального экстремума в задаче размещения многоугольников в полосе. Харьков, 1987.-24с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №263).318

178. Стоян Ю.Г., Новожилова М.В., Карташов А.В. Матиматическая модель и оптимизация линейных Ek(R ) задач размещения. - Харьков, 1991.-44с,-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №353).

179. Стоян Ю.Г., Панасенко А.А. Периодическое размещение геометрических объектов. Киев: Наук, думка, 1978. -178с.

180. Стоян Ю.Г., Соколовский В.З. Решение некоторых задач методом сужающихся окрестностей. Киев: Наук, думка, 1980.-206с.

181. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев. : Наук, думка, 1986. -286с.

182. Тарасов В.Б. Новые стратегии реорганизации и автоматизации предприятий: на пути к интеллектуальным предприятиям. Новости искусственного интеллекта. 1996. №4.-С.40-84.

183. Тарасов В.Б. Предприятия XXI века: проблемы проектированияи управления// Автоматизация проектирования, №4, 1998.-С.45-50.

184. Таха X. Введение в исследование операций. -М.: Мир, 1985, т. 1-279с., т.2-496с.

185. Томарченко Л.И. Опыт организации безостаткового раскроя. Легкая промышленность, 1941,1 .-С. 19-26.

186. Тот Ф.Л. Расположения на плоскости, на сфере и в пространстве.-М. :Физматгиз, 1958.-363с.

187. Управление машиностроительным предприятием/ под ред. С.Г.Пуртова и С.В.Смирнова. -М.: Высшая школа, 1989.-240с.319

188. Фаддеев Д.К., Фаддева Д.Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963.-453с.

189. Федоров Е.С. Начала учения о фигурах. Записки Мин. Общества, 2-я серия, 1885, 21.-С. 1-289.

190. Федоров Е.С. Симметрия и структура кристаллов. Изд-во АН СССР, М., 1949.-154с.

191. Фесенко А.Г. Решетчатая укладка плоских геометрических объектов с поворотом на угол п. Киев: Ж АН УССР, 1980.- 23 с. - /АН УССР. Ин-т кибернетики: Препринт - 80-53.

192. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. М.: Мир, 1982. -304с.

193. Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. М.-.Наука, 1966.-416с.

194. Чебышев П.Л. О кройке одежды. Журн. Успехи матем. наук, 1946,С. 27.

195. Черноморец А.А. Математическая модель и метод решения задачи размещения трехмерных многогранных объектов: Автореф.дисс. канд.техн.наук. Харьков:ИПМаш, 1993.-16с.

196. Шавырин Н.В. Раскрой ткани без остатка. Швейная промышленность, 1940,2.-С.49-57.

197. Шехтман Л.И. Линейный алгоритм решения задачи регулярной трехмерной упаковки.//Принятие решений в условиях неопределенности. -Уфа, 1996.-С.38-40.

198. Шехтман Л.И., Мухачева Э.А. Применение метода оценок для решения задачи трехмерной регулярной упаковки.//Принятие решений в условиях неопределенности. -Уфа, 1996.-С.82-84.

199. Шкурба В.В., Саенко Ю.И.О решении задач оптимального раскроя. -Журн.Вестник машиностроения,1965.-С.27-37.

200. Шпур Г., Краузе Ф.-Л. Автоматизированное проектирование в320машиностроении.-М. Машиностроение, 1988.-648с.

201. Якунин В.И. Геометрические основы САПР технических поверхностей. -М.: МАИ, 1980.-86с.

202. Aarts Е., Lenstra J.K. (eds.) Local search in combinatorial optimization, John Wiley & Sons Ltd, 1997.-315p.

203. Aarts L., Van Laarhoven P. Statistical cooling: a general approach to combinatorial optimization problems, Philips J.Res 40, pp. 193-226, 1985.

204. Abdou, G., Yang, M. A Sistematic Approach for the Three-Dimensional Palletization Problem.//International Journal of Production Research, 32, №10,1994, pp.381-394.

205. Adamowicz M., Allano A. Nesting Two-dimensional shapes in rectangular modules. Comput. Aided Des., 1976, 8,Nl,pp.27-33.

206. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. Annals of OR, 41(1-4), pp.313-325, 1993.

207. Brooks R. L., Smith С. А. В., Stone A. H., Tutte W. T. The dissection of rectangles into squares. Duke Mathematical Journal 7, 1940, pp.312-340.

208. Cagan J., Degentesh D., Yin S. A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout-Computer Aided Design, Vol.30,No.10,1998, pp.781-790.

209. Cerny V. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Opt. Theory Appl., 45, 1985, pp.41-51.

210. Chen, C.S., Lee, S.M., Shen, Q. S. An Analitical Model for the Container Loading Problem./ International Transactions in Operational Research, Vol.80,1995, pp.68-76.

211. Cheng C.H., Feiring B.R., Cheng T.C.E. The cutting stock problem a survey, Int. J. Production Economics 36, 1994, pp.291-3 05.

212. Christofides, N. and Whitlock, C. An algorithm for the two dimensional cutting problems. Oper. Res., 25: pp.30 - 44.321

213. Coffman E., Shor P. Packing in two dimensions: asymptotic average-case analysis of algorithms, Algorithmica, 9, 1993, pp.253-277.

214. Customer Synchronized Resource Planning: Become indispensable, Catherine de Rosa, APICS.-75p.

215. Daniels K., Li Z., Milenkovic V.J. Automatic marker making, in: Proc. 3rd Canadian conf. On Computational geometry, ed. T.Shermer, August, 1991.pp. 11-24.

216. Daniels K., Milenkovic V.J. Multiple translational containment, part I: an approximation algorithm.- Algorithmica special issue on Computational geometry in manufacturing, 1994, 46p.

217. Daniels K., Milenkovic V. J. Multiple Translational Containment: Approximate and Exact Algorithms /Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms.- San Francisco, CA, January 22-24, 1995, pp.205-214.

218. Dorigo M., Gambardella L.M. Ant colonies for the traveling salesman problem. BioSystems, 43, pp.73-81.

219. Dowsland K.A. Some experiments with simulated annealing techniques for packing problems, EJOR, 68, 1993, pp.389-399.

220. Dowsland K.A., Dowsland W.B. Solution approaches to irregular nesting problems, EJOR, 84(3), 1995, pp.506-521.

221. Dueck G. New optimization heuristics, J.Comp. Phys. 104, 1993, pp.86-92.

222. Dueck G. Scheuer T. Threshold accepting : a general purpose optimization algorithm appearing superior to simulated annealing. J.Comp.Phys., 1990,90р.

223. Dycknoff H. A typology of cutting and packing problems. F.R.Germany., 1991,-41p.

224. Dyckhoff, H. Scheithauer, J. Terno. Cutting and packing : An annotated bibliography. Technical Report MATH-NM-08-1996, TU Dresden, 1996.-3 5p.

225. Faigle U., Kern W. Some convergence results for probabilistic tabu search. ORSA Journal on Computing 4(%),pp.32-37,1992.322

226. Feo T.A., Resende M.G.C. Greedy randomized adaptive search procedures. Journal of Global Optimization, 1995.6:pp. 109-133.

227. Ferreira J.S., Oliveira J.F. Algorithms for nesting problems, in "Applied simulated annealing." Berlin, Springer, ed. R.V.Vidal, 1993, pp.255-273.

228. Folkenauer E. The grouping genetic algorithms for Bin-Packing. JORBEL-Belgian Journal of Operations Research, Statustics and Computer Science, 1995, vol 35, pp.64-88.

229. Fortune S., Milencovic V. Numerical stability of algorithms for line arrangements, 7-th annual ACM SCG, 1991, pp.334-341.

230. Fraser, H.J., George, J.A. Integrated Container Loading Software for Pulp and Paper Industry.//EJOR, 77, 1994, pp.466-474.

231. Freeman, H. and Shapira, R. Determining the minimum area encasing rectangle for an arbitrary closed curve, Comm.ACM.18(7), pp.409 - 413 (1975).

232. Gehring H., Bortfeldt A. A Genetic Algorithm for Solving the Container Loading Problem. // International transactions in Oper. Res. 1997, vol.4, № 5/6, pp.401-418.

233. George, J.F. A Method for Solving Container Packing for a Single Size of Box./Journal of the Operational Research Soviety,Vol.43,№4,1992,pp.307-312.

234. Gilmore P.C., Gomory R. E. A linear programming approach to the cutting stock problem (Part I/II). Oper. Res. 9, p.849-859, and Oper. Res. 1961/63. 11, pp.863-888.

235. Gilmory P.C., Gomory R.E. Multistage cutting stock problem of two and more dimensions.: Oper.Res., 1965, 13, pp.94-120.

236. Gilmore P. C., Gomory R. E. The theory and computation of knapsack functions. Oper. Res, 1966,14, pp. 145-175.

237. Glover F. Tabu search part I, ORSA Journal on Computing 7(3), pp. 190206, 1989.323

238. Glover F. Tabu search part II, ORSA Journal on Computing 2(1),pp.4-32, 1990.

239. Glover F., Laguna M. Tabu search in modern heuristic techniques for combinatorial problems, Blackwell Publishing, 1992.-144p.

240. Goldberg D. Genetic algorithms in search, Optimization and machine learning, Adision-Wesley publ., 1989.-99p.

241. Guibas L., Ramshaw L., Stolfi J. A kinetic framework for computational geometry, IEEE Annual Symposium on Foundations of Computer Science, vol.24, 1983, pp. 100-1

242. Haessler, R.W. Cost Minimization of Multiple-Vehicle Shipment./SICUP-Bulletin №9, January 1993, pp.2-3.

243. Heckmann R., Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry.- Annals of OR, 57, pp.103-133, 1995.

244. Heckmann R., Lengauer T. Computing closely matching upper and lower bounds on textile nesting problems. European Journal of Operational Research, 108, 1998, pp.473-489.

245. Heesch H., Kinzle O. Fluchenschlub System der Formen luckenlous aneinanduschliebenden Flachenteile. Berlin -Heilberg, 1963.-105p.

246. Heesch H. Zur Klassification der ebenen kongruenten Abbildungen.- Der Mathem. und Natirwiss.Untersicht. 1959/60, 12, l.-34p.

247. Heesch H. Der topologisch gleichwertige Kristallein -dungen.- Zeitschrift fur Kristallographic., 1933/84, 5, 6. -27p.

248. Heistermann J., Lengauer T. The nesting problem in the leather manufacturing industry. European Journal of Operational Research, 57, 1995, pp.147-173.

249. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975.-96p.324

250. Ikonen I.T., Biles W.E., et al. Concept for a genetic algorithm for packing three dimensional objects of complex shape, Proceedings of the first online workshop of soft computing, 1996.-pp. 12-24.

251. Ikonen I.T., Biles W.E. Three dimensional chromosomal representation for a genetic algorithm for packing non-convex parts in 3D, Proceedings of the 3NWGA, Helsinki, Finland, 1997, pp. 101-119.

252. Kaul A., O'Connor M., Srinivasan V. Computing Minkowski sums of regular polygons, Proceedings of the 3rd Canadian Conference on Computational geometry, Vancouver, ВС, 1991.-pp.45-54.

253. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing, Science 220, 1983, pp.671-680.

254. Li Z., Milenkovic V. J. Compaction and Separation Algorithms for Nonconvex Polygons and Their Applications. // EJOR, 84:pp.539-561, 1995.

255. Laarhoven P., Aarts L. Simulated annealing: theory and applications. -Boston,Kluwer Academic Publishers, 1987. -67p.

256. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles // EJOR, 1999, 112, pp.413-420.

257. Lutfiyya H., McMillin В., Poshyanonda P., Dagli C. Composite stock cutting through simulated annealing.- Tech. report numbers CSC 91-09 and ISC 91-04, University of Missouri at Rolla, Rolla,50p.,1991.

258. Metropolis, N., Rosenbluth A., Rosenbluth M., Teller, A. and Teller, E., "Equation of State Calculations by Fast Computing Machines" J. Of Chem. Physics, 21, 1953, pp. 1087-1092.

259. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming.-ITOR special issue with papers from IFORS'96, 1996, 30p.

260. Milenkovic V.J. Multiple translational containment, part II: exact algorithms.- Algorithmica special issue on Computational geometry in manufacturing, 1994, 40p.

261. Milenkovic V.J. Rotational polygon overlap minimization.- Computational geometry: theory and application, 1997, 16p.

262. Minkowski H. Volumen und oberflache. Mathematische annalen, 57:pp.447-495, 1903.

263. Mohanty, B.B., Mathur, K., Ivancic, N.J. Value Consideration in Three-Dimensional Packing-A Heuristic Procedure Using the Fractional Knapsack Problem// EJOR, 74, 1994, pp.143-151.

264. Morabito, R., Arenales, M. An AND/OR-Graph Approach to the Container Loading Problem.//International Transactions in Oper.Res,l,№ 1,1994,pp.59-73.

265. Mukhacheva E.A., Zalgaller W.A. Linear programming cutting problems: International Journal of Software Engineering and Knowledge Engineering. Vol.3., N4(1993), pp.463-476.

266. Ngoi, B.K.A., Tay, M.L., Chua, E.S. Applying Spatial Represention Techniques to the Container Packing Problem.// International Journal of Production Research, 32, №1, 1994, pp.111-123.

267. Perry E.C., Landon M.D., Balling R.J. Spatial packaging of complex parametric solid objectives via optimization.- EDMI. Report 89-9, Engineering Design Methods Labs., Bringham University, 1989.-5 lp.

268. Portmann, M.-C. An Efficient Algoritm for Container Loading./Working Paper, 1990, pp.23-25.326

269. Rayward V.J., Osman I.h., ets al. (eda) Reactive search: toward self-tuning heuristics, Modern heuristic search methods, J.Wiley and sons ltd, 1996,61 p.

270. Reeves C. Hybrid Genetic Algorithms for Bin-packing and Related Problems, submited to Annals of OR "Metaheuristics in Combinatorial Optimization, G.Laporte and I.H. Osman (Eds), Baltzer, Bazel, 1995.-pp.32-43.

271. Serra J. Image analysis and mathematical morphology, vol.1, Academic press, New York, 1982.-123p.

272. Sha E.L. Area efficient and volume efficient algorithms for loading cargo, master's thesis (unpublished), US Navy Post-Graduate School, 1970.-188p.

273. Scheithauer,G. Algoritm for the Container Loading Problem./Operations Research Proceedings 1991, Springer-Verlag, Berlin/Heidelberg 1992(ISBN 3540-55410-6), pp.445-452.

274. Szykman S., Cagan J. A simulated annealing-based approach to three-dimensional component packing.- ASME Journal of Mechanical Design, Vol.117, No.2(A), 1995, pp.308-314.

275. Szykman S., Cagan J. Constrained three dimensional component layout using simulated annealing.- ASME Journal of Mechanical Design, Vol.119, No.l, 1997, pp.28-35.

276. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre prakti-sche. Losung.- Leiprig, 1987, -pp.207-217.

277. Takayuki Osogami Approaches to 3D free-form cutting and packing problems and their applications: a survey.- Research report RT0287, IBM Japan, 1998, 12p.

278. Tinarelli U., Addonizio M. Un problema di caricamento di containers, Proc. AIRO congress, 1978.-pp.79-91.

279. Udy J.L., Balling R.J., Benzley S.E., Landon M.D. Computation of interferences between three-dimensional objects and the optimal packing problem. Advances in Engineering Software, Vol.10, No.l, 1988, pp.8-14.