FINDING ACCEPTABLE SOLUTIONS OF CONVEYOR SYSTEMS PROBLEM FOR FOUR AND MORE OPERATIONS APPLYING DIRECTIONAL SEARCH METHOD
Authors:
1.
Saint-Petersburg State Marine Technical University
2.
Saint-Petersburg State Marine Technical University
Type:
Article
Pages:
from 123
to 131
Status:
Published
Received:
05.12.2017
Accepted:
28.02.2020
Published:
25.12.2017
Subject area:
VAC 08.00.05 Экономика и управление народным хозяйством
VAC 08.00.10 Финансы, денежное обращение и кредит
UDK 519.8
GRNTI 06.52 Экономическое развитие и рост. Прогнозир-ние и планирование экономики. Экономич. циклы и кризисы
GRNTI 06.61 Территориальная структура экономики. Региональная и городская экономика
GRNTI 06.81 Экономика и организация предприятия. Управление предприятием
GRNTI 65.01 Общие вопросы пищевой промышленности
GRNTI 82.01 Общие вопросы организации и управления
GRNTI 83.01 Общие вопросы статистики
VAC 08.00.10 Финансы, денежное обращение и кредит
UDK 519.8
GRNTI 06.52 Экономическое развитие и рост. Прогнозир-ние и планирование экономики. Экономич. циклы и кризисы
GRNTI 06.61 Территориальная структура экономики. Региональная и городская экономика
GRNTI 06.81 Экономика и организация предприятия. Управление предприятием
GRNTI 65.01 Общие вопросы пищевой промышленности
GRNTI 82.01 Общие вопросы организации и управления
GRNTI 83.01 Общие вопросы статистики
Language:
Russian
Keywords:
ordering problems, directional search methods, problem of conveyor processing, Bellman-Johnson’s problem for conveyor systems, optimal solution, linear combinatorics, scheduling theory
Abstract (English):
When forming various production plans of short-term or long-term nature, managers often have to solve the problem of reducing the production time of a certain product or parts (blocks) of a single complex product. Solving such problems can be reduced to a mathematical formulation of combinatorial optimization problems - the so-called ordering problems, the methods of solving which have been developing and improving for several centuries. Many of these methods have their own application limitations. In particular, in order to formulate the problem of conveyor processing (producing a set of items, where each item passes through several technological operations, whose order is strictly determined and must not be violated) the early algorithm for obtaining the optimal launch program was developed only for the process with two technological operations (manufacturing stages). It was Bellman-Johnson’s algorithm. In the given example there are four operations, but the search logic will be the same for the larger number of operations. The proposed method for obtaining solutions to the combinatorial problem of determining the sequence of manufacturing a batch of products or components of one complex product at minimal time consumption is intuitive and simple. It does not require to use deep mathematical knowledge or special computer programs. At the same time, calculations have shown that such logical step-by-step approach allows to obtain solutions that are very close to optimal (or are optimal, in fact). The example given illustrates the search logic. Dimensions of the original matrix (the number of products and the number of technological operations for their manufacture) can be arbitrary. The complexity of the calculations does not depend on it. The algorithm can be used both for forming the changing production plans, and for the task of conveyor processing in various industries.
When forming various production plans of short-term or long-term nature, managers often have to solve the problem of reducing the production time of a certain product or parts (blocks) of a single complex product. Solving such problems can be reduced to a mathematical formulation of combinatorial optimization problems - the so-called ordering problems, the methods of solving which have been developing and improving for several centuries. Many of these methods have their own application limitations. In particular, in order to formulate the problem of conveyor processing (producing a set of items, where each item passes through several technological operations, whose order is strictly determined and must not be violated) the early algorithm for obtaining the optimal launch program was developed only for the process with two technological operations (manufacturing stages). It was Bellman-Johnson’s algorithm. In the given example there are four operations, but the search logic will be the same for the larger number of operations. The proposed method for obtaining solutions to the combinatorial problem of determining the sequence of manufacturing a batch of products or components of one complex product at minimal time consumption is intuitive and simple. It does not require to use deep mathematical knowledge or special computer programs. At the same time, calculations have shown that such logical step-by-step approach allows to obtain solutions that are very close to optimal (or are optimal, in fact). The example given illustrates the search logic. Dimensions of the original matrix (the number of products and the number of technological operations for their manufacture) can be arbitrary. The complexity of the calculations does not depend on it. The algorithm can be used both for forming the changing production plans, and for the task of conveyor processing in various industries.
Keywords:
ordering problems, directional search methods, problem of conveyor processing, Bellman-Johnson’s problem for conveyor systems, optimal solution, linear combinatorics, scheduling theory
ordering problems, directional search methods, problem of conveyor processing, Bellman-Johnson’s problem for conveyor systems, optimal solution, linear combinatorics, scheduling theory
Введение В практике управления часто встречаются задачи, суть которых состоит в том, чтобы найти последовательность выполнения некоторой совокупности действий за минимальное время либо с минимальными затратами иных ресурсов. В экономической науке они названы задачами упорядочения. Исторически это самый старый тип задач линейной комбинаторики, решать которые люди пытались еще в 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. Alehin M. Yu., Ivanova L. N. Metody optimizacii v ekonomicheskih issledovaniyah: uchebn. posob. SPb.: Izd-vo SPbGMTU, 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. Levin V. I. Zadacha Bellmana - Dzhonsona dlya konveyernyh sistem s peremennym poryadkom rabot // Vestn. Tambov. gos. tehn. un-ta. 2003. T. 9. № 3. S. 457-463.
5. Levitin A. V. Algoritmy. Vvedenie v razrabotku i analiz: per. s angl. M.; SPb.; Kiev: Vil'yams, 2006. 576 s.
6. Alehin M. Yu., Kolobkova I. E. Organizacionno-ekonomicheskiy analiz v upravlenii proektami: uchebn. posob. SPb.: Izd-vo SPbGMTU, 2017. C. 82.
