Оптимизация производственного расписания

Оптимизация производственных расписаний

В этой статье мы разберем задачу по оптимизации производственных расписаний составим математическую модель оптимизации производственных расписаний и решим ее с помощью линейного программирования.Трудно переоценить  важность методик позволяющих производить оперативное оптимальное планирование. Они используются для планирования производств( так называемые MES технологии),  в планировании крупных проектов, при распределенных вычислениях в много процессорных компьютерах.
Задача  оптимизации производственных расписаний в общем виде не решена.
В данной работе была исследована возможность формализации задачи производственного расписания  в терминах задачи линейного программирования.В качестве критерия оптимизации в задаче было выбрано суммарное время выполнения всех задач всеми исполнителями. Соответственно мы должны так распределить исполнителей по задачам , чтобы общее время выполнение всех задача было минимальным. Разумеется, это не один возможный критерий оптимизации, в нашей работе мы выбрали этот критерий как наиболее часто встречающийся в практике. Как правило, задачи оптимизации производственных расписаний решаются в сложных дорогостоящих расчетных MES комплексах с помощью эвристик или с помощью генетических алгоритмов. 
В России  оперативное производственное планирование наиболее полно реализовано в программном комплексе  Фобос. Данный программный продукт позволяет строить оптимальное  производственное распивание для машиностроительных предприятий. Оптимизация расписания в программе производится с помощью  эвристик и генетических алгоритмов.
Оптимизация расписаний позволят наиболее плотно загрузить оборудование, сократить общее выполнение задач до 10 % по сравнению с ручным  планированием.Особо следует отметить, что в отличии любые эвристики  и генетические алгоритмы не дают абсолютно оптимального решения, кроме того часто они приводят к  локальным экстремумам.  
Поэтому,   так актуальны любые методики оптимизации производственных расписаний, которые можно свести к с хорошо сходящимся алгоритмам, например, алгоритму линейного программирования или к алгоритмам бинарного программирования.  Конечно, данные задачи будут иметь большую размерность, но с колоссальным ростом производительности современных компьютеров эта трудность становится преодолимой.
Цель исследования: формализация задачи оптимизации производственного расписания в терминах линейного (бинарного) программирования. Создание расчетного модуля в Excel, реализующего построенную модель
Объект исследования: задача оптимального производственного расписания. 
Предмет исследования: математическая модель производственного расписания расчётный модуль Excel, реализующий построенную модель

 Математическая модель оптимизации расписаний средствами линейного программирования

В нашей задаче  исполнителями являются процессоры. Имеется ряд параллельных задач. Необходимо составить оптимальное расписание для полного выполнения всех задач за минимальное время. Проблема  может быть решена в общем виде для любого количества процессоров и задач, но для наглядности в нашем примере оптимального расписания мы рассмотрим  5 задач, которые выполняются 3 процессорами (исполнителями).
Разобьем общий интервал времени на равные промежутки (в нашем случае для наглядности мы взяли 5). Условимся, что каждый из процессоров в каждый промежуток времени может
работать только над одной задачей, и в установленный промежуток времени выполняет  объем работы равный единице. 
Критерием оптимальности нашей задачи будет минимум общего времени выполнения всех задач. Каждому промежутку времени  мы присваиваем свой вес t. Более поздним промежуткам времени присваивается больший вес.
     Введем переменные:
Atij – бинарная матрица решения, где i – номер задачи, j – номер процессора, t – номер промежутка времени. Если Atij=1, то это значит, что в момент времени t j-ый процессор выполняет i-ую задачу. Если Atij=0, то не выполняет.
n – Количество задач (в примере n=5)
Vi – размер (объем) i задачи
m – Количество процессоров (в примере m=3)
Cj – производительность (мощность) j процессора
t – Номер промежутка времени (в примере количество промежутков равно 5)
    Задание основные условий и уравнений модели:
Условие на выполнение (перевыполнение) i задачи:   
Условие о работе процессора j в промежутке t только над одной задачей:  , Atij равно 0 или 1.
Целевая функция  включает полную загрузку процессоров в каждый промежуток времени. Так как  вес  более поздних промежутков возрастает  то стремление к минимуму данной целевой функции обеспечит нам наиболее полную загрузку более ранних промежутков времени  и соответственно уменьшит общее время выполнения всех задач
Итак наша целевая функция стремится к минимуму:
Разработанная методология может быть применена для оптимизации планов крупных проектов. А именно оптимизация календарных графиков, сокращение критического пути проекта. Данная задача является очень актуальной так, как количество крупных инновационных проектов стремительно растет, при этом отсутствует  математическая методология оптимального планирования календарных графиков крупных проектов.
Также данную методику можно применить для решения параллельных задач в многопроцессорных компьютерах. По сути, тестовый пример в нашей работе  был приведен для решения такой задачи.

Литература по линейному программированию

Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования.
Гасс С. Линейное программирование.
Зуховицкий С.И., Авдеева Л.И. Линейное программирование.
Юдин Д.Б., Гольштейн Е.Г. Линейное программирование.

Вернуться к содержанию

Поделиться: