Slide - Programação de Sistemas Flow-shop e Job-shop - Pesquisa Operacional 2 - 2023-2

SEP 406 SEP 406 PESQUISA PESQUISA OPERACIONAL OPERACIONAL II II Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Departamento de Engenharia de Produção Departamento de Engenharia de Produção Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 2 Programação de Sistemas Flow-Shop e Job-Shop CONSIDERAÇÕES GERAIS:  n  2 finito, número de tarefas a serem processadas.  conjunto de gi operações (1  gi  m). • Precedências tecnológicas entre as operações de uma tarefa Ji (estrutura linear):  n  i 2 1 ,..., J ,..., J J , J = J   igi ij i2 i1 i ,..., op ,..., op , op op = J opi1 opi2 opij opigi Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 3 • ri = r ou ri = 0 i = 1, 2, …, n. • pij = cte tempo de processamento da opij.  m  2 finito, conjunto de máquinas distintas. Cada máquina  M é capaz de executar um sub-conjunto de operações das diversas tarefas, sendo identificada através desse sub-conjunto de operações. • Demais hipóteses do Job-Shop básico.  m  2 1 ,..., M M , M = M Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 4 Algoritmo de Johnson para a solução do problema n/2/F/Fmax ou M TEOREMA DE JOHNSON "No problema n/2/F/M, a programação ótima é uma programação permutacional onde: A tarefa Ji precede a tarefa Jk se    K1  i2 K2 i1 p , min p p , min p  Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 5 ALGORITMO DE JOHNSON PASSO 1: Determine i = 1, 2, ..., n. PASSO 2A: Se o mínimo tempo de processamento refere-se a uma operação opi1 a ser processada na máquina M1, coloque a tarefa Ji na primeira posição disponível da seqüência de tarefas. Vá para o PASSO 3. PASSO 2B: Se o mínimo tempo de processamento refere-se a uma operação opi2 a ser processada na máquina M2, coloque a tarefa Ji na última posição disponível da seqüência de tarefas. Vá para o PASSO 3. PASSO 3: Remova a tarefa designada do conjunto de n tarefas e volte ao PASSO 1, até que todas as posições na seqüência de tarefas sejam ocupadas (os desempates podem ser feitos arbitrariamente).  i1 p , i2  p min i Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 6 Exemplo: Ji J1 J2 J3 J4 J5 pi1 3 5 1 6 7 pi2 6 2 2 6 5 Estágio Tarefas ainda não programadas Mínimo Pij Designação Seqüência Parcial 1 J1, J2, J3, J4, J5 p31 J3 = J[1] J3 _ _ _ _ 2 J1, J2, J4, J5 p22 J2 = J[5] J3 _ _ _ J2 3 J1, J4, J5 p11 J1 = J[2] J3 J1 _ _ J2 4 J4, J5 p52 J5 = J[4] J3 J1 _ J5 J2 5 J4 p41 = p42 J4 = J[3] J3 J1 J4 J5 J2 Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 7 Exemplo: M1 1 2 3 4 5 6 7 8 9 10 11 1 3 6 7 J3 J1 J1 J5 M2 2 6 6 J3 J4 24 J4 13 14 15 16 17 18 19 20 21 22 23 12 5 J5 2 J2 min M = min Fmax = 24 5 J2 tempo J3 J2 J1 J4 J5 Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 8 Formulações em Programação Linear (Inteira Mista) PROBLEMA n/m/G/M Seja: gi = m (número de operações de cada tarefa). xij = data de término da j-ésima operação opij da tarefa Ji , a ser executada por uma determinada máquina. Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 9 Condições a serem satisfeitas (restrições) a) Precedências tecnológicas entre as operações de uma tarefa (estrutura LINEAR) Considerando todas as n tarefas, ter-se-á um conjunto de mn restrições de precedência tecnológica entre as operações. 0 com x 1, 2, ..., m = j p + x x de restrições conjunto p + x x p + x x p x i0 ij i(j-1) ij im i(m-1) im i2 i1 i2 i1 i1             m  opi1 xi1 opi2 xi2 opij ... x ij opim ... xim Ji tempo Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 10 b) Seqüência entre as operações a serem executadas por uma mesma máquina . seqüência LINEAR de n operações n! seqüências alternativas possíveis. op.. oprs xrs optu xtu MK tempo Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 11 Seja oprs e optu duas operações a serem executadas pela máquina MK. Em uma seqüência qualquer, devemos ter uma das duas situações: ou DISJUNTIVAS RESTRIÇÕES p + x 2a. situação: x Na p + x 1a. situação: x Na rs tu rs tu rs tu          oprs PRECEDE optu optu PRECEDE oprs Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 12 • Para levar em conta as duas situações possíveis, define-se: y = 1 , se a operação op preceder a operação op , na máquina M y = 0 , caso contrário, ou seja: se op preceder op , na máquina M rtK rs tu K rtK tu rs K ; . Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 13 • Desta forma, as restrições disjuntivas para as operações oprs e optu ficam: onde H é um número positivo suficientemente grande, por exemplo, • As restrições disjuntivas deverão ser consideradas para todas as combinações de 2 operações do conjunto de n operações a serem executadas pela máquina MK (K = 1, 2, ..., m), o que leva a um conjunto de mn (n-1) restrições.      rs rtK tu rs tu rtK rs tu p + H y . - x x p ) + H (1 y - - x x H = p i j ij   Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 14 c) Duração total da programação (M) M x im i = 1, 2, ..., n (n restrições)  Última operação da tarefa Ji M Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 15 Formulação: Minimizar M com                  0 i = 1, 2, ..., n. - x M t > r t = 2, 3, ..., n p + H y . - x x r = 1, 2, ..., n - 1 K = 1, 2, ..., m p ) + H (1 y - - x x i = 1, 2, ..., n j= 1, 2, ..., m p - x x a Sujeito im rs rtK tu rs tu rtK rs tu ij i(j-1) ij M , x 0 H = p i j ij ..    y {0, 1} x = 0 . r t k io  Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 16 • OBS.: Exercício: Formular o problema n/m/G/F , em termos de Programação Linear.    + 1 2 = mn (n +1) 2 mn + mn (n -1) + 1 de variáveis = No. de restrições = mn + mn (n -1) + n = n(mn +1) No. n = 4 m = 3 52 restrições 31 variáveis n = 10 m = 5 510 restrições 276 variáveis _ Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 17 Métodos Heurísticos PROBLEMA n/m/F/M (e n/m/P/M) P = programação Flow-Shop permutacional ALGORITMO DE CAMPBELL, DUDEK e SMITH (CDS) Baseado em duas propriedades: a) Utiliza a Regra de Johnson de forma heurística. b) Geralmente obtém diversas programações viáveis, sendo destas escolhida a melhor. Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 18 Algoritmo CDS Corresponde a um procedimento heurístico de Múltiplos Estágios, onde em cada estágio é aplicada a Regra de Johnson a um novo problema (com m = 2) proveniente do problema original, utilizando tempos de processamento p*i1 e p*i2, como segue: • Estágio 1: • Estágio 2: • Estágio s: p = p p = p i1 i1 i2 im * * p = p + p p = p + p i1 i1 i2 i2 im i(m-1) * * p = p p = p i1 ij i2 i(m-j+1) j=1 s j=1 s * *   Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 19 Ou seja: • No estágio 1, aplica-se a Regra de Johnson considerando-se somente a primeira e a última máquina (as demais são ignoradas). • No estágio 2, aplica-se a Regra de Johnson às somas dos tempos de processamento da primeira com a segunda máquina e da última com a penúltima máquina. • E assim, sucessivamente, até o estágio (m - 1). Em cada estágio, a seqüência das tarefas obtida é usada para calcular a correspondente duração total da programação (M). A melhor programação é escolhida dentre as (m - 1) programações viáveis obtidas nos (m - 1) estágios. Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 20 Exemplo: • melhor seqüência obtida: J3, J5, J4, J1, J2. • Duração total da programação M = 35 . Ji J1 J2 J3 J4 J5 M1 pi1 6 4 3 9 5 M2 pi2 8 1 9 5 6 M3 pi3 2 1 5 8 6 Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 21 PROBLEMAS n/m/G/M e n/m/G/F ALGORITMO GERAL para obtenção de soluções heurísticas (versão modificada do algoritmo proposto por BAKER) Seja: • PSt = uma programação parcial na qual estão já programadas t operações; • COCt = o conjunto de operações CANDIDATAS a serem programadas no estágio t, correspondente a uma dada PSt; • Ev = data mais cedo de início da operação opv  COCt, a ser executada por uma máquina MK; Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 22 Cprec = data de término da operação que precede diretamente a opv; CK = data de "liberação" da máquina MK, a qual deverá executar a opv. M K op prec. Cprec. CK M. E v = max {Cprec. , CK} tempo Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 23 ALGORITMO • PASSO a: Faça t = 0 e inicie com PS0 como a programação parcial nula. Inicialmente COC0 inclui todas as operações sem operações precedentes, ou seja, as primeiras operações de todas as tarefas; • PASSO b:Calcule o valor de Ev das operações opv pertencentes a COCt. Determine a MENOR DATA entre os Ev dessas operações. Denote essa data por E* ; • PASSO c: Identifique as máquinas que executam as operações com Ev = E* ; Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 24 • PASSO c.1: Programe todas as operações pertencentes à COCt com Ev = E* , cujas máquinas têm uma única designação nesse conjunto COCt; • PASSO c.2: Agrupe as operações pertencentes a COCt com Ev = E* não programadas no passo anterior, de acordo com a máquina a ser utilizada. Esses grupos constituem os conjuntos de OPERAÇÕES CONFLITANTES. Operações conflitantes são aquelas que têm a mesma data de início E* e que utilizam uma mesma máquina. Para cada conjunto de operações conflitantes, calcule os ÍNDICES DE PRIORIDADE de acordo com a Regra de Prioridade (R) adotada. Para cada conjunto de operações conflitantes, coloque na Programação Parcial a operação com o MELHOR ÍNDICE DE PRIORIDADE (desempate arbitrário ou de acordo com uma segunda regra de prioridade), programando-a o mais cedo possível; Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 25 • PASSO d: Para a nova Programação Parcial criada nos passos (c.1) e (c.2) atualize os dados da seguinte maneira: – (i) Incremente t de h unidades, onde h é o número de operações programadas nos passos (c.1) e (c.2); – (ii) Remova de COCt as operações já programadas nos passos (c.1) e (c.2); – (iii) Forme o conjunto COCt+h ao adicionar a COCt as operações imediatamente sucessoras (da mesma tarefa) daquelas que foram programadas nos passos (c.1) e (c.2). • PASSO e: Retorne ao PASSO b considerando a Programação Parcial PSt+h gerada nos passos (c.1) e (c.2), até que uma Programação Completa tenha sido obtida. Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 26 REGRAS DE PRIORIDADE usuais: • SPT (Shortest Processing Time): seleciona a operação com o menor tempo de processamento. • FCFS (First Come First Served): seleciona a operação que entrou no conjunto em primeiro lugar. • MWKR (Most Work Remaining): seleciona a operação correspondente à tarefa que tem a maior quantidade de trabalho remanescente a ser executado (medida em unidades de tempo). • MOPNR (Most Operations Remaining): seleciona a operação que tem o maior número de operações sucessoras. Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 27 • LWKR (Least Work Remaining): seleciona a operação correspondente à tarefa que tem a menor quantidade de trabalho remanescente a ser executado. • RANDOM: seleciona a operação de maneira aleatória, ou seja, por "sorteio". • OBS: – regras que têm se mostrado relativamente melhores para o problema n/m/G/F: SPT / LWKR – regra que tem se mostrado relativamente melhor para o problema n/m/G/M: MWKR. _ Prof. Dr. Marcelo S. Nagano Prof. Dr. Marcelo S. Nagano Pesquisa Operacional III Pesquisa Operacional III 28 Exemplo: 4/3/G/M R = MWKR (desempates com SPT) Ji J1 J2 J3 J4 pi1 4 1 3 3 pi2 3 4 2 3 pi3 2 4 3 1 Ji J1 J2 J3 J4 opi1 M1 M2 M3 M2 opi2 M2 M1 M2 M3 opi3 M3 M3 M1 M1 Tempos de processamento Quadro de precedências (Routing)