Исследование и разработка средств для решения 1D-CSP задачи в информационной среде

предприятий

Д.Н. Малышев,
аспирант кафедры «Прикладные информационные технологии»

МФТИ, г. Долгопрудный

Г. Г. Андреев,
директор центра ПКТ,
к.т.н., доцент,
МФТИ, Долгопрудный

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

Данному типу задач принадлежат задачи 1D, 2D и 3D раскроя/упаковки, (Cutting Stock Problem). Особенностью данной задачи является то, что задачи этого типа принадлежат к классу NP-задач, и несмотря на большое количество исследований [1-3], посвященных данной теме, в ряде случаев остается необходимость разработки эффективных и практически применимых методов решения данной задачи.

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

Для выполнения изложенных требований был разработан программный комплекс для решения одномерной задачи (1D-CSP). Данная разработка включает в себя следующие модули:

· Модуль ввода информации для формирования карт кроя.

· Расчетный модуль.

· Модуль «виртуального» склада.

· Настраиваемую систему генерации отчетов.

· Создание обменных файлов.

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

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

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

Высокая степень интегрируемости данного комплекса в информационную среду предприятия обусловлена следующим:

· Предоставляет возможность выбора хранилища данных.

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

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

Апробация представленной технологии проводилась на предприятиях легкой промышленности РФ.

Литература

1. Л.В. Канторович, В.А. Залгаллер, Рациональный раскрой промышленных материалов;

2. P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting-stock problem, Operations Research: Part 2, 11(6) (1963), 863–888;

3. Б.Н. Белов, А.С. Мухачева, Проектирование одномерных раскроев с использованием нерпрерывной релаксации и метода секущих плоскостей. УГАТУ.