TÉCNICAS DETÉCNICAS DE PROGRAMAÇÃO … · Processo de tomada de decisão presente tanto em sistemas de produção como em ambientes de processamento de informações, além das

TÉCNICAS DETÉCNICAS DETÉCNICAS DETÉCNICAS DE PROGRAMAÇÃO PROGRAMAÇÃO PROGRAMAÇÃO PROGRAMAÇÃO

DE OPERAÇÕES EM MÁQUDE OPERAÇÕES EM MÁQUDE OPERAÇÕES EM MÁQUDE OPERAÇÕES EM MÁQUINASINASINASINAS

Hélio Y.Hélio Y.Hélio Y.Hélio Y. FuchigamiFuchigamiFuchigamiFuchigami

2010

versão 2

Programação de Operações em Máquinas - Hélio Fuchigami � 1

1. PROGRAMAÇÃO DA PRODUÇÃO

1.1. Definições

Programação da produção (“ scheduling” )

� Alocação de recursos escassos para a execução de tarefas em uma base de

tempo. (BAKER, 1974)

� Processo de tomada de decisão presente tanto em sistemas de produção como em

ambientes de processamento de informações, além das empresas de transporte e

distribuição e outros tipos de serviços industriais. (PINEDO, 1995)

� Recursos:

� máquinas em uma fábrica

� pistas em um aeroporto

� trabalhadores em construções

� unidades de processamento em ambiente computacional

� Tarefas:

� pedidos de produção (ordens de serviço ou de produção)

� decolagens e aterrissagens de aviões

� estágios de um projeto de construção

� execuções de programas computacionais

Definições clássicas:

� Tarefa: conjunto de operações inter-relacionadas por restrições de precedência e

tecnológicas

� Operação: atividade elementar a ser executada

� Máquina: equipamento, dispositivo ou instalação capaz de executar uma operação

� Tempo de processamento: tempo requerido para execução de uma operação

Etapas da programação da produção:

� Alocação: associação das tarefas às máquinas

� Sequenciamento: ordenação das tarefas em cada máquina

� Programação: definição do instante de início e término de cada operação

2 � Programação de Operações em Máquinas - Hélio Fuchigami

� Programação da produção é uma das atividades mais complexas:

� Diferentes recursos e habilidades de pessoal e natureza combinatorial

� Para n tarefas há n! sequências possíveis

� Para n tarefas e m máquinas há (n!)m programações

� Importante ferramenta: Gráfico de Gantt

� inventado em 1917 por Henry Laurence Gantt (1861-1919)

� representa visualmente por barras o tempo de processamento das operações

� indica início e fim das atividades e o seu progresso

� vantagem: representação visual simples de cada operação

EXEMPLO: INFLUÊNCIA DA PROGRAMAÇÃO

� 3 máquinas em série: corte, costura, passadoria

� 4 tarefas (produtos): meia, cueca, lingerie, pijama

Sequência 1

Figura 1 – Exemplo de programação de quatro tarefas em três máquinas usando uma sequência aleatória

� duração da programação: 21

� tempo total de espera das máquinas para início da 1ª tarefa: 6

� tempo total de máquina ociosa: 13

Sequência 2

Figura 2 – Exemplo de programação de quatro tarefas em três máquinas usando uma nova sequência aleatória


� duração da programação: 27

� tempo total de espera das máquinas para início da 1ª tarefa: 16

� tempo total de máquina ociosa: 22

� vantagens:

o se as primeiras tarefas tiverem menor prazo de entrega

o se quiser reduzir tempo ocioso entre as operações (no-idle)

1.2. Classificação de problemas

Legenda: Tarefa a processar

Tarefa processada

Máquina

Fluxo das tarefas

� Máquina única: apenas uma máquina disponível para o processamento

Exemplos: pista em um aeroporto, equipamentos de uma sala de cirurgia

Figura 3 – Ilustração de um problema de máquina única

� Máquinas paralelas: várias máquinas disponíveis para o processamento (cada

tarefa pode ser processada em qualquer máquina, porém em apenas uma)

Exemplos: vários pontos de atracação de navios, caixas de banco

Figura 4 – Ilustração de um problema de máquinas paralelas

M ... ...

M2 ... ...

M1

Mm

. . .


� Flow shop : as tarefas possuem um fluxo de processamento passando por várias

máquinas (cada máquina é um estágio de produção)

Exemplos: máquinas de uma célula de produção, operações de fundição e laminação

Figura 5 – Ilustração de um flow shop

Observação: quando a ordem de processamento das tarefas em cada máquina é a

mesma, o problema é denominado flow shop permutacional

Figura 6 – Ilustração de um flow shop permutacional

