Single Row Facility Layout Problem SRFLP

O SRFLP trata-se de um problema de pesquisa desafiador que possui diversas aplicações na vida real. Nos setores produtivos, o algoritmo modela o layout linear das máquinas dentro das células de fabricação. Neste tipo de layout, as máquinas são colocadas ao longo de um caminho direto, que viabilize de forma otimizada o fluxo de pessoas e materiais (HERAGU e KUSIAK, 1988). Outras aplicações do SRFLP incluem a organização de instalações, máquinas, equipamentos em corredores de supermercados, hospitais e escritórios (SIMMONS, 1969), podendo até organizar livros em uma prateleira em uma biblioteca (PICARD e QUEYRANNE, 1981). Devido à importância prática do SRFLP, dedicação considerável foi dado ao desenvolvimento de algoritmos para sua solução. Já Simmons (1969, 1971) apresentou um algoritmo de ramificação e limitação para resolver o problema de ordenação linear, propôs um algoritmo que gera uma sequência de máquinas que aplicado, é capaz de resolver a organização da linha geral de um problema de layout da instalação.

Este algoritmo stepwise, referido por Kusiak (1990) como o algoritmo Modified Spanning Tree (MST), seleciona o par de instalações com o maior elemento no fluxo matriz e, em seguida, prossegue adicionando instalações para a esquerda e a direita desse par. Teste de Performance O comportamento da heurística já foi avaliado em diversos casos com 4 à 30 instalações. Em todos os problemas considerados, as dimensões das instalações eram diferentes. Para avaliar a eficácia da heurística, o custo de manuseio de materiais e o tempo computacional de cada problemática foram comparados com a solução fornecida por outros métodos heurísticos de uma única fila, como os apresentados por Hall (1970), Neghabat (1974), Heragu e Kusiak (1988), Heragu e Kusiak (1991) e Heragu e Alfa (1992). O algoritmo de Heragu e Kusiak produz soluções inferiores em termos de custo, mas é computacionalmente mais barato que em relação a outras heurísticas.

Para problemas de proporções maiores, o algoritmo de Hall é o menos caro computacionalmente entre todos os métodos. O terceiro conjunto de problemas consiste em 8 dilemas. As dimensões das instalações e a matriz de fluxo para o problema 1 podem ser encontradas em Beghin-Picavet e Hansen (1982), para os problemas 2 e 6 em Love e Wong (1976b) e para os problemas 3, 4 e 5 em Simmons (1969). A matriz de fluxo para os problemas 7 e 8 pode ser encontrada em Nugent et al. problemas de layout e, portanto, o SRLP pode ser categorizado de acordo com sua formulação de modelo, representação, tipo de dados de entrada, função objetivo e métodos de solução. Desta forma, Kumar et al (1995) acrescentam dois critérios: o tema geral do algoritmo e as folgas, que são consideradas como uma extensão de modelo interessante e maduras para pesquisas futuras.

