WEB-ресурс научно-практических конференций

Белкина И.А., д. т. н. Пистунов И.Н.

Национальный горный университет, г. Днепропетровск

ПРИМЕНЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ДЛЯ МИНИМИЗАЦИИ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОИЗВОДСТВЕННЫХ ОПЕРАЦИЙ

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

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

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

1) каждая машина (станок) эксплуатируется в течение периода времени, т. е. исключается остановка или поломка маши­ны;

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

3) на участке имеется только один станок данного типа;

4) следующая операция на этом же станке может выполняться только после полного завершения предыду­щей ;

5) каждый станок в данный момент времени может выполнять не более одной операции.

Далее представлена модель загрузки станков, параметрами которой являются:

M – разнообразие станков в цехе, C ^k ij , i=1...N, j=1…T – матрица издержек за час работы k -го вида станка, где C ij – матрица издержек обработки i -го вида продукции в j -й час работы станка. В данной работе будет рассмотрен случай, когда в цехе имеется по одному станку каждого типа, т.е. выполняется условие 3. X ^k ij – матриця переходів з компонентами : X ^k ij = 1, если k –й станок обрабатывает i -й вид продукции в j -й час, k =1... M , X ^k ij = 0, если не обрабатывает, V ^k ij – матрица заказа ( определяет количество часов, необходимых для обработки i -го вида продукции на k -м станке)

Тогда задача минимизации времени на изготовление единицы продукции может быть сформулирована так:

. (1)

Ограничения:

, (2)

, j = 1… T , (3)

. (4)

Ограничение (2) – матрица собственно обработки i -го вида продукции в j -й час на k – ом станке, элементами матрицы являются булевы функции (1, если обрабатывает; 0, если не обрабатывает). Получение оптимальным образом скомпонованной матрицы обработки является целью задачи. Ограничение (3) означает, что количество часов в течени и которого обрабатывался i -й вид продукции на k – ом станке должен строго соответствовать технологи (заказу).

Ограничение (4) актуально, если имеется только один станок k –ого типа, способный надлежащим образом обработать продукт, т.е. выполняются условия 3 и 5. В случае , если в цеху имеется более, чем одна машина данного типа, либо станок способен одновременно обрабатывать более, чем одну единицу продукции, в правой части ограничения (4) указываются соответствующая пропускная способность станка/станков (дискретно).

Таким образом, задача планирования графика сводится к тривиальной транспортной задаче. При такой постановке задаче, представляется возможным ввести дополнительные ограничения F _i ( x ) i=1... N , экономическим смыслом которых является премия за досрочное изготовление i -го продукта:

. (5)

В этом выражении:

, (6)

Очевидно, что введение в задачу F _i ( x ), должно улучшать решение задачи. Таким образом, a _i - отрицательное число, исходя из того, что целевая функция (5) стремится к минимуму.

Необходимо отметить, что применение нумерации станков и связанная с этим матрица C ij позволяет , если это необходимо, задавать технологическую последовательность обработки продукта на разных станках.

Литература:

1. Исследование операций : В 2 - х томах. Пер. с англ./ Под ред . Дж . Моудера , С. Элмаграби . – М.: Мир, 1981. Т .2. - 712 с.