Figura 7 – Ilustração de um flow shop não permutacional

� Flexible flow shop : flow shop em que os estágios de produção podem conter

várias máquinas disponíveis

Exemplos: várias prensas operando em paralelo

Figura 8 – Ilustração de um flexible flow shop

M1 ... ... M2 Mm ...

M1 M2 M3 J1 J2 J3 J4

J1 J2 J3 J4 J1 J2 J3 J4 J1 J2 J3 J4

J1 J2 J3 J4

M1 M2 M3 J1 J2 J3 J4

J3 J1 J4 J2 J2 J3 J1 J4 J4 J2 J1 J3

J4 J2 J1 J3

... ... ... M2

M1

. . .

Mm1

M2

M1

. . .

Mmg

Estágio 1 ... Estágio g


� Job shop : cada tarefa tem seu fluxo individual ou rota específica nas máquinas

Exemplos: oficina de manutenção, funilaria de carros, oficina de ferramentaria

Figura 9 – Ilustração de um job shop

M1 ... ...

M2

M3


2. PROCESSO GERAL DE PROGRAMAÇÃO DE OPERAÇÕES EM MÁQUINAS

2.1. Hipóteses dos problemas de programação

1) As tarefas e os seus dados relevantes ao problema (tempos de processamento e

de setup, datas de liberação, prazos de entrega, penalidades) são conhecidos

previamente.

2) Todas as tarefas deverão ser executadas.

3) A sequência das operações de cada tarefa (rota) é conhecida e a sua execução

deve respeitar as precedências tecnológicas. O processo de execução também é

conhecido e deve existir pelo menos um conjunto de recursos capaz de executar

cada operação.

4) Os recursos (mão-de-obra, máquinas, equipamentos, ferramentas etc.) a serem

utilizados na execução das tarefas são previamente especificados.

5) Cada máquina está disponível desde o início da programação e assim

permanece continuamente durante um período de tempo suficiente para executar

todas as tarefas. Não são consideradas indisponibilidades temporárias devido a

quebras ou manutenção.

6) Uma máquina não pode executar duas operações simultaneamente.

7) Cada operação pode ser executada por somente uma máquina.

8) Não é permitida a interrupção (preemption) da execução de qualquer operação.

9) As tarefas podem esperar entre dois estágios de produção e o armazenamento

intermediário (buffer) é ilimitado.

10) As operações de cada tarefa não podem ser subdivididas (no splitting).


2.2. Medidas de desempenho

Variáveis que definem um problema de programação:

� n tarefas: J = {J1, ..., Jn} � m máquinas: M = {M1, ..., Mm} � rj: data de liberação da tarefa j (release date)

� dj: data de entrega (prazo) da tarefa j (due date)

� opjk: k-ésima operação da tarefa j; conjunto de g operações: {opj1, opj2, ..., opjg} � pjk: tempo de processamento da tarefa j na máquina k (“pj” com uma máquina)

� sjk: tempo de setup da tarefa j na máquina k (“sj” com uma máquina)

Figura 10 – Ilustração das variáveis que definem um problema

Variáveis que descrevem a solução de um problema de programação:

� Wjk: tempo de espera da tarefa na máquina k � Cj: data de término da tarefa j

� Fj: tempo de fluxo da tarefa j (Fj = Cj – rj )

� Lj: pontualidade (lateness) da tarefa j (Lj = Cj – dj )

o Lj > 0: atraso o Lj < 0: adiantamento

� Tj: atraso da tarefa j (Tj = max{0,Lj} )

J1

r1=3

s1=2

M1

p1=6

C1=11 d1=14


Figura 11 – Ilustração das variáveis que descrevem a solução de um problema

Medidas de desempenho mais comuns:

� Duração total da programação (makespan): Cmax = max Cj

� Tempo total de fluxo (flowtime): ΣFj

� Tempo médio de fluxo (flowtime médio): ∑ ==

n

j jFn

F1

1

� Pontualidade (lateness): ΣLj

� Atraso máximo (tardiness): Tmax = max Tj

� Atraso total (total tardiness): ΣTj

� Número de tarefas atrasadas (tardy jobs): nT

EXERCÍCIO

1) Com os valores das variáveis definidas em cada conjunto de tarefas, considere a ordem de processamento tal como aparece na tabela. Construa o gráfico de Gantt representando os valores de Cj, Fj e Tj.

a) J1 J2 J3 rj 3 10 6 pj 6 2 3 dj 11 12 13

b) J1 J2 J3 J4 rj 1 5 9 10 pj 2 3 2 5 dj 2 9 7 12

2) Calcule cada uma das medidas de desempenho para o problema da Figura 8.

