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

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

где - невыполненные за предыдущую смену(смены) заказы, их штрафы =, где - функция увеличения штрафа за невыполнение j-го заказа.

Таблица 1. Оценки эффективности для задачи планирования загрузки уникального оборудования на рабочую неделю

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

Задача планирования решалась при помощи алгоритма с базой опыта [4]. Данный алгоритм позволяет сохранять хорошие найденные решения, что актуально в случае перехода части невыполненных заказов на следующую смену. Для оценки качества решения, получаемой при помощи указанного метода, использовались верхняя и нижняя оценка соответствующей задачи о ранце. В качестве верхней оценки (Upper) получаемого решения рассматривалось решение линейной задачи о ранце, нижней (Low) - решение дискретной по методу Данцига [11]. При этом верхняя оценка может быть недостижимой для дискретной задачи о ранце.

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

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

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

Таким образом, необходимо решить две задачи: составление оптимального плана работы на смену , упорядочивание заказов , где порядок выполнения заказов. Здесь применим один из жадных подходов: упорядочим заказы, составляющие оптимальный план, по не убыванию их относительной полезности (2).

(2)

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

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

Рис. 1. График адаптации решений для задачи оперативного управления загрузкой уникального оборудования.

На графике (рис.1) также представлены верхняя и нижняя оценка для решаемой задачи. В качестве верхней оценки (Upper) выступает решение линейной задачи о ранце, нижней (Low) - решение дискретной по методу Данцига.

Таблица 2. Оценки полученного решения для задачи оперативного управления.

Таблица 2 представляет усредненные отношения лучшего найденного решения к нижней оценке (Low) и к верхней оценке (Upper) при внесении 5 изменений в план загрузки оборудования за смену и при внесении 10 изменений в план загрузки оборудования за смену. Полученные результаты позволяют говорить об устойчивости модели и ее адекватности реальной производственной задаче.

Литература