МАПП — модель автоматизированного планирования производства¶

МАПП (модель автоматизированного планирования производства) — математическая модель и метод планирования загрузки производственных ресурсов, разработанная в СССР в 1970-х годах в Институте управления народным хозяйством (ИУНХ) АН СССР под руководством В. С. Михайлова. МАПП предназначена для определения оптимального или близкого к оптимальному графика выполнения заказов на производственной системе с учётом ограничений по ресурсам, срокам и технологическим маршрутам. Модель является одним из наиболее известных отечественных достижений в области автоматизированного планирования и управления (АСУП) и применяется в задачах диспетчеризации производства.

¶История создания

Работы по созданию МАПП начались в конце 1960-х — начале 1970-х годов в лаборатории моделирования промышленных систем ИУНХ АН СССР. Руководителем направления был Виктор Степанович Михайлов — математик, один из основоположников советской науки об управлении, впоследствии академик и вице-президент АН СССР.

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

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

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

В классической постановке МАПП решает задачу, близкую к обобщённой задаче о назначениях и задаче о расписании (job-shop scheduling). Исходные данные включают:

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

Целевая функция, как правило, направлена на минимизацию суммарного срока изготовления всех заказов (makespan), максимизацию пропускной способности или минимизацию простоев. Задача в общем виде является NP-трудной, поэтому для практических размеров применяются эвристические и приближённые алгоритмы, обеспечивающие получение достаточно хороших решений за приемлемое время.

¶Алгоритмы и методы решения

В МАПП используются комбинаторные алгоритмы поиска расписания. Основные подходы включают:

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

Известные эвристики, применявшиеся в МАПП и смежных системах, включают правила типа SPT (Shortest Processing Time — кратчайшая операция первой), EDD (Earliest Due Date — ближайший срок первой) и их модификации с учётом загрузки ресурсов.

¶Применение

Основными областями применения МАПП стали:

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

Модель легла в основу ряда отечественных систем автоматизированного планирования, разрабатывавшихся в 1970–1980-е годы для предприятий Советского Союза. Результаты исследований по МАПП публиковались в трудах ИУНХ АН СССР и нашли отражение в монографиях по теории планирования производства.

¶Значение

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

Источники:

• Михайлов В. С., Цыпкин Ю. А. «Автоматизированное планирование производства»
• Труды Института управления народным хозяйством АН СССР
• Герасименко В. В., Федоров В. Г. «Планирование производства на машиностроительных предприятиях»
• Ковалёв Г. М. «Математические методы планирования производства»