J2

r1=2

M1

p1=4

C2=17

d2=15

J1

W1=3

C1=9

p2=8

r2=5

L2>0 (atraso: T2=2)

d1=12

L1<0 (adiantamento)

F1=7

F2=12


2.3. Notação dos problemas

Notação de 3 campos: γβα

α : ambiente de produção (1, P, J, F) com o número de máquinas ou estágios

β : propriedades (ou restrições) dos recursos e tarefas (rj, dj, sj, ∅∅∅∅)

γ : medida de desempenho (Cmax, F , Tmax, ...)

Exemplos:

� max||2 CF : flow shop com duas máquinas e minimização do makespan (Problema

de Johnson)

� FP || : máquinas paralelas e minimização do flowtime médio

� max||1 Tsj : máquina única com tempos de setup e minimização do atraso máximo

2.4 Regras de sequenciamento

� “Regras de sequenciamento”, “regras de prioridade” ou “regras de despacho”

� Regras de decisão lógica que seleciona uma ordem de produção a ser executada

em uma máquina que ficou livre

� Vantagens: simplicidade, facilidade de implementação, úteis na prática

Regras mais conhecidas:

� SPT (Shortest Processing Time): sequenciar pelo menor tempo de processamento (pj)

� LPT (Longest Processing Time): sequenciar pelo maior tempo de processamento (pj)

� WSPT (Weighted Shortest Processing Time): sequenciar pela maior razão entre a

prioridade (ou penalidade de atraso) e o tempo de processamento, ou seja, pelo

maior valor de wj/pj

� WLPT (Weighted Longest Processing Time): sequenciar pela menor razão wj/pj

� EDD (Earliest Due Date): sequenciar pela menor data de entrega (dj)


� MS (Minimum Slack Time): sequenciar pelo menor tempo de folga, ou seja, pelo

menor valor de dj – pj

� FIFO (First In First Out): sequenciar em “fila”, a primeira que chega é a primeira a

ser processada, ou seja, ordenar pela menor data de liberação rj

� LIFO (Last In First Out): sequenciar em “pilha”, a última que chega é a primeira a

ser processada, ou seja, ordenar pela maior data de liberação rj

� CR (Critical Ratio): sequenciar pela menor razão crítica, ou seja, o tempo

disponível dividido pelo tempo de processamento ( [dj – rj]/pj )

EXERCÍCIOS

1) Considerando os dados do Exercício 1 da página 8, ordene as tarefas de cada conjunto pelas regras SPT, LPT, EDD, FIFO, LIFO e CR. 2) Utilizando as nove regras de sequenciamento descritas na Seção 2.4, ordene as seguintes tarefas:

J1 J2 J3 J4 J5 rj 5 2 1 4 3 pj 3 5 2 6 1 dj 13 7 4 10 8 wj 2 1 3 2 4

3) Uma empresa de consultoria deverá executar 7 projetos, tendo cada um sua data de entrega estabelecida. A empresa é de pequeno porte, de modo que somente executará um projeto de cada vez, ou seja, os projetos serão executados sequencialmente e sem interrupção. De acordo com o contrato, a empresa receberá um prêmio de $800 para cada projeto terminado sem atraso e pagará uma multa de $500 para cada projeto que for concluído após a data de entrega estabelecida. As durações dos projetos e as respectivas datas de entrega são dadas abaixo. Como deverão ser sequenciados os projetos, de forma a maximizar o prêmio líquido? (MOCCELLIN, 1999) Projeto Proj 1 Proj 2 Proj 3 Proj 4 Proj 5 Proj 6 Proj 7

Duração 2 4 6 8 10 12 14

Data de entrega 6 12 30 19 12 18 24


3. PROGRAMAÇÃO DE OPERAÇÕES EM UMA MÁQUINA

3.1. Considerações gerais

Aplicações:

� Oficinas com uma única máquina

� Conjunto de máquinas e equipamentos que operam como se fosse uma única

máquina. Exemplo: indústrias químicas

� Máquina-dominante de um processo. Exemplo: indústria de papel

� Máquina gargalo

Parâmetros:

� n ≥ 2 finito � m = 1 � g = 1 (uma única operação por tarefa) � rj = 0 (todas as tarefas têm a mesma data de liberação, igual a zero) � pj � dj

� Número de sequências possíveis para n tarefas: n! � Todas as n! sequências têm o mesmo valor de Fmax

EXERCÍCIO

1) Considere o problema de máquina única e as sequências obtidas no Exercício 2 da página 10. Construa gráficos de Gantt e analise o desempenho das regras SPT, LPT, WSPT, EDD, FIFO (ou FCFS), MS e CR por meio do tempo total de fluxo, atraso máximo, número de tarefas atrasadas e atraso total.

