Статистический анализ расписаний многоассортиментного производства на параллельноработающих установках периодического действия

УДК 641

Статистический анализ расписаний многоассортиментного производства на параллельно-работающих установках периодического действия

Косачев В.С., Кошевой Е.П., Сергеев А.А.

Кубанский государственный технологический университет

В работе дается оценка близости результатов перестановочного решения по исходным параметрам параллельно-работающих установок периодического действия к оптимальным расписаниям по длительности.

Ключевые слова: статистический анализ, расписания, установки периодического действия.

В современных условиях основным для эффективно работающих производств является выпуск конкурентоспособной продукции в количествах и сроки требуемых рыночными условиями. В целом ряде отраслей промышленности (пищевой, фармацевтической, химической и др.) производство ценных высококачественных продуктов широкого ассортимента производится небольшими партиями на параллельно-работающих установках периодического действия [1]. Управление и проектирование таких производств представляет актуальную техническую задачу [2]. Сложное поведение, как на рынке сырья, так и на рынке продуктов при варьировании стоимости и ограничений на различные ресурсы требует углубления научных основ управления и проектирования подобных систем, что представляет актуальную научную задачу.

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

Обилие предлагаемых алгоритмов и общих подходов говорит об отсутствии общего решения для таких задач большой размерности [3,4]. В то же время, специфика рассматриваемого процесса позволяет существенно упростить постановку задачи оптимизации реального производственного процесса, а значительный рост вычислительных мощностей современных компьютерных технологий позволяет использовать метод «грубой силы» (полного перебора) для поиска подмножества оптимальных решений в данной постановке. Для задачи множества машин удобно использовать вариант полного перебора, который по-

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

При каждом сдвиге 1-я работа текущей перестановки перемещается на последнее место без изменения взаимного расположения остальных, образуя новую перестановку. Такая организация циклического сдвига называется вращением. Вращение всех работ нужно продолжать, пока оно порождает новые перестановки, не встречавшиеся ранее. Перестановка считается оригинальной, когда после сдвига позиция последнего вращаемой части не равна его позиции в исходной перестановке. Если в результате очередного вращения получается ранее порожденная перестановка, нужно исследовать возможность построить оригинальную перестановку, применяя процедуру локального вращения последовательно для к = п-1, п-2, ..., 2 начальных работ при фиксированном положении остальных п-к хвостовых работ партии. Если локальное вращение первых 1<к<п работ порождает оригинальную перестановку, следует продолжить вращение циклическим сдвигом всех п работ партии. В противном случае ( к = 1 ), перебор считается завершенным, т.к. перечислены все п! перестановок. Для каждой оригинальной перестановки, порождаемой рассмотренным алгоритмом вращения, определяется продолжительность соответствующего расписания процесса обслуживания. Сравнительная оценка длительности работ позволяет отобрать в качестве оптимальных вариантов все перестановки с минимальной продолжительностью процесса обслуживания. Следует отметить, что полный перебор всех оптимальных решений задачи произвольного числа машин не может быть практически реализован для достаточно представительных партий работ по ресурсным соображениям, в связи с тем, что мощность перебора возрастает не полиномиально при увеличении объема партии и быстро превосходит возможности современных вычислительных систем.

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

ления поиска. «Эвристика - некоторое произвольное правило, стратегия, хитрость, упрощение или любое другое средство, которое решительным образом ограничивает объем поиска решений в проблемных пространствах» - Э. Фей-генбаум (патриарх экспертных систем). Используя операторы расчета эвристики будем осуществлять поиск в пространстве перестановок и введем следующую эвристическую функцию:

^п) = ё

где ё(п) - стоимость оптимального пути от начальной перестановки до п-й перестановки (глубина вершины на дереве поиска) - ё(0) = 0; ,^п) - стоимость оптимального пути от п-й перестановки к оптимальной (в нашем случае заранее неизвестной и динамически изменяемой при наличии стохастической составляющей).

