View
46
Download
0
Category
Preview:
DESCRIPTION
UM ESTUDO DA PROGRAMAÇÃO DA PRODUÇÃO EM AMBIENTES DO TIPO JOBSHOP FLEXÍVEL POR MEIO DE EXPERIMENTAÇÃO COMPUTACIONAL
Citation preview
1
UNIVERSIDADE FEDERAL DO CEARÁ
CURSO DE GRADUAÇÃO EM ENGENHARIA DE PRODUÇÃO MECÂNICA
Giulliano Costa e Silva de Albuquerque
UM ESTUDO DA PROGRAMAÇÃO DA PRODUÇÃO EM AMBIENTES DO TIPO JOBSHOP FLEXÍVEL POR MEIO DE EXPERIMENTAÇÃO
COMPUTACIONAL
Fortaleza
2010
2
GIULLIANO COSTA E SILVA DE ALBUQUERQUE
UM ESTUDO DA PROGRAMAÇÃO DA PRODUÇÃO EM AMBIENTES DO TIPO JOBSHOP FLEXÍVEL POR MEIO DE EXPERIMENTAÇÃO
COMPUTACIONAL
Trabalho Final de Curso submetido à Coordenação do Curso de Engenharia de Produção Mecânica, como requisito parcial para a obtenção do título de Engenheiro de Produção Mecânica
Orientador: Prof. Msc. Anselmo Ramalho Pitombeira Neto
Fortaleza
2010
3
GIULLIANO COSTA E SILVA DE ALBUQUERQUE
UM ESTUDO DA PROGRAMAÇÃO DA PRODUÇÃO EM AMBIENTES DO TIPO JOBSHOP FLEXÍVEL POR MEIO DE EXPERIMENTAÇÃO
COMPUTACIONAL
Este Trabalho Final de Curso foi julgado adequado para obtenção do título de Engenheiro de Produção Mecânica da Universidade
Federal do Ceará.
Fortaleza, ___ de _______ de 2010
_____________________________________________
Prof. José Belo Torres, Dr.
Coordenador do Curso
Banca Examinadora:
____________________________________
Prof. Msc. Anselmo Ramalho Pitombeira Neto
Orientador
_________________________________
Prof..
____________________________________
Examinador - UFC
4
E os que dançavam foram considerados loucos por aqueles que não ouviam a música.
Friedrich Wilhelm Nietzsche
5
Aos meus pais e minhas tias.
6
AGRADECIMENTOS
Aos meus pais, minhas tias e meus irmãos, por tudo.
Aos meus amigos que me acompanharam em cada trajeto da minha vida.
À Malaki, pela compreensão.
Ao Professor Anselmo Ramalho Pitombeira Neto, que orientou para a elaboração deste
trabalho.
Aos docentes do curso.
7
RESUMO
O presente trabalho pretende apresentar um estudo aplicado à implementação de um
algoritmo de sequenciamento de produção em um ambiente job shop flexível usando
heurísticas construtivas de regras de despacho. A programação da produção é um processo de
tomada de decisão crucial para o desempenho competitivo das empresas. Os problemas de
programação e sequenciamento da produção são aqueles que envolvem alocação de tarefas
em recursos com capacidade finita, através de prioridades. As prioridades podem ser obtidas
por heurísticas, incluindo regras de despacho. As regras de despacho utilizadas e comparadas
pela experimentação computacional deste trabalho foram SPT, LPT, MWKR, LWKR e
RANDOM. A programação e sequenciamento da produção em ambiente de produção job
shop é considerado um dos problemas mais difíceis de otimização combinatória. O ambiente
jobshop se diferencia dentre os outros pelo fato das tarefas apresentarem rota de operações
variadas. Neste estudo foi implementado um algoritmo de sequenciamento em ambiente
jobshop flexível, e avaliado os dados de acordo com as funções objetivas de makespan e
tempo de fluxo médio. Uma conclusão importante deste estudo é que certa regra de despacho
pode apresentar um desempenho excelente ou péssimo, dependendo da função objetiva
utilizada.
Palavras-chave: Programação da Produção, JobShop Flexível, Regras de Despacho.
8
ABSTRACT
This paper presents a study applied to implement an algorithm for production scheduling in a
flexible job shop environment using constructive heuristics rules of dispatching rules. The
production scheduling is a process of decision making crucial to the competitive performance
of companies. The problems of planning and production scheduling are those which involve
the allocation of tasks to resources with finite capacity, through priorities. Priorities can be
obtained by heuristics, including dispatching rules. The dispatching rules used and compared
on computational experimentation of this work were SPT, LPT, MWKR, LWKR and
RANDOM. The programming and production scheduling in job shop production environment
is considered one of the most difficult combinatorial optimization. The job shop environment
is different from the others because the jobs present different route of operations. This study
implemented an algorithm for scheduling in flexible job shop environment, and evaluated the
data according to the objective function of makespan and mean flow time. An important
finding of this study is that certain dispatching rule may perform good or bad, depending of
the objective function used.
Keywords: Production Scheduling, Flexible Job Shop, Dispatching Rules.
9
LISTA DE FIGURAS
Figura 1 – Hierarquia do planejamento e Controle da Produção..............................................20
Figura 2 – Atividades de planejamento e controle....................................................................21Figura 3 – Programação e sequenciamento da produção e sistemas produtivos......................22Figura 4 – Programação Empurrada x Puxada.........................................................................23Figura 5 – Exemplo de um gráfico de Gantt.............................................................................24Figura 6 – Fluxograma em um ambiente de manufatura..........................................................26Figura 7 – Fluxograma em organização de serviços.................................................................28Figura 8 – Relações entre classes de problemas de programação de operações em máquinas.36Figura 9 – Principais algoritmos de sequenciamento................................................................39Figura 11 – Configuração do cenário 1.....................................................................................44
Figura 12 – Configuração do cenário 2.....................................................................................45
Figura 13 – Configuração do cenário 3.....................................................................................45
Figura 14 - Quantidade de operações para cada tarefa.............................................................46
Figura 15 – Média dos makespans para cada cenário...............................................................62
Figura 16 – Conjuntos com a quantidade de vezes que cada RD obteve o menor makespan no cenário 1....................................................................................................................................63
Figura 17 – Conjuntos com a quantidade de vezes que cada RD obteve o menor makespan no cenário 2....................................................................................................................................64
Figura 18 – Conjuntos com a quantidade de vezes que cada RD obteve o menor makespan no cenário 3....................................................................................................................................64
Figura 19 – Média dos tempos de fluxo médio para cada cenário............................................69
Figura 20 – Conjuntos com a quantidade de vezes que cada RD obteve o menor TFM no cenário 1....................................................................................................................................70
Figura 21 – Conjuntos com a quantidade de vezes que cada RD obteve o menor TFM no cenário 2....................................................................................................................................71
Figura 22 – Conjuntos com a quantidade de vezes que cada RD obteve o menor TFM no cenário 3....................................................................................................................................71
10
LISTA DE TABELAS
Tabela 1 - Distribuição de Frequências do makespan para o cenário 1....................................58
Tabela 2 - Distribuição de Frequências do makespan para o cenário 2....................................59
Tabelas 3 - Distribuição de Frequências do makespan para o cenário 1..................................60
Tabela 4 - Medidas do makespan das instâncias para o cenário 1............................................61
Tabela 5 - Medidas do makespan das instâncias para o cenário 2............................................61
Tabela 6 - Medidas do makespan das instâncias para o cenário 3............................................61
Tabela 7 - Medidas de dispersão das médias dos makespans das RD não aleatórias...............62
Tabela 8 - Percentual de variação das médias do makespan em relação a BA*.......................63
Tabela 9 - Quantidade e percentagem de instância que cada RD obteve o menor makespan no
cenário 1....................................................................................................................................65
Tabela 10 - Quantidade e percentagem de instância que cada RD obteve o menor makespan
no cenário 2...............................................................................................................................65
Tabela 11 - Quantidade e percentagem de instância que cada RD obteve o menor makespan
no cenário 3...............................................................................................................................65
Tabela 12 - Probabilidades empíricas do makespan da regra RDM ser menor ou igual ao
makespan das RDs....................................................................................................................65
Tabelas 13 - Distribuição de Frequências do tempo de fluxo médio para o cenário 1.............66
Tabelas 14 - Distribuição de Frequências do tempo de fluxo médio para o cenário 2.............66
Tabelas 15 - Distribuição de Frequências do tempo de fluxo médio para o cenário 3.............67
Tabela 16 - Medidas dos tempos de fluxo médio para o cenários 1.........................................68
Tabela 17 - Medidas dos tempos de fluxo médio para o cenários 2.........................................68
Tabela 18 - Medidas dos tempos de fluxo médio para o cenários 3.........................................68
Tabela 19 - Medidas de dispersão das médias dos tempos de fluxo médio das RDs não
aleatórias...................................................................................................................................69
Tabela 20 - Percentual de variação das médias dos TFM em relação BA*..............................70
Tabela 21 - Quantidade e percentagem de instância que cada RD obteve o menor TFM no
cenário 1....................................................................................................................................72
11
Tabela 22 - Quantidade e percentagem de instância que cada RD obteve o menor TFM no
cenário 2....................................................................................................................................72
Tabela 23 - Quantidade e percentagem de instância que cada RD obteve o menor TFM no
cenário 3....................................................................................................................................72
Tabela 24 - Probabilidades empíricas do TFM da regra RDM ser menor ou igual ao TFM das
RDs............................................................................................................................................72
12
LISTA DE QUADROS
Quadro 1 – Principais características de um ambiente Job Shop..............................................37
Quadro 2 - Parâmetros variáveis e fixos para instâncias e cenários.........................................46
Quadro 3 – Pseudocódigo do gerador de instâncias.................................................................48
Quadro 4 – Pseudocódigo do selecionador de tarefas..............................................................49
Quadro 5 – Pseudocódigo do sequenciador de tarefas pela regra SPT.....................................50
Quadro 6 – Pseudocódigo do sequenciador de tarefas pela regra LPT.....................................50
Quadro 7 – Pseudocódigo do sequenciador de tarefas pela regra LWKR................................51
Quadro 8 – Pseudocódigo do sequenciador de tarefas pela regra MWKR...............................52
Quadro 9 – Pseudocódigo do sequenciador de tarefas pela regra RANDOM..........................52
Quadro 10 – Pseudocódigo do sequenciador de tarefas pela regra FIFO.................................53
Quadro 11 – Pseudocódigo componente alocador de tarefas...................................................54
13
SUMÁRIO
E os que dançavam foram considerados loucos por aqueles que não ouviam a música.........................4
1 – INTRODUÇÃO.............................................................................................................................14
1.1. Contextualização..................................................................................................................15
1.2. Objetivos..............................................................................................................................16
1.2.1. Objetivo Geral..............................................................................................................16
1.2.2. Objetivos específicos....................................................................................................16
1.3. Justificativa...........................................................................................................................16
1.4. Metodologia..........................................................................................................................17
1.5. Estrutura do trabalho............................................................................................................17
2 PROGRAMAÇÃO E SEQUENCIAMENTO DA PRODUÇÃO.................................................18
2.1 Programação e sequenciamento da produção como função do processo de tomada de decisão19
2.1 Definição de sequenciamento da produção...........................................................................25
2.2 Sequenciamento em ambiente de manufatura e de serviços..................................................26
2.3 Características do sistema de sequenciamento da produção..................................................28
2.4 Considerações e restrições de processamento no ambiente de sequenciamento da produção29
2.5 Ambientes de sequenciamento de produção.........................................................................31
2.5.1 General Shop................................................................................................................32
2.5.2 Máquina Única.............................................................................................................32
2.5.3 Máquinas Paralelas.......................................................................................................33
2.5.4 Open Shop....................................................................................................................34
2.5.5 Flow Shop.....................................................................................................................35
2.5.6 Job Shop.......................................................................................................................35
2.5.7 JobShop Flexível..........................................................................................................36
2.6 Características de um ambiente job shop..............................................................................37
2.7 Medidas de desempenho.......................................................................................................38
2.7.1 Makespan......................................................................................................................38
2.7.2 Tempo de fluxo médio..................................................................................................38
14
2.8 Regras De Sequenciamento..................................................................................................39
3. DESENVOLVIMENTO E IMPLEMENTAÇÃO COMPUTACIONAL.....................................43
3.1. Implementação do computacional........................................................................................47
3.2. Análise do dos resultados.....................................................................................................54
4. EXPERIMENTAÇÃO COMPUTACIONAL E ANÁLISE DOS RESULTADOS......................58
4.1 Análise dos resultados para o makespan...............................................................................58
4.2 Análise dos resultados para o Tempo de Fluxo Médio.........................................................66
5 – CONCLUSÕES..............................................................................................................................73
REFERÊNCIAS...................................................................................................................................76
15
1 – INTRODUÇÃO
O presente capítulo descreve as etapas do trabalho. As etapas são a contextualização,
inserindo o leitor na realidade abordada, objetivos gerais e específicos, justificativa,
metodologia utilizada e por fim a estrutura do trabalho.
1.1. Contextualização
A competição pela sobrevivência das organizações no mercado global, e a intensa
diversificação dos produtos, com ciclos de vida cada vez menores, o desejos dos clientes por
prazos mais curtos e maior qualidade nos produtos e serviços, proporciona novos desafios de
desenvolvimento de processos de trabalho, ferramentas de gestão mais eficazes, técnicas de
otimização, gestão de pessoas, além da administração geral da organização.
Nessa conjectura global, mercados dinâmicos e estruturas organizacionais complexas,
as oportunidades de reduzir tempo e custo tornam-se bastante procurada por muitas empresas
de vários setores, seja serviço ou manufatura.
Sistemas de programação e sequenciamento da produção que lidam com as
complexidades da fabricação num cenário de competição global, estão atualmente com suas
importâncias muito destacadas. É cada vez mais reconhecido que todos os pontos fortes da
pesquisa operacional, tecnologia da informação, e sofisticados softwares de gestão da
produção serão requisitados para desenvolver sistemas para o futuro das empresas.
Decisões operacionais influenciam as táticas de um planejamento organizacional, que
reflete diretamente na estratégia da empresa. Um componente essencial para atingir uma
utilização eficaz da capacidade dos recursos disponíveis em uma empresa é uma programação
e sequenciamento da produção bem implementada. Aplicação de técnicas e modelos para
obter uma sinergia em todos os processos de tomada de decisão de uma empresa é essencial
para se obter ótimos resultados. Para atender às necessidades do cenário apresentado, as
técnicas de sequenciamento permitem alcançar soluções que minimizam o tempo de ciclo nos
16
ambientes de produção, proporcionando crescimento da capacidade dos recursos e redução de
custos, tornando as empresas mais competitivas.
Os ambientes de produção tradicionais estão, cada vez mais, a dar lugar a um tipo de
produção que absorve as principais características do ambiente de produção job shop. A
produção em pequenos lotes e a produção por encomenda estão se tornando cada vez mais
importantes que a produção em massa de um único produto. Este cenário se deve ao fato das
organizações apresentarem a necessidade de diferenciar-se em seu mercado. A busca por
produtos e serviços cada vez mais customizados impulsiona sistemas de produção sob
encomenda.
1.1. Objetivos
1.1.1. Objetivo Geral
O presente trabalho apresenta um estudo com aimplementação de um algoritmo de
sequenciamento de produção em um ambiente job shop flexível usandoheurísticas
construtivas de regras de despacho
1.1.1. Objetivos específicos
Implementação de um algoritmo de sequenciamento de produção em um ambiente
jobshop flexível.
Análise dos resultados dos critérios de avaliação obtidos entre as heurísticas testadas,
através de simulação.
Obtenção das melhores regras nos cenários simulados.
Obtenção de dados quantitativos entre as heurísticas e a variação de seus desempenhos
mediante as funções objetivas analisadas.
17
1.1. Justificativa
Atualmente, há um grande número de empresas que apresenta ambiente de produção
tipo job shop flexível. Uma grande quantidade de estudos, afirmam que o numero de
organizações com tipo de ambiente de produção tende a aumentar.
Na maioria dos países, as pequenas empresas (geralmente com sistema job shop) além
de constituírem uma percentagem elevada da rede empresarial, têm um contributo
significativo para a produção nacional.
Desta forma, o presente trabalho é justificado pela importância deste estudo em
ambiente de produção jobshop,que tem flexibilidade para suprir a necessidade uma demanda
versátil, através de regras de sequenciamento para proporcionar uma analise do desempenho
das heurísticas testadas mediante as funções objetivas delimitadas.
1.1. Metodologia
Quanto aos procedimentos técnicos, o desenvolvimento deste estudo incluiu um
levantamento bibliográfico de livros, artigos e web sites, que proporcionam um suporte
teórico para a implementação do algoritmo e a textualização do contexto que este estudo
aborda. A análise dos resultados foi baseada em dados quantitativos obtidos por meio de
experimentação computacional.
1.1. Estrutura do trabalho
O estudo apresentado é composto por cinco capítulos, incluindo este. O segundo
capítulo envolve o referencial teórico. No referencial teórico são descritos os conceitos,
características, aplicações, importâncias, dentre outras informações importantes para a
compreensão do assunto, sobre a programação da produção em ambientes do tipo job shop
flexível.
18
O terceiro capítulo descreve o desenvolvimento e a implementação computacional.
Nesse capitulo é descrito o método de construção do algoritmo, o delineamento experimental,
e os métodos de avaliação dos resultados.
O quarto capítulo apresenta os resultados das simulações do algoritmo em ambiente
job shop flexível. Apresentando dados, em forma de tabelas e figuras, através de várias
formas, resultando assim em uma ferramenta para avaliação do desempenho das regras de
despacho testadas.
O quinto capítulo, concluindo o trabalho, apresenta a conclusão do estudo, a
interpretação dos dados obtidos, as considerações finais sobre o assunto e as sugestões para
trabalhos futuros.
19
2 PROGRAMAÇÃO E SEQUENCIAMENTO DA PRODUÇÃO
1.1 Programação e sequenciamento da produção como função do processo de tomada de decisão
De acordo com Tubino (2007), a Programação da Produção estabelece no curto prazo
quanto e quando comprar, fabricar ou montar de cada item necessário à composição dos
produtos acabados, propostos pelo plano-mestre de produção com base no PMP
(Planejamento-Mestre de produção), nas informações do controle de estoques. Neste sentido,
como resultado da programação da produção, são emitidas ordens de compra, ordens de
fabricação e ordens de montagem.
Na hierarquia em que as funções do PCP estão distribuídas, apresentada pela figura 1, a
programação da produção é a primeira dentro do nível operacional de curto prazo, disparando
as atividades produtivas. Se o plano de produção de longo prazo providenciou os recursos
necessários, e o planejamento-mestre da produção gerou um plano-mestre de produção viável,
não deverão ocorrer problemas de capacidade na execução do programa de produção, cabendo
à programação da produção sequenciar as ordens emitidas no sentido de minimizar os
leadtimes e estoques do sistema. Dessa forma, as decisões relacionadas aos três níveis (longo,
médio e curto prazo) de planejamento e à função de controle estão intrinsecamente
interrelacionadas, o que implica que um sistema de administração deve ser projetado
considerando este conjunto de decisões, bem como a importância relativa de cada nível de
decisão dentro do contexto particular de cada empresa, complementa Corrêa et al. (1997).
20
Figura 1 – Hierarquia do planejamento e Controle da ProduçãoFonte: Tubino (2007)
Pinedo (2008) explica que, em muitos ambientes de produção, não pode ser
imediatamente claro qual o impacto do planejamento, programação e sequenciamento da
produção tem em uma meta, na prática, a escolha do modelo de sequenciamento da produção
geralmente tem um impacto mensurável sobre o desempenho do sistema. De fato, uma
melhoria em um modelo de sequenciamento da produção, pode reduzir os custos diretos e
indiretos significativamente, especialmente em um ambiente de produção complexo.
Planejamento, programação e sequenciamento da produção em qualquer tipo de organização
de manufatura ou serviço devem interagir com muitas outras funções. Essas interações são
tipicamente dependentes do sistema e podem variar substancialmente de um cenário para
outro, que por muitas vezes ocorrem dentro de uma rede de computadores. Existem também
muitas situações em que a troca de informações entre o PPCP (Planejamento Programação e
Controle da Produção) e outras funções de tomada de decisão ocorre em reuniões ou através
de memorandos.
As atividades da programação da produção, apesar de serem desenvolvidas
simultaneamente, podem ser divididas para efeito de estudo em três grupos: a administração
de estoques, o sequenciamento e a emissão e liberação de ordens (TUBINO, 2007).
21
Para Liddell (2009), o sequenciamento é a área central do cérebro que dirige o lado
operacional de uma empresa manufatureira. O programa de produção gerado deve ser capaz
de absorver a enorme quantidade de fluxo de informações e mudanças que causam impacto no
negócio e permitir a criação de um novo plano de ação rapidamente.
Para Slacket al. (2008), para conciliar o volume e o tempo, quatro atividades justapostas
são desempenhadas: carregamento, sequenciamento, programação e controle. A figura 2
ilustra a justaposição dessas atividades.
Figura 2 – Atividades de planejamento e controleFonte: Adaptado de Slack et al. (2008)
Quanto à função de programação e sequenciamento, Tubino (2007) afirma que a
intensidade e detalhamento com que são executadas as funções de programação e
sequenciamento da produção, dependem do tipo de sistema produtivo que se está
programando. Nos sistemas de produção contínuos e de produção em massa, onde a demanda
de uma pouca variedade de produtos apresentam um grande volume, a função de programação
e sequenciamento da produção, se dá apenas no nível do produto acabado, definindo seus
volumes de produção, seus estoques de abastecimento e de distribuição. Desta forma, o foco é
na função de administração de estoques ou logística e não no sequenciamento em si.
Nos sistemas de produção repetitivos em lotes, visto que a variedade de produtos não
justifica uma focalização da produção deles, a competição por espaço nos recursos produtivos
é grande, fazendo com que a programação da produção necessite desdobrar o PMP em seus
diferentes níveis e componentes, geralmente via MRP (Material Requirements Planning). As
ordens (compra, fabricação e montagem) geradas pelo MRP devem ser sequenciadas por um
APS (AdvancedProgram System), recurso a recurso, visando garantir certa fluidez no
processo produtivo.
22
De acordo com Tubino (2007), nesse tipo de sistema produtivo, a função de
sequenciamento é crítica, pois a maior parcela do lead time de um produto fabricado em lotes
compreende o tempo em que o lote desse produto espera para ser processado em um recurso,
sendo que, caso essa função não seja adequadamente estruturada, esse tempo pode chegar
facilmente a 80% do tempo total. Em processos repetitivos em lotes, o tempo de espera é
considerado o maior gerador de desperdícios da Manufatura Enxuta. Em um sistema
produtivo voltado para atender sob encomenda, o foco da programação da produção é a
administração da capacidade produtiva, através de um sistema APS de capacidade finita para
sequenciamento e um acompanhamento e controle a entrega do pedido ao cliente no prazo
acordado.
Herrmann et al. (2006) explica que, sistemas APS são normalmente destinados a cobrir
todas as classes de problemas de programação e são capazes de considerar muitas restrições
do mundo real. Portanto, não é muito comum encontrar conhecidos algoritmos de
programação específicos em um sistema APS, e sim uma abordagem mais geral. Ainda assim,
os sistemas APS geralmente têm interfaces que permitem ao usuário incluir seus próprios
algoritmos.
A figura 3 ilustra a diferenciação do nível do foco das funções de programação e
sequenciamento da produção em relação aos tipos de sistemas produtivos básicos.
Figura 3 – Programação e sequenciamento da produção e sistemas produtivosFonte: TUBINO (2007)
23
Além das diferenças entre os modelos de programação, em relação aos sistemas
produtivos, descritos pelo Tubino (2007), existe a distinção entre a programação da produção
entre um sistema de planejamento e controle da produção empurrado e o puxado,
apresentados na figura 4.
Figura 4 – Programação Empurrada x PuxadaFonte: Tubino (2007)
Slacket al. (2008) afirma que em um sistema de planejamento e controle empurrado, as
atividades são programadas por meio de um sistema central e completadas em linha com as
instruções centrais, como em um sistema MRP. Cada centro de trabalho empurra o trabalho,
sem levar em consideração se o centro de trabalho seguinte pode utilizá-lo. Os centros de
trabalho são coordenados pelo sistema central de planejamento e controle de operações. Em
um sistema de planejamento e controle puxado, o passo e as especificações de o que é feito
são estabelecidos pela estação de trabalho do “consumidor”, que “puxa” o trabalho da estação
de trabalho antecedente (fornecedor). Dessa forma a demanda é transmitida para trás ao longo
das etapas, a partir do ponto de demanda original pelo consumidor original.
Tubino (2007) complementa que na programação empurrada, o programa de produção
do período é obtido a partir da inclusão da demanda dos diferentes produtos acabados no
PMP, que gera as necessidades dos produtos acabados no tempo. Estas necessidades passadas
para o sistema MRP calcular as necessidades de materiais e dimensionadas as necessidades de
ordens de fabricação e montagem, elas passam por um sistema de sequenciamento para gerar
prioridades, ficando então disponíveis para a emissão e liberação delas aos setores produtivos.
24
Em termos operacionais, na programação da produção empurrada durante o período
congelado de programação, os postos de trabalho receberão um conjunto de ordens
sequenciadas para execução. Por outro lado, na programação puxada as necessidades de
materiais resultantes da aplicação do MRP são utilizadas como previsão de demanda para
dimensionamento de estoques que ficam à disposição dos postos clientes dentro da fábrica.
Em termos operacionais, uma vez montado os estoques, quando os centros de trabalho que
“puxam” necessitam de itens para trabalhar, eles recorrem a esses estoques (supermercados)
para se abastecer, gerando disparo de uma ordem padrão (cartão kanban, por exemplo) para o
centro de trabalho fornecedor deste supermercado, que está autorizado a produzi-lo. Essa
regra dosistema puxado garante a função de sequenciamento dentro do conceito just in time.
Visando apoiar as decisões no âmbito da programação da produção (e, em alguns casos, na geração do plano-mestre de produção), foram desenvolvidos os sistemas de programação da produção com capacidade finita. Esses sistemas têm a característica principal de considerar a capacidade produtiva e as características tecnológicas do sistema produtivo como uma restrição apriori para a tomada de decisão de programação, buscando garantir que o programa de produção resultante seja viável, ou seja, caiba dentro da capacidade disponível (CORRÊA et al. 1997).
Segundo Herrmann et al. (2006), desde a separação que estabeleceu como o
sequenciamento da produção como uma função distinta da administração da produção, as
grandes mudanças na programação e sequenciamento da produção são devido a dois eventos
importantes. O primeiro é criação de Henry Gantt de formas úteis para entender as complexas
relações entre os homens, ordens de máquinas e tempo.
Slack et al. (2007) afirma que o método mais comumente de programação usado é o do
gráfico de Gantt. Um gráfico de Gantt, exemplificado na figura 5, é uma ferramenta simples,
que representa o tempo como uma barra num gráfico. As vantagens do gráfico de Gantt são
que proporcionam uma representação visual simples do que deveria e o que está realmente
acontecendo na operação. Além disso, eles podem ser usados para “testar” programas
alternativos. O gráfico de Gantt não é uma ferramenta de otimização. Ele simplesmente
facilita o desenvolvimento de programações alternativas por comunicá-las eficazmente. A
segunda é o devastador poder da tecnologia da informação de coletar todos os tipos de tomada
de decisões, complementa Herrmann et al. (2006).
25
Figura 5 – Exemplo de um gráfico de GanttFonte: Autor
1.1 Definição de sequenciamento da produção
A entrada de informações para o processo de programação e sequenciamento da
produção está em um plano geral da produção, assumindo capacidade de recursos ilimitada,
que foi o resultado do processo de planejamento da produção. A principal tarefa da
programação e sequenciamento da produção é a criação de um plano de produção viável, que
considere todas as restrições modeladas (como a capacidade de recursos, restrições de tempo
mínimo e máximo entre as operações, os recursos secundários e os recursos de várias
atividades, dentre outros parâmetros.), afirma Herrmann et al. (2006).
Segundo Slacket al. (2008), quando o trabalho chega, decisões devem ser tomadas sobre
a ordem em que as tarefas serão executadas, seja a abordagem do carregamento finita ou
infinita. Essa atividade é denominada sequenciamento da produção.
Pinedo (2008) e Morton e Pentico (1993) afirmam que, o sequenciamento da produção é
um processo de tomada de decisão presente em muitos sistemas de manufatura e serviços
industriais. Trata-se de alocação de recursos limitados para tarefas ao longo do tempo. Os
objetivos podem também assumir várias formas diferentes. O objetivo pode ser minimizar o
26
tempo de finalização da ultima tarefa (makespan) e outra forma pode ser minimizar a
quantidade de tarefas finalizadas depois de suas respectivas datas de entrega.
A atividade de sequenciamento busca gerar um programa de produção para os itens
fabricados e montados que utilize inteligentemente os recursos disponíveis, promovendo
produtos com qualidade e custos baixos (TUBINO, 2007). Uma programação da produção é
uma distribuição temporal utilizada para distribuir atividades, utilizando recursos ou alocando
instalações, complementa Davis et al. (2001).
1.2 Sequenciamento em ambiente de manufatura e de serviços
Pinedo (2008), quanto às interações entre sequenciamento da produção e outros
processos de tomada de decisão, afirma que, as ordens que são liberadas em um ambiente de
manufatura são transformadas em tarefas com associadas datas de entrega. Esses trabalhos,
muitas vezes são processados em uma máquina de um centro de trabalho em uma determinada
ordem ou sequência. O processamento dos trabalhos às vezespode ser adiado se certas
máquinas estão ocupadas. Preempção pode ocorrer quando as tarefas de alta prioridade são
liberadas e devem ser processadas imediatamente. Eventos inesperados no chão de fábrica,
tais como quebra de máquinas ou tempos de processamento mais longos que o esperado,
também devem ser levados em conta, uma vez que eles podem ter um grande impacto sobre o
sequenciamento da produção. Desenvolvendo, em tal ambiente, um sequenciamento
detalhado das tarefas a serem executadas ajuda a manter a eficiência e o controle das
operações.
O chão de fábrica não é a única parte da organização que tem impacto sobre o processo
de sequenciamento da produção. O processo de sequenciamento também interage com o
processo de planejamento da produção, que trata do planejamento de médio a longo prazo
para toda a organização. Este processo tem a intenção de otimizar o mix de produtos total da
empresa e alocação de recursos a longo prazo com base nos níveis de estoque, previsões de
demanda e necessidades de recursos. Decisões tomadas a este nível superior de planejamento
podem afetar diretamente o mais detalhado processo de sequenciamento, afirma Pinedo
(2008). A figura 6 apresenta o fluxograma das interações em um ambiente de manufatura.
27
Figura 6 – Fluxograma em um ambiente de manufaturaFonte: Adaptado de Pinedo (2008)
Pinedo (2008) complementa que, em um ambiente de manufatura, a programação da
produção interage com outras funções de tomada de decisão. Um sistema popular que é
amplamente usado é o sistema MRP (Material Requirements Planning). Depois de gerada
uma programação da produção é necessário que todas as matérias primas e recursos estejam
disponíveis no momento específico. As datas de início de processamento de todas as tarefas
devem ser determinadas conjuntamente pelo PPCP e o sistema MRP.
O sistema de sequenciamento, em um ambiente de serviços, deve ser coordenado com
outros processos de tomada de decisão, geralmente dentro de sistemas de informação
elaborados, da mesma forma que a função de programação em um ambiente de
produção. Esses sistemas de informação geralmente contam com bancos de dados extensos
28
que contêm todas as informações relevantes no que diz respeito à disponibilidade de recursos
e clientes. O sistema de programação interage frequentemente com os módulos de previsão e
financeiro. A figura 7 apresenta o fluxograma das interações em uma organização de serviços.
Em contraste com um ambiente de manufatura, geralmente não há um sistema MRP em uma
organização de serviços (PINEDO, 2005).
Figura 7 – Fluxograma em organização de serviçosFonte: Adaptado de Pinedo (2008)
1.3 Características do sistema de sequenciamento da produção
Pinedo (2008) explica que, as funções de um sequenciamento da produção de uma
empresa dependem de técnicas matemáticas e métodos heurísticos para alocar recursos
limitados nas atividades que devem ser realizadas. A alocação de recursos deve ser feita de tal
forma que a empresa otimize as suas funções objetivas e alcance suas metas.
Segundo Liddell (2009), para ser útil, o sistema de sequenciamento deve ser capaz de
usar modelos que reflitam as restrições do mundo real, de modo a fornecer aos gerentes
informações confiáveis e atualizadas para que possam tomar decisões importantes e acertadas.
Além de usar lógica do tipo causa e efeito para gerar e avaliar cenários alternativos, antes de
decidirem qual o melhor caminho a seguir.
Pinedo (2008) complementa que a programação e o sequenciamento da produção não só
proporcionam um processo coerente para gerenciar o projeto, mas também fornece uma boa
estimativa para o seu tempo de conclusão, revela as tarefas que são críticas e determina o
tempo real de todo o projeto.
29
A tarefa de programação tem que ser repetida frequentemente para permitir resposta ás
variações de mercado e às mudanças no mix de produtos. Mudanças menores no mix de
produção podem fazer recursos limitantes de capacidade dentro das instalações mudarem
bastante em um tempo curto; assim, gargalos podem mover-se pela fabrica rapidamente,
complementa Slacket al. (2008).
1.4 Considerações e restrições de processamento no ambiente de sequenciamento da
produção
O processamento de tarefas tem varias características distintas e frequentemente está
sujeito a restrições. As características, considerações e restrições de processamento mais
comuns são descritas segundo Pinedo (2008):
Precedência: Requer que certo conjunto de tarefas esteja finalizado para que uma tarefa
específica esteja disponível para ser iniciada em certo processo.
Tempos de setup dependentes da sequência:Representa o tempo de setup dependente
da sequencia ocorrida entre o processo de duas tarefas.
Família de tarefas: Tarefas de uma mesma família podem ter diferentes tempos de
processo, mas estas tarefas podem ser processadas em uma máquina após outra,sem requerer
nenhum setup entre elas.
Processamento em lotes: Uma máquina pode ser capaz de processar um numero de
tarefas simultaneamente, ou seja, pode processar um lote de tarefas ao mesmo tempo. Todos
os tempos de processos das tarefas em um lote podem não ser iguais e o lote todo é finalizado
somente quando a ultima tarefa de um lote for finalizada, isto implica que o tempo de término
de um lote é determinado pela tarefa com maior tempo de processamento.
Quebra de máquina: Uma máquina pode não está sempre disponível. Os períodos em
que a maquina não está disponível, representa o período em que a máquina está com defeito
ou em manutenção.
Elegibilidade de máquina: Ocorre em ambiente com máquinas paralelas, onde pode
ser o caso de certa tarefa não poder ser alocada em qualquer uma das máquinas disponíveis. A
tarefa pode somente ser alocada a uma máquina que pertença a um especifico conjunto de
30
maquinas. Isto pode acontecer quando as máquinas em paralelo de um centro de trabalho não
são idênticas.
Restrição de mão-de-obra: Uma máquina pode sempre requerer um ou mais
operadores específicos para processar a tarefa e a habilidade de operar a tarefa em certa
máquina pode pertencer a poucas pessoas. Tarefas que necessitam ser processadas em certa
máquina podem ter que esperar até um desses operadores (ou outros recursos) esteja
disponível.
Restrição de rota: Especifica que a rota de uma tarefa deve acompanhar através do
sistema um fluxo de ambiente flow shop ou job shop. Certa tarefa pode consistir em um
numero de operações que tenham de ser processada em certa sequência ou ordem. Restrição
de rota representa a ordem em que a tarefa deve seguir pelos centros de trabalho.
Restrição de manuseio de materiais: Sistemas de montagem modernos apresentam
muitas vezes sistemas de manuseio de materiais que transferem as tarefas de um centro de
trabalho para outro.O nível de automação do sistema de manuseio de material depende do
nível de automação do centro de trabalho. Se os centros de trabalho são altamente
automatizados, então os tempos de processamento são determinísticos e não variam. Um
sistema de manuseio de material impõe uma forte dependência entre o momento inicial de
uma determinada operação e o tempo de conclusão dos seus antecessores. Além disso, a
presença de um sistema de manuseio de materiais, muitas vezes limita a o espaço do
“pulmão”, que restringe a quantidade de material em processo.
Restrição de armazenamento e de tempo de espera: O tamanho do espaço disponível
para armazenamento do material em processo pode ser limitado. Isto estabelece um limite
superior na quantidade de tarefas em espera de uma máquina.
Make-to-Stock e Make-to-Order: As indústrias de manufatura podem optar por manter
itens em estoque para uma demanda constante e sem risco de obsolescência. Esta decisão de
produzir para estoque, afeta o processo de sequenciamento da produção, pois itens que têm de
ser produzidos para estoque não têm datas de entrega com folga pequena. Tarefas feitas sob
encomenda têm datas de entrega e volume produzido determinado pelo cliente.
Preempção: Algumas vezes, durante a execução de uma tarefa, um evento que força o
programador a interromper o processamento dessa tarefa, a fim de tornar a máquina
disponível para outro trabalho. Isso acontece, para situações, em que uma ordem de produção
31
com alta prioridade entra no sistema. A tarefa retirada da máquina representa uma preempção
do sequenciamento.
Restrição de Transporte: Se há várias instalações de manufatura conectadas entre si,
em uma rede, então o planejamento e programação de uma cadeia de suprimentos torna-se
importante. O tempo de transporte de material entre duas fábricas ocorre na realidade e deve
ser considerado na prática.
1.5 Ambientes de sequenciamento de produção
A classificação dos ambientes de sequenciamento produção tem uma grande
importância para os profissionais da área de produção, pois o conhecimento dos tipos de
ambientes de produção proporciona um melhor entendimento das relações entre as
características do sistema, da seleção de ferramentas, técnicas e modelos de programação e
sequenciamento da produção.
Ambientes de sequenciamento de produção podem se diferenciar na maneira como as
tarefas chegam ao sistema, e na diferença entre o número e as sequencias de operações dos
trabalhos. Quanto à natureza da chegada do trabalho ao sistema se diferencia entre processos
estáticos e dinâmicos. No processo estático, chega certa quantidade de tarefas
simultaneamente ao sistema que está ocioso e imediatamente é disponibilizado para trabalho.
Mais tarefas não serão incorporadas ao sistema até que todas as tarefas anteriores sejam
finalizadas. O grande foco é nas tarefas conhecidas e disponíveis na programação. No
processo dinâmico o sistema está em processo continuo. Tarefas chegam intermitentemente,
em uma frequência que só é possível prever estatisticamente. O processo de chegada de
tarefas na programação continua indefinidamente. A rota em que cada tarefa segue entre as
operações, determina quando é um ambiente flow shop, job shop, open shop, dentre outros
ambiente de sequenciamento de produção, descreve Herrmann et al. (2006)
A literatura sobre sequenciamento de produção apresenta algumas classificações
para problemas de sequenciamento de produção. A classificação é baseada, além de
outros critérios, em relação ao número de máquinas, fluxo do material e em relação
à função objetivo. Problemas de sequenciamento de produção são classificados na
literatura como problemas de máquina única, problemas de máquinas paralelas,
problemas de flow shop, problemas de job shop, e problemas de open shop.
32
Diferentes funções objetivas e critérios adicionais, como prioridades, tempos de
setup dependentes da sequência ou recursos paralelos, proporcionam um grande
numero de classes para problemas de sequenciamento. Cada classe de problemas de
sequenciamento pode ser tratada através de simples regras de prioridade, ou por
meio de algoritmos sofisticados. Exemplos de algoritmos de escalonamento famosos
incluem o algoritmo de Johnson para minimização do makespan em duas máquinas
flowshop e o "Shiftingbottleneck procedure" que foi desenvolvido para minimizar o
makespan em problemas de jobshop. (HERRMANN etal. 2006)
1.5.1 General Shop
O problema clássico de sequenciamento/programação envolve uma série de tarefas e
uma série de recursos, onde recursos realizam operações e cada tarefa requer uma ou mais
operações para serem completadas. A sequência de tarefas para cada recurso (ou a rota de
recursos para cada tarefa) deve ser determinada de tal forma que a combinação dos objetivos
sejam otimizadas e as restrições respeitadas, explica Herrmmanet al. (2006).
Segundo Brucker (2007), o modelo clássico do problema de sequenciamento em
ambiente de produção pode ser definido como a seguir. Há n tarefas j = 1,..., n e m máquina
M1,..., Mm. Cada tarefa j consiste em um conjunto de operações Oji (i = 1,..., ni) com tempos
de processo pji. Cada operação Ojideve ser processada na máquina μij {M1,..., Mm}. Nestas,
deve haver relações de precedência entre as operações de todas as tarefas. Cada tarefa pode
ser processada por apenas uma máquina por vez e cada máquina pode processar apenas uma
tarefa por vez. O objetivo é encontrar o sequenciamento viável que minimize uma ou mais
funções objetivo dos tempos de finalização Cj das tarefas j = 1,..., n.
1.5.2 Máquina Única
Problemas de máquina única podem ser descrito na forma de um sistema em que há n
tarefas Jjcom tempos de processamento pj(j = 1,...,n) onde cada tarefa deve ser processada em
uma única máquina M1.
Pinedo (2007) comenta que muitos sistemas de produção apresentam modelos de
máquina única. Caso haja um único gargalo, o desempenho de todo o sistema estará
33
determinada por este gargalo. Isto implica que o problema original, primeiro deve ser
reduzido a um único problema desequenciamento de máquina única. Modelos de máquina
única também são importantes nos métodos de decomposição, quando os problemas de
programação da máquina em ambientes mais complicados são decompostos em uma série de
pequenos problemas de programação de máquina única.
1.5.3 Máquinas Paralelas
Um conjunto de máquinas em paralelo é uma generalização do modelo de máquina
única. Muitos ambientes de produção consistem em vários estágios ou centros de trabalho,
cada um com um número de máquinas em paralelo. As máquinas em um centro de trabalho
podem ser idênticas, de modo que um trabalho pode ser processado em qualquer uma das
máquinas disponíveis. Modelos de máquinas paralelas são importantes pela mesma razão que
os modelos de máquina única. Caso um centro de trabalho em particular é um gargalo, então o
sequenciamento neste centro de trabalho vai determinar o desempenho de todo o
sistema. Gargalo que pode ser modelado como um conjunto de máquinas paralelas e
analisados separadamente.Às vezes, as máquinas em paralelo podem não ser exatamente
idênticas. Algumas máquinas podem ser mais velhas e operar em uma velocidade menor, ou
algumas máquinas podem ter capacidade de fazer um trabalho de maior qualidade. Se for esse
o caso, então alguns trabalhos podem ser processados em qualquer uma dasm máquinas.
Quandoos recursos são pessoas, então o tempo de processamento de uma operação depende
do desempenho do operador com a tarefa. Um operador pode ser excelente em um tipo de
trabalho, enquanto outro operador pode ser mais especializado em outro tipo. (PINEDO,
2007).
Pinedo (2007) define os três tipos de máquinas paralelas como:
1) Máquinas paralelas idênticas: Há m máquinas idênticas em paralelo. Cada tarefa j
requer uma única operação que pode ser processada em qualquer uma das m
máquinas.
2) Máquinas paralelas com velocidades diferentes: Há m máquinas em paralelo com
diferentes velocidades. A velocidade da máquina i é denotada por υi. Otempo pijque
cada tarefa j demora na máquina i é igual apj÷υi. Este ambiente de sequenciamento de
34
produção também é referido como “máquinas paralelas uniformes”. Se todas as
máquinas têm o mesmo tempo υi = 1 para todo i e pij = pj, então o ambiente será
idêntico ao de máquinas paralelas idênticas.
3) Máquinas paralelas não relacionadas: Este ambiente de sequenciamento de
produção é uma generalização do ambiente de máquinas paralelas uniformes. Onde há
m máquinas diferentes em paralelo. A máquina i pode processar a tarefa j com
velocidade υij. O tempo pji que a tarefa j demora na máquina i é igual apj÷υji. Caso as
velocidades das máquinas sejam independentes das tarefas a quais processam, υji = υi
para todos i e j, então este ambiente de sequenciamento será igual ao de máquinas
paralelas uniformes (velocidades diferentes.).
1.5.4 Open Shop
De acordo com Brucker (2007), um ambiente de sequenciamenoopenshop é um caso
especial do general shop em que:
Cada tarefa j consiste em m operações Oji (i = 1,..., m) onde Oji deve ser processada na
máquina Mi, e
Não há relações de precedência entre as operações.
Desta forma, o objetivo é encontrar ordens de operações pertencentes à mesma tarefa, e
ordens de operações a serem processadas na mesma máquina.
Para Pinedo (2005), um ambiente open shop pode ser definido como um cenário que há
m máquinas. Cada tarefa tem que ser processada novamente em cada uma das m máquinas.
No entanto, alguns desses tempos de processamento podem ser zero. Não há restrições no que
diz respeito à rota de cada trabalho através dos centros de trabalho. O programador está
autorizado a determinar uma rota para cada tarefa e tarefas diferentes podem ter diferentes
rotas.
35
1.5.5 Flow Shop
De acordo com Brucker (2007), o ambiente de seqüenciamento flow shop é um
ambiente general shop em que:
Cada tarefa j consiste em m operações Oji com tempos de processamento pji (i =
1,..., m) onde Oji tem que ser processada na máquina Mi, e
Há restrições de precedência de forma que Oji → Oj,i+1 (i = 1, ..., m – 1) para
cada i = 1, ..., n. Assim, cada tarefa é primeiramente processada na máquina 1,
depois máquina 2, depois máquina 3, e assim por diante.
Desta maneira, o objetivo é encontra a ordem de tarefas para cada máquina i.
Pinedo (2005) explica que em um ambiente flow shop, há m máquinas em série. Cada
tarefa tem que ser processada em cada uma das m máquinas. Todas as tarefas têm que seguir a
mesma rota. Após a conclusão de uma operação em uma máquina, a tarefa é alocada na fila da
próxima máquina.
Morton e Pentico (1993) e Conway et al. (2003) descreve que o flow shop consiste em
uma série de operações iguais para serem realizadas na mesma sequência na mesma série de
máquinas, para todas as tarefas. Há uma máquina que realiza a primeira operação de cada
tarefa, outra máquina realiza a segunda operação, assim por diante.
FlowShop Flexível: Pinedo (2005) define flow shop flexível com uma generalização do flow
shop devido à presença de máquinas em paralelo nos centros de trabalho. Em vez de m
máquinas em série, há c centros de trabalho agrupando máquinas idênticas que funcionam em
paralelo. Um trabalho é processado em uma máquina de um centro, mas todas as máquinas
deste centro poderiam processá-lo da mesma forma.
FlowShop Permutacional: Flow shop permutacional acontece quando a sequência das tarefas em cada máquina é a mesma.
1.5.6 Job Shop
Brucker (2007) explica que o ambiente job shop é um caso especial do general shop que
é uma generalização do flow shop. Dado n tarefas j = 1,..., n e m máquinas M1, ...Mm. A tarefa
36
j consiste de um sequência de ni operações Oj1, Oj2,..., Ojni que devem ser processadas em
uma ordem, devido a existência de restrições de precedência na forma Oji→Oj,i+1 (i = 1, ..., ni
-1). Há uma máquina μij {M1,..., Mm} e um tempo de processamento pji associado à cada
operação Oji. A operação Oji deve ser processada durante pji unidades de tempo na máquina
μji. O objetivo é encontrar um sequenciamento viável que minimize algumas funções
objetivas que dependem do tempo de término Cjdas ultima operações Oi,ni das tarefas.
Assume-se que μij ≠ μij+1 para i = 1,...,ni – 1, caso não seja indicado de forma diferente.
Morton & Pentico (1993) complementa que, o job shop clássico também é chamado de
closed shop, pois as ordens são distintas e o material em processo costuma não poder ser
emprestado de outra tarefa.
1.5.7 JobShop Flexível
De acordo com Pinedo (2005), o jobshop flexível é uma generalização do job shop
clássico em que há máquinas em paralelo. Em vez de m máquinas, há c centros de trabalho
que agrupam máquinas idênticas que funcionam em paralelo. Além de cada trabalho ter sua
própria rota a seguir, um trabalho é processado em uma máquina de um centro de trabalho,
mas as outras máquinas deste centro poderiam processá-lo da mesma forma.
Esses diversos tipos de problemas são ilustrados na figura 8, onde i é o número de
estágios da produção, e Mi é o número de máquinas do estágio i(com i = 1,2,...m).
Figura 8 – Relações entre classes de problemas de programação de operações em máquinas.Fonte: Adaptado de MACCARTHY, (1993) apud MORAIS (2010).
37
1.6 Características de um ambiente job shop
Daviset al. (2001) descreve um ambiente job shop como uma organização funcional
cujos centros de trabalhos são organizados em tornos de processos particulares, os quais
consistem em tipos específicos de equipamentos e operações. Os bens produzidos ou os
serviços oferecidos são originados por pedidos individuais de um cliente específico.
Para Davis et al. (2001), a proposta da programação de operações em um ambiente job
shop é desmembrar o Planejamento Mestre de Produção em atividades semanais, diárias ou
por hora, sequenciadas no tempo. Desta forma especifica-se precisamente a carga de trabalho
planejada no processo de produção para o curto prazo. O quadro 1 apresenta as características
de um ambiente job shop.
Características No ambiente Job Shop Missão Venda de capacidade e habilidades. Fluxo dos itens Poucos ou nenhum caminho dominante. Gargalos Desloca-se frequentemente. Seleção de equipamentos De uso geral, flexível. Duração de processamento Curta. Custo de setup Baixo. Uso de mão de obra Alto. Escopo dos trabalhos diretos Amplo. Controle do ritmo de trabalho Operador, chefe de turno, expedidor. Estoque de matéria-prima Baixo. Estoque em processo Alto. Estoque de bens acabados Baixo ou nenhum. Fornecedores Frequentemente, utiliza-se vários fornecedores. Informações para o ..trabalhador ..necessárias para ..a tarefas
Novas instruções são necessárias para cada tarefa; treinamento especializado algumas vezes necessário.
Programação
Incerto, mudanças são frequentes; componentes de uma tarefa complexa precisam ser finalizados aproximadamente ao mesmo tempo.
Desafios
Estimativa das necessidades, programação e resposta rápida aos gargalos.
Resposta para a diminuição da ..demanda
Demitir funcionários dos departamentos atingidos.
Quadro 1 – Principais características de um ambiente Job Shop.Fonte: Robert. H. (1984). Apud Davis et al. (2001)
38
1.7 Medidas de desempenho
Vários tipos de objetivos são importantes no sistema de manufatura. Os objetivos são
muitas vezes compostos de objetivos básicos. Segundo Brucker (2007), alguns objetivos
básicos mais importantes são o makespan e o tempo de fluxo.
1.7.1 Makespan
Para Pinedo (2008), em várias fábricas, maximizar a quantidade de material que é
produzida por um processo em uma unidade de tempo (Throughput) é o mais importante. O
throughput em uma fábrica, que é o mesmo que a taxa de saída, é frequentemente
determinado pelas máquinas gargalos. Desta forma, maximizar a taxa de throughput da
fábrica é quase sempre o mesmo que maximizar o throughput das máquinas gargalos. O
makespan é importante quando há uma quantidade finita de tarefas. O makespan é denotado
por Cmax e é definido como o tempo em que o ultimo trabalho sai do sistema.
Cmax = max(C1, ..., Cn),... (1)
Onde Cj é o tempo de finalização da tarefa j.
Pinedo (2005) complementa que o makespan é diretamente relacionado com o
throughput. Heurísticas que tendem a minimizar o makespan em um ambiente com números
finitos de tarefas, também tendem a maximizar a taxa de throughput quando há um fluxo
constante de tarefas ao longo do tempo.
1.7.2 Tempo de fluxo médio
O somatório dos tempos de finalizaçãoCj das n tarefas. Pode indicar os custos de
estoque incorrido pela programação.
39
(2)
Segundo Conway et al. (2003), o tempo de fluxo médio é diretamente proporcionalao
fluxo de material em processo. Um procedimento de sequenciamento que minimiza o tempo
de fluxo médio, também minimiza o atraso médio, tempo de espera médio, e a quantidade
média de tarefas no sistema.
1.8 Regras De Sequenciamento
De acordo com Tubino (2007), as regras de sequenciamento são heurísticas usadas para
selecionar, a partir de informações sobre características dos itens ou lotes e sobre o estado do
sistema produtivo, qual das tarefas esperando na fila de um centro de trabalho terá prioridade
de processamento, e qual recurso deste centro de trabalho será alocado essa tarefa.
Os principais algoritmos de sequenciamento são:
Algoritmos de solução ótima (exatos): Estes encontram a solução ótima para o
problema de sequenciamento.
Algoritmos de aproximação:Produzem soluções que garantem uma distância
percentual fixa da solução ótima com um processamento computacional rápido.
Algoritmos heurísticos: Produzem soluções que não garantem estarem próximas da
solução ótima. O desempenho das heurísticas são geralmente avaliados empiricamente.
Os algoritmos heurísticos podem ser classificados como Heuristicas de Construção e
Heurísticas de Melhoria.
Heurísticas de Construção: Iniciam sem uma sequencia predeterminada e adicionam
uma tarefa por vez.
Heurísticas de melhoria: Iniciam com uma sequencia predeterminada e tenta
encontrar sequencias semelhantes melhores.
Regras de despacho são exemplos de heurísticas de construção. Método de busca local
são exemplos de heurísticas de melhoria. A figura 9 apresenta a hierarquia básica das
heurísticas de sequenciamento
40
Figura 9 – Principais algoritmos de sequenciamento.Fonte: Autor.
Pacheco (1999) detalha que regras de Despachosão modelos no qual a sequência a ser
obedecida pelo programa é construída simultaneamente ao mesmo tempo, priorizando-se as
ordens presentes na fila por meio de regras. Para tal, utiliza-se um procedimento de liberação
no qual, tão logo uma máquina torna-se disponível, inicia-se a operação da ordem em
primeiro lugar na fila. A prioridade das tarefas pode ser dada estática ou dinamicamente
(dependendo do momento de sua atribuição), local ou globalmente (regras que analisam
outras filas para a definição da prioridade) ou de forma míope. Regras míopes são aquelas nas
quais a prioridade é atribuída "otimizando-se" o problema em cada máquina
independentemente das outras, sem preocupação com otimização global. A mesma regra de
liberação pode ser utilizada em todas as máquinas, ou regras diferentes podem ser utilizadas
em máquinas distintas.
Soluções otimizadas para o problema de sequenciamento, empregando técnicas de
Pesquisa Operacional (programação linear, inteira, grafos etc.), são viáveis
matematicamente e podem ser desenvolvidas para soluções particulares. Contudo, a
natureza combinatória do problema que cresce, que cresce a cada vez que novos
produtos e roteiros são lançados, faz com que na prática seja difícil conciliar a
variabilidade, não só dos dados de produção, como também no próprio sistema
produtivo, com a dinâmica de atualização dos parâmetros do algoritmo otimizador.
Por esta razão, as empresas nesse segmento de mercado em lotes preferem trabalhar
com regras simplificadas que, se não garantem o atendimento da solução ótima no
momento, procuram chegar a uma solução boa e rápida frentea constante mudança
da dinâmica de produção. (TUBINO, 2007)
41
Regras de despacho são simples de implementar, proporcionam um processo
computacional rápido, podem encontrar uma solução razoavelmente boa em um tempo
relativamente pequeno e encontram soluções ótimas em alguns casos especiais. Porém podem,
imprevisivelmente, encontrar soluções relativamente ruins.
Abaixo são apresentadas as regras de sequenciamento (também chamadas de regras de
despacho) mais utilizadas, citadas por Tubino (2007), Slack (2008), Davis (2001) e outras
referências consultadas.
SPT (Shortest Processing Time)
Consiste em dar uma maior prioridade às tarefas que tenham o menor tempo
deprocessamento pi :
p1 ≤ p2 ≤ …≤ pn. Costuma ser usada para minimizar o tempo médio de fluxoMF.
EDD (Earliest Due Date)
Consiste em dar uma maior prioridade às tarefas que tenham a menor data de entrega di,
ou seja, àquelas que precisam ser entregues mais rapidamente:
d1≤ d2≤ … ≤ dn
FIFO (First In First Out)
Também chamada deFCFS (First ComeFirst Served). Consiste em dar uma
maiorprioridade à tarefa se encontra há mais tempo na fila de processamento de um centro de
trabalho.
LWKR (Least WorK Remaining)
Também chamada LWR. Consiste em dar uma maior prioridade à tarefa que tenha
omenor tempo de processamento pi dentro das operações ainda não executadas.
TWK (Total WorK)
Consiste em dar uma maior prioridade à tarefa que tiver o menor tempo de
processamentopi para todas as operações
NXQL (NeXt Queue Length)
Consiste em dar maior prioridade à tarefa cuja estação de trabalho tiver a menor fila.
42
LIFO (Last In First Out)
Também chamada FILO (First In Last Out). Consiste em dar uma maior prioridade
àtarefa que se encontra a menos tempo de espera em uma fila do centro de trabalho.
WNS (least Work at Next Station)
Representa o tempo total em fila que uma tarefa i tem em relação à próxima estaçãode
trabalho. Consiste em dar uma maior prioridade à tarefa que puder ser deslocada parauma
máquina “folgada”. Consequentemente a menor prioridade é dado à tarefa cujapróxima
estação de trabalho estiver sobrecarregada.
LPT (Longest Processing Time)
Consiste em dar uma maior prioridade à tarefa que tiver o maior tempo de
processamento pi.
CR (Critical Ratio)
É a razão critica. É calculada como a diferença entre a data de entrega e a data atual
dividida pelo trabalho restante. Os pedidos com menor CR são executados primeiro. O CR
representa: (tempo restante para atingir a data de entrega) ÷ (tempo deprocessamento
restante).
GNTP (Greater Number of Times Processed)
Consiste em dar uma maior prioridade à tarefa que mais vezes tiver sido processada.
LNTP (Lower Number of Times Processed)
Consiste em dar uma maior prioridade à tarefa que menos vezes tiver sido processada.
MWKR (Most WorK Remaining)
Consiste em dar uma maior prioridade à tarefa que tiver o maior tempo de
processamentoainda a ser executado.
MOPNR (Most OPeratioNs Remaining)
Consiste em dar uma maior prioridade à tarefa que tiver o maior número de
operaçõesainda a serem executadas.
43
RANDOM
Consiste em estipular aleatoriamente as prioridades das tarefas.
Além dessas regras básicas existem várias outras regras básicas e regras mistas, estas
que combinam regras de despacho para otimizar certos objetivos. As regras mistas costumam
apresentar resultados melhores para otimização desses objetivos.
Estudos comprovam que a eficiência de uma regra dependerá da variedade dos lotes,
dos tamanhos destes lotes, e da participação relativa de cada tipo de peça, o que faz com que
uma boa regra numa situação não seja necessariamente boa em outra. (TUBINO, 2007)
3. DESENVOLVIMENTO E IMPLEMENTAÇÃO COMPUTACIONAL
Neste capítulo é apresentado a metodologia realizada para o estudo, que auxilia na
análise e comparação dos resultados do algoritmo implementado para escalonamento em
ambiente de produção Job Shop Flexível. Também são apresentados os cenários das
instâncias, a forma de tratamento dos resultados e os pseudocódigos do algoritmo
computacional.
O estudo desenvolvido da implementação computacional segue o roteiro de atividades a
seguir:
1) Revisão Bibliográfica
Esta etapa envolve o levantamento de livros e publicações que servem de suporte
teórico para implementação do algoritmo e auxilia o desenvolvimento do estudo.
2) Desenvolvimento e Implementação do algoritmo
Esta segunda etapa tem como foco o desenvolvimento do algoritmo computacional, em
linguagem de programação Python, para um ambiente Job Shop Flexível.
44
3) Testes do algoritmo
Esta fase se caracteriza por serem realizados os testes das instâncias e verificar possíveis
erros do algoritmo. Nesta etapa também foi testado o algoritmo para vários cenários,
incluindo os cenários apresentados por este estudo. Os testes dos resultados do algoritmo
foram realizados por resolução manual, através do gráfico de Gantt, de uma amostra de
instâncias geradas.
4) Delineamento experimental:
Os três cenários simulado são diferenciados pela quantidade de máquinas por centros de
trabalho, ilustrados pelas figuras 11, 12 e 13. A quantidade de centros de trabalho e a
quantidade de tarefas foram mantidas fixas para os três cenários. Os tempos das operações das
tarefas e a sequencia de operações de cada tarefa, são escolhidas aleatoriamente pelo
simulador em cada instância. O tempo de processamento de uma operação em máquina não
difere das demais máquinas do centro. O conjunto de operações contém seis tipos de
operações que cada tarefa pode ser processada, que correspondem aos seis centros de
trabalho. A quantidade de tarefas foi estabelecida como quinze, para que haja fila de tarefas
pelo menos para algum centro de trabalho. A quantidade de operações por tarefas variam
entre si, de duas a seis operações, essa quantidade se mantém fixa nos cenários testados.
Foram realizadas mil simulações para cada cenário e comparados os resultados de cada regra
de despacho e da regra RANDOM (aleatória) entre si. Para a regra de despacho RANDOM,
foram realizadas mil simulações em cada instância, resultando em um milhão de resultados
por cenário. Tal quantidade de simulações por instância se fez necessária para obter uma
média dos resultados em um sistema sem regras de despacho definidas, e também devido ao
fato dessa regra ter um imenso conjunto de resultados diferentes, dependendo do tamanho do
problema, para cada instância. Enquanto as outras regras de despacho têm um conjunto de
resultados com apenas um elemento por instância, cada.
O tempo de processamento para cada operação de uma tarefa pode variar entre dez a
cem unidades de tempo. Tal variedade no tempo de processamento é independente do tipo de
operação ou tipo de máquina ao qual será processada a tarefa. Em ambiente real, nas
indústrias, essa variação no tempo pode ser variada devido ao tipo do produto para aquela
operação, o tamanho do lote, o tempo de setup, dentre outros.
45
No primeiro cenário foi configurada uma quantidade de máquinas mij, para cada centro
de Trabalho CTi, onde i = 1, 2, 3,..., 6. Essa configuração foi proposta para que o cenário se
comportasse como um sistema de produção com capacidade produtiva não balanceada. Desta
forma o cenário apresenta três máquinas para o centro de trabalho 1, duas máquinas para o
centro de trabalho 2, três máquinas para o centro de trabalho 3, uma máquina para o centro de
trabalho 4, uma máquina para o centro de trabalho 5 e uma máquina para o centro de trabalho
6. A figura 11 ilustra o cenário 1.
CENÁRIO 1
CT1 CT2 CT3 CT4 CT5 CT6
m1,1 m2,1 m3,1 m4,1 m5,1 m6,1
m1,2 m2,2 m3,2
m1,3 m3,3 Figura 11 – Configuração do cenário 1
Fonte: Elaborado pelo autor.
No segundo cenário a quantidade de máquinas por centro é igual, para que se tenha um
comportamento de um sistema de capacidade produtiva balanceada. Logo, a configuração dos
recursos do cenário 2 apresenta três máquinas em cada centro de trabalho. A figura 12 ilustra
o cenário 2.
CENÁRIO 2
CT1 CT2 CT3 CT4 CT5 CT6
m1,1 m2,1 m3,1 m4,1 m5,1 m6,1
m1,2 m2,2 m3,2 m4,2 m5,2 m6,2
m1,3 m2,3 m3,3 m4,3 m5,3 m6,3Figura 12 – Configuração do cenário 2
Fonte: Elaborado pelo autor.
No terceiro cenário a configuração da quantidade de máquinas por centro segue o
comportamento de uma planta fabril com um gargalo potencial. Assim, o cenário 3 apresenta
uma configuração de um sistema com capacidade produtiva balanceada, exceto por um centro
46
de trabalho que apresenta a capacidade dos recursos equivalente a um terço de outro centro de
trabalho neste cenário. A figura 13 ilustra o cenário 3.
CENÁRIO 3
CT1 CT2 CT3 CT4 CT5 CT6
m1,2 m2,1 m3,1 m4,1 m5,1 m6,1
m1,2 m2,2 m3,2 m4,2 m5,2
m1,3 m2,3 m3,3 m4,3 m5,3Figura 13 – Configuração do cenário 3
Fonte: Elaborado pelo autor.
A quantidade de operações a serem sequenciadas para cada tarefa é apresentada pela
figura 14. A quantidade de operações por tarefa tem um comportamento variado para que
simule um ambiente de produção em que as tarefas obedeçam a uma variação como acontece
na realidade em muitas empresas que apresentam um ambiente de produção Job Shop. As
instâncias geradas admitem que haja tarefas que apresentem regime recirculante de operações,
ou seja, uma tarefa pode ser processada por uma mesma operação mais de uma vez. Logo,
tarefas que tenham mais de 6 operações apresentam comportamento recirculante. As tarefas
com menos de 7 operações podem apresentar comportamento recirculante ou não.
Quantidade de operaçõesTarefas 1 2 3 4 5 6 7
1 2 2 3 3 4 4 5 5 6 6 77 2 8 3 9 4 10 5 11 6 12 713 4 14 5 15 6
Figura 14 - Quantidade de operações para cada tarefa
Fonte: Elaborado pelo autor
47
O Quadro 2 resume os parâmetros variáveis e fixos em relação à mudanças de instância
e em relação à mudança de cenário.
Descrição Instâncias CenáriosOperações das tarefas Variável Variável
Quantidade de operações em cada tarefa Fixo FixoTempo das operações Variável Variável
Quantidade de máquinas por centro de trabalho Fixo VariávelQuadro 2 - Parâmetros variáveis e fixos para instâncias e cenários
Fonte: Elaborado pelo autor
1.1. Implementação do computacional
O problema estudado é definido como Scheduling Job-Shop Flexível. Para estudo de tal
sistema de escalonamento de tarefas foi implementado um algoritmo em Python 2.6 para a
simulação de três cenários, contendo cada um mil instâncias, em ambientes de produção Job-
shop Flexível.
O algoritmo foi implementado com a premissa de que uma máquina somente ficará
ociosa se não houver nenhuma tarefa disponível para ser processada nesta máquina naquele
momento.
A regra RANDOM foi simulada mil vezes para cada uma das mil instâncias geradas
pelo simulador nos três cenários. Tal quantidade de simulações para cada instância foi
necessária para obter uma análise estatística de tal regra. Pois esta regra será importante para
demostrar o grau de importância de se usar uma regra de despacho em um ambiente de
produção JobShop Flexível.
O algoritmo pode ser dividido em quatro componentes. O primeiro componente é o
gerador de instâncias, onde são geradas as instâncias para simulação. Escolhem-se,
aleatoriamente, as operações (cada uma correspondente a um centro de trabalho) e seus
respectivos tempos de processamento para as tarefas que serão sequenciadas, de acordo com a
quantidade de operações definida das tarefas. O segundo componente é o selecionador de
tarefas, onde são selecionadas as tarefas que têm o menor valor do tempo mais cedo possível
de início da próxima operação a ser sequenciada, iguais. O terceiro componente é o
sequenciador, o qual utiliza a regra de prioridade para sequenciamento. E o quarto
componente é o alocador de tarefas, o qual aloca a tarefa na sequencia da máquina.
48
p: Posição do elemento no vetor;
j: Índice da tarefa;
c: Índice do centro;
m: Índice da máquina;
NJ: Quantidade de tarefas;
VPT: Lista que contém todas as operações, ou seja, centros de tarefas, para a simulação.
VPT = [1,2,3,4,5,6];
Jj: Vetor de operações da tarefa j;
TJj: Vetor de tempos das operações da tarefa j.
RTJj: Tempo de liberação da tarefa j;
RTMjcm: Tempo de liberação da próxima máquina m no centro de trabalho c a
processar a tarefa j.
TMCAj: Tempo mais cedo possível de início da próxima operação da tarefa j.
GTMCAp: Vetor de TMCAj selecionadas na posição p.
GTMCA2p: Vetor de menor TMCAj na posição p.
SMcm: Sequencia de tarefas na máquina m do centro de trabalho c.
VPRIORIDADE: Vetor de tarefas em ordem de prioridade.
WKRj: Tempo de operações acumulado nos processos seguintes, incluindo a operação
corrente da tarefa j.
Primeiro componente (Gerador de Instâncias):
Passo 1: Seleciona uma operação, isto é, um centro de tarefa, aleatoriamente, para a
ordem de sequência da tarefa j.
Passo 2: Gera um valor, entre dez a cem, para cada operação, da tarefa J.
O quadro 3 apresenta o pseudocódigo do gerador de instâncias.
49
Gerador_de_instâncias(J, NJ, VPT, TJ)
Início
Para J de 0 a NJ, Faça:
Para p de 0 a Tamanho de Jj, Faça:
Jjp <= um_elemento_do_vetor (VPT)
TJjp<= um_valor_entre_(10)_a_(100)
Fim_Para
Fim
Quadro 3 – Pseudocódigo do gerador de instânciasFonte: Elaborado pelo autor
Segundo componente (Selecionador de tarefas):
Passo1: Determinar o tempo mais cedo possível de início da próxima operação de cada
tarefa.
Passo 2: Ordena tarefas por tempo mais cedo possível de início da próxima operação;
Passo 3: Guardar as tarefas que têm o menor tempo mais cedo de início da próxima
operação.
50
O quadro 4 apresenta o pseudocódigo do selecionador de tarefas.
Selecionador_de_tarefas(RTJ, RTM, TMCA, GTMCA, GTMCA2):
Início
Para j de 0 a tamanho de J
Se RTJj >= RTMjcm então
TMCAj := RTJj;
Senão
TMCAj := RTMjcm;
GTMCA.acrescenta(TMCAj);
Fim_Se
Fim_Para
Ordena_por_ordem_crescente_de_TMCA(GTMCA)
Condição := verdade
P := 1
Enquanto condição = verdade, Faça
Se tamanho de (GTMCA) >= p e (GTMCA(1) = GTMCA(p)
GTMCA2 <- GTMCAp
p := p+1
Senão
Condição := falso
Fim_Se
Fim_Enquanto
Fim
Quadro 4 – Pseudocódigo do selecionador de tarefasFonte: Elaborado pelo autor
Terceiro componente (Sequenciador):
Passo 1: Ordenar grupo de tarefas a serem sequenciadas por prioridade;
51
Regra SPT (Shortest Processing Time): Prioriza a tarefa com menor tempo de
processamento na operação em análise.
O quadro 5 apresenta o pseudocódigo do sequenciador pela regra SPT.
Prioridade_SPT (GTMCA2, VPRIORIDADE, TJ):
Início
Para j de 0 a Tamanho de GTMCA2. Faça:
VPRIORIDADE.acrescenta( TJjp;j)
Fim_Para
Ordenar_por_ordem_crescente_de_TJjp(VPRIORIDADE)
Fim
* Tal que j sejam as tarefas contidas em GTMCA2.
* A posição p é a primeira do vetor TJj.
Quadro 5 – Pseudocódigo do sequenciador de tarefas pela regra SPTFonte: Elaborado pelo autor
Regra LPT (Longest Processing Time): Prioriza a tarefa com o maior tempo de
processamento na operação em análise.
O quadro 6 apresenta o pseudocódigo do sequenciador pela regra LPT.
Prioridade_LPT (GTMCA2, VPRIORIDADE, TJ):
Início
Para j de 0 a Tamanho de GTMCA2. Faça:
VPRIORIDADE.acrescenta( TJjp;j)
Fim_Para
Ordenar_por_ordem_decrescente_de_TJjp(VPRIORIDADE)
Fim
* Tal que j sejam as tarefas contidas em GTMCA2
* A posição p é a primeira do vetor TJj.
Quadro 6 – Pseudocódigo do sequenciador de tarefas pela regra LPTFonte: Elaborado pelo autor
52
Regra LWKR (LeastWorkRemaining): Prioriza a tarefa que tem o menor tempo de
processo acumulado nas operações seguintes, incluindo a corrente.
O quadro 7 apresenta o pseudocódigo do sequenciador pela regra LWKR.
Prioridade_LWKR (GTMCA2, WKR, VPRIORIDADE, TJ):
Início
Para j de 0 a Tamanho de GTMCA2. Faça:
WKRj := 0
Para p de 0 a tamanho de TJj. Faça:
WKRj := WKRj + TJjp
Fim_para
VPRIORIDADE.acrescenta(WKRj,j)
Fim_Para
Ordenar_por_ordem_decrescente_de_WKR(VPRIORIDADE)
Fim
* Tal que j sejam as tarefas contidas em GTMCA2.
Quadro 7 – Pseudocódigo do sequenciador de tarefas pela regra LWKRFonte: Elaborado pelo autor
Regra MWKR (MostWorkRemaining): Prioriza a tarefa que tem o maior tempo de
processo acumulado nas operações seguintes, incluindo a corrente.
53
O quadro 8 apresenta o pseudocódigo do sequenciador pela regra MWKR.
Prioridade_MWKR (GTMCA2, WKR, VPRIORIDADE, TJ)::
Início
Para j de 0 a Tamanho de GTMCA2. Faça:
WKRj := 0
Para p de 0 a tamanho de TJj. Faça:
WKRj := WKRj + TJjp
Fim_Para
VPRIORIDADE.acrescenta(WKRj;j)
Fim_Para
Ordenar_por_ordem_decrescente_de_WKR(VPRIORIDADE)
Fim
* Tal que j sejam as tarefas contidas em GTMCA2.
Quadro 8 – Pseudocódigo do sequenciador de tarefas pela regra MWKRFonte: Elaborado pelo autor
Regra RANDOM: Prioriza uma tarefa da fila aleatoriamente.
O quadro 9 apresenta o pseudocódigo do sequenciador pela regra RANDOM.
Prioridade_RANDOM (VPRIORIDADE, GTMCA2):
Início
VPRIORIDADE:=GTMCA2
Ordenar_aleatoriamente(VPRIORIDADE)
Fim
Quadro 9 – Pseudocódigo do sequenciador de tarefas pela regra RANDOMFonte: Elaborado pelo autor
54
FIFO (First-in First-out): Prioriza a tarefa que está a mais tempo na fila do centro de
trabalho.
O quadro 10 apresenta o pseudocódigo do sequenciador pela regra FIFO.
Prioridade_FIFO (GTMCA2, VPRIORIDADE, RTJ):
Início
Para j de 0 a Tamanho de GTMCA2. Faça:
VPRIORIDADE.acrescenta( RTJj;j)
Fim_Para
Ordenar_por_ordem_crescente_de_RTJ(VPRIORIDADE)
Fim
* Tal que j sejam as tarefas contidas em GTMCA2
Quadro 10 – Pseudocódigo do sequenciador de tarefas pela regra FIFOFonte: Elaborado pelo autor
Quarto componente (Alocador de Tarefas):
Passo 1: Se o tempo mais cedo possível de início da próxima operação a ser
sequenciada da tarefa selecionada for igual ao tempo de liberação da máquina que libera mais
cedo do seu centro de máquinas, então tempo de liberação da máquina que libera mais cedo
do seu centro de máquina soma-se com o tempo de processo da operação da tarefa alocada à
máquina e o tempo de liberação da tarefa alocada é igualado ao novo tempo de liberação da
máquina alocadora. Se não, faça o passo 2.
Passo 2: Se o tempo mais cedo possível de início da próxima operação a ser
sequenciada da tarefa selecionada não for igual ao tempo de liberação da máquina que libera
mais cedo do seu centro de máquina, então tempo de liberação da tarefa alocada soma-se com
o tempo de processo da operação da tarefa alocada á máquina e o tempo de liberação da
máquina alocadora iguala-se ao novo tempo de liberação da tarefa alocada;
Passo 3: A operação alocada e o seu tempo de processamento é eliminada do grupo de
operações a serem sequenciadas da tarefa alocada;
Passo 4: Se não há mais operações a serem alocadas, pare. Senão volte ao passo 1 do
componente 2.
55
O quadro 11 apresenta o pseudocódigo do componente alocador de tarefas.
Alocador_de_Tarefas (VPRIORIDADE, TMCA, RTM, P, RTJ, TJ, J,
SM):
Se VPRIORIDADE não for vazio. Faça:
Se TMCAj > RTMjcm Faça:
RTMjcm := RTMjcm + Pij e RTJj := RTMcm
Senão RTJj := RTJj + Pij e RTMjcm := RTJj
Jjp é eliminado e TJjp é eliminado (Onde p=1)
SMcm.acrescenta(Jj)
Volte ao passo 1 do componente 2.
Senão Pare
*Sendo j a tarefa contida em VPRIORIDADE na primeira posição e
m a máquina com menor RTM do cento de máquina c ao qual a
tarefa j será sequenciada.
* Tal que p é a primeira posição do vetor indicado.
Quadro 11 – Pseudocódigo componente alocador de tarefas.Fonte: Elaborado pelo autor
1.1. Análise do dos resultados
A avaliação do resultado de um escalonamento depende dos objetivos e características
de cada empresa.
Para tal estudo, foram testadas técnicas heurísticas de despacho. E seus resultados foram
comparados através de funções de custo.
Para determinar os principais critérios de custo usados em problemas de escalonamento,
é necessário determinar o instante em que cada tarefa termina a sua execução total. Este
instante foi denominado de RTJjmáx nos pseudocódigos descritos.
O makespan e o tempo de fluxo médio são umas das funções objetivas sem data
relacionada, mais utilizada pela literatura. O critério makespan, pode ser definido como o
56
instante de tempo quando a ultima tarefa é finalizada, e o tempo de fluxo médio, que pode ser
definido como a soma dos tempos que as tarefas gastam desde o início em que estas estão
disponíveis até o fim dos seus últimos processos, divididas pelo número de tarefas.
A análise comparativa dos resultados das simulações de escalonamento das tarefas entre
as regras de despacho foi baseada nos seguintes critérios:
Onde:
ié o índice da instância.
n é a quantidade de instâncias.
é a média dos resultados obtidos pela regra s.
é a média das esperanças da regra RANDOM.
é a média dos resultados obtidos pela regra de despacho em comparação.
é a média dos melhores resultados obtidos pelas regras de despacho.
é a média dos melhores resultados encontrados pela Busca Aleatória.
Cálculo da média amostral do makespan e do tempo de fluxo médio para cada regra de
despacho, e a média das esperanças da regra RANDOM.
Média dos resultados da Função objetiva:
(3)
Média das esperanças da regra RANDOM:
(4)
57
Como são realizadas mil simulações para cada regra de despacho, n é igual a mil. No
caso da regra RANDOM será comparada a média das médias de cada instância.
Cálculo da amplitude total dos resultados do makespan e do tempo de fluxo médio para
cada regra de despacho, e para as esperanças da regra RANDOM.
Amplitude Total:
(5)
Cálculo do desvio padrão amostral dos resultados makespan e tempo de fluxo médio
para cada regra de despacho, e para as esperanças da regra RANDOM.
Fórmula do Desvio padrão amostral:
(6)
Cálculo do coeficiente de variação de Pearson dos resultados makespan e tempo de
fluxo médio para cada regra de despacho, e para as esperanças da regra RANDOM.
Coeficiente de variação de Pearson:
(7)
Cálculo da percentagem da diferença da média dos resultados de uma regra de despacho
e a média dos melhores valores encontrados pela busca aleatória (BA*) em relação à média
dos resultados obtidos pela busca aleatória.
(8)
Percentagem da diferença entre a média das médias das simulações pela regra
RANDOM e a média dos valores obtidos pela busca aleatória em relação á média dos
resultados da busca aleatória
58
(9)
Todos os parâmetros de comparação, apresentados, e os tipos de cenários testados,
proporcionam uma comparação e análise consistente entre as regras de despacho utilizadas.
Além dos métodos de analise já apresentados, também foi calculado a quantidade de
instâncias que cada regra de despacho proporcionou o melhor resultado para as funções
objetivas analisadas. A variação dos cenários apoia a análise dos dados para situações
diferentes. A variação dos tempos, operações e tamanho das tarefas entre si, é interessante
para uma análise global dos dados obtidos através das mil simulações realizadas.
Outra avaliação de desempenho das regras de despacho testadas foi através do cálculo
da probabilidade empírica da regra RANDOM obter um resultado, de makespan ou tempo de
fluxo médio, menor ou igual do resultado de cada uma das outras regras de despacho, nos três
cenários testados.
59
4. EXPERIMENTAÇÃO COMPUTACIONAL E ANÁLISE DOS RESULTADOS
Para estudo problema de escalonamento em um sistema job shop flexível, sem
considerar as datas de entrega, turnos de produção e tempos de setup, dentre outras
considerações já comentadas, foi implementado um algoritmo computacional que utiliza
técnicas heurísticas de regras de despacho.
O algoritmo computacional foi escrito na linguagem Python e as simulações realizadas
em um computador Pentium I5 com clock de 2,27 GHz. O tempo de processamento
computacional resultou em 25 horas e 30 minutos para cada um dos três cenários, para
simulação das mil instâncias. Para verificar o desempenho das regras de despacho, nos três
cenários simulados pelo algoritmo implementado, foram comparados entre si através de uma
análise do makespan e do tempo de fluxo médio.
1.1 Análise dos resultados para o makespan
As tabelas 1, 2 e 3 apresentam as distribuições de frequências dos resultados obtidos do
makespan nos cenários 1, 2 e 3 respectivamente, para cada regra de despacho dentro dos
intervalos de makespan selecionados.
Analisando os resultados das tabelas 1,2 e 3, pode-se verificar o desempenho superior
da regra MWKR e o desempenho inferior da regra LWKR em relação às outras regras, para
todos os cenários testados, tendo como objetivo o menor makespan.
Tabela 1 - Distribuição de Frequências do makespan para o cenário 1
Intervalos SPT LPT LWKR MWKR FIFO RDM MÉDIA451 - 500 0 0 0 4 0 0
60
501 - 550 3 0 1 5 2 1551 - 600 4 2 2 25 11 3601 - 650 23 8 0 74 19 12651 - 700 52 27 11 111 61 33701 - 750 79 52 23 128 111 82751 - 800 106 92 56 126 123 114801 - 850 101 93 69 145 126 140851 - 900 130 113 101 116 150 131901 - 950 116 131 108 92 111 142951 - 1000 116 107 131 62 103 1181001 - 1050 92 118 105 38 67 711051 - 1100 52 88 128 31 43 541101 - 1150 45 53 69 19 32 471151 - 1200 34 34 60 9 11 181201 - 1250 13 28 43 4 13 151251 - 1300 12 23 34 3 7 71301 - 1350 8 16 26 5 4 31351 - 1400 7 8 12 2 2 41401 - 1450 1 3 10 1 2 31451 - 1500 3 2 4 0 2 21501 - 1550 0 2 2 0 0 01551 - 1600 1 0 1 0 0 01601 - 1650 0 0 4 0 0 01651 - 1700 0 0 0 0 0 01701 - 1750 2 0 0 0 0 0
Fonte: Elaborada pelo autor
Tabela 2 - Distribuição de Frequências do makespan para o cenário 2
Intervalos SPT LPT LWKR MWKR FIFO RDM MÉDIA301 - 350 0 0 0 1 0 0351 - 400 2 2 0 5 2 0401 - 450 17 8 6 48 16 11451 - 500 63 46 22 105 63 47501 - 550 73 67 40 133 90 80551 - 600 112 66 70 123 117 99601 - 650 88 89 71 105 110 98651 - 700 97 82 67 99 122 109701 - 750 84 106 75 102 113 120751 - 800 93 97 85 76 86 87801 - 850 89 92 93 58 74 99851 - 900 73 95 93 53 56 67901 - 950 55 68 83 37 49 50951 - 1000 35 55 78 16 32 45
61
1001 - 1050 43 44 54 16 31 401051 - 1100 28 20 54 8 14 171101 - 1150 20 23 37 8 11 111151 - 1200 16 19 32 5 8 111201 - 1250 7 12 16 2 3 61251 - 1300 3 6 11 0 2 31301 - 1350 1 3 8 0 0 01351 - 1400 1 0 4 0 1 01401 - 1450 0 0 1 0 0 0
Fonte: Elaborada pelo autor
Tabela 3 - Distribuição de Frequências do makespan para o cenário 1
Intervalos SPT LPT LWKR MWKR FIFO RDM MÉDIA301 - 325 0 1 0 1 0 0326 - 350 2 2 0 4 3 0351 - 375 15 7 6 33 12 11376 - 400 49 44 17 88 41 33401 - 425 90 99 50 185 111 96426 - 450 157 133 71 199 141 142451 - 475 187 178 132 195 184 204476 - 500 141 175 137 141 187 177501 - 525 118 158 135 90 149 160526 - 550 86 81 118 39 89 86551 - 575 65 58 113 14 43 58576 - 600 33 34 75 9 22 16601 - 625 23 15 54 1 10 10626 - 650 10 6 32 1 4 4651 - 675 14 6 24 0 2 2676 - 700 3 2 14 0 2 1701 - 725 2 0 12 0 0 0726 - 750 3 0 7 0 0 0751 - 775 1 1 1 0 0 0776 - 800 0 0 1 0 0 0801 - 825 1 0 0 0 0 0826 - 850 0 0 1 0 0 0
Fonte: Elaborada pelo autor
As Tabelas 4, 5 e 6apresentam as médias e algumas medidas de dispersão dos resultados
do makespan obtidos pelas simulações para cada RD (regra de despacho), para os menores e
maiores valores obtidos por uma regra de despacho não aleatória, e para o menor valor
encontrado pela busca aleatória nos três cenários testados. Através da análise das tabelas 4, 5
62
e 6 é reforçado o desempenho superior da regra MWKR. Em se tratando de medida de
dispersão, a regra MWKR obteve menor desvio padrão e a regra LWKR obteve maior desvio
padrão nos três cenários. O coeficiente de variação de Pearson apresentou valores bem
próximos entre as regras. O coeficiente de variação de Pearson geral das RD foi maior no
segundo cenário, que pode ser interpretado como um cenário de maior erro de previsão do
tempo de makespan em relação à média deste. As medidas de dispersão não foram calculadas
para os valores das médias da regra RANDOM devido ao fato do cálculo de tais não ser
relevante para aplicação das comparações propostas por este estudo. Em comparação com as
médias, a regra RANDOM, apesar de não ter um método lógico constante para seu
escalonamento, sua média das esperanças ainda obteve melhores resultados que a média dass
regras LWKR, SPT e LPT. A ordem crescente das médias dos makespan entre as RD é
MWKR, FIFO, SPT, LPT, LWKR para o primeiro e segundo cenário e MWKR, FIFO, LPT,
SPT, LWKR para o terceiro cenário. Apesar da troca de posição entre as regras SPT e LPT
referente ao terceiro cenário, os valores de suas médias apresentaram-se bem próximas no
terceiro cenário.
Tabela 4 - Medidas do makespan das instâncias para o cenário 1Descrição RD* RD Máx SPT LPT LWKR MWKR FIFO Média RDM BA*Média 819,1 1036,9 914,1 955,3 1014,1 821,3 877,0 905,7 812,9Amplitude 947,0 1098,0 1213,0 954,0 1080,0 947,0 942,0 926,0 953,0Desvio Padrão 147,5 165,4 165,2 161,5 168,6 147,2 147,4 144,6 150,0Coef. Pearson 18% 16% 18% 17% 17% 18% 17% 16% 18%
Fonte: Elaborado pelo autor
Tabela 5 - Medidas do makespan das instâncias para o cenário 2
Descrição RD* RD Máx SPT LPT LWKR MWKR FIFO Média RDM BA*
Média662,
6854,3 748,0 778,4 838,9 664,9 715,3 742,0 657,5
Amplitude880,
01033,0 977,0 951,0 1033,0 880,0 968,0 876,0 869,0
Desvio Padrão163,
4198,5 189,9 188,6 201,6 163,3 169,8 172,7 165,8
Coef. Pearson 25% 23% 25% 24% 24% 25% 24% 23% 0,3Fonte: Elaborado pelo autor
Tabela 6 - Medidas do makespan das instâncias para o cenário 3
Descrição RD* RD Máx SPT LPT LWKR MWKR FIFO Média RDM BA*Média 448,3 531,0 486,5 483,8 524,5 451,9 478,2 480,4 442,0Amplitude 307,0 474,0 456,0 438,0 475,0 306,0 355,0 326,0 280,0Desvio Padrão 45,7 72,8 65,6 56,9 73,5 46,6 52,7 50,2 45,4Coef. Pearson 10% 14% 13% 12% 14% 10% 11% 10% 10%
Fonte: Elaborado pelo autor
63
A figura 15 apresenta as médias do makespan das instâncias de cada regra de despacho,
dos menores valores obtidos por uma RD (RD*), dos maiores valores obtidos por uma RD e
dos menores valores encontrados pela busca aleatória, para os três cenários configurados.
MEN
OR
RDM
AIO
R RD SP
TLP
TLW
KRM
WKR
FIFO
Méd
ia R
DM BA*
MEN
OR
RDM
AIO
R RD SP
TLP
TLW
KRFI
FOM
édia
RDM BA
*
MEN
OR
RDM
AIO
R RD SP
TLP
TLW
KRM
WKR
FIFO
Méd
ia R
DM BA*
MAKESPAN - CENÁRIO 1 MAKESPAN - CENÁRIO 2 MAKESPAN - CENÁRIO 3
.000100.000200.000300.000400.000500.000600.000700.000800.000900.000
1000.0001100.000
Figura 15 – Média dos makespans para cada cenário
Fonte: Elaborado pelo autor.
A tabela 7 apresenta o desvio padrão entres as médias das RDs, para os dados do
makespans para cada cenário. Através desta tabela é demostrado que, para a previsão no
tempo de makespan de uma instância, o erro seria maior no cenário um. Mas se o erro de
previsão for baseado pela razão da média do makespan, o coeficiente de Pearson verifica um
erro de previsão maior no cenário dois. O cenário 3 que apresenta em sua configuração de
recursos um gargalo potencial, apesar de apresentar uma capacidade produtiva menor que a
do cenário 2 e maior que a do cenário1, apresenta suas medidas de dispersão
significativamente menor que a medida dos outros cenários apresentados.
Tabela 7 - Medidas de dispersão das médias dos makespans das RD não aleatórias
Descrição Cenário 1 Cenário 2 Cenário 3Desvio Padrão das médias 65,8 58,6 23,3Coeficiende de Pearson 7,2% 7,8% 4,8%
Fonte: Elaborado pelo autor
64
A tabela 8 apresentam os percentuais de variação das médias dos resultados obtidos
pelas RDs em relação às BA*, que significa o menor valor encontrado pela busca aleatória,
para cada um dos três cenários.
Verifica-se com os dados da tabela 8 que os resultados obtidos com a regra MWKR têm
variações de sua média de apenas 1,0%, 1,13% e 2,23% em relação à média dos menores
valores encontrados pela Busca Aleatória, para os três cenários respectivamente. E que a regra
LWKR tem seus valores de média 24,8%, 27,58% e 18,66% maiores que a média dos
menores valores da busca aleatória (BA*), para os três cenários respectivamente.
Tabela 8 - Percentual de variação das médias do makespan em relação a BA*
Cenários SPT LPT LWKR MWKR FIFO RDM média RD*Cenário 1 12,4% 17,5% 24,8% 1,0% 7,9% 11,4% 0,8%Cenário 2 13,77% 18,38% 27,58% 1,13% 8,78% 12,85% 0,77%Cenário 3 10,07% 9,46% 18,66% 2,23% 8,18% 8,69% 1,41%
Fonte: Elaborado pelo autor
As figuras 16, 17 e 18 apresentam a quantidade de instâncias que cada regra de despacho obteve o menor makespan e suas interseções, para o cenário 1, 2 e 3 respectivamente. Verifica-se com as figuras 16, 17 e 18 que a regra MWKR obteve o menor resultado em 906 instâncias no cenário 1. Destas, 672 foram obtidas apenas pela regra MWKR e 117 foram obtidas pela regra MWKR e a regra FIFO, nas mesmas instâncias. Observa-se que os valores dos elementos nas interseções dos conjuntos em geral, aumentam do cenário 1 ao cenário 3. As interseções apresentam a quantidade de vezes que as regras dos conjuntos que se intersecionam obtiveram o menor valor em uma mesma instância.
65
Figura 16 – Conjuntos com a quantidade de vezes que cada RD obteve o menor makespan no cenário 1
Fonte: Elaborado pelo autor
Figura 17– Conjuntos com a quantidade de vezes que cada RD obteve o menor makespan no cenário 2
Fonte: Elaborado pelo autor
66
Figura 18 – Conjuntos com a quantidade de vezes que cada RD obteve o menor makespan no cenário 3
Fonte: Elaborado pelo autor
As tabelas 9, 10 e 11 apresentam as quantidades de instâncias que cada regra de despacho obteve o menor makespan e sua percentagem para as mil instâncias testadas.
Tabela 9 - Quantidade e percentagem de instância que cada RD obteve o menor makespan no cenário 1
Descrição SPT LPT LWKR MWKR FIFOQuantidade 134 41 5 906 213Percentual 13% 4% 1% 91% 21%
Fonte: Elaborado pelo autor
Tabela 10 - Quantidade e percentagem de instância que cada RD obteve o menor makespan no cenário 2
Descrição SPT LPT LWKR MWKR FIFOQuantidade 183 67 21 885 247Percentual 18% 7% 2% 89% 25%
Fonte: Elaborado pelo autor
Tabela 11 - Quantidade e percentagem de instância que cada RD obteve o menor makespan no cenário 3
Descrição SPT LPT LWKR MWKR FIFOQuantidade 221 304 71 723 207Percentual 22% 30% 7% 72% 21%
Fonte: Elaborado pelo autor
67
Através da análise dos dados dos três cenários, é constatado que a regra MWKR foi
superior e a regra LWKR foi inferior no critério de minimizar o makespan nas instâncias
simuladas.
A tabela 12 apresenta as probabilidades empíricas de a regra RANDOM obter um valor
do makespan menor ou igual a das outras regras de despacho, nos três cenários. Com esses
dados, verifica-se que a regra MWKR é a única que apresenta probabilidades bem menores
que 50% em todos os cenários. Através desta análise, conclui-se que a regra MWKR deve
obter resultados do makespan menores que os valores do makespan da regra RANDOM, na
grande maioria das vezes. As regras SPT, LPT e LWKR apresentam probabilidades maiores
que 50% em todos os cenários simulados, logo apresentam um mal desempenho para o
critério de makespan. Essas probabilidades estão detalhadas na tabela 12.
Tabela 12 - Probabilidades empíricas do makespan da regra RDM ser menor ou igual ao makespan das RDs
Cenários SPT LPT LWKR MWKR FIFOCenário 1 56,3% 70,5% 88,9% 14,7% 42,7%Cenário 2 55,9% 65,5% 88,7% 16,3% 44,0%Cenário 3 61,3% 56,5% 88,0% 29,0% 57,0%
Fonte: Elaborado pelo autor
1.2 Análise dos resultados para o Tempo de Fluxo Médio
As tabelas 13, 14 e 15 apresentam as distribuições de frequencias dos resultados obtidos
do Tempo de Fluxo Médio nos cenários 1, 2 e 3 respectivamente, para cada regra de despacho
dentro dos intervalos de makespan selecionados.
Analisando os resultados destas tabelas verificar-se o desempenho superior das regras
SPT e LWKR e o desempenho inferior das regras LPT e MWKR em relação às outras regras
para todos os cenários testados, tendo como objetivo o menor Tempo de Fluxo médio.
Tabela 13 - Distribuição de Frequências do tempo de fluxo médio para o cenário 1
Intervalos SPT LPT LWKR MWKR FIFO RDM MÉDIA
301 - 350 15 0 20 1 3 3
351 - 400 152 32 161 14 58 52
401 - 450 307 96 337 77 167 178
68
451 - 500 274 201 294 160 241 255
501 - 550 170 223 127 197 227 243
551 - 600 61 199 42 215 175 166
601 - 650 14 129 14 151 81 64
651 - 700 4 62 4 98 23 21
701 - 750 2 37 0 43 15 11
751 - 800 1 6 1 21 5 4
801 - 850 0 9 0 10 3 2
851 - 900 0 3 0 8 1 1
901 - 950 0 3 0 2 1 0
951 - 1000 0 0 0 2 0 0
1001 - 1050 0 0 0 1 0 0
Fonte: Elaborada pelo autor
Tabela 14 - Distribuição de Frequências do tempo de fluxo médio para o cenário 2
Intervalos SPT LPT LWKR MWKR FIFO RDM MÉDIA
251 - 300 145 62 125 59 82 78
301 - 350 409 209 375 228 312 311
351 - 400 258 261 278 249 248 263
401 - 450 117 203 138 201 183 188
451 - 500 45 123 52 113 84 84
501 - 550 21 63 27 68 55 47
551 - 600 5 46 5 46 24 22
601 - 650 0 22 0 22 11 6
651 - 700 0 7 0 9 1 1
701 - 750 0 3 0 5 0 0
751 - 800 0 1 0 0 0 0
Fonte: Elaborada pelo autor
69
Tabela 15 - Distribuição de Frequências do tempo de fluxo médio para o cenário 3
Intervalos SPT LPT LWKR MWKR FIFO RDM MÉDIA221 - 230 2 0 3 1 1 0231 - 240 16 8 14 10 13 11241 - 250 36 25 39 22 34 33251 - 260 91 55 79 55 70 66261 - 270 174 108 168 123 151 140271 - 280 197 138 194 166 170 185281 - 290 167 169 195 160 191 187291 - 300 167 176 138 167 160 166301 - 310 77 130 93 118 99 94311 - 320 44 88 44 78 59 71321 - 330 14 43 20 44 29 25331 - 340 8 31 6 25 8 7341 - 350 4 13 5 12 7 7351 - 360 1 4 1 8 5 5361 - 370 2 7 1 6 0 0371 - 380 0 3 0 1 2 3381 - 390 0 1 0 3 1 0391 - 400 0 1 0 1 0 0
Fonte: Elaborada pelo autor
As Tabelas 16, 17 e 18 apresentam as médias e medidas de dispersão dos resultados do
Tempo de Fluxo médio obtidos pelas simulações e realizada as mesmas comparações
realizadas com os dados do makespan. Através dessa análise é notável a proximidade entre as
médias dos tempos de fluxo médio das regras LPT com MWKR, SPT com LWKR e FIFO
com a média das esperanças da regra RANDOM. O desempenho é superior da regra SPT e
LWKR em todos os cenários. Em se tratando de medida de dispersão a proximidade entre as
médias de cada regra se replica no desvio padrão, nos três cenários testados. O coeficiente de
variação de Pearson apresentou valores bem aproximados entre as regras. Em comparação
com as médias, médias das esperanças da regra RANDOM (RDM) obteve melhores
resultados que a regra MWKR e LPT nos três cenários e, apesar da grande proximidade entre
os valores, foi melhor que a regra FIFO nos dois primeiros cenários. A ordem crescente das
médias dos makespan entre as RD é LWKR, SPT, média RDM, FIFO, LPT e MWKR para o
primeiro cenário, SPT, LWKR, média RDM, FIFO, MWKR e LPT para o segundo cenário e
SPT, LWKR, FIFO, média RDM, MWKR e LPT para o terceiro cenário.
70
Tabela 16 - Medidas dos tempos de fluxo médio para o cenários 1
Descrição RD* RD Máx SPT LPTLWK
RMWK
RFIFO
Média RDM BA*
Média 447,4 575,0 460,7 546,9 453,5 570,1 513,9 508,7 445,6
Amplitude 434,0 664,0 433,0 582,0 443,0 675,0 600,0 516,0 417,0
Desvio Padrão 57,6 96,9 63,2 90,1 59,5 97,2 82,0 75,6 60,0
Coef. Pearson 13% 17% 14% 16% 13% 17% 16% 15% 13%
Fonte: Elaborado pelo autor
Tabela 17 - Medidas dos tempos de fluxo médio para o cenários 2
Descrição RD* RD Máx SPT LPT LWKR MWKRFIFO
Média RDM BA*
Média351,
0418,7
355,3
409,8
361,2 408,3 385,3 383,3345,
3
Amplitude313,
0491,0
330,0
499,0
327,0 482,0 423,0 410,0310,
0Desvio Padrão 53,8 89,5 56,7 85,7 58,7 87,3 74,6 70,9 52,3
Coef. Pearson 15% 21% 16% 21% 16% 21% 19% 18% 15%
Fonte: Elaborado pelo autor
Tabela 18 - Medidas dos tempos de fluxo médio para o cenários 3
Descrição RD* RD Máx SPT LPT LWKR MWKRFIFO
Média RDM BA*
Média279,
1293,6
280,8
291,2
281,7 289,9 284,7 285,0276,
1
Amplitude141,
0162,0
143,0
162,0
137,0 164,0 154,0 146,0134,
0Desvio Padrão 19,6 24,6 20,3 23,9 20,1 24,2 21,8 21,3 18,7
Coef. Pearson 7% 8% 7% 8% 7% 8% 8% 7% 7%
Fonte: Elaborado pelo autor
A figura 19 apresenta as médias do tempo de fluxo médio das instâncias de cada RD
para os três cenários configurados.
71
MEN
OR
RD
MAI
OR
RD SPT
LPT
LWKR
MW
KR
FIFO
MÉD
IA R
DM
BA*
MEN
OR
RD
MAI
OR
RD SPT
LPT
LWKR
MW
KR
FIFO
MÉD
IA R
DM
BA*
MEN
OR
RD
MAI
OR
RD SPT
LPT
LWKR
MW
KR
FIFO
MÉD
IA R
DM
BA*
TEMPO DE FLUXO MÉDIO - CENÁRIO 1 TEMPO DE FLUXO MÉDIO - CENÁRIO 2 TEMPO DE FLUXO MÉDIO - CENÁRIO 3
.000
100.000
200.000
300.000
400.000
500.000
600.000
Figura 19 – Média dos tempos de fluxo médio para cada cenário
Fonte: Elaborado pelo autor.
A tabela 19 apresenta o desvio padrão entres as médias das RDs, para os dados do
tempo de fluxo médio. Para a previsão do resultado do tempo de fluxo médio, verifica-se que
o cenário 1 deve obter um maior erro de previsão devido ao desvio padrão e coeficiente de
Pearson maior.
Tabela 19 - Medidas de dispersão das médias dos tempos de fluxo médio das RDs não aleatórias
Descrição Cenário 1 Cenário 2 Cenário 3Desvio Padrão das médias 46,1 22,8 4,2
Coeficiente de Pearson 9,1% 5,9% 1,5%Fonte: Elaborado pelo autor
Os dados da tabela 20 demonstram que os tempos de fluxo médio obtidos com a regra
LWKR têm uma variação de sua média de apenas 1,75%, 4,62% e 2,00% em relação à média
dos menores valores encontrados pela busca aleatória (BA*) nos cenários 1, 2 e 3
respectivamente. E que a regra MWKR tem um valor de sua média 27,93%, 18,25% e 4,99%
maior que a média dos melhores resultados encontrados pela busca aleatória nos cenários 1, 2
e 3 respectivamente. E para a média das esperanças da regra RANDOM (RDM) a diferença
percentual foi de 14,14%, 11,02% e 3,21% para os três cenários respectivamente, em relação
a média dos menores valores encontrado pela busca aleatória.
Tabela 20 - Percentual de variação das médias dos TFM em relação BA*
Cenários SPT LPT LWKR MWKR FIFO RDM média RD*Cenário 1 3,38% 22,72% 1,75% 27,93% 15,32% 14,14% 0,39%Cenário 2 2,89% 18,68% 4,62% 18,25% 11,59% 11,02% 1,65%Cenário 3 1,69% 5,46% 2,00% 4,99% 3,11% 3,21% 1,07%
72
Fonte: Elaborado pelo autor
As figuras 20, 21 e 22 apresentam a quantidade de instâncias que cada regra de
despacho obteve o menor tempo de fluxo médio e suas interseções, para o cenário 1, 2 e 3
respectivamente. Verifica-se com as figuras 20, 21 e 22 que a regra SPT obteve o menor
resultado em 386 instâncias no cenário 1. Destas, 363 foram obtidas apenas pela regra SPT e
23 foram obtidas pela regra SPT e a regra LWKR, nas mesmas instâncias. Observa-se que no
cenário 1 a regra MWKR não obteve o menor resultado do tempo de fluxo médio em
nenhuma das instâncias. Os valores dos elementos nas interseções dos conjuntos em geral,
aumentam do cenário 1 ao cenário 3.
Figura 20 – Conjuntos com a quantidade de vezes que cada RD obteve o menor TFM no cenário 1
Fonte: Elaborado pelo autor
73
Figura 21 – Conjuntos com a quantidade de vezes que cada RD obteve o menor TFM no cenário 1
Fonte: Elaborado pelo autor
Figura 22 – Conjuntos com a quantidade de vezes que cada RD obteve o menor TFM no cenário 1
Fonte: Elaborado pelo autor
74
As tabelas 21, 22 e 23 apresentam a quantidade de vezes que cada regra de despacho
obteve o menor valor da instância e sua percentagem para as mil instâncias, nos cenários 1, 2
e 3 respectivamente.
Tabela 21 - Quantidade e percentagem de instância que cada RD obteve o menor TFM no cenário 1
Descrição SPT LPT LWKR MWKR FIFOQuantidade 386 1 627 0 9Percentual 39% 0% 63% 0% 1%
Fonte: Elaborado pelo autor
Tabela 22 - Quantidade e percentagem de instância que cada RD obteve o menor TFM no cenário 2
Descrição SPT LPT LWKR MWKR FIFOQuantidade 619 12 376 3 29Percentual 62% 1% 38% 0% 3%
Fonte: Elaborado pelo autor
Tabela 23 - Quantidade e percentagem de instância que cada RD obteve o menor TFM no cenário 3
Descrição SPT LPT LWKR MWKR FIFOQuantidade 543 54 442 63 159Percentual 54% 5% 44% 6% 16%
Fonte: Elaborado pelo autor
A tabela 24 apresentam as probabilidades empíricas da regra RANDOM obter
um valor menor ou igual a das outras regras de despacho, nos três cenários. Com
esses dados, verifica-se que as regras LPT, MWKR e FIFO apresentam
probabilidades maiores que 50%. Através dessa análise, conclui-se que a as regras
LPT, MWKR e FIFO devem obter resultados do tempo de fluxo médio maior que os
valores do tempo de fluxo médio da regra RANDOM, na maioria das vezes.
Tabela 24 - Probabilidades empíricas do TFM da regra RDM ser menor ou igual ao TFM das RDs
Cenários SPT LPT LWKR MWKR FIFOCenário 1 6,3% 84,9% 4,6% 96,7% 58,5%Cenário 2 9,6% 85,9% 18,4% 85,6% 55,4%Cenário 3 28,6% 81,9% 35,1% 78,8% 53,7%
Fonte: Elaborado pelo autor
75
5. CONCLUSÕES
O presente estudo envolve a implementação de um algoritmo para estudo comparativo
entre heurísticas construtivas de regras de despacho, em um ambiente de produção job shop
flexível (ambiente que corresponde à realidade da maioria das organizações), através de
experimentação computacional.
Através dos dados obtidos com a experimentação computacional realizada e os testes
realizados conclui-se que o algoritmo foi implementado com êxito. A análise dos
desempenhos das regras de despacho testadas, baseado no método de avaliação descrito no
capítulo 3, proporcionou uma distinção entre as regras de despachos, onde se pode concluir as
regras que obtiveram melhor e pior desempenho de acordo com a função objetiva (makespan
ou tempo de fluxo médio) utilizada.
Avaliando o desempenho das regras de despacho nos três cenários testados sob as
condições comentadas no delineamento experimental e através do método mencionado
anteriormente, formulando como função objetiva do problema estudado a minimização do
makespan, conclui-se que a regra MWKR obteve o melhor desempenho geral em relação às
outras regras. Este resultado reforça as conclusões de Montevechi (2002). Neste mesmo
76
critério de makespan como função objetiva, a regra LWKR foi a que obteve o pior
desempenho em relação às outras regras de despacho testadas. A regra FIFO obteve seus
resultados relativamente um pouco melhor que a média da regra RANDOM. A regra SPT
obteve um desempenho relativamente inferior que o desempenho da regra RANDOM.
A avaliação do desempenho das regras de despacho, sob as condições em que se é
analisado o problema, adotando como função objetiva do problema proposto a minimização
do tempo de fluxo médio, conclui-se que a regra SPT e LWKR obtiveram os melhores
desempenhos nos três cenários testados. Dependendo do cenário ou critério de analise de
desempenho para o tempo de fluxo médio, uma dessas duas regras (SPT e LWKR) pode ter
desempenho melhor ou pior que a outra. A regra MWKR obteve o pior desempenho nos
critérios avaliados. A regra FIFO obtevedesempenho um pouco inferior ao desempenho da
regra RANDOM.
A regra LPT obteve um desempenho inferior à regra RANDOM nas duas funções
objetivos adotadas, em todos os cenários testados.
A regra RANDOM como parâmetro, foi importante para a avaliação de uma regra de
despacho de lógica constante em relação à um tipo de sequenciamento “sem regras”, ou sem
uma lógica constante. Ou seja, caso a heurística tenha um desempenho geral pior que a regra
RANDOM,é melhor não adotá-la. Claro que isso depende da função objetivo adota e dos
critérios de avaliação delineados.
As medidas de dispersão utilizadas indicam que o terceiro cenário obteve menor
dispersão das médias dos resultados das regras de despacho testadas. Isto pode implicar a
conclusão de que sistema produtivos onde há um único grande gargalo potencial, as regras de
despacho testadas obtêm diferenças de desempenhos menos elásticas que em sistemas
produtivos com capacidade de recursos mais balanceados. Ou seja, as regras de despacho
testadas podem obter desempenhos mais significativos em manufaturas com capacidade de
recursos mais balanceados.
Uma importante conclusão obtida com o estudo é que a regra de despacho utilizada na
programação de uma empresa deve ser escolhida dependendo da função objetiva que a
empresa deseja atingir, pois algumas regras despacho obtiveram desempenhos excelentes para
certa função objetiva e desempenhos bem inferiores para outra função objetiva.
77
O estudo realizado tem como limitações de implementação computacional uma série de
considerações e restrições que são citadas no capítulo dois. Outras considerações devem ser
destacadas, como os métodos de avaliação realizados, o estudo envolveu apenas duas funções
objetivas, o resultado dos desempenhos das heurísticas não foram comparados com a solução
ótima das instâncias testadas, o algoritmo implementado se comporta como um ambiente de
produção intermitente, ou seja, não envolve a programação da produção em regime dinâmico
(onde ordens de produção ou tarefas entram no sistema continuamente).
Como sugestões para trabalhos futuros:
Deve-se realizar um estudo com a implementação de um algoritmo que simule um
ambiente job shop flexível considerando e avaliando o desempenho de outras heurísticas de
sequenciamento da produção, incluindo regras de despacho mista, heurísticas de solução
exata, heurísticas evolutivas, dentre outras. A implementação de um algoritmo que se
comporte em regime dinâmico com chegada de ordens baseada em previsão estocástica,
proporcionando um ambiente de simulação mais próximo da realidade das empresas de
manufatura. Além destas, a avaliação de desempenho das heurísticas testadas também deve
envolver outras funções objetivas.
78
REFERÊNCIAS
BRUCKER, P. Scheduling Algorithms. Berlin / Heidelberg: Springer, 2001.
CONWAY, R. W; MAXWELL, W. L;MILL, L. W. Theory of Scheduling.USA: Dover,
2003.
CORRÊA, H.; GIANESI, I. G. N; e CAON, M. Planejamento, Programação e Controle da
Produção: MRP II/ERP- conceitos, uso e implantação. São Paulo: Gianesi Corrêa &
Associados: Atlas, 2001.
DAVIS, M. M; AQUILANO, N. J; CHASE, R. B. Fundamentos da Administração da
Produção. Ed: 3ª. Porto Alegre: Bookman.
HERRMMAN, J. W. Handbook of Production Scheduling.USA: Springer, 2006.
LIDDEL, M. O Pequeno Livro Azul da Programação da Produção. São Paulo: Tecmaran,
2008.
MONTEVECHI, J. A; TURRIONI, J. B; ALMEIDA, D. A; MERGULHÃO, R. C; LEAL, F.
L. Análise comparativa entre regras heurísticas de sequenciamento da produção aplicada em
job shop. Produto & Produção, vol. 6, n.2, p. 12-18, 2002.
79
MORAIS, M. F; MOCCELLIN, J. V. Métodos heurísticos construtivos para redução do
estoque em processo em ambiente de produção flow shop híbridos com tempos de setup
dependentes da sequencia. São Carlos: Gestão & Produção. vol.17 no.2, 2010.
MORTON. T. E; PENTICO. D. W. Heuristic scheduling systems: with applications to
production system and Project management. Ed.USA:John Wiley & Sons, Inc. 1993.
PACHECO, R. F; SANTORO, C. M. Proposta de classificação hierarquizada dos modelos de
solução para o problema de job shop scheduling.São Carlos:Gestão
Produção. vol.6 nº.1, 1999.
PINEDO. M. L. Planning and Scheduling in Manufacturing and Services. USA: Springer,
2005.
PINEDO. M. L. Scheduling: Theory, Algorithms and Systems. Ed. USA: Prentice-Hall,
2008.
SLACK, N;CHAMBERS,S; JOHNSTON, R. Administração da Produção. Ed. 2ª São
Paulo: Atlas, de 2007.
TUBINO. D. F. Planejamento e Controle da Produção. São Paulo: Atlas S.A, 2007.
Recommended