J1 J2 J3 J4 J5 rj 5 2 1 4 3 pj 3 5 2 6 1 dj 13 7 4 10 8 wj 2 1 3 2 4

2) Resolva o Exercício 1 acima, implementando os problemas no software Lekin.


3.2. Problema F||1

� ∑ ==

n

j jFn

F1

1

� Problema ∑ jF||1

� solução ótima: SPT

Exemplo 1:

J1 J2 J3 J4 J5 pj 5 6 2 5 3

SPT: J3 – J5 – J1 – J4 – J2

J3 J5 J1 J4 J2 Cj 2 5 9 14 20

� Construir o gráfico de Gantt

105

)2014952(* =++++=F

3.3. Problema max||1 Td j

� jnjTT

,...,1max max

== , com },0max{ jj LT = e jjj dCL −= , j=1,...,n

� Problema max||1 Ld j (minimização dos atrasos e adiantamentos)

� solução ótima: EDD

Exemplo 1:

J1 J2 J3 J4 J5 pj 4 2 3 5 3 dj 7 6 11 13 5


EDD: J5 – J2 – J1 – J3 – J4

J5 J2 J1 J3 J4 Cj 3 5 9 12 17 Tj 0 0 2 1 4


4*max =T

Exemplo 2:

J1 J2 J3 J4 J5 J6 pj 4 6 4 2 5 3 dj 6 20 10 5 22 9

3.4. Problema Tj nd ||1

� minimizar o número de tarefas programadas com atraso

ALGORITMO DE HODGSON (adaptação do Algoritmo de Moore):

PASSO 1 – Ordene as tarefas pela regra EDD.

PASSO 2 – Se não houver tarefas com atraso, esta é a sequência ótima. Caso

contrário, vá para o Passo 3.

PASSO 3 – Identifique a primeira tarefa com atraso (JT). Da primeira tarefa até JT,

selecione a tarefa com maior tempo de processamento e desloque-a para o

final da sequência. Vá para o Passo 2.

Exemplo 1:

J1 J2 J3 J4 J5 J6 J7 J8 pj 10 6 3 1 4 8 7 6 dj 35 20 11 8 6 25 28 9


EDD: J5 – J4 – J8 – J3 – J2 – J6 – J7 – J1

J5 J4 J8 J3 J2 J6 J7 J1 Cj 4 5 11 Tj 0 0 2

J5 J4 J3 J2 J6 J7 J1 J8 Cj 4 5 8 14 22 29 Tj 0 0 0 0 0 1

J5 J4 J3 J2 J7 J1 J8 J6 Cj 4 5 8 14 21 31 37 45 Tj 0 0 0 0 0 0 28 20

� Construir o gráfico de Gantt da solução

2* =Tn

EXERCÍCIOS

Nos Exercícios 1 a 4, considere o problema de máquina única e os conjuntos de tarefas com seus respectivos dados apresentados nas tabelas:

a) J1 J2 J3 J4

pj 6 3 4 8

dj 10 12 9 20

b) J1 J2 J3 J4 J5

pj 3 9 5 1 7

dj 11 10 24 5 12

wj 2 7 4 1 5

c) J1 J2 J3 J4 J5 J6 J7 J8

pj 5 2 4 8 2 4 7 3

dj 14 10 32 25 12 15 22 7

maior p j

maior p j


d) J1 J2 J3 J4 J5 J6 J7 J8

pj 8 5 2 4 3 7 3 6

dj 21 32 18 26 14 30 25 12

e) J1 J2 J3 J4 J5 J6 J7 J8

pj 5 6 9 5 11 7 3 2

dj 21 40 12 32 22 8 17 15

wj 4 8 5 3 2 1 9 3

f) J1 J2 J3 J4 J5 J6 J7 J8 J9 J10

pj 3 6 5 3 7 2 2 4 5 4

dj 15 25 14 7 22 10 12 32 26 18

wj 6 5 9 2 10 1 8 3 2 7

1) Sequencie as tarefas pelas regras SPT, LPT, WSPT (quando houver prioridades), EDD, FIFO (ou FCFS), MS e CR por meio do tempo total de fluxo, atraso máximo, número de tarefas atrasadas, atraso total.

2) Resolva os problemas F||1 , max||1 Td j e Tj nd ||1 .

