ПОИСК ПРИЕМЛЕМЫХ РЕШЕНИЙ КОНВЕЙЕРНОЙ ЗАДАЧИ ДЛЯ ЧЕТЫРЕХ И БОЛЕЕ ОПЕРАЦИЙ МЕТОДОМ НАПРАВЛЕННОГО ПОИСКА
Авторы:
1.
Санкт-Петербургский государственный морской технический университет
2.
Санкт-Петербургский государственный морской технический университет
Тип:
Статья
Страницы:
с 123
по 131
Статус:
Опубликован
Получено:
05.12.2017
Одобрено:
25.12.2017
Опубликовано:
25.12.2017
Классификаторы:
ВАК 08.00.05 Экономика и управление народным хозяйством
ВАК 08.00.10 Финансы, денежное обращение и кредит
УДК 519.8
ГРНТИ 06.52 Экономическое развитие и рост. Прогнозир-ние и планирование экономики. Экономич. циклы и кризисы
ГРНТИ 06.61 Территориальная структура экономики. Региональная и городская экономика
ГРНТИ 06.81 Экономика и организация предприятия. Управление предприятием
ГРНТИ 65.01 Общие вопросы пищевой промышленности
ГРНТИ 82.01 Общие вопросы организации и управления
ГРНТИ 83.01 Общие вопросы статистики
ВАК 08.00.10 Финансы, денежное обращение и кредит
УДК 519.8
ГРНТИ 06.52 Экономическое развитие и рост. Прогнозир-ние и планирование экономики. Экономич. циклы и кризисы
ГРНТИ 06.61 Территориальная структура экономики. Региональная и городская экономика
ГРНТИ 06.81 Экономика и организация предприятия. Управление предприятием
ГРНТИ 65.01 Общие вопросы пищевой промышленности
ГРНТИ 82.01 Общие вопросы организации и управления
ГРНТИ 83.01 Общие вопросы статистики
Язык материала:
русский
Ключевые слова:
задачи упорядочения, методы направленного поиска, конвейерная задача, задача Бэллмана - Джонсона, оптимальное решение, линейная комбинаторика, теория расписаний
Аннотация (русский):
При формировании различных производственных планов как оперативного, так и долгосрочного характера менеджерам часто приходится решать задачу сокращения сроков изготовления определенной номенклатуры изделий либо частей (блоков) единого сложного изделия. Решение таких проблем может быть сведено к математической постановке задач комбинаторной оптимизации - так называемым задачам упорядочения, методы решения которых разрабатываются и совершенствуются уже на протяжении нескольких столетий. Большинство этих методов имеют свои ограничения по применению. В частности, для постановки конвейерной задачи (изготовление партии изделий, каждое из которых в процессе производства проходит несколько технологических операций, порядок которых жестко определен и не может быть нарушен), алгоритм получения оптимальной программы запуска ранее был разработан лишь для случая, когда число технологических операций (этапов изготовления) равно двум (алгоритм Бэллмана - Джонсона). В исследуемом примере четыре операции, при этом логика поиска будет неизменной и для большего их количества. Предложенный метод получения решений комбинаторной задачи определения последовательности изготовления партии изделий или составных частей одного сложного изделия при минимальных затратах времени нагляден и прост. Он не требует для использования наличия глубоких математических знаний и применения специальных компьютерных программ, при этом расчеты показали, что такой логический пошаговый подход позволяет получать решения, очень близкие к оптимальному (или непосредственно оптимальные). Приведенный пример иллюстрирует логику поиска. Размерность исходной матрицы (количество изделий, а также число технологических операций их изготовления) может быть и больше, сложность расчетов от этого не изменится. Алгоритм можно применять как для целей формирования изменяющихся текущих производственных планов, так и для конвейерной постановки задачи в различных отраслях промышленного производства.
При формировании различных производственных планов как оперативного, так и долгосрочного характера менеджерам часто приходится решать задачу сокращения сроков изготовления определенной номенклатуры изделий либо частей (блоков) единого сложного изделия. Решение таких проблем может быть сведено к математической постановке задач комбинаторной оптимизации - так называемым задачам упорядочения, методы решения которых разрабатываются и совершенствуются уже на протяжении нескольких столетий. Большинство этих методов имеют свои ограничения по применению. В частности, для постановки конвейерной задачи (изготовление партии изделий, каждое из которых в процессе производства проходит несколько технологических операций, порядок которых жестко определен и не может быть нарушен), алгоритм получения оптимальной программы запуска ранее был разработан лишь для случая, когда число технологических операций (этапов изготовления) равно двум (алгоритм Бэллмана - Джонсона). В исследуемом примере четыре операции, при этом логика поиска будет неизменной и для большего их количества. Предложенный метод получения решений комбинаторной задачи определения последовательности изготовления партии изделий или составных частей одного сложного изделия при минимальных затратах времени нагляден и прост. Он не требует для использования наличия глубоких математических знаний и применения специальных компьютерных программ, при этом расчеты показали, что такой логический пошаговый подход позволяет получать решения, очень близкие к оптимальному (или непосредственно оптимальные). Приведенный пример иллюстрирует логику поиска. Размерность исходной матрицы (количество изделий, а также число технологических операций их изготовления) может быть и больше, сложность расчетов от этого не изменится. Алгоритм можно применять как для целей формирования изменяющихся текущих производственных планов, так и для конвейерной постановки задачи в различных отраслях промышленного производства.
Ключевые слова:
задачи упорядочения, методы направленного поиска, конвейерная задача, задача Бэллмана - Джонсона, оптимальное решение, линейная комбинаторика, теория расписаний
задачи упорядочения, методы направленного поиска, конвейерная задача, задача Бэллмана - Джонсона, оптимальное решение, линейная комбинаторика, теория расписаний
Введение В практике управления часто встречаются задачи, суть которых состоит в том, чтобы найти последовательность выполнения некоторой совокупности действий за минимальное время либо с минимальными затратами иных ресурсов. В экономической науке они названы задачами упорядочения. Исторически это самый старый тип задач линейной комбинаторики, решать которые люди пытались еще в XIX веке. Время - невосполнимый ресурс. А экономика - наука о рациональном использовании заведомо ограниченных ресурсов. Поиск математических методов решения обусловлен тем, что число возможных альтернатив в таких задачах зависит от количества звеньев в последовательности (N), а именно определяется как N! Понятно становится, что решить задачу методом полного перебора вариантов оказывается возможным лишь для малых значений N даже с применением компьютера. Для решения задач упорядочения, не считая полного перебора, существует несколько математических методов: метод случайного поиска, метод ветвей и границ, методы направленного поиска [1]. Именно к последним относится предлагаемый в статье подход к поиску рационального решения нахождения последовательности изготовления партии изделий, обеспечивающей минимизацию времени выполнения работы. Постановка и решение задачи Предположим, что предприятию необходимо изготовить некоторое количество изделий, каждое из которых проходит в процессе производства несколько технологических операций, порядок которых жестко определен и не может быть нарушен. Причем одновременно каждый производственный участок (рабочий, станок, сборочное место) может осуществлять работы по изготовлению только одного изделия. Известно время выполнения каждой операции, не одинаковое для различных изделий. Требуется найти последовательность запуска, которая обеспечит минимальное суммарное время изготовления партии. Приведенный числовой пример (табл. 1, 2) демонстрирует, насколько выбор последовательности может влиять на результирующие сроки. Примем количество изделий равным четырем. Производственных участков тоже четыре. В табл. 1 сведены все исходные данные. Таблица 1 Продолжительность изготовления изделий на участках предприятия tij Изделие (j) Участок (i) Изделие 1 Изделие 2 Изделие 3 Изделие 4 Ед. врем. 1 8 10 8 6 2 6 3 7 4 3 7 9 4 7 4 5 2 9 8 Чтобы получить продолжительность выполнения всех работ при базовой последовательности изготовления - по порядку (т. е. 1 → 2 → 3 → 4), определяем моменты начала и окончания каждой работы. Очевидно, что первое изделие изготавливается без простоев. Далее простои возможны, поскольку нельзя передавать на следующую операцию изделие, еще не завершенное на предыдущем технологическом этапе, и нельзя одновременно разместить на одном участке два изделия. Таким образом, в каждый момент выбирается максимум из двух чисел. Интервал между ними представляет собой вынужденный простой участка либо изделия. Логика расчета и сам расчет представлены в табл. 2. Суммарное время изготовления всех изделий составило 54 единицы времени. Таблица 2 Определение сроков выполнения работ при базовой последовательности запуска изделий в производство i tij, ед. врем. Изделие 1 Изделие 2 Изделие 3 Изделие 4 1 0 ® 8 8 ® 18 18 ® 26 26 ® 32 8 10 8 6 2 8 ® 14 18 = max[14; 18] 26 ® 33 33 ® 37 6 3 7 4 3 14 ® 21 21 ® 30 33 ® 37 37 ® 44 7 9 4 7 4 21 ® 26 30 ® 32 37 ® 46 46 ® 54 5 2 9 8 Теперь произвольным образом изменим последовательность запуска и выполним те же расчеты. Условно примем в качестве альтернативной последовательность 3 → 1 → 4 → 2. В табл. 3 столбцы исходной матрицы переставлены. Таблица 3 Определение сроков выполнения работ при случайно выбранной последовательности запуска изделий в производство i tij, ед. врем. Изделие 3 Изделие 1 Изделие 4 Изделие 2 1 0 8 8 16 16 22 22 32 8 8 6 10 2 8 15 16 22 22 26 32 35 7 6 4 3 3 15 19 22 29 29 36 36 45 4 7 7 9 4 19 28 29 34 36 44 45 47 9 5 8 2 Полученное значение продолжительности изготовления партии существенно (на 7 единиц) меньше полученного ранее - 47 единиц времени. Мог получиться и результат хуже базового. Очевидно, что на всем множестве возможных решений есть одно или несколько оптимальных, обеспечивающих минимум временных затрат на изготовление. Его и требуется определить в данной разновидности задач упорядочения. Впервые такую задачу сформулировал в 1945 г. Р. Бэллман [2] для случая с двумя технологическими операциями (двумя станками) и значительным числом различных деталей, которые должны быть обработаны на этих двух станках. В 1954 г. С. М. Джонсон [3] предложил правило и алгоритм ее решения. Постановка получила название задачи Бэллмана - Джонсона (или конвейерной задачи) и стала одной из самых известных в теории расписаний. Метод получения строго оптимального решения этой задачи разработан только для ситуации двух технологических операций [4, 5]. С увеличением числа станков до трех оптимальное решение может быть получено только при наложении определенных ограничений на продолжительности выполнения работ. Таким образом, поставленная нами задача (в которой технологических участков четыре) не является оптимизационной, и говорить можно только о получении условно оптимальных (близких к оптимуму, приемлемых) решений с применением методов направленного поиска. Алгоритм Джонсона специфичен тем, что число деталей предполагается достаточно большим. Для рассматриваемого случая, более распространенного на практике (когда число изделий невелико), можно руководствоваться следующим алгоритмом, сочетающим в себе элементы сетевого моделирования, метода ветвей и границ, а также правила Джонсона. Поисковый алгоритм решения задачи Очевидны два факта: во время выполнения самой первой и самой последней работ никакие другие работы не выполняются. Таким образом, следует стараться минимизировать время их выполнения - t11 и t44. В остальном критический путь однозначно затронет те производственные участки, которые наиболее загружены. Пытаясь «разгрузить» их, можно с большой вероятностью получить решения, обеспечивающие если не абсолютный минимум суммарного времени выполнения работ, то вполне приемлемые решения, незначительно отстоящие от оптимума. Логика принятия решений в зависимости от загрузки производственных участков схематично представлена на рис. 1. Рис. 1. Логика принятия решений в зависимости от загрузки производственных участков: а - наиболее загружен участок № 1; б - наиболее загружен участок № 2; в - наиболее загружен участок № 3; г - наиболее загружен участок № 4 Таким образом, на первом шаге можно определить либо то изделие, которое целесообразно запустить в производство первым, либо определиться с работой, завершающей искомую последовательность. После исключения выбранного изделия из рассмотрения область поиска сузится и можно будет перейти к следующему шагу поискового алгоритма [4]. Далее показан ход поиска рациональных решений для примера, представленного выше, в соответствии с логическим алгоритмом на рис. 1. Первым шагом определяется суммарная загрузка производственных участков, расчет которой показан в табл. 4. Таблица 4 Определение загрузки производственных участков (шаг первый) Участок Продолжительность tij, ед. врем. Σ Блок 1 Блок 2 Блок 3 Блок 4 1 8 10 8 6 32 2 6 3 7 4 20 3 7 9 4 7 27 4 5 2 9 8 24 t2 + t3 + t4 18 14 20 19 - Цель настоящей итерации - выявить тот участок, на который приходится максимальный объем работ и, в зависимости от его места в технологической цепочке, выбрать одну из четырех потенциально возможных ситуаций. В общем случае количество таких ситуаций равно числу технологических звеньев. Самым загруженным оказался участок № 1, следовательно, теперь необходимо определить изделие, для которого минимальна сумма продолжительностей t2 + t3 + t4. По результатам расчетов можно принять решение о том, что блок № 2 (с минимальным значением t2 + t3 + t4) будет изготавливаться четвертым. Далее вновь считаем загрузку, исключив из рассмотрения блок № 2. Результаты расчетов представлены в табл. 5. Таблица 5 Определение загрузки производственных участков (шаг второй) Участок Продолжительность tij, ед. врем. Σ Блок 1 Блок 2 Блок 3 Блок 4 1 8 8 6 22 2 6 7 4 17 3 7 4 7 18 4 5 9 8 22 Поскольку два участка оказались загружены в равной степени, на данном шаге появились «ветви», и можно предположить, что рациональное решение будет не единственным. Вероятность ветвления возрастает с увеличением размерности исходной матрицы. Но следует упомянуть и о том, что иметь альтернативы всегда лучше с практической точки зрения. Трудоемкость поиска возрастает очень несущественно. В приведенном примере необходимо рассмотреть две ситуации: 1. Поставить третьим номером работу, у которой минимальна сумма t2 + t3 + t4 (по аналогии с первым шагом алгоритма). 2. Поставить первой работу, у которой минимально t1 + t2 + t3 (см. рис. 1). Это позволит с большой вероятностью начать раньше работы критического пути. Данное обстоятельство и является залогом сокращения общей продолжительности изготовления всей партии изделий. В общем случае на втором шаге возможны четыре варианта прохождения пути поиска, логику которых иллюстрирует рис. 2. Рис. 2. Возможные варианты прохождения пути поиска Определим для нашей задачи работы с минимальным значением t2 + t3 + t4, а также с минимальным значением t1 + t2 + t3. Расчет искомых сумм сведен в табл. 6. Таблица 6 Принятие решения на втором шаге поискового алгоритма Участок Продолжительность tij, ед. врем. Σ Блок 1 Блок 2 Блок 3 Блок 4 1 8 8 6 22 2 6 7 4 17 3 7 4 7 18 4 5 9 8 22 t2 + t3 + t4 18 - 20 19 - t1 + t2 + t3 21 - 19 17 - Таким образом, имеются две альтернативы: поставить третьей работу по изготовлению 1-го блока либо ставить первой работу по изготовлению четвертого блока. Двигаясь по каждой из веток, необходимо вновь рассчитать загрузку оставшихся участков (табл. 7). Таблица 7 Определение загрузки производственных участков (шаг третий) Ветвь №1 Участок Продолжительность tij, ед. врем. Σ Блок 1 Блок 2 Блок 3 Блок 4 1 8 6 14 2 7 4 11 3 4 7 11 4 9 8 17 Ветвь №2 Участок Продолжительность tij, ед. врем. Σ Блок 1 Блок 2 Блок 3 Блок 4 1 8 8 16 2 6 7 13 3 7 4 11 4 5 9 14 Следуя по ветви № 1, можно увидеть, что наиболее загружен четвертый производственный участок. Следовательно, из оставшихся двух работ вперед нужно поставить ту, продолжительность которой на четвертом участке больше. Это работа по изготовлению 3-го блока. Она пойдет первой, изготовление четвертого блока будет вторым. Первая найденная последовательность изготовления: 3 → 4 → 1 → 2. По ветви № 2 наиболее загружен первый участок. Обе работы имеют равные продолжительности выполнения на этом участке и могут быть поставлены первыми. Следовательно, может быть получено два решения. Вторая последовательность: 4 → 1 → 3 → 2; третья последовательность: 4 → 3 → 1 → 2. Результаты направленного поиска можно отобразить в виде графа, представленного на рис. 3. Он наглядно демонстрирует поисковые ветви, а также логику принятия решений на каждом шаге. Рис. 3. Ход направленного поиска условно-оптимальных решений В табл. 8 определены продолжительности изготовления партии блоков для полученных методом направленного поиска последовательностей. Следует отметить, что в реальной практике получение абсолютного оптимума не всегда необходимо. Решение, очень близкое к оптимальному и при этом выработанное в кратчайшее время, будет приемлемым и ценным. Таблица 8 Продолжительность выполнения работ для найденных последовательностей Последовательность 3 → 4 → 1 → 2 Участок Блок 3 Блок 4 Блок 1 Блок 2 1 0 8 8 14 14 22 22 32 8 6 8 10 2 8 15 15 19 22 28 32 35 7 4 6 3 3 15 19 19 26 28 35 35 44 4 7 7 9 4 19 28 28 36 36 41 44 46 9 8 5 2 Продолжение табл. 8 Последовательность 4 → 1 → 3 → 2 Участок Блок 4 Блок 1 Блок 3 Блок 2 1 0 6 6 14 14 22 22 32 6 8 8 10 2 6 10 14 20 22 29 32 35 4 6 7 3 3 10 17 20 27 29 33 35 44 7 7 4 9 4 17 25 27 32 33 42 44 46 8 5 9 2 Последовательность 4 → 3 → 1 → 2 Участок Блок 4 Блок 3 Блок 1 Блок 2 1 0 6 6 14 14 22 22 32 6 8 8 10 2 6 10 14 21 22 28 32 35 4 7 6 3 3 10 17 21 25 28 35 35 44 7 4 7 9 4 17 25 25 34 35 40 44 46 8 9 5 2 Из данных табл. 8 следует, что продолжительности изготовления партии из четырех изделий одинаковы для всех найденных поисковым алгоритмом последовательностей. В следующем разделе осуществлена проверка полученных значений на оптимальность. Проверка полученных решений на предмет близости к оптимуму Метод полного перебора решений (количество которых в данном случае равно 4! = 24) позволяет выявить строго оптимальное решение поставленной задачи. Его реализация на приведенном примере показала, что оптимальных решений четыре. Значения продолжительностей изготовления партии для всех возможных последовательностей сведены в табл. 9. Таблица 9 Продолжительности изготовления для всех возможных вариантов последовательностей № Последовательность T, ед. врем. № Последовательность T, ед. врем. 1. 1 2 3 4 54 13. 3 1 2 4 53 2. 1 2 4 3 54 14. 3 1 4 2 47 3. 1 3 2 4 53 15. 3 2 1 4 54 4. 1 3 4 2 46 16. 3 2 4 1 50 5. 1 4 2 3 52 17. 3 4 1 2 46 6. 1 4 3 2 47 18. 3 4 2 1 50 7. 2 1 3 4 54 19. 4 1 2 3 52 8. 2 1 4 3 55 20. 4 1 3 2 46 9. 2 3 1 4 54 21. 4 2 1 3 52 10. 2 3 4 1 51 22. 4 2 3 1 50 11. 2 4 1 3 52 23. 4 3 1 2 46 12. 2 4 3 1 51 24. 4 3 2 1 50 Согласно полученным данным, оптимальное время изготовления всей партии составляет 46 единиц времени. Добиться такого результата можно, изготавливая блоки в четырех различных порядках: 1 → 3 → 4 → 2, 3 → 4 → 1 → 2, 4 → 1 → 3 → 2 и 4 → 3 → 1 → 2. Три из них были получены в ходе реализации предложенного поискового алгоритма, т. е. результат представляет собой абсолютный математический оптимум. Заключение Большинство путей решения подобных комбинаторных задач требуют от исполнителя достаточно серьезной математической подготовки, а иногда даже применения специальных компьютерных программ. Алгоритм, предложенный выше, очень прост и может быть наглядно представлен в виде графа. Решения, получаемые с его применением, часто совпадают с оптимальными либо отличаются от оптимума очень незначительно. В случае увеличения размерности исходной матрицы (числа изделий либо технологических операций) общая логика решения задачи сохранится. Число итераций увеличится, но сложность не возрастет. Алгоритм можно применять как для целей формирования разовых оперативных производственных планов, так и для конвейерных задач. Очевидно, что во втором случае потенциально достижимый экономический эффект возрастет соразмерно величине партий. Еще с XIX в. известно, что к экономии времени сводится, в конечном счете, вся экономия. Время - невосполнимый ресурс.
1. Алехин М. Ю., Иванова Л. Н. Методы оптимизации в экономических исследованиях: учебн. пособ. СПб.: Изд-во СПбГМТУ, 2012. C. 5.
2. Bellman R., Gross O. Some Combinatorial Problems Arising in the Theory of Multistage Processes // J. Soc. Indust. and Appl. Math. 1945. Vol. 2. No. 3. P. 175-183.
3. Johnson S.M. Optimal Two- and Three-Stage Production Schedules with Setup Times Included // Nav. Res. Log. Quart. 1954. Vol. 1. No. 1. P. 61-68.
4. Левин В. И. Задача Беллмана - Джонсона для конвейерных систем с переменным порядком работ // Вестн. Тамбов. гос. техн. ун-та. 2003. Т. 9. № 3. С. 457-463.
5. Левитин А. В. Алгоритмы. Введение в разработку и анализ: пер. с англ. М.; СПб.; Киев: Вильямс, 2006. 576 с.
6. Алехин М. Ю., Колобкова И. Е. Организационно-экономический анализ в управлении проектами: учебн. пособ. СПб.: Изд-во СПбГМТУ, 2017. C. 82.
