Оптимизация технологического потока многоассортиментного производства хлебных изделий
УДК 641
Оптимизация технологического потока многоассортиментного производства хлебных изделий
Косачев В.С., Кошевой Е.П., Сергеев А.А., ep-koshevoi@mail.ru Кубанский государственный технологический университет
В работе дается оценка оптимального расписания производства многоассортиментных хлебных изделий конвейерным производством на группе машин. Сформулирован ряд критериев оптимальности. Для решения задачи применен алгоритм вращения.
Ключевые слова: технологический поток, многоассортиментное
производство, оптимальное расписание
Решение задач упорядочения большой размерности для технологического потока [1] и гибких производств [2] может осуществляться путем сведения их к более простым задачам с использованием определенных условий и допущений. Наиболее часто задачи упорядочения встречаются при календарном планировании работы цехов и предприятий. В теории расписаний [3,4] рассматривается большое число модельных задач оптимального планирования простого процесса обслуживания. Их формальные постановки и численные методы решения определяются выбором критерия оптимальности и показателями процесса обслуживания. В работе предлагается метод многокритериальной оптимизации задачи краткосрочного планировании работы хлебозавода на примере реального хронометража, данные по которому представлены ниже (Таблица 1).
Возможное изменение длительности расписаний на последовательном множестве машин, если все длительности обработок равны, может быть вычислено по формуле:
T t, n, m t n m 1 t
(1)
где t - время выполнения одной работы (размах отсутствует); n количество обрабатываемых материалов; m - число стадий обработки. При подстановке обработки минимальной и максимальной длительностей работ из матрицы расписания получаем соответственно sup T и inf T на основе этих показателей:
sup T n, m max ti, j n m 1 max ti, j
(2)
inf T n, m min ti, j n m 1 min ti, j
Таблица 1 Длительности производственных стадий
Материалы
(3)
время Круассаны Русская коса 0,35 кг Сдоба «Дуэт» 0,3 кг Перепечи 0,13 кг б-н «Радужный» 0,25 кг
Стадии обработки Завес сырья Замес теста Приготовление начинки Разделка теста на куски
Отлежка теста Слоение теста Разделка на линии Укладка Расстойка
Выпечка
Остывание продукции Начинение продукции Упаковка продукции количество обрабатываемых материалов число стадий обработки
мин 4 мин 25 мин 0 мин 2
мин 5 мин 13 мин 25 мин 17 мин 90
мин 17 12
мин 0 мин 30 мин 28
36 25 25 15 18 22
105 15 00 15 20 8 15 70 80
2025 21
120 120 00 20 19
10 7 15 20 00 22
10 5 00 30 15 27 8 90 100
17 20
90 120 00 30 20
n
5 минимум
2 inf T(n,m) 490
m 13 максимум 120 sup T(n,m) 204
Формулы ( 2 ) и ( 3 ) использовали без учета нулевых значений в представленной таблице, так как в этом случае данная стадия отсутствует. Как видно из представленных данных (Таблица 1) размах длительностей стадий весьма значителен (от 490 до 2040), поэтому дальнейший анализ
проводили по данным универсума всех возможных вариантов расписаний для данных представленной выше таблицы. Для задачи множества машин удобно использовать вариант полного перебора, который порождает перестановки циклическим сдвигом, известный также как алгоритм вращения. Естественный способ перечисления перестановок циклическим сдвигом состоит в том, что, начав с некоторой произвольной перестановки, последовательно сдвигать по циклу на одно место влево все m работ партии. При каждом сдвиге 1-я работа текущей перестановки перемещается на последнее место без изменения взаимного расположения остальных, образуя новую перестановку. Такая организация циклического сдвига называется вращением. Вращение всех работ нужно продолжать, пока оно порождает новые перестановки, не встречавшиеся ранее. Перестановка считается оригинальной, когда после сдвига позиция последнего вращаемой части не равна его позиции в исходной перестановке. Если в результате очередного вращения получается ранее порожденная перестановка, нужно исследовать возможность построить оригинальную перестановку, применяя процедуру локального вращения последовательно для k = m-1, m-2, ..., 2 начальных работ при фиксированном положении остальных n-k хвостовых работ партии. Если локальное вращение первых 1
Оптимизация технологического потока многоассортиментного производства хлебных изделий
Косачев В.С., Кошевой Е.П., Сергеев А.А., ep-koshevoi@mail.ru Кубанский государственный технологический университет
В работе дается оценка оптимального расписания производства многоассортиментных хлебных изделий конвейерным производством на группе машин. Сформулирован ряд критериев оптимальности. Для решения задачи применен алгоритм вращения.
Ключевые слова: технологический поток, многоассортиментное
производство, оптимальное расписание
Решение задач упорядочения большой размерности для технологического потока [1] и гибких производств [2] может осуществляться путем сведения их к более простым задачам с использованием определенных условий и допущений. Наиболее часто задачи упорядочения встречаются при календарном планировании работы цехов и предприятий. В теории расписаний [3,4] рассматривается большое число модельных задач оптимального планирования простого процесса обслуживания. Их формальные постановки и численные методы решения определяются выбором критерия оптимальности и показателями процесса обслуживания. В работе предлагается метод многокритериальной оптимизации задачи краткосрочного планировании работы хлебозавода на примере реального хронометража, данные по которому представлены ниже (Таблица 1).
Возможное изменение длительности расписаний на последовательном множестве машин, если все длительности обработок равны, может быть вычислено по формуле:
T t, n, m t n m 1 t
(1)
где t - время выполнения одной работы (размах отсутствует); n количество обрабатываемых материалов; m - число стадий обработки. При подстановке обработки минимальной и максимальной длительностей работ из матрицы расписания получаем соответственно sup T и inf T на основе этих показателей:
sup T n, m max ti, j n m 1 max ti, j
(2)
inf T n, m min ti, j n m 1 min ti, j
Таблица 1 Длительности производственных стадий
Материалы
(3)
время Круассаны Русская коса 0,35 кг Сдоба «Дуэт» 0,3 кг Перепечи 0,13 кг б-н «Радужный» 0,25 кг
Стадии обработки Завес сырья Замес теста Приготовление начинки Разделка теста на куски
Отлежка теста Слоение теста Разделка на линии Укладка Расстойка
Выпечка
Остывание продукции Начинение продукции Упаковка продукции количество обрабатываемых материалов число стадий обработки
мин 4 мин 25 мин 0 мин 2
мин 5 мин 13 мин 25 мин 17 мин 90
мин 17 12
мин 0 мин 30 мин 28
36 25 25 15 18 22
105 15 00 15 20 8 15 70 80
2025 21
120 120 00 20 19
10 7 15 20 00 22
10 5 00 30 15 27 8 90 100
17 20
90 120 00 30 20
n
5 минимум
2 inf T(n,m) 490
m 13 максимум 120 sup T(n,m) 204
Формулы ( 2 ) и ( 3 ) использовали без учета нулевых значений в представленной таблице, так как в этом случае данная стадия отсутствует. Как видно из представленных данных (Таблица 1) размах длительностей стадий весьма значителен (от 490 до 2040), поэтому дальнейший анализ
проводили по данным универсума всех возможных вариантов расписаний для данных представленной выше таблицы. Для задачи множества машин удобно использовать вариант полного перебора, который порождает перестановки циклическим сдвигом, известный также как алгоритм вращения. Естественный способ перечисления перестановок циклическим сдвигом состоит в том, что, начав с некоторой произвольной перестановки, последовательно сдвигать по циклу на одно место влево все m работ партии. При каждом сдвиге 1-я работа текущей перестановки перемещается на последнее место без изменения взаимного расположения остальных, образуя новую перестановку. Такая организация циклического сдвига называется вращением. Вращение всех работ нужно продолжать, пока оно порождает новые перестановки, не встречавшиеся ранее. Перестановка считается оригинальной, когда после сдвига позиция последнего вращаемой части не равна его позиции в исходной перестановке. Если в результате очередного вращения получается ранее порожденная перестановка, нужно исследовать возможность построить оригинальную перестановку, применяя процедуру локального вращения последовательно для k = m-1, m-2, ..., 2 начальных работ при фиксированном положении остальных n-k хвостовых работ партии. Если локальное вращение первых 1