3) Implemente os problemas do Exercício 1 no software Lekin. 4) Com o auxílio do software Lekin, analise o desempenho das regras (do Exercício 1), considerando duas medidas de desempenho simultaneamente: i) tempo total de fluxo e atraso máximo ii) tempo total de fluxo e número de tarefas atrasadas iii) tempo total de fluxo e atraso total 5) Imagine que você foi indicado como gerente de operações para a Advantan Company, que fabrica artigos usados em vários outros produtos. Atuando em um ambiente muito competitivo, a Advantan não pode permitir que os prazos não sejam cumpridos. O gerente de operações precisa sequenciar seis tarefas do centro de trabalho, cujos tempos de processamento são dados na tabela a seguir.

Tarefas 1 2 3 4 5 6

Tempo de processamento (dias) 8 14 10 16 11 18

Prazo de entrega (dias) 13 22 10 23 21 24 Considere que a ordem de chegada destas tarefas é tal como apresentado na tabela. Como gerente de operações, você deve determinar a sequência, o tempo médio de fluxo,


o atraso médio e o número de tarefas atrasadas no centro de trabalho. Compare o resultado das seguintes regras de sequenciamento: FIFO, SPT, EDD e CR. (adaptado de KRUGER; DE WIT; RAMDASS, 2005) 6) A Precision Machining realiza usinagem personalizada para seus clientes. A empresa usa atualmente a regra de sequenciamento “primeiro a entrar, primeiro a ser atendido”. Uma vez que a empresa quer finalizar as tarefas dos clientes mais rapidamente, ela está considerando duas outras regras: menor tempo de processamento e razão crítica. A empresa acha que estes critérios são importantes na escolha de uma regra de sequenciamento: tempo médio de fluxo, atraso médio das tarefas e número de tarefas atrasadas. Estude a situação da Precision e recomende uma regra de sequenciamento.

Tarefas A B C D E F

Tempo de produção (horas) 2 5 3 4 6 4

Tempo de entrega prometido (horas) 4 18 8 4 20 24 (adaptado de GAITHER; FRAZIER, 2002) 7) A maioria das pessoas que trabalham em atividades administrativas como professores, consultores, administradores, engenheiros etc. tem sempre uma fila de atividades para serem realizadas. Cada uma dessas atividades demanda um tempo. As atividades podem ser por exemplo: ler uma reportagem (0,4 hora), ler um relatório (2 horas), ligar para a avó (0,2 hora), escrever um e-mail (0,1 hora), escrever um artigo (200 horas), escrever um livro (2000 horas), atender subordinados (1 hora), delegar atividades (1,5 hora), fazer a proposta de um evento de marketing (16 horas) etc. Para que as atividades sejam realizadas o quanto antes, em qual ordem elas deve ser feitas? (adaptado de COLIN, 2007) 8) Uma empresa produtora de rodas automotivas especiais de alumínio possui um único centro de usinagem, que executa todas as operações das rodas fabricadas por ela. A empresa precisa programar o centro de usinagem de modo que algum critério seja otimizado. Para o dia em que se deseja fazer a programação, a carteira de pedidos dos clientes é apresentada na tabela abaixo:

Produto Quantidade Horário de entrega solicitado pelo cliente

Penalidade de atraso Cliente

Roda A 200 8 9 Ferrari

Roda B 360 6 8 Chrysler

Roda C 100 9 1 Rolls-Royce

Roda D 800 4 3 Land-Rover

Roda E 100 21 6 Lamborghini


A produção horária dos produtos no centro de usinagem e os tempos de preparação das máquinas para cada produto são conhecidos e apresentados na tabela a seguir:

Produto Produção horária (peças/hora)

Tempo de preparação (horas)

Roda A 34 0,1

Roda B 120 2,0

Roda C 50 1,0

Roda D 129 1,8

Roda E 59 0,3

Com estes dados, consegue-se definir a quantidade de horas necessárias para o dia de produção. No tempo de produção das rodas, deve-se incluir o tempo de preparação da máquina para cada produto. Os tempos de preparação são fixos e sem relações de precedência, isto é, o tempo é o mesmo para qualquer combinação de entrada e saída de produtos. Isso acontece porque ferramentas e fixadores são individuais para cada produto, não podendo ser aproveitados de uma troca para outra.

horáriaprodução

produtosdenúmeropreparaçãodetempoordemumadeproduçãodetempo +=

Assim, com as informações descritas anteriormente, pode-se resumir na tabela a seguir os dados necessários para a programação:

Produto Tempo de processamento

Data de entrega

Penalidade de atraso

Roda A

Roda B

Roda C

Roda D

Roda E

Considere que não haja tempo de espera entre a realização de duas ordens de produção e que todas as ordens estejam disponíveis para o processamento antes de se iniciar a primeira delas. Analise o desempenho das regras SPT, LPT, WSPT, EDD, MS e CR no caso de se querer minimizar o tempo total de fluxo, o atraso máximo, o número de tarefas atrasadas e o atraso total. (adaptado de COLIN, 2007)