Tema As publicações são divididas em seus temas gerais, se novos modelos (M) ou abordagens de solução (S) são apresentados, uma análise estrutural (A) de SRLP é discutida ou a literatura de SRLP é resumida em uma revisão (R). Grande parte dos pesquisadores se concentram no desenvolvimento de abordagens mais eficientes ou novas formas de solução, por exemplo, adotando conceitos biológicos (Kumar et al. Entretanto, novas formulações de modelos e discussões analíticas não alcançaram uma relevância semelhante em relação ao número de artigos publicados sobre o assunto. Os autores propõem um possível esquema de classificação de problemas de layout de instalações, em que o layout de fila única é uma configuração de layout especial afetada pelo sistema de manuseio de materiais.

Um levantamento sobre métodos para SRLP é feito por Hungerländer e Rendl (2013a), no qual eles comparam distintas abordagens de modelagem. Formulação de modelo Na literatura revisada, foi encontrado diversas formulações de modelos para SRLP que pertencem a modelos de programação linear ou não linear, PL ou NPL, respectivamente. Restringindo o domínio de variáveis, eles também podem ser diferenciados em modelos inteiros mistos (IM) ou inteiros puros (IP), onde apenas algumas ou todas as variáveis devem ser valores inteiros. As formulações geralmente mais encontradas são não-lineares, como a formulação de atribuição quadrática tradicional (QAP) ou ABSMODEL (ABS) introduzida por Heragu e Kusiak (1991). Formalmente, a variável binária Xij leva o valor 1 se a máquina é atribuído à alguma localização, e j é atribuido ao valor 0 caso contrário.

Ao assumir locais conhecidos, as distâncias Dhk entre os centroides de dois locais, h e k, na linha também estão predefinidos e não mudam de acordo com diferentes tarefas de máquinas. Implicando, de forma implícita, que as máquinas são assumidas como sendo idênticas em tamanho e forma, geralmente retangulares ou quadrado. Desta forma, não é necessário considerar a orientação das máquinas que não influenciam a atribuição ou o cálculo da distância. Representações contínuas O SRLP contínuo tem o objetivo de superar as desvantagens acima mencionadas das representações do modelo discreto. Na prática, em sistemas produtivos, isso só pode ser realizado se um mínimo de espaço entre as máquinas (clearance eij) está de acordo com questões de segurança e considerações operacionais do processo.

Em produções diferentes, existe a necessidade de armazenar produtos ou componentes temporariamente em ordem a ser processada na máquina ou a ser manipulada pelo sistema de transporte de material (SOLIMANPUR et al. Da mesma forma, que o carregamento de máquinas de descarga requerem espaço suficiente para garantir operações seguras e movimento para os trabalhadores (OZCELIK, 2012). Brunese e Tanchocoa (2013) referem-se a ocorrência de manutenção quando ocorrem falhas na máquina e os componentes devem ser trocados ou reparados. Interações indesejadas de máquinas adjacentes devido à emissão de oscilações ou outros elementos de interferência, como as ocasiões acima mencionadas, exigem liberação de diferentes tamanhos de espaços entre máquinas (CHAIEB e KORBAA, 2003). No entanto, especialmente, se o objetivo almejado é a minimização de backtracking ou maximização em sequência, fluxos assimétricos influenciarão o valor objetivo e o arranjo de layout devido à determinação de qual movimento de fluxo, de i para j ou de j para i, precisando ser retrocedido ou avançado.

Wang e Sarker (2002) e Yu e Sarker (2003, 2006) consideram a conceito de matriz de fluxo assimétrico. Em contraposição, Samarghandi e Eshghi (2010) aborda o caso especial de movimentos de fluxo idênticos entre cada par de máquinas (i, j) com cij = c, então a função objetivo é composto apenas de distâncias da máquina. Desta forma, este caso é usado para gerar soluções viáveis ​​iniciais. Mensuração de distância Na representação discreta, presume-se que todas as máquinas são equidistantes, com exceção dos artigos publicados por Yu e Sarker (2006) e Diponegoro e Sarker (2003). Em grande parte dos casos, os custos de manipulação do material de uma máquina para outra é linearmente proporcional à distância entre elas. É salientado de que apenas três documentos levantam essa suposição de custos por partes linear (Chan & Malmborg, 2010a) e, consequentemente, os custos de transporte não-linear (Chan & Malmborg, 2010b; Chan & Malmborg, 2013).

No entanto, Braglia et al. adicionam custos de atribuição, que são característicos das formulações do modelo de layout dinâmico. Além do custo de atribuição, Ou-Yang e Utamima (2013) usam um termo de penalização para garantir que restrições de segurança são mantidas. As operações de retrocesso devem ser realizadas contra o fluxo de material principal em sistemas unidirecionais, que dificultam o fluxo de trabalho e afetam a produtividade e os custos (Morad, 2000). Enquanto que, nessa conta, esse movimento de fluxo é o menos cobiçável, os movimentos correspondentes ao fluxo principal ou viável devem ser aumentados. Após isso, Ponnambalam e Ramkumar (2001) e Chen et al. maximizam o número de movimentos em sequência. Além da maioria das publicações com parâmetros de otimização baseados em distância, é observado poucos trabalhos propondo outros objetivos.

Desta forma, um critério de diferenciação comum em problemas de layout de instalações é o método de solução em uso, são destacados quatro tipos de métodos: abordagens exatas, heurísticas, meta-heurísticas e métodos de solução que não podem ser incluídos nas abordagens anteriores e são resumidos como outros (KUMAR et al, 1995). Como o SRLP é uma otimização combinatória de resolução difícil, apenas pequenas instâncias do problema - até 40 máquinas - podem ser resolvidas por algoritmos exatos. Predominantemente, os algoritmos usam técnicas de relaxamento para reduzir o problema de otimização e diminuir a complexidade computacional (HUNGERLÄNDER, 2014). Ainda que o algoritmo exato gere soluções ótimas globais e, portanto, seja favorecido por muitos pesquisadores, abordagens de soluções aproximadas ganharam muito mais atenção nos últimos anos (KUMAR et al, 1995).

Meta-heurísticas são amplamente discutidas por quase metade dos autores, enquanto o número de artigos que abordam métodos heurísticos diminui, em contraste com os anos anteriores a 2000. Grande parte dos autores simplifica os modelos de otimização removendo restrições específicas para que o problema relaxado resultante possa ser resolvido de forma mais simplificada, e assim obter um resultado ideal. Normalmente, distingue-se entre relaxações baseadas em PL e baseadas em SDP, das quais modelos de programação linear e modelos baseados em matriz estão relaxados, respectivamente. Desta forma, o espaço de solução viável aumenta, e o valor ideal do problema relaxado é concomitante com um ótimo do problema original se satisfizer a restrição relaxada. Geralmente, nenhuma satisfação é obtida e, portanto, relaxamentos fornece apenas um limite inferior do problema original.

ANJOS et al, 2005). Este último introduz um estágio de dois processos heurísticos em que o problema é primeiro decomposto em vários problemas da máquina e depois a atribuição de fluxo correspondente é obtido. Diponegoro e Sarker (2003) usam propriedades específicas de distância entre as máquinas em sua heurística para encontrar uma solução eficiente. Em relação à fabricação em layout de células Wang e Sarker (2002) determinam uma solução inicial através de uma heurística de comparação de três pares onde a técnica Bubble Search melhora a solução inicial. Já Kothari e Ghosh (2013a) introduziu uma heurística baseada em uma inserção de pesquisa neigbourhood. A heurística de Kothari e Ghosh (2013) é capaz de melhorar as soluções mais conhecidas de algumas instâncias de problemas.

“Fuzzy approach to the robust facility layout in uncer tain production environments. ” International Journal of Production Research, 30 (18),4089–4101. ANJOS,M. F. Kennings,A. Moghaddam, M. Asadzadeh, S. Negahban, A. “An integrated fuzzy simulation fuzzy data envelopment analysis algorithm for job shop layout optimization: The case of injection process with ambiguous data. ” European Journal of Operational Research, 214,768–779. “Layout design in dynamic environments: Strategies and quantitative índices”. International Journal of Production Research, 41 , 995–1016. BRUNESE, P. TANCHOCOA,J. “On implied within building constraints for machine layout. “A monte carlo simulation based heuristic procedure for solving dynamic line layout problems for facilities using conventional material handling devices. ” International Journal of Production Research, 48(10), 2937–2956. CHAN, W. K. MALMBORG, C. CHAN, W. K. MALMBORG, C. J. “Theory and applications of Monte Carlo simulations “(pp. R. a). “Flow distance reduction for a multi-product flowline with sets of identical machines.

” European Journal of Operational Research, 147(3), 591–612. DIPONEGORO, A. HASSAN, M. M. D. “Machine layout problem inmodernmanufacturing facilities. ” International JournalofProduction Research, 32,2559–2584. HUNGERLÄNDER, P. Single-row equidistant facility layout as a special case of single-row facility layout. International Journal of Production Research, 52(5), 1257–1268. HUNGERLÄNDER, P. Rendl, F. SlAM Journal on Applied Mathematics 15/3, 693-718. KELLER, Birgit. BUSCHER, Udo. Single row layout models. European Journal of Operational Research 245 (2015) 629–644. KUMAR, K. Ravi. HADJINICOLA, George C. LIN, Ting-li. A heuristic procedure for the single-row facility layout problem. ” International Journal of Production Research,49,6749–6768. KUSIAK, A. “Intelligent Manufacturing Systems, Prentice-Hall, Englewood Cliffs”, NJ. LIN, M. T. “Hybrid estimation of distribution algorithm for solving single row facility layout problem”. Computers & Industrial Engineering, 66(0), 95–103. OZCELIK, F. “A hybrid genetic algorithm for the single row layout problem. ” International Journal of Production Research,50,1–15. RAMKUMAR, V.

“A genetic algorithm for the design of a single row layout in automated manufacturing systems. ” The International Journal of Advanced Manufacturing Technology, 18,512–519. SAMARGHANDI, H. ESHGHI, K. “A particle swarm optimization for the single row facility layout problem. ” Computers & Industrial Engineering, 58(4), 529–534. SARKER, B. R. WILHELM, W. Operations Research, 17(5), 812–826. SIMMONS, D. M. One-dimensional space allocation: An ordering algorithm", Operations Research 17/5, 812-826. SIMMONS, D. “An antalgorithm for the single row layout problem in flexible manufacturing systems. ” Computers & Operations Research,32(3),583–598. WANG, S. SARKER, B. R. “A directional decomposition heuristic for one-dimensional,non-equidistant machine-cell location problems. ” Computers & Operations Research, 33(1), 64–92.