Рисунок 1: Зависимость разнообразия продукции и объема продукции с различным типом производства
Исходный URL: http://www.journal.au.edu/ijcim/jan00/morad.doc
Резюме
Этот документ дает описания на различных методах решения проблемы планировки и описывает новый метод, основанный на генетических алгоритмах (GA), чтобы решить проблему размещения оборудования. Развитие размещения оборудования - важный шаг в проектировании производственного оборудования благодаря воздействию планировки на экономию погрузочно-разгрузочных работ и времени, и, следовательно, затрагивает полную производительность цеха. Плохая планировка привела бы к наличию большего количества деталей, тратящих более длительное время, перемещаясь от одной машины к другой, и таким образом привела бы к увеличению затрат погрузочно-разгрузочных работ. В отличие от блочного расположения, цель проблемы размещения оборудования состоит в том, чтобы найти подходящее размещение машин в ячейке. GA-based метод развитый, чтобы решить это, имеет целью уменьшение движений деталей, обрабатываемых в ячейке.
Один из самых важных факторов в проектировании производственного оборудования - найти эффективную планировку. Общее определение проблемы планировки завода – это найти лучшее расположение физического оборудования, чтобы обеспечить эффективную операцию. Планировка затрагивает стоимость погрузочно-разгрузочных работ, времени и пропускной способности, и следовательно затрагивает полную производительность и эффективность завода (Hassan (1995)).
Планировка машин обычно зависит от типа обрабатывающей промышленности. В случае, где объемы продукта высоки и разнообразие продуктов низко, производственный процесс известен как процесс “flow shop”, и планировка обычно основана на продуктах. Следовательно, планировку называют “layout by product”. С другой стороны, завод – изготовитель может иметь высокое разнообразие продуктов с низким объемом производства, где процесс известен как “job shop” и планировка известна как “job shop layout”, “layout by function”, “function layout” или “layout by process” (Dilworth (1996)). Групповая технология (GT) или гибкое автоматизированное производство (ГАП) обычно применяется к производственным системам, которые являются средним между этими крайностями с планировкой, известной как “cellular layout” ячеистая планировка. Иллюстрация 1 показывает тип планировок для различных видов производственных систем.
Рисунок 1: Зависимость разнообразия продукции и объема продукции с различным типом производства
Ещё один тип планировки продукта – “fixed product layout” фиксированная планировка продукта. В отличие от других типов планировки, в фиксированной планировке производственное оборудование перемещается к продукту и не иначе. Этот тип планировки обычно применяется, когда продукты являются большими в размере, например такие, как для создания судов или самолетов.
В ГАП, проблема планировки ячейки, или иногда известная как проблема размещения оборудования, в основном сосредоточена на обнаружении лучшей схемы оборудования в каждой ячейке. Три главных типа схем в ячейках GT - одиночный ряд, мультиряды или круговая планировка, как показано в иллюстрации 2.
Планировка одиночного ряда, или иногда известная как планировка поточной линии GT, используется, когда детали в группе обрабатываются в той же самой последовательности, как и расположены машины.
Планировка мультиряда, или планировка ячейки GT, разрешают деталям перемещаться с любой машины на любую другую машину. Поток деталей, может и не быть однонаправлен в этой планировке.
Планировка центра GT, с другой стороны, основана на функциональной схеме машин и подходит, когда соединение продукта (“product mix”) изменяется часто.
Рисунок 2: Типы планировки в ячейке GT.
Развитие планировки GT в основном включает 3 шага (Jajodia и другие (1992)):
Каждый из этих шагов - комбинаторная проблема, и много эвристик было предложено за эти годы, чтобы решить их. Эти шаги обычно выполняются последовательно.
Исходные данные, необходимые для планировки GT следующие:
Hassan и Albin (1994) дают обширное исследование типа данных, требуемых в проблеме размещения оборудования. Данные размещения оборудования считают в иерархии, (показанными в рисунке 3) в зависимости от того, как детальная планировка разработана. Если от планировки требуется только найти относительную расстановку машин, то данные, представляющие число машин и их отношения движений достаточны, что является вплоть до Уровня II в иерархии. Однако, если необходима детальная планировка, требуется больше данных. В обнаружении данных на Уровне III, немного трудностей могут возникнуть особенно на новых заводах, где данные еще не доступны. Когда планировка развита для современных и автоматизированных средств, необходимые данные не могут быть взяты со старых данных или от подобных средств, так как они, возможно, не существуют.
Другая трудность в подготовке данных размещения оборудования – требование определения количества некоторых качественных факторов. Преобразование этих факторов сделано субъективно и могло вызвать погрешность. Данные требовали в диаграмме отношений, которая описывает желательность наличия расстояний между машинами, первоначально качественна, но должна быть обозначена численными величинами. Нет никакого универсального соглашения по численным величинам, которые должны быть назначены на элементы диаграммы отношений.
Машины могут быть выстроены в одиночный ряд, мультиряд или в круговую планировку в зависимости от последовательности операций. Одиночная планировка ряда может принять различную конфигурацию, например, полукруглую, линейную или U-образную. Машины в одиночной планировке ряда выстроены так близко насколько это возможно к последовательности обработки всех деталей, чтобы минимизировать время передвижения. В этой планировке, последовательность операций обычно подобна от одной детали к другой, и используемое оборудование погрузочно-разгрузочных работ - обычно конвейеры. Планировка мультиряда обычно линейна, и движения деталей могут осуществляться между любыми машинами в различных рядах так же как в одном и том же ряду, что является удобным для FMS. В круговой планировке машины выстроены в овальный путь с однонаправленным движением.
Рисунок 3: Иерархия данных размещения оборудованиия
Тип размещения оборудования затронут множеством факторов, а именно, числом машин, доступным местом, последовательностью и используемой системой погрузочно-разгрузочных работ. Тип оборудования погрузочно-разгрузочных работ играет важную роль в проекте и операции современного завода. Это определяет время передвижения и затрагивает пропускную способность и гибкость FMS. В идеале, разработку размещения оборудования и выбор погрузочно-разгрузочного оборудования нужно рассматривать одновременно. Однако, комбинаторная природа каждой проблемы запрещает объединенное рассмотрение. Обычно, это решается последовательно, где решение первой проблемы используется как вклад ко второй проблеме.
Есть много типов оборудования погрузочно-разгрузочных работ, среди которых и AGVs (Автоматизированные Управляемые Транспортные средства), конвейерные системы и роботы. Конвейерная система более удобна для процессов типа поточной линии, где каждая деталь идет от одной машины в единственной линии, в то время как роботы обычно используются в процессах “job shop” или “FMS”.
Есть два типа движений, связанных с планировкой поточной линии, которая затрагивает поток обработки грузов, а именно, “backtracking and bypassing” с возвратом и с обходом. Возвращение – движение детали от одной машины к другой, которая предшествует ей в последовательности машин в схеме поточной линии. Возвращение происходит, когда обрабатываемые части имеют различную последовательность обработки в типе поточной линии в схеме. С другой стороны, обход происходит, когда деталь пропускает некоторые машины, в то время как она перемещается к концу схемы поточной линии. Подобно возвращению, обход происходит из-за различия в последовательности обработки грузов частей. В идеале, оба из этих движений должны быть минимизированы в максимально возможной степени, так как они затрагивают стоимость движения и производительность.
Обычная техника нахождения лучшей возможной планировки вовлекает использование диаграмм и графов. Детальный анализ должен быть проведен по направлению деталей, передвигаемому объему, расстоянию, частоте передвижения, курсу по которому происходит передвижение детали и стоимость движения. Используются несколько похожих техник - диаграммы сборки, которые дают графическое представление потока деталей, технологические карты операций, многопрофильные технологические карты, ленточная диаграмма, технологические карты и т.д.
Количественные подходы с другой стороны, прежде всего обеспокоены оптимизацией местоположения оборудования с движением материала, и включают методы исследования операций в дополнение к математическим методам. Мера эффективности, используемая в количественном подходе - расстояние, по которому путешествуют части.
Математическая ТехникаСреди методов, используемых в решении проблемы планировки - линейное программирование, задача о назначениях, программирование транспортировки, программирование перегрузки, и интегральное программирование, и т.д. Koopmans и Beckman (1957) развили модель квадратной задачи о назначениях (QAP), чтобы решить планировку мультиряда. В этой модели, цель состоит в том, чтобы минимизировать стоимость транспортировки материалов и деталей, максимизируя прибыль, полученную, вычитанием из прибыли от использования точной планировки транспортные расходы. Garey и Джонсоном (1979) было доказано, что QAP является np-сложной задачей. Используемое уравнение задается как:
Maximise
где,
aij - чистый доход от работающей машины i в местоположении j
cjl - стоимость транспортировки единицы материала от местоположения j к l
fik - поток материала от машины i к k
n - общее количество местоположений
xij = 1, если машина i - в местоположении j и = 0 в другом случае
Другие Методы
Более свежие подходы решения проблемы планировки включают моделируемый отжиг, и генетические алгоритмы. Suresh (1995) использовал генетический подход решения проблемы планировки средств, где цель состоит в том, чтобы минимизировать стоимость взаимодействия между различными отделами. В отличие от проблемы размещения оборудования, проблема планировки средства более сконцентрирована в обнаружении лучшей планировки для ячеек/отделов, а не обнаружения расположения машин. Hassan (1994) дал хорошее описание различий между размещением оборудованиия и планировкой средств или блочным расположением.
Kouvelis (1995) используют цель проекта уменьшение общего возвращающегося расстояния для устройства погрузочно-разгрузочных работ в проблеме планировки ряда автоматизированной производственной системы, где машины выстроены в прямой линии.
Gupta (1996) использовал GA, чтобы найти семейство деталей так же как и планировку между ячейками. В его формулировке, он ограничил расположение ячеек как для линейного одиночного ряда так и для линейный двойного ряда. Разработанный алгоритм – сводится больше к планировке системы ячеек или планировке пола производства, чем к планировке ячейки или размещения оборудования. Фактическую планировку машин в пределах ячеек не рассматривали. Banerjee и Zhou (1995) сформулировали проблему оптимизации проекта средств для планировки одиночной петли, используя генетические алгоритмы. Разработанный алгоритм - для планировки систем ячейки и следовательно не рассматривает планировку машин в пределах ячейки.
Генетические алгоритмы (GA) - адаптивная техника поиска, которая подражает процессу биологического развития (Goldberg (1989)). Метод, используя генетические алгоритмы был развит, чтобы решить проблему размещения оборудованиия, и программирование сделано, используя программное обеспечение Matlab с комплектом инструментов GA (Чипперфильд и. аль. (1994)). Два типа планировки рассматривают, планировка единственного ряда, обычно связанная с проблемами поточной линии, где части должны подвергнуться подобной последовательности процессов, и планировки мультиряда, которая является более соответствующей проблемам цеха, где части могут подвергнуться процессам в любой последовательности. Так как стоимость, связанная с планировкой пропорциональна расстоянию, по которому путешествуют части, алгоритмы, развитые для планировки мультиряда имеет цель уменьшения расстояния, по которому путешествуют части. В формулировках, стоимость, понесенная, используя оборудование погрузочно-разгрузочных работ, как предполагают, является постоянной. Следовательно, проистекающая планировка фактически минимизирует стоимость путешествия по расстоянию. Стоимости генетических используемых параметров задаются начальным населением, произведенным наугад. Стохастическое универсальное осуществление выборки используется, чтобы поручить ожидаемое число потомства быть произведенным в следующем поколении для каждой особи. Конфликт поколений (GGAP) 0.1 используется, что означает, что 10 процентов лучших людей продвигаются к следующему поколению.
Планировка одиночного ряда описана как планировка, которая имеет машины только в одной стороне оборудования погрузочно-разгрузочных работ. Тип оборудования погрузочно-разгрузочных работ, используемого в этом типе планировки - обычно конвейерная система или AGV. В производственном процессе, однако, есть случаи, где не все части пройдут все машины для того, чтобы обработать в той же самой последовательности. Некоторые части, возможно, должны возвратиться конвейер, чтобы подвергнуться определенному процессу. Обработка таких частей обычно делается, используя AGVs или оператор, предполагая, что конвейер однонаправлен. Для этого типа проблемы, соответствующая цель, которая используется состоит в том, чтобы минимизировать возвращение. Формула дается следующим образом:
где
wij = число частей обработанных в машине i в единицу времени, которое должно быть разбито к j.
xij =, назад отслеживают расстояние от машины j к i.
Wij матрица - фактически из/в диаграмму, которая показывает число партий, которое идет от одной машины от другого.
Эта матрица получена, используя информацию, найденную в последовательности процесса для всех частей. Если последовательность, быть изменен, отличное от матрицы будет сформировано.
Представление хромосомы основано на перестановке целых чисел, представляющих последовательность машин в планировке. Например, особь {3 2 1 4} представил бы планировку машины 3 сопровождаемый машинами 2, 1 и 4, соответственно. Xij матрица может быть вычислена основанная на каждом особи. Эта матрица показывает индивидуальное возвращающееся расстояние в зависимости от планировки. Тем не менее, части, которые обходят определенную операцию, не включены, так как стоимость обхода определенного автоматизированного рабочего места минимальна в конвейерной системе по сравнению с стоимостью возвращения. Следовательно, общее возвращающееся расстояние всех частей дает объективную стоимость особи. Генетические операторы, используемые в этой формулировке - операторы на основе заказа и операторы на основе положения.
Планировка мультиряда обычно связывается с цехом и FMS, где части могут быть обработаны в любой последовательности. Обычно, последовательность обработки оптимизирована, используя различные методы планирования. Планировка основана на последовательности, найденной, минимизируя расстояние, по которому путешествуют. В отличие от планировки единственного ряда, оборудование погрузочно-разгрузочных работ, используемое для планировки мультиряда - AGVs или человеческие операторы, чтобы обращаться с подъемами вилки или другим оборудованием.
Представление хромосомы основано на перестановке целого числа, которые представляют числа машины, где местоположение гена представляет местоположение машин. Например: хромосома {5 2 1 3 4} представила бы планировку, показанную в рисунке 4.
Рисунок 4: Layout for chromosome
{5 2 1 3 4}
Расстояния между местоположениями, так же как возможными местоположениями машин, известны заранее, следовательно цель состоит в том, чтобы найти лучшее положение машин, которые минимизировали бы общее расстояние, по которому путешествуют части. Другие важные данные, требуемые для проблемы планировки - частота движения между машинами, которое указывает количество раз, которое часть должна переместить от одного местоположения до другого.
Критерий, чаще всего используемый в проблеме планировки должен минимизировать стоимость путешествия частей, со стоимостью, связанной с расстоянием, по которому путешествуют. Следовательно, цель сформулирована как уменьшение общего расстояния путешествия частей. Целевая функция дается следующим образом:
где,
fij = frequency/volume движения
cij = cost, чтобы переместить одну единицу загружают в одну единицу расстояния между двумя машинами
dij = distance между машиной i и j.
Принятие стоимости cij остается постоянным, цель была бы уменьшена до уменьшения общего расстояния, поехало для частей. В определенной компании, которые предвидят возможное будущее расширение shopfloor, есть вполне достаточное доступное место, создавая ситуацию, где число возможных местоположений машины превышает число машин. В этой ситуации, фиктивные числа машины используются в представлении. Например, в случае семи местоположений и 5 машин, мы поручаем машину 6 и 7 быть фиктивными машинами и машинами 1-5 как реальные машины. Алгоритм найдет местоположения, которые минимизируют общее расстояние, по которому путешествуют части, оставляя пустые места для местоположений, назначенных на фиктивные машины. Эти пустые места могут использоваться для других использований, типа области хранения в цехе. Если компания решает купить дополнительные машины, эти места будут тогда использоваться, чтобы поместить новые машины.
Этот документ описывает в детальных проблемах относительно проблемы размещения оборудованиия, связанной с гибкими производственными модулями. Новый подход, используя генетические алгоритмы предложен, чтобы обращаться с проблемой. Два алгоритма развиты, чтобы решить единственные планировки ряда и мультиряда в клеточном гибком производственном модуле, чтобы найти относительные местоположения машин в ячейке. Результаты, о которых сообщают, показывают, что генетические подходы в состоянии произвести хорошие решения в разумно короткое вычислительное время по сравнению с использованием исчисляющих подходов. Преимущество этого алгоритма состоит в том, что размещение оборудованиия может быть определено, используя минимальное количество данных, предлагая преимущество в областях, где стоимость изменения от одной планировки до другого не известна из-за отсутствия данных относительно стоимости, понесенной в расстояние движения. Однако, в планировке мультиряда, если бы используемое оборудование погрузочно-разгрузочных работ отличается от одного местоположения к другому, и таким образом понесенная себестоимость единицы продукции изменилась бы, этот алгоритм мог все еще применяться, включая себестоимость единицы продукции, cij, в целевой функции.