4. PROGRAMAÇÃO DE MÁQUINAS PARALELAS


Aplicações:

� Várias injetoras operando em paralelo

� Caixas de um banco

� Pontos de atracação de navios

Parâmetros:

� n ≥ 2 finito � 2 ≤ m ≤ n, m máquinas paralelas idênticas � g = 1 (uma única operação por tarefa) � rj = 0 (todas as tarefas têm a mesma data de liberação, igual a zero) � pj � dj

� máquina única: programação = sequenciamento

� máquinas paralelas: programação = alocação + sequenciamento

� nova medida de desempenho: makespan (duração total da programação)

� Tipos de máquinas:

o Idênticas: todas as máquinas são iguais, têm o mesmo pj

o Uniformes ou proporcionais: os tempos pj se diferem por um fator multiplicativo

o Não relacionadas: em cada máquina, as operações têm diferentes pj

EXERCÍCIO

1) Considere o problema programação em duas máquinas paralelas idênticas e as sequências obtidas no Exercício 2 da página 10. Construa gráficos de Gantt e analise o desempenho das regras SPT, LPT, WSPT, EDD, FIFO, MS e CR por meio do makespan, tempo total de fluxo, atraso máximo, número de tarefas atrasadas e atraso total.

J1 J2 J3 J4 J5 rj 5 2 1 4 3 pj 3 5 2 6 1 dj 13 7 4 10 8 wj 2 1 3 2 4



4.2. Problema FP ||

ALGORITMO (solução ótima):

PASSO 1 – Ordene as tarefas pela regra SPT.

PASSO 2 – Designe uma tarefa de cada vez à máquina de menor carga.

Exemplo 1: m = 2

J1 J2 J3 J4 J5 J6 J7 pj 3 2 2 1 4 6 5

SPT: J4 – J2 – J3 – J1 – J5 – J7 – J6


8,5*

=F

4.3. Problema max|| CP

ALGORITMO (solução heurística):

PASSO 1 – Ordene as tarefas pela regra LPT.

PASSO 2 – Designe uma tarefa de cada vez à máquina de menor carga.

Do Exemplo 1:

LPT: J6 – J7 – J5 – J1 – J3 – J2 – J4


12max =C


4.4. Problema maxmin|| CcomFP

ALGORITMO (solução heurística):

PASSO 1 – Resolva o Problema max|| CP .

PASSO 2 – Reordene as tarefas de cada máquina segundo a regra SPT.

Ainda do Exemplo 1:

LPT: J6 – J7 – J5 – J1 – J3 – J2 – J4

M1: J4 – J2 – J1 – J1

M2: J3 – J5 – J7


8,512max == FeC

EXERCÍCIOS

Nos Exercícios 1 a 4, considere o problema de máquinas paralelas e os conjuntos de tarefas com seus respectivos dados apresentados nas tabelas das páginas 14 e 15. 1) Considerando o problema de 3 máquinas paralelas , sequencie as tarefas pelas regras SPT, LPT, WSPT (quando houver prioridades), EDD, FIFO (ou FCFS), MS e CR por meio do tempo total de fluxo, atraso máximo, número de tarefas atrasadas, atraso total.

2) Resolva os problemas FP ||2 , FP ||3 , max||2 CP , max||3 CP e

maxmin||2 CcomFP .

3) Implemente os problemas do Exercício 1 no software Lekin. 4) Com o auxílio do software Lekin, analise o desempenho das regras (do Exercício 1), considerando duas medidas de desempenho simultaneamente no problema de 2 máquinas paralelas :

a) makespan e tempo total de fluxo b) makespan e número de tarefas atrasadas c) tempo total de fluxo e atraso máximo

SPT


5. PROGRAMAÇÃO DE SISTEMAS FLOW SHOP


Aplicações:

� Máquinas organizadas em série

� Sequência de células de produção especializadas em determinados tipos de produtos

� Exemplo: operações de fundição e laminação com fluxo único

Parâmetros:

� n ≥ 2 finito

� m ≥ 2 finito, conjunto de máquinas distintas � 1 ≤ gj ≤ m, gj operações para cada tarefa j � rj = 0 (todas as tarefas têm a mesma data de liberação, igual a zero) � pjk (diferentes tempos de processamento das tarefas em cada máquina) � dj

EXERCÍCIO

1) Considere o problema programação em um flow shop com duas máquinas e as sequências obtidas no Exercício 2 da página 10. Construa gráficos de Gantt e analise o desempenho das regras SPT, LPT, WSPT, EDD, FIFO, MS e CR por meio do makespan, tempo total de fluxo, atraso máximo, número de tarefas atrasadas e atraso total.