Определив, таким образом, оценочную функцию, выберем стратегию прохождения вершин (сохранения перестановок), в которых значение функций минимальны. Выбираем вершину с наименьшим из значений оценочной функции, применяем эвристику (1) и оцениваем вершину, затем создаем дочерние вершины (при этом не возвращаемся к уже появившимся вершинам). Повторяем эту процедуру до достижения целевого состояния. Как видно из выше изложенного использование оценочных функций (эвристик) возможно при наличии достаточно эффективной эвристики. С точки зрения эффективности оценки эвристики делятся на два вида. Общие эвристики, как правило, не гарантирующие хорошее, но дающие какое-то решение. Специальные эвристики, основанные на знаниях для конкретной проблемной области, для конкретной задачи. Областью применения эвристик является поиск любого решение, не обязательно лучшего. Таким образом, использование эвристик возможно при наличии достаточно надежных оценок степени оптимальности перестановок.

Используем статистическое моделирование процесса при наличии матрицы длительностей задаваемой равномерным статистическим распределением:

0, х £ а х - а

Ь - а

1, х > Ь

а < х £ Ь

где а,Ь - границы распределения; х - длительность обработки 1-й машиной ]-го задания.

Рассмотрим возможное изменение длительности расписаний на последовательном множестве машин при изменении ширины (а£х£Ь) этого равномерного

<

распределения. Если ширина окна стремится к нулю (все длительности обработок равны), то выполнение всего объема работ может быть вычислено по формуле:

T

где t - время выполнения одной работы (размах отсутствует); n - количество обрабатываемых материалов; m - число стадий обработки.

Результаты расчетов по предложенной нами формуле представлены в соответствующих таблицах 1 2, 3. Данная формула позволяет определить нижнюю и верхнюю границу длительности расписаний. При подстановке обработки минимальной и максимальной длительностей работ из матрицы расписания

Т* р ГТЧ

и inf T на основе этих показателей: sup T

inf T

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

Размах отсутствует, m стадии обработки т= 1

T я

1 2 3 4 5 6 7 8 9 10

1 1 2 3 4 5 6 7 8 9 10

2 2 4 6 8 10 12 14 16 18 20

3 3 6 9 12 15 18 21 24 27 30

'я к н о эК О к о t4 <u CP И 4 4 8 12 16 20 24 28 32 36 40

5 5 10 15 20 25 30 35 40 45 50

6 6 12 18 24 30 36 42 48 54 60

7 7 14 21 28 35 42 49 56 63 70

8 8 16 24 32 40 48 56 64 72 80

9 9 18 27 36 45 54 63 72 81 90

10 10 20 30 40 50 60 70 80 90 100

Таблица 2. Число обработок равно 5.

Размах отсутствует, m стадии обработки m= 5

T materials

1 2 3 4 5 6 7 8 9 10

1 5 6 7 8 9 10 11 12 13 14

2 10 12 14 16 18 20 22 24 26 28

3 15 18 21 24 27 30 33 36 39 42

к к а н о эК О к о t4 <D CP PQ 4 20 24 28 32 36 40 44 48 52 56

5 25 30 35 40 45 50 55 60 65 70

6 30 36 42 48 54 60 66 72 78 84

7 35 42 49 56 63 70 77 84 91 98

8 40 48 56 64 72 80 88 96 104 112

9 45 54 63 72 81 90 99 108 117 126

10 50 60 70 80 90 100 110 120 130 140

Размах отсутствует, т стадии обработки т= 10

T materials

1 2 3 4 5 6 7 8 9 10

1 10 11 12 13 14 15 16 17 18 19

2 20 22 24 26 28 30 32 34 36 38

3 30 33 36 39 42 45 48 51 54 57

к н о эК О к о t4 <D CP 03 4 40 44 48 52 56 60 64 68 72 76

5 50 55 60 65 70 75 80 85 90 95

6 60 66 72 78 84 90 96 102 108 114

7 70 77 84 91 98 105 112 119 126 133