J1 J2 J3 J4 J5 rj 5 2 1 4 3

pj1 3 5 2 6 1 pj2 4 6 3 2 5 dj 13 7 4 10 8 wj 2 1 3 2 4


5.2. Algoritmo de Johnson

� solução ótima do problema max||2 CF (apenas para 2 máquinas)


ALGORITMO DE JOHNSON:

PASSO 1 – Determine min{pjk}.

PASSO 2 – Se min{pjk}∈M1, coloque a tarefa na primeira posição disponível da

sequência, senão coloque-a na última posição disponível.

PASSO 3 – Desconsiderando a tarefa alocada, repita os Passos 1 e 2 até que todas as

tarefas sejam programadas.

Exemplo 1:

J1 J2 J3 J4 J5 pj1 3 5 1 6 7 pj2 6 2 2 6 5

ITERAÇÃO 1: min{pjk}: p31∈M1 (primeira posição)

J3

J1 J2 J3 J4 J5 pj1 3 5 1 6 7 pj2 6 2 2 6 5

ITERAÇÃO 2: min{pjk}: p22∈M2 (última posição)

J3 J2

J1 J2 J3 J4 J5 pj1 3 5 1 6 7 pj2 6 2 2 6 5

ITERAÇÃO 3: min{pjk}: p11∈M1 (primeira posição)

J3 J1 J2

J1 J2 J3 J4 J5 pj1 3 5 1 6 7 pj2 6 2 2 6 5


ITERAÇÃO 4: min{pjk}: p52∈M2 (última posição)

J3 J1 J5 J2

J1 J2 J3 J4 J5 pj1 3 5 1 6 7 pj2 6 2 2 6 5

ITERAÇÃO 5: última tarefa remanescente

J3 J1 J4 J5 J2


24*max =C

5.2. Métodos heurísticos

� solução heurística do problema max|| CF (qualquer número de máquinas)

ALGORITMO CDS (CAMPBELL; DUDEK; SMITH, 1970)

� utiliza o Algoritmo de Johnson de forma heurística

� obtém diversas programações viáveis, escolhendo a melhor

ETAPA 1 – Aplique o Algoritmo de Johnson considerando somente a primeira e a última

máquina (as demais são ignoradas).

ETAPA 2 – Aplique o Algoritmo de Johnson considerando a soma dos tempos de

processamento da primeira e da segunda máquina e da última e a

penúltima máquina.

...

ETAPA (m-1) – Aplique o Algoritmo de Johnson considerando a soma dos tempos de

processamentos das (m-1) primeiras máquinas e das (m-1) últimas

máquinas.


� Exemplo: se o problema tiver 5 máquinas (m=5), o algoritmo CDS obterá 4

programações possíveis (m-1) e considerará a de melhor makespan. Assim, com 5

máquinas, o algoritmo CDS terá 4 etapas.

Exemplo 2:

J1 J2 J3 J4 J5 pj1 6 4 3 9 5 pj2 8 1 9 5 6 pj3 2 1 5 8 6

3 máquinas � 2 etapas

ETAPA 1: primeira X última máquina

J1 J2 J3 J4 J5 pj1 6 4 3 9 5 pj3 2 1 5 8 6

Algoritmo de Johnson: J3 – J5 – J4 – J1 – J2

Cmax = 35


ETAPA 2: primeira e segunda máquinas X penúltima e última máquinas

J1 J2 J3 J4 J5 pj1+pj2 14 5 12 14 11 pj2+pj3 10 2 4 13 12

Algoritmo de Johnson: J5 – J4 – J1 – J3 – J2

Cmax = 43


Melhor programação: J3 – J5 – J4 – J1 – J2 (Etapa 1)

35max =C


ALGORITMO NEH (NAWAZ; ENSCORE JR.; HAM, 1983):

PASSO 1 – Ordene as tarefas pela regra LPT (considerando a soma dos tempos de

processamento em todas as máquinas).

PASSO 2 – Com as duas primeiras tarefas da ordenação obtida, encontre a

subsequência (entre as duas possíveis) com o melhor makespan.

PASSO 3 – Sem alterar as posições relativas das tarefas já alocadas, insira a próxima

tarefa da ordenação obtida no Passo 1 em todas as posições possíveis da

subsequência atual e considere a que fornece o melhor makespan.

PASSO 4 – Repita o Passo 3 até que todas tarefas estejam programadas.

Resolvendo o Exemplo 2 pelo Algoritmo NEH:

J1 J2 J3 J4 J5 pj1 6 4 3 9 5 pj2 8 1 9 5 6 pj3 2 1 5 8 6 ∑pjk 16 6 17 22 17

LPT: J4 – J3 – J5 – J1 – J2

� Construir os gráficos de Gantt das inserções

Solução: J3 – J4 – J5 – J1 – J2

34*max =C

EXERCÍCIOS

1) Considerando os dados das tabelas abaixo, resolva o problema max||2 CF utilizando

o Algoritmo de Johnson. a) J1 J2 J3 J4 J5

pj1 5 4 8 2 7

pj2 3 7 6 4 5


b) J1 J2 J3 J4 J5 J6

pj1 6 2 5 8 7 2

pj2 4 1 6 7 9 5

2) Considerando os dados das tabelas abaixo, resolva o problema de minimização do makepan (Cmax) em um flow shop, utilizando os algoritmos CDS e NEH.

a) J1 J2 J3 J4 b) J1 J2 J3 J4 J5

pj1 13 7 26 2 pj1 2 3 1 4 3

pj2 3 12 9 6 pj2 1 2 1 2 7

pj3 12 16 7 1 pj3 2 4 2 3 5

pj4 6 10 14 4 2

c) J1 J2 J3 J4 J5 J6

pj1 13 7 9 2 10 15

pj2 8 12 10 6 5 5

pj3 14 6 7 1 12 8

3) Implemente os problemas dos Exercícios 1 e 2 no Lekin, resolvendo-os com as regras SPT e LPT. Compare os resultados. 4) Seis ordens de produção devem ser processadas na máquina A e em seguida na máquina B. Os tempos de processamento incluindo os setups, as datas de entrega (em horas a partir do início da programação) e as prioridades atribuídas a cada ordem são apresentados na tabela a seguir. Sequencie estas ordens segundo as regras SPT, LPT, WSPT, EDD, FIFO, MS e CR e pelo Algoritmo de Johnson, construa os respectivos gráficos de Gantt e avalie cada alternativa pelo tempo total da programação (makespan), tempo total de fluxo (lead time total) e atraso total. Para a aplicação da regra FIFO, admita que as ordens de fabricação chegaram na sequência em que aparecem na tabela. (adaptado de TUBINO, 2006)

Ordem de Fabricação

Tempo de processamento Entrega (horas) Prioridade

Máquina A Máquina B

OF1 15 10 30 5

OF2 18 16 40 1

OF3 14 15 55 3

OF4 13 14 35 2

OF5 10 17 45 4

OF6 14 13 30 6 5) Implemente o Exercício 4 no Lekin (insira manualmente a sequência obtida pelo Algoritmo de Johnson).


BIBLIOGRAFIA ARENALES, M.; ARMENTANO, V.; MORABITO, R; YANASSE, H. Pesquisa Operacional para Cursos de Engenharia. Rio de Janeiro: Elsevier, 2007. BAKER, K.R. Introduction to sequencing and scheduling . New York: John Wiley & Sons, 1974. CAMPBELL, H.G.; DUDEK, R.A.; SMITH, M.L. A heuristic algorithm for the n job m machine sequencing problem. Management Science , Rhode Island, v.16, p.B630-637. 1970. COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro: LTC, 2007. CONWAY, R.W.; MAXWELL, W.L.; MILLER, L.W. Theory of Scheduling . Reading: Addison-Wesley, 1967. FERNANDES, F.C.F.; GODINHO FILHO, M. Planejamento e Controle da Produção: dos fundamentos ao essencial. São Paulo: Atlas, 2010. GAITHER, N.; FRAZIER, G. Adminstração da produção e operações . São Paulo: Pioneira Thomson Learning, 2004. 8ª ed. JOHNSON, S.M. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly , Hoboken, v.1, p.61-68. 1954. KRUGER, D.; DE WIT, P.; RAMDASS, K. Operations Management . Southern Africa: Oxford University Press, 2005. MOCCELLIN, J.V. Introdução à Programação de Operações em Máquinas . São Carlos: USP, 1999. NAWAZ, M.; ENSCORE JR., E.E.; HAM, I. A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. OMEGA – The International Journal of Management Science , v.11, n.1, p.91-95. 1983. PINEDO, M. Scheduling: theory, algorithms and systems. New Jersey, Prentice-Hall, 1995. TUBINO, D.F. Manual de Planejamento e Controle da Produção . São Paulo: Atlas, 2006. 2ª ed.

Documents

TÉCNICAS DETÉCNICAS DE PROGRAMAÇÃO … · Processo de tomada de decisão presente tanto em sistemas de produção como em ambientes de processamento de informações, além das