8 80 88 96 104 112 120 128 136 144 152

9 90 99 108 117 126 135 144 153 162 171

10 100 110 120 130 140 150 160 170 180 190

Таблица 4. Несбалансированная матрица длительностей с постоянным интервалом завершения работ.

Стадии обработки Виды сырья

1 2 3 4

Длительности 1 1 1 2 2

2 1 1 2 1

3 1 1 1 2

Начало работ 1 0 1 2 4

2 1 2 4 6

3 2 3 6 7

Завершение работ 1 1 2 4 6

2 2 3 6 7

3 3 4 7 9

Таблица 5. Сбалансированная матрица длительностей с постоянным интервалом завершения работ.

Стадии обработки Виды сырья

1 2 3 4

Длительности 1 1 1 2 2

2 1 2 1 2

3 1 1 2 2

Начало работ 1 0 1 2 4

2 1 2 4 6

3 2 4 5 8

Завершение работ 1 1 2 4 6

2 2 4 5 8

3 3 5 7 10

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

Таблица 6. Коэффициенты корреляции показателей моделей бинарных расписаний (1<Х<2).

Показатели Лу^Х ЛvgY Ymin

AvgX 1,000 0,963 0,808

AvgY 0,963 1,000 0,879

Ушт 0,808 0,879 1,000

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

12 2

1 ГЬ 1 ГЬ

гь - 3-----= 0.956 гь = 0.963 гь + 3-----------= 0.970

л/1000 л/1000

12 2

1 ГЬ 1 ГЬ

гЬ- 3-------= 0.775 гь = 0.808 гЬ + 3-------------= 0.841

71000 V1000

22

1 ГЬ 1 ГЬ

гЬ - 3-= 0.857 гь = 0.879 гЬ + 3-= 0.901

л/1000 л/1000

где гь - выборочный коэффициент корреляции соответствующих показателей (таблица 6).

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

Таблица 7. Коэффициенты корреляции показателей моделей расписаний 1<Х<3.

Показатели ЛvgX ЛvgY Ymin

AvgX 1,000 0,958 0,850

AvgY 0,958 1,000 0,907

Ушт 0,850 0,907 1,000

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

Время завершения работ Время завершения работ

ДудХ

♦ АудУ ИУтт

Рисунок 1. Регрессионные уравнения связи параметров расписаний для 1<Х<2.

ДудХ

♦ АудУ ИУтт

Рисунок 2. Регрессионные уравнения связи параметров расписаний для 1 <Х<3.

Выводы

1. Установлена статистически значимая зависимость между средним значением матрицы длительностей (AvgX), средним значением времени завершения работ всех возможных расписаний (AvgY) и величиной рекорда этих расписаний (Ymin).

2. Получены статистически значимые эвристические функции (Рисунок 1, Рисунок 2) позволяющие определять близость полученного текущего варианта расписания к наилучшему по исходным данным этого расписания, не прибегая к алгоритму полного перебора.

3. Использование предлагаемых эвристик позволяет значительно сократить объем вычислений при реализации алгоритмов направленного случайного поиска (например, генетический алгоритм) контролируя текущий результат по степени его близости к рекорду в процессе промежуточных вычислений.

Список литературы

1. Кафаров, В.В., Макаров В.В. Гибкие автоматизированные производственные системы в химической промышленности - М. : Химия, 1990. - 320 с.

2. Кафаров, В.В., Мешалкин В.П. Анализ и синтез химико-технологических систем. М. : Химия, 1991.- 431 с.

3. Танаев B.C., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984. - 384 с.

4. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. - 322 с.

Statistical analysis of multiassortment production schedules for concurrent-operated batch-type units

Kosachev V.S., Koshevoy E.P., Sergeev A.A.

Kuban State Technological University

The paper evaluates the proximity of the permutation solution results based on

initial parameters of concurrent run batch-type units to optimum time duration

schedules.

Keywords: statistical analysis, schedules, batch-type units.