7/21/2019 Kazama_Elton_Koji Ho and Chang
1/111
UNIVERSIDADE DE SO PAULOESCOLA DE ENGENHARIA DE SO CARLOS
DEPARTAMENTO DE ENGENHARIA DE PRODUOTRABALHO DE CONCLUSO DE CURSO
ELTON KJI KAZAMA
HEURSTICAS CONSTRUTIVAS PARA PROGRAMAO DEOPERAES EM SISTEMAS DE PRODUO FLOWSHOP
PERMUTACIONAL: CLASSIFICAO DE SUAS FASESCONSTRUTIVAS
So Carlos2011
7/21/2019 Kazama_Elton_Koji Ho and Chang
2/111
UNIVERSIDADE DE SO PAULOESCOLA DE ENGENHARIA DE SO CARLOS
DEPARTAMENTO DE ENGENHARIA DEPRODUO
TRABALHO DE CONCLUSO DE CURSO II
ELTON KJI KAZAMAN USP 5909489
HEURSTICAS CONSTRUTIVAS PARA PROGRAMAO DEOPERAES EM SISTEMAS DE PRODUO FLOWSHOP
PERMUTACIONAL: CLASSIFICAO DE SUAS FASESCONSTRUTIVAS
Trabalho apresentado ao Departamento deEngenharia de Produo da Escola de Engenhariade So Carlos - Universidade de So Paulo, comoTrabalho de Concluso de Curso em Engenhariade Produo Mecnica.
Disciplina: SEP 1800081Trabalho deConcluso de Curso II
Orientador: Prof. Dr. Marcelo Seido Nagano
So Carlos2011
7/21/2019 Kazama_Elton_Koji Ho and Chang
3/111
Faa o que for necessrio para ser feliz.Mas no esquea que a felicidade um sentimento simples,
Voc pode encontr-la e deix-la ir embora por no percebera sua simplicidade.
(Mrio Quintana)
7/21/2019 Kazama_Elton_Koji Ho and Chang
4/111
Dedico este trabalho a minha amada, Tssia Marques.
7/21/2019 Kazama_Elton_Koji Ho and Chang
5/111
AGRADECIMENTOS
Agradeo primeiramente a Deus, por todas as oportunidades a mim concedidas, pelasade e pelas pessoas que Ele colocou em minha vida.
Gostaria de agradecer tambm ao meu orientador, professor Dr Marcelo Seido Nagano,pelo conhecimento e orientao dados que foram muito alm deste trabalho, queperdurou pelo longo e valoroso trajeto da faculdade.
Agradeo imensamente a minha famlia, e em especial aos meus pais Kiyoji e Massae,por todo o apoio que possibilitou a concretizao de um grande sonhome formar emuma renomada escola. Agradeo pelo amor, carinho e dedicao que pude contar desdeos meus primeiros segundos de vida at o presente momento.
Agradeo a todos que indiretamente contriburam para a concluso desta fase de minhavida.
E por fim, agradeo ao meu grande amor, Tssia, que esteve comigo em todos osmomentos da confeco deste trabalho, com seu suporte e carinho que foramfundamentais para a finalizao deste ciclo.
Muito obrigado!
7/21/2019 Kazama_Elton_Koji Ho and Chang
6/111
KAZAMA, E.K. Heursticas construtivas para programao de operaes emsistemas de produo flowshop permutacional: classificao de suas fasesconstrutivas. So Carlos, 2011. 99 pg. Trabalho de Concluso de Curso Escola deEngenharia de So Carlos, Universidade de So Paulo.
RESUMO
Este trabalho se prope a classificar os melhores mtodos heursticos da literatura quetratam da programao de operaes em ambiente flowshop permutacional paraminimizao da durao total da programao (makespan). Tal classificao feitasegundo a proposta de Framinan, Gupta e Leisten (2004). Inicialmente foi feita umaanlise bibliogrfica das heursticas construtivas que tratam do tema em questo.Posteriormente, procedeu-se classificao de suas fases de construo e elaboraode exemplos numricos ilustrados de cada uma. Com isso, a pesquisa busca facilitar alocalizao de heursticas simples ou compostas dentro de um quadro mais amplo,
permitindo a identificao de combinaes entre elas que possam melhorar seusresultados individuais em trabalhos futuros.
Palavras-chave: Flowshop permutacional. Programao da produo. Mtodosheursticos construtivos.Makespan.
7/21/2019 Kazama_Elton_Koji Ho and Chang
7/111
ABSTRACT
The proposal of this work is to classify the best heuristics methods from the literature
that deal with the Permutation Flowshop scheduling problem with the objective of
minimizing the total flow time of jobs (makespan) according to Framinan, Gupta andLeisten (2004) classification system. The first step done was a literature review and
analysis of the best constructive heuristics that deal with makespan minimization.
Subsequently, this work proceeded with the classification of the constructive phases for
each heuristic and the numeric illustration of the application for better understanding.
In this way, this research seeks to facilitate the choice of simple or composed heuristics
in the literature, enabling the identification of combination between them in order to
improve individual results for future research.
Key-words:Permutation flowshop. Scheduling. Constructive heuristics. Makespan.
7/21/2019 Kazama_Elton_Koji Ho and Chang
8/111
LISTA DE FIGURAS
Figura 1 - Programao da produo em funo dos prazos solicitados.Fonte: Gigante (2010) ..................................................................................................... 20
Figura 2 - Sequncia tima. Regra de Johnson .............................................................. 51
Figura 3 - Grfico de Gantt da sequncia obtida por Palmer ......................................... 53
Figura 4 - Grfico de Gantt da sequncia obtida utilizando o mtodo CDS. ................. 56
Figura 5 - Grfico de Gantt da sequncia parcial obtida J1 - J3 ..................................... 59
Figura 6 - Grfico de Gantt da sequncia parcial obtida J3 - J1 ..................................... 60
Figura 7 - Grfico de Gantt da sequncia parcial obtida J3 - J1 - J2 .............................. 60
Figura 8 - Grfico de Gantt da sequncia parcial obtida J3 - J2 - J1 .............................. 60
Figura 9 - Grfico de Gantt da sequncia parcial obtida J2 - J3 - J1 .............................. 61
Figura 10 - Grfico de Gantt da sequncia obtida J3 - J1 - J2 - J4 ................................ 61
Figura 11 - Grfico de Gantt da sequncia obtida J3 - J1 - J4 - J2 ................................. 61
Figura 12 - Grfico de Gantt da sequncia obtida J3 - J4 - J1 - J2 ................................. 62
Figura 13 - Grfico de Gantt da sequncia obtida J4 - J3 - J1 - J2 ................................. 62
Figura 14 - Grfico de Gantt da sequncia parcial obtida J5 - J2 ................................... 66
Figura 15 - Grfico de Gantt da sequncia parcial obtida J2 - J5 ................................... 66
Figura 16 - Grfico de Gantt da sequncia parcial obtida J4 - J2 - J5 ............................ 66
Figura 17 - Grfico de Gantt da sequncia parcial obtida J2 - J4 - J5 ............................ 67
Figura 18 - Grfico de Gantt da sequncia parcial obtida J2 - J5 - J4 ............................ 67
Figura 19 - Grfico de Gantt da sequncia parcial obtida J1 - J2 - J4 - J5 ..................... 68
Figura 20 - Grfico de Gantt da sequncia parcial obtida J2 - J1 - J4 - J5 ..................... 68
Figura 21 - Grfico de Gantt da sequncia parcial obtida J2 - J4 - J1 - J5 ..................... 68
Figura 22 - Grfico de Gantt da sequncia parcial obtida J2 - J4 - J5 - J1 ..................... 69
Figura 23 - Grfico de Gantt da sequncia obtida J3 - J1 - J2 - J4 - J5 .......................... 69
Figura 24 - Grfico de Gantt da sequncia obtida J1 - J3 - J2 - J4 - J5 .......................... 70
7/21/2019 Kazama_Elton_Koji Ho and Chang
9/111
Figura 25 - Grfico de Gantt da sequncia obtida J1 - J2 - J3 - J4 - J5 .......................... 70
Figura 26 - Grfico de Gantt da sequncia obtida J1 - J2 - J4 - J3 - J5 .......................... 71
Figura 27 - Grfico de Gantt da sequncia obtida J1 - J2 - J4 - J5 - J3 .......................... 71
Figura 28 - Grfico de Gantt da sequncia obtida J4 - J5 - J6 - J8 - J2 -J3 - J9 - J10 - J1 - J7 ....................................................................................................... 72
Figura 29 - Grfico de Gantt da sequncia obtida J4 - J8 - J6 - J2 - J9 -J3 - J10 - J7 - J5 - J1 ....................................................................................................... 72
Figura 30 - Grfico de Gantt da sequncia obtida J1 - J5............................................... 76
Figura 31 - Grfico de Gantt da sequncia obtida J5 - J1............................................... 76
Figura 32 - Grfico de Gantt da sequncia obtida J2 - J1 - J5 ........................................ 76
Figura 33 - Grfico de Gantt da sequncia obtida J1 - J2 - J5 ........................................ 76
Figura 34 - Grfico de Gantt da sequncia obtida J1 - J5 - J2 ........................................ 77
Figura 35 - Grfico de Gantt da sequncia obtida J4 - J1 - J2 - J5 ................................. 77
Figura 36 - Grfico de Gantt da sequncia obtida J1 - J4 - J2 - J5 ................................. 77
Figura 37 - Grfico de Gantt da sequncia obtida J1 - J2 - J4 - J5 ................................. 77
Figura 38 - Grfico de Gantt da sequncia obtida J1 - J2 - J5 - J4 ................................. 78
Figura 39 - Grfico de Gantt da sequncia obtida J3 - J4 - J1 - J2 - J5 .......................... 78
Figura 40 - Grfico de Gantt da sequncia obtida J4 - J3 - J1 - J2 - J5 .......................... 78
Figura 41 - Grfico de Gantt da sequncia obtida J4 - J1 - J3 - J2 - J5 .......................... 78
Figura 42 - Grfico de Gantt da sequncia obtida J4 - J1 - J2 - J3 - J5 .......................... 79Figura 43 - Grfico de Gantt da sequncia obtida J4 - J1 - J2 - J5 - J3 .......................... 79
Figura 44 - Grfico de Gantt da sequncia obtida J6 - J3 - J4 - J1 - J2 - J5 ................... 81
Figura 45 - Grfico de Gantt da sequncia obtida J3 - J6 - J4 - J1 - J2 - J5 ................... 81
Figura 46 - Grfico de Gantt da sequncia obtida J3 - J4 - J6 - J1 - J2 - J5 ................... 81
Figura 47 - Grfico de Gantt da sequncia obtida J3 - J4 - J1 - J6 - J2 - J5 ................... 82
Figura 48 - Grfico de Gantt da sequncia obtida J3 - J4 - J1 - J2 - J6 - J5 ................... 82
7/21/2019 Kazama_Elton_Koji Ho and Chang
10/111
Figura 49 - Grfico de Gantt da sequncia obtida J3 - J4 - J1 - J2 - J5 - J6 ................... 82
Figura 50 - Grfico de Gantt da sequncia parcial obtida J5 - J1 ................................... 84
Figura 51 - Grfico de Gantt da sequncia parcial obtida J1 - J5 ................................... 84
Figura 52 - Grfico de Gantt da sequncia parcial obtida J2 - J5 - J1 ............................ 85
Figura 53 - Grfico de Gantt da sequncia parcial obtida J5 - J2 - J1 ............................ 85
Figura 54 - Grfico de Gantt da sequncia parcial obtida J5 - J1 - J2 ............................ 85
Figura 55 - Grfico de Gantt da sequncia parcial obtida J3 - J2 - J1- J5 ...................... 86
Figura 56 - Grfico de Gantt da sequncia parcial obtida J2 - J3 - J1- J5 ..................... 86
Figura 57 - Grfico de Gantt da sequncia parcial obtida J2 - J1- J3 - J5 ..................... 86
Figura 58 - Grfico de Gantt da sequncia parcial obtida J2 - J1- J5- J3 ...................... 86
Figura 59 - Grfico de Gantt da sequncia obtida J4- J2 - J1- J5 - J3 ............................ 87
Figura 60 - Grfico de Gantt da sequncia obtida J2 - J4 - J1- J5 - J3 .......................... 88
Figura 61 - Grfico de Gantt da sequncia obtida J2 - J1- J4- J5 - J3 ........................... 88
Figura 62 - Grfico de Gantt da sequncia obtida J2 - J1- J5 - J4 - J3 .......................... 88
Figura 63 - Grfico de Gantt da sequncia obtida J2 - J1- J5 - J3 - J4 .......................... 88
Figura 64 - Grfico de Gantt da sequncia obtida pelo mtodo FRB3........................... 90
Figura 65 - Componentes doMakespan......................................................................... 90
Figura 66 - Grfico de Gantt da sequncia obtida J4 - J2 - J1 - J5 - J3 .......................... 93
Figura 67 - Grfico de Gantt da sequncia obtida J4 - J5 - J1 - J2 - J3 .......................... 95Figura 68 - Grfico de Gantt da sequncia obtida J4 - J2 - J5 - J1 - J3 .......................... 96
Figura 69 - Tempo total para executar uma programao permutacional(MakespanM())............................................................................................................ 97
Figura 70 - Demonstrao da propriedade LBY ............................................................ 98
Figura 71 - Grfico de Gantt da sequncia obtida J2J10J1J3J5J7J8J9J4J6 .................................................................................................... 102
7/21/2019 Kazama_Elton_Koji Ho and Chang
11/111
Figura 72 - Grfico de Gantt da sequncia obtida J2J8J10J7J5J9J3J1J6J4 .................................................................................................... 103
Figura 73 - Quadro Geral de Classificao das Fases Construtivas ............................. 104
7/21/2019 Kazama_Elton_Koji Ho and Chang
12/111
LISTA DE TABELAS
Tabela 1 - Tempos de processamento para a Regra de Johnson50
Tabela 2 -Tempos de processamento para a heurstica Palmer ...................................... 52
Tabela 3 - Tempos de processamento para a heurstica CDS......................................... 54
Tabela 4 - Tempo de processamento para k=1 ............................................................... 55
Tabela 5 - Tempo de processamento para k=2 ............................................................... 55
Tabela 6 - Quadro resumo at a k-sima sequncia........................................................ 56
Tabela 7 - Tempos de processamento para a heurstica NEH ........................................ 59
Tabela 8 - Tempos de processamento para o mtodo NEHKK ...................................... 65
Tabela 9 - Tempos de processamento 10 tarefas - heurstica NEHKK .......................... 72
Tabela 10 - Tempos de processamento heurstica NEH-D............................................. 75
Tabela 11 Tempos de processamento heurstica FRB3 .................................................. 83
Tabela 12 - Tempos de Processamento heurstica HC ................................................... 93
Tabela 13 - Clculo do gap d1
ij....................................................................................... 94
Tabela 14 - Clculo do gap d2i.j...................................................................................... 94
Tabela 15 - Clculo do gap d3i,j...................................................................................... 94
Tabela 16 - Gaps ajustados dRi,j...................................................................................... 95
Tabela 17 - Tempos de Processamentoheurstica N&M .......................................... 100
7/21/2019 Kazama_Elton_Koji Ho and Chang
13/111
SUMRIO
Resumo
Abstract
1 INTRODUO .................................................................................................... 14
1.1 OBJETIVOS .................................................................................................. 16
1.2 MTODO DE PESQUISA ............................................................................... 17
2
REVISO BIBLIOGRFICA ............................................................................ 18
2.1 PLANEJAMENTO E PROGRAMAO DA PRODUO................................ 18
2.2
VISO GERAL SOBRE PROGRAMAO DA PRODUO (SCHEDULING). 22
2.3 O AMBIENTE FLOWSHOP PERMUTACIONAL............................................. 25
2.4 TIPOS DE MODELOS PARA FLOWSHOP ...................................................... 26
2.4.1
Algoritmo Exato ....................................................................................... 26
2.4.2 Heursticas ................................................................................................ 26
2.5 HEURSTICAS CONSTRUTIVAS.................................................................. 28
3 CLASSIFICAES EXISTENTES DE HEURSTICAS DE FLOWSHOP
PERMUTACIONAL .................................................................................................... 38
3.1 CLASSIFICAO PROPOSTA POR FRAMINAN, GUPTA E LEISTEN (2004). 39
3.1.1 Fase I: Desenvolvimento do ndice .......................................................... 393.1.2 Fase II: construo da soluo .................................................................. 423.1.3 Fase III: melhoramento da soluo ........................................................... 443.1.4 Estratgias para cada fase de classificao das heursticas ...................... 45
4 RESULTADOS E DISCUSSO ......................................................................... 49
4.1 HEURSTICAS SIMPLES ............................................................................... 49
4.1.1 Regra de Johnson (1954) .......................................................................... 494.1.1 Palmer (1965) ........................................................................................... 524.1.2 Campbell, Dudek e Smith (1970) ............................................................. 534.1.3 Dannenbring (1977) .................................................................................. 564.1.4 Nawaz, Enscore e Ham (1983) ................................................................. 574.1.5 Moccellin (1995) ...................................................................................... 624.1.6 Kalczynski e Kamburowski (2008) .......................................................... 644.1.7 Dong, Huang e Chen(2009) ...................................................................... 734.1.8 Rad, Ruiz e Boroojerdian (2009) .............................................................. 82
4.2
HEURSTICAS COMPOSTAS ........................................................................ 90
4.2.1
Ho e Chang (1991) ................................................................................... 90
7/21/2019 Kazama_Elton_Koji Ho and Chang
14/111
4.2.2 Nagano e Moccellin (2002) ...................................................................... 964.3 QUADRO DE CLASSIFICAO .................................................................. 103
5
CONSIDERAES FINAIS ............................................................................ 105
6 REFERNCIAS BIBLIOGRFICAS ............................................................ 106
7/21/2019 Kazama_Elton_Koji Ho and Chang
15/111
14
1. INTRODUO
Os tipos de problemas de programao de operaes em mquinas vm sendocaracterizados por diversos autores como Baker (1974), French (1982), Blazewicz et al.
(1996) e Pinedo (2008). Problemas complexos podem surgir na programao de
operaes nas mquinas disponveis. As restries tecnolgicas determinadas pelo fluxo
das tarefas nas mquinas e a medida de desempenho da programao devem ser
especificadas. Maccarthy e Liu (1993) classificam os problemas de programao de
operaes do seguinte modo:
Flowshoptodas as tarefas possuem o mesmo fluxo de processamento em todasas mquinas;
Jobshop as tarefas possuem um roteiro especfico de processamento,
determinado para cada uma em particular;
Openshopno h roteiros de processamento pr-estabelecidos para as tarefas;
Flowshop permutacionalflowshop onde a ordem de processamento das
tarefas a mesma para todas as mquinas;
Mquina nicamquina nica disponvel para a execuo das tarefas; Mquinas paralelasduas ou mais mquinas disponveis que podem executar
qualquer tarefa, onde a tarefa s executada em uma mquina;
Jobshopcom mquinas mltiplas um jobshop no qual existem ki mquinas
idnticas em cada estgio i (i= 1, 2, ..., m). Em cada estgio, cada tarefa
processada apenas por uma mquina.
Flowshop com mquinas mltiplas um flowshop onde as tarefas so
processadas em mltiplos estgios seguindo a mesma ordem em cada um deles.
possvel variar a quantidade por estgio e as tarefas so processadas em
apenas uma mquina por estgio.
Os problemas de programao da produo remetem rea de otimizao
combinatria. No incio da dcada de 70, Cook (1971) elaborou a base da teoria da
complexidade computacional para problemas dessa rea considerados intratveis. Um
problema de otimizao intratvel aquele que no apresenta algoritmo em tempo
polinomial para sua soluo. Esta categoria de problemas enquadra-se na classe NP-
hard, cuja definio pode ser encontrada em Garey e Johnson (1979). A partir da dcada
7/21/2019 Kazama_Elton_Koji Ho and Chang
16/111
15
de 80, demonstrou-se que a maioria dos problemas de programao da produo
enquadram-se nesta classeNP-hard(LAWLER et al. 1993; BLAZEWICZ et al. 1996).
Com isso, os pesquisadores voltaram-se para mtodos heursticos de resoluo
desses problemas, buscando uma soluo de boa qualidade em tempo computacional
baixosituao desejvel no cenrio da produo, onde o tempo de tomada de deciso
curto, geralmente um dia ou um turno (GIGANTE, 2010).
A pesquisa aborda o problema de programao de operaes em ambiente
flowshoppermutacional, onde o nmero de solues viveis (n!), sendo n o nmero de
tarefas a serem programadas independentemente do nmero de mquinas do sistema.
Para resolver problemas de programao flowshop permutacional, as principais
abordagens na literatura incluem programao matemtica, mtodos heursticos e meta-
heursticos. Mtodos heursticos construtivos podem fornecer boas solues, uma vez
que apresentam o melhor trade-off entre a qualidade da soluo e o custo
computacional.
Desta forma, o objeto de estudo deste trabalho so os mtodos heursticos
construtivos voltados para ambientes de flowshop permutacional, com o objetivo de
reduo do tempo total de fluxo (makespan). Dentre os fatores a serem considerados
durante a programao em ambientes flowshop, a minimizao do tempo de concluso
mximo (Cmx) ou makespan so diretamente relacionados maximizao do
rendimento e da utilizao dos recursos. Portanto, no surpresa que a maioria das
pesquisas referente s ultimas dcadas se concentraram sobre a minimizao do
makespan. Um ambiente flowshopconsiste de n tarefas que devem ser processadas em
m mquinas na mesma ordem (Fm). O problema de programao em ambientes
flowshop em encontrar uma sequncia de tarefas para cada mquina de acordo com
determinada(s) medida(s) de desempenho. Alm disso, para muitas situaes, assume-se
que todas as sequncias de tarefas sero as mesmas em todas as mquinas (flowshoppermutacional -prmu).
Este um assunto relevante para o dinmico ambiente de produo atual, e tem
atrado ateno de muitos pesquisadores nos ltimos anos. De fato, houve um
crescimento exponencial de heursticas do tipo Fm/prmu/Cmax a partir da dcada de
1960. Um certo nmero de abordagens foi sugerido (SZWARC, 1971; LAGEWEG et
al, 1978; POTTS, 1980, ou CARLIER; REBAI,1996), considerando o problema do tipo
NP-hard para trs ou mais mquinas, mas a maioria dos esforos se concentraram empropor procedimentos heursticos que produzam boas solues (e no necessariamente
7/21/2019 Kazama_Elton_Koji Ho and Chang
17/111
16
timas) dentro de intervalos relativamente curtos, tais como aqueles requeridos na
tomada de decises de programao e seqenciamento.
Como o nmero de heursticas disponveis para estes tipos de problema estava
aumentando, tornou-se claro que nem todos eles eram da mesma natureza, apresentando
vrias propriedades diferentes, tais como ordem de complexidade, tempo de
processamento computacional ou memria requerida. Por exemplo, Widemer e Hertz
(1991) ou Moccellin (1995) apresentaram heursticas que requerem uma soluo inicial
(obtidas em ambos os casos por uma analogia ao problema do caixeiro viajante) seguida
de uma busca-tabu que, a princpio, poderia ser empregada como uma soluo inicial
para qualquer outra soluo heurstica.
Atualmente, portanto, existem diversas heursticas disponveis que tratam do
problema citado,Fm/prmu/Cmax, contudo, embora muitas tentativas de classificao j
tenham sido realizadas por exemplo, Gupta (1971), Pinedo (2008), ou Loureno
(1996) , no existe nenhum quadro de classificao aprofundado sobre essas
heursticas. Tal quadro fundamental para conduzir possveis pontos de pesquisas
futuras. Ao analisar estas heursticas de acordo com uma classificao comum,
possvel entender o modo como elas so construdas estruturalmente, e assim enxergar
combinaes de duas ou mais heursticas para obter uma heurstica composta que leve a
solues de melhor qualidade.
1.1OBJETIVOS
O trabalho tem como objetivo uma classificao das fases de heursticas
construtivas para o ambiente deflowshoppermutacional. A heurstica pode ser definida
como um mtodo desenvolvido atravs de um modelo cognitivo, usualmente atravs de
regras baseadas na experincia dos desenvolvedores. Heursticas construtivas so assimdenominadas por construrem a soluo de um problema de maneira incremental, a
partir do zero.
Devido ao fato de os problemas de flowshoppermutacional com n-tarefas e m-
mquinas pertencerem aos problemas NP-hard, (Johnson e Montgomery, 1974), os
requisitos computacionais para obter solues timas, que aumentam exponencialmente
medida que aumenta o tamanho do problema, tornam-se importantes na resoluo de
problemas de flowshop permutacional. Heursticas construtivas foram desenvolvidassob esta situao. Embora a meta-heurstica melhore muito a qualidade das solues, os
7/21/2019 Kazama_Elton_Koji Ho and Chang
18/111
17
requisitos computacionais e a complexidade de implementao tambm aumentam, que
uma desvantagem quando se aplica na prtica. Encontrar uma heurstica construtiva
eficaz e computacionalmente vivel traz contribuies tanto para a prtica quanto para a
literatura, pois os resultados podem ser usados como inicializao para as meta-
heursticas, como por exemplo, para o algoritmo gentico hbrido, e Busca Tabu
(REEVES, 1993), o Algoritmo Gentico (CHEN et al, 1995), etc.
Inicialmente, portanto, busca-se identificar e analisar os principais mtodos
heursticos relacionados ao tema, para, posteriormente, estabelecer uma classificao de
suas fases. Com isso, procura-se disponibilizar uma sntese das ferramentas heursticas
utilizadas para otimizar a programao das operaes em Flowshop permutacional,
fornecendo um panorama geral sobre o que existe na rea e facilitando a combinao
destas heursticas para a resoluo de problemas.
1.2MTODO DE PESQUISA
O trabalho envolveu pesquisa bibliogrfica sobre o tema abordado e
levantamentos e sistematizao de informaes, obtidas atravs de pesquisa em teses,
artigos e livros relacionados ao tema, e em ferramentas disponveis no meio eletrnico.
A pesquisa bibliogrfica abrangeu, alm do material especfico sobre os mtodos
heursticos a serem estudados, materiais sobre programao da produo e sobre
resoluo de problemas de programao com flowshop permutacional. Esse
instrumental terico forneceu subsdios s investigaes dos dados especficos sobre o
objeto de estudo, permitindo balizar e analisar as informaes obtidas.
A princpio, foi estabelecido um processo de leitura de modo a identificar os
principais mtodos heursticos construtivos voltados ao problema de programao de
Flowshoppermutacional. A segunda etapa desse processo consistiu em estabelecer uma
metodologia de classificao das fases necessrias para a aplicao dos mtodos. Feita a
classificao dos principais mtodos heursticos estudados a partir da metodologia
sistematizada por Framinan, Gupta e Leisten (2004), elaborou-se um quadro-resumo das
fases de cada um, permitindo melhor visualizao e comparao dos dados. A ilustrao
das heursticas analisadas foi feita atravs do software LEKIN (Flexible Job-Shop
Scheduling System), desenvolvido pela Stern School of Business(NYU).
7/21/2019 Kazama_Elton_Koji Ho and Chang
19/111
18
2 REVISO BIBLIOGRFICA
2.1PLANEJAMENTO E PROGRAMAO DA PRODUO
A funo da atividade de Planejamento e Controle da Produo (PCP) garantir,
de forma correta e eficaz, a execuo, controle e planejamento de todo o processo
produtivo. Fala-se em processo produtivo porque, segundo Gigante (2010), a produo
de bens ou servios pode ser considerada como um conjunto de processos, ou um
processo nico, no qual ocorre a transformao de insumos em produtos e servios. O
objetivo final do PCP atingir tempo e quantidade de produo adequados, alm de
proporcionar produtos de qualidade aos clientes.
Para um melhor entendimento sobre o PCP, importante diferenciarmos
planejamento e controle, uma vez que as atividades envolvidas nessa disciplina
relacionam-se gesto da capacidade de execuo de uma certa operao com as
demandas que ela exige (SLACK, 2002). De acordo com Gigante (2010), planejamento
o detalhamento do que se intenciona fazer em um determinado perodo de tempo. J
controle o processo de ajustes necessrios para que operaes e atividades sejam feitas
de acordo com o estabelecido.
Slack (2002) destaca ainda que, uma vez que planejamento e controle a tcnica
de conciliar demanda e fornecimento, a tomada de decises para planejar e controlar
uma operao produtiva depender da natureza da demanda e do fornecimento da
operao em questo.
O gerenciamento de processos produtivos feito pelo PCP deve levar em conta as
restries tecnolgicas do ambiente e ajustar a produo ao tempo de execuo das
atividades e aos volumes de demanda, suprindo suas necessidades. E para conciliar
volume e tempo so necessrias trs atividades integradas, porm de carter distinto:
carregamento, sequncia e programao (GIGANTE, 2010).
Carregamento pode ser definido como a quantidade de trabalho colocada em
determinado centro de trabalho. Tal quantidade pode ser fixa para um certo perodo de
tempo, ou contnua, com variao da quantidade de trabalho de acordo com a sada das
atividades acabadas.
Sequenciamento o ordenamento de execuo das operaes. Trata-se de uma
atividade bastante complexa. Pode ser exemplificada da seguinte forma: uma mquinapossui o sequenciamento de cinco atividades independentes, sendo 5! sequncias
7/21/2019 Kazama_Elton_Koji Ho and Chang
20/111
19
distintas para a execuo dessas atividades ou 120 solues possveis de ordenamento.
Em um caso que apresente dez atividades, o nmero de alternativas cresce para
3.268.800problema ainda pequeno em comparao ao que ocorre em ambientes reais
(GIGANTE, 2010).
Por fim, programao o conjunto de atividades que definem os volumes de cada
produto, datas de incio e trmino de produo e os equipamentos usados para sua
fabricao. Seu objetivo, segundo Rodammer e White Jr. (1981), encontrar um modo
adequado de distribuir e sequenciar o uso de recursos compartilhados de forma que
atenda s restries da produo e minimize os custos.
Segundo Nambiar et al (1981), a programao da produo est no nvel mais
baixo na hierarquia de um sistema de planejamento da produo. Nessa hierarquia, o
primeiro nvel determinado pelo programa mestre, elaborado com base nas decises
agregadas sobre produo e capacidade. Uma vez fixado o programa mestre de
produo, temos o segundo nvel da hierarquia, onde se determinam as quantidades a
serem produzidas (ou compradas) dos diferentes componentes. O terceiro e ltimo nvel
encontra-se aps a definio das quantidades e datas de entrega dos diferentes
componentes, e compreende os programas de produo e as alocaes dos recursos
necessrios. Para o autor, portanto, o objetivo de uma programao atribuir e
seqenciar a utilizao desses recursos compartilhados, minimizando os custos e
atendendo s restries de produo.
De modo geral, a programao da produo envolve um conjunto de tarefas a
serem processadas, e cada tarefa, por sua vez, compreende um conjunto de operaes
distintas. As operaes requerem mquinas, recursos humanos e recursos materiais e
devem ser executadas de acordo com uma sequncia tecnolgica vivel. A programao
influenciada, portanto, por diversos fatores: prioridade de tarefas, prazos de entrega,
restries de custos, nveis de produo, restries quanto aos tamanhos dos lotes,disponibilidade e capacidade de mquinas, precedncias de operaes, requerimentos de
recursos e disponibilidade de recursos. O programa gerado seleciona uma seqncia
adequada de operaes que resultar na concluso de todas as tarefas do conjunto no
menor tempo possvel.
No nvel da programao de produo, as decises tomadas no apresentam
importncia de forma individual. O conjunto de decises tomadas em um perodo de
tempo, contudo, possuem enorme influncia nos planos elaborados nos nveissuperiores da hierarquia, podendo comprometer o desempenho de um dado ambiente de
7/21/2019 Kazama_Elton_Koji Ho and Chang
21/111
20
programao. Uma programao de baixa qualidade pode ocasionar desperdcio de
recursos e materiais, atrasos nas datas de entregas, baixa qualidade de produtos, baixa
lucratividade, entre outros.
Para Graves (1981), o problema de programao da produo abrange um
conjunto de tarefas a serem realizadas e os critrios de realizao, que podem
determinar, por exemplo, um trmino adiantado ou prolongado dessas tarefas.
A programao da produo e os estoques acomodam a demanda pelos produtos.
Entretanto, h variveis controlveis externas, como o nvel de estoque e carga-
mquina, que influenciam o desempenho do sistema produtivo. Assim, tais fatores
tambm devem ser considerados na programao da produo, bem como os fatores
internos, ambos levando a estratgias distintas.
Quanto orientao externa, a programao busca atender a influncia da
demanda, representada pelas solicitaes dos clientes em quantidade e prazo. J a
orientao externa, ligada produtividade, envolve o uso eficiente dos recursos.
A programao da produo orientada aos fatores externos abrange a
considerao de prazos, isto , estabelecer os tempos de execuo ou durao, bem
como as tolerncias de fabricao, a partir de um prazo de entrega ou data de trmino.
Deste modo so obtidas as datas de incio de fabricao ou execuo das atividades.
Prazos podem ser estabelecidos de diversas maneiras, de acordo com os aspectos
especficos de cada processo produtivo. Abaixo, tem-se um exemplo:
Figura 1 - Programao da produo em funo dos prazos solicitados. Fonte: Gigante (2010)
7/21/2019 Kazama_Elton_Koji Ho and Chang
22/111
21
A situao ilustrada em (a) aplica-se aos casos onde j esto disponveis as
matrias-primas a serem usadas na fabricao. O prazo para incio da funo obtido
subtraindo-se o tempo de execuo da funo do prazo solicitado pelo cliente, ou do
prazo dado pela reposio do estoque. O tempo de execuo da funo pode
complementar tempos de espera caso haja indisponibilidade de equipamentos devido
fabricao de demais produtos da empresa, entre outros.
Na situao (b), onde no h disponibilidade de matria-prima (ou outros
recursos), ocorre um atraso no pedido do cliente, que s processado aps a obteno
dos recursos. Assim, alm de coordenar a programao, preciso coordenar tambm a
obteno dos recursos necessrios.
Pode ocorrer ainda uma terceira situao, na qual o pedido do cliente marca o
incio da funo. Nesse caso, o prazo de entrega ou trmino dado pela durao da
funo ou atividade. Recebido o pedido do cliente, o incio da funo depende apenas
da disponibilidade de recursos.
A programao da produo voltada aos fatores internos procura uma utilizao
eficiente da capacidade, como por exemplo, a mxima utilizao das mquinas, atravs
da coordenao das atividades simultneas que ocorrem internamente.
Assim, a programao da produo orientada externamente busca atender critrios
de servios ao cliente, enquanto a orientada internamente busca atingir a produtividade
dos recursos. Apesar do fato de que a estratgia de programao da produo dependa
da prtica de cada empresa, alguns objetivos bsicos so preservados: entrega dos
produtos fabricados nas datas compromissadas ou estabelecidas; distribuio da carga
de trabalho para obter mxima utilizao dos recursos; garantia de disponibilidade da
matria-prima e componentes quando solicitados pela fabricao; impedimento de
grande concentrao de trabalho em poucas mquinas; previso da ociosidade da
capacidade produtiva; estabelecimento de sequncias de produo que minimizem otempo de equipamento sem trabalho.
Os problemas de capacidade e de estoques esto fortemente ligados aos problemas
de programao da produo, tanto ligados aos aspectos externos como aos internos.
A programao se torna mais complexa nas situaes em que no h estoques de
produtos acabados e as decises de programao so influenciadas pela demanda
imposta pelos clientes, pois o grau de competitividade das tarefas baixo, o que
demanda um alto controle na programao.
7/21/2019 Kazama_Elton_Koji Ho and Chang
23/111
22
J nas situaes em que h estoque, a programao deve analisar trs estgios do
sistema: o prazo para o produto final entrar no estoque, o incio da fabricao do
produto e a disponibilidade de matrias-primas para a fabricao. Apesar de envolver
mais estgios e ser tecnicamente mais complexa, nesta situao a determinao dos
prazos mais simples porque se volta para a demanda do estoque, e no para o cliente
(GIGANTE, 2010).
De modo geral, um nvel alto de demanda est ligado padronizao de produtos
e servios, o que acarreta uma repetitividade da funo e a existncia de recursos com
finalidades especficas. Um nvel baixo de demanda, por sua vez, pode estar associado
variedade de produtos e servios no padronizados, que gera baixa repetitividade das
tarefas e exige mquinas e equipamentos de uso geral.
A eficincia da programao da produo pode ser avaliada por parmetros
ligados a aspectos internos e externos. So parmetros de orientao interna: nvel de
produtos acabados ou trabalhos em andamento/progresso; porcentagem de faltas nos
estoques; e tempo parado por outros motivos (quebras, falta de uso, etc). So
parmetros de orientao externa: porcentagem das ordens entregues antes do prazo ou
no prazo e tempo de espera do cliente. E h, ainda, parmetros de origem externa e
interna: porcentagem de utilizao dos recursos, quantidade de clientes perdidos e
tempo de preparao das mquinas.
Tcnicas e mtodos com finalidades especficas foram desenvolvidos para
executar a programao da produo de acordo com seus objetivos, tanto para atender
aos aspectos externos como para cumprir orientaes internas. Entre os mais difundidos
esto os Grficos de Gantt, o Diagrama de Montagem, as Tcnicas de Redes (CPM e
PERT) e diversos mtodos heursticos que determinam o melhor seqenciamento da
produo.
2.2VISO GERAL SOBRE PROGRAMAO DA PRODUO(SCHEDULING)
Um sistema de scheduling, ou programao da produo, segundo Morton e
Pentico (1993), se refere a procedimentos dinmicos para tomar decises relacionando
atividades de uma tarefa ou projeto com os recursos que as executam, de modo que os
objetivos sejam atingidos, ou seja, as atividades sejam executadas pontualmente e comalta qualidade e, simultaneamente, o volume de produo seja maximizado e os custos
7/21/2019 Kazama_Elton_Koji Ho and Chang
24/111
23
operacionais diretos minimizados. J Sipper e Bulfin Jr. (1997) definem scheduling
como o processo de organizar, escolher e temporizar o uso de recursos na realizao de
todas as atividades necessrias para produzir sadas nos momentos necessrios. O
schedulingdeve satisfazer um grande nmero de restries de tempo e de relaes entre
as atividades e os recursos. Caso os recursos sejam ilimitados, um problema de
scheduling no existe (FERNANDES; FILHO, 2010).
Considerando uma mquina que processe 32 tarefas, o nmero de sequncias
possveis seria de 32! = 2,5x1035, nmero excepcionalmente grande (SIPPER; BULFIN
JR, 1997). Utilizando um computador sofisticado para avaliar todas as alternativas, este
processo levaria centenas de anos. Portanto, verifica-se a necessidade de algoritmos
para reduzir este universo de possibilidades de modo a obter as melhores sequncias.
De modo geral, podemos afirmar que a programao da produo ouscheduling
um processo de deciso onde o objetivo a otimizao da produo e onde o uso dos
recursos est sujeito a uma srie de restries. Portanto, esta programao diz respeito
alocao de recursos limitados para tarefas ao longo do tempo. As formas de recursos e
tarefas podem ser diferentes, dada a variedade de indstrias e seus objetivos.
Em um sistema de manufatura, os pedidos devem ser liberados e traduzidos em
tarefas, com suas respectivas datas de entregas. Tais tarefas devem ser processadas por
mquinas em centros de trabalhos em uma determinada ordem ou sequncia, e podem
ter que esperar ou adiantar seu processamento caso as mquinas estejam ocupadas ou
quando tarefas de alta prioridade precisam ser processadas antecipadamente. O
planejamento detalhado das tarefas a serem executadas em um sistema de produo
necessrio para manter a eficincia e o controle das operaes. A programao um
importante processo de tomada de deciso existente na maioria dos sistemas de
manufatura e produo, em ambientes de processamento de informaes, de transporte e
distribuio e outros tipos de indstrias de servios. A programao da produo temdiferentes focos, desde o ponto de vista tcnico at o da implementao. Na academia,
os trabalhos cientficos do destaque para problemas de programao so semelhantes
aos modelos de otimizao combinatria e modelagem estocstica. As dificuldades que
ocorrem durante a implementao na indstria, contudo, so de um tipo diferente e
esto relacionados com a modelagem dos problemas de programao do mundo real e
recuperao da informao (PINEDO, 2008).
De fato, a programao da produo tem sido objeto de estudo altamenteexplorado pelas comunidades acadmicas nas ltimas dcadas. Trata-se de uma das
7/21/2019 Kazama_Elton_Koji Ho and Chang
25/111
24
reas com mais publicaes em conferncias e revistas especializadas. No entanto,
tambm uma das reas onde h uma enorme distncia entre a teoria e o que se consegue
aplicar na prtica industrial. Embora considerada relativamente simples em termos de
formulao e visualizao do que requerido, esta classe de problemas apresenta alto
grau de dificuldade para obter solues timas at mesmo nas situaes mais comuns. A
maioria dos problemas reais de programao da produo por natureza muito
complexa e de difcil resoluo, em termos da soluo tima. Tal constatao no
implica dizer que os problemas de programao da produo do cotidiano das empresas
no sejam resolvidos. O que se quer dizer que as solues encontradas por elas no
so as solues timas, mas sim solues semi-timas que resolvem os problemas com
a mxima eficincia possvel.
Existem duas maneiras de descrever os problemas de programao. Conway et al.
(1967) introduziram uma notao de parmetros A/B/C/D, em que A representa o
nmero de tarefas, B o nmero de mquinas, C o ambiente da mquina, e D a funo
objetivo. Graham et al. (1979) introduziram uma notao de trs parmetros //,
amplamente utilizada na literatura atual. O campo descreve o ambiente da mquina e
contm uma nica entrada. O campo fornece detalhes das caractersticas de
processamento e as restries, e pode no conter entradas, uma entrada nica, ou
mltiplas entradas. O campo contm o objetivo a ser minimizado e, geralmente,
contm uma nica entrada.
Existem cinco principais categorias de ambiente de mquina em problemas de
programao: mquina nica, mquinas paralelas, flowshop, jobshop e openshop.
Alguns deles podem ser quebrados em subcategorias. O caso de uma nica mquina
apresentado no campo =1 e o mais simples de todos os ambientes de mquinas
possvel. Pmdescreve o ambiente de mmquinas idnticas paralelas. A tarefajrequer
uma nica operao e pode ser processada em qualquer uma das mmquinas ou emqualquer uma pertencente a um dado subconjunto. Qm descreve o ambiente de
mquinas paralelas uniformes, em que mmquinas em paralelo possuem velocidades
diferentes, mas a relao de velocidade conhecida. O ambiente de mquinas paralelas
generalizado usando as letras Rm para representar mquinas paralelas no
relacionadas, no qual as velocidades das mquinas so diferentes e a relao das
velocidades so desconhecidas.
Os exemplos depossveis dados de entrada no campo so: data de liberao (rj),os tempos de set up dependentes da seqncia (sjk), interrupes (prmp), restries de
7/21/2019 Kazama_Elton_Koji Ho and Chang
26/111
25
precedncia (prec), avarias (brkdwn), restries de elegibilidade de mquina (Mj),
permutaes (prmu), bloqueio (block), sem-espera (nwt) e recirculao (recrc).
Exemplos de possveis dados de entrada no campo so: data de trmino (Ci j),
tempo de fluxo (Fj), atraso da tarefa (Lj), tempo de atraso da tarefa (Tj), makespano
tempo para completar todas as tarefas (Cmax), atraso mximo (Lmax), atraso ponderado
( ), tempo de trmino total ponderado ( ), nmero ponderado detarefas atrasadas ( ), etc. O objetivo determinado pela exigncia da operaoe gesto.
O ambiente Fluxoshop (Fm) descreve o ambiente em que mmquinas esto em
srie. Cada tarefa tem que ser processada em cada uma das m mquinas. Todas as
tarefas tm as mesmas sequncias. Aps a concluso em uma mquina, uma tarefa
precisa esperar na fila caso a prxima mquina esteja ocupada. Se todas as filas so
assumidas para operar sob o regime first in first out(FIFO), oflowshop conhecido
como F lowshop permutacional. OFlowshopflexvel uma generalizao do ambiente
deflowshope de mquinas paralelas, e denotado por FFs.
2.3O AMBIENTE FLOWSHOP PERMUTACIONAL
Em muitas linhas de fabricao e montagem, vrias operaes necessitam serrealizadas em todas as tarefas. Muitas vezes, essas operaes tm de ser realizadas em
todas as tarefas na mesma ordem, o que implica que essas tarefas devem seguir a mesma
sequncia. Assume-se que as mquinas esto instaladas em srie e o ambiente referido
oflowshop. Em um problema de programao flowshoppermutacional, h um conjunto
de n tarefas para serem processadas em um conjunto de m mquinas, o ambiente
assumido dispes de m mquinas instaladas em srie e cada tarefa processada
exatamente na mesma ordem. O objetivo encontrar uma sequncia, entre as n!
possveis, para o processamento das tarefas nas mquinas, de modo que alguma funo-
objetivo previamente estabelecida seja minimizada. Neste trabalho, o objetivo a
minimizao do tempo total da programao ou makespan, que o critrio mais comum
citado na literatura (RUIZ e MAROTO, 2005).
Os tempos de processamento necessrios para as tarefas nas mquinas so
representados por tij, onde i = 1, ... n, e j = 1, ..., m. Os tempos de processamento so
fixos, conhecidos previamente, e no negativos. Baker (1974) lista vrias premissas que
so comumente feitas sobre esse problema:
7/21/2019 Kazama_Elton_Koji Ho and Chang
27/111
26
Cada tarefa i pode ser processada no mximo em uma mquinajpor vez;
Cada mquina m pode processar apenas uma tarefa ipor vez;
Aps o incio da operao, no so permitidas as interrupes;
Cada operao tem no mximo uma precedente e uma sucessora, isto , possuemfluxo unidirecional;
os tempos deset-upso insignificantes e portanto podem ser ignorados;
as mquinas esto continuamente disponveis;
estoque em processo permitido, entre outros.
2.4TIPOS DE MODELOS PARA FLOWSHOP
2.4.1 Algoritmo Exato
As primeiras pesquisas sobre flowshop eram extremamente tericas. A maioria
dos pesquisadores considerava as abordagens de programao matemtica para os
problemas de programaoflowshop, tais como a programao linear inteira (MANNE,
1960). Solues branch and bound (LOMNICK 1965; MCMAHON E BURTON,
1967) foram desenvolvidas na dcada de 1960 para obter solues timas. Entretanto,
estas tcnicas funcionam bem apenas em casos de pequenas dimenses. medida que o
tamanho do problema aumenta, elas se tornam ineficientes.
Johnson (1954), por exemplo, props um algoritmo de otimizao para o
problema de flowshop com duas mquinas e tarefas, e mostrou que a mesma
permutao de tarefas pode ser aplicada em ambas as mquinas. Seu mtodo provou ser
ideal quando o nmero de mquinas igual a dois ou trs, sob determinadas condies,
mas ele se torna ineficiente quando o nmero de mquinas superior a trs (JOHNSON,
1954).
2.4.2 Heursticas
Uma heurstica um procedimento desenvolvido atravs de um modelo cognitivo,
usualmente atravs de regras baseadas na experincia dos desenvolvedores. Ao
contrrio dos mtodos exatos, que buscam encontrar uma forma algortmica de achar
uma soluo tima atravs da combinao ou busca de todas as solues possveis, as
heursticas normalmente tendem a apresentar um certo grau de conhecimento acerca do
7/21/2019 Kazama_Elton_Koji Ho and Chang
28/111
27
comportamento do problema, gerando um nmero muito menor de solues. Diante da
dificuldade em encontrar uma soluo tima para o problema de flowshop, mtodos
heursticos englobam estratgias, procedimentos e mtodos aproximativos com o
objetivo de encontrar uma boa soluo, mesmo que no seja a ideal, em um tempo
computacional razovel (FERNANDES; FILHO, 2010).
Quanto forma de obteno da soluo, a literatura classifica os mtodos
heursticos em construtivos e melhorativos.
Os mtodos construtivos consistem em construir a soluo de um problema a
partir do zero, de forma incremental, e que ser o resultado final do problema
(PALMER, 1965; CAMPBELL et al., 1970; DANNENBRING, 1977; KOULAMAS,
1998; DAVOUD POUR, 2001; NAGANO e MOCCELLIN, 2002; KALCZYNSKI e
KAMBUROWSKI, 2007; DONG; HUANG e CHENG, 2008; KALCZYNSKI e
KAMBUROWSKI, 2008; RAD; RUIZ e BOROOJERDIAN, 2009). Este tipo de
mtodo gera uma soluo factvel para o problema das seguintes maneiras:
A partir de gerao sucessiva de sequncias parciais das tarefas (subseqncias)
at a obteno de uma sequncia completa, respeitando algum critrio para
realizar a insero das tarefas, como citam Nagano e Moccellin (2002);
Kalczynski e Kamburowski (2007); Dong; Huang e Chen (2008); Rad; Ruiz eBoroojerdian (2009);
A partir da ordenao das tarefas segundo ndices de prioridade calculados em
funo dos tempos de processamento das tarefas, por exemplo, atravs da
heurstica de Palmer (1965);
Ou ainda, dado um conjunto de sequncia, escolhe-se a melhor sequncia
utilizando-se tambm ndices de prioridades associados a cada tarefa, como
citado atravs de Campbell, Dudek e Smith (1970) e Hundal e Rajgopal (1988).
Heursticas melhorativas partem de uma soluo factvel e procuram uma soluo
melhor dentro de uma vizinhana, definida geralmente por meio de permutaes de
posies das tarefas na sequncia. Uma heurstica clssica melhorativa pra quando no
existe nenhum vizinho melhor que a soluo corrente (timo local), dado uma medida
de desempenho adotada. Dannenbring (1977) props duas heursticas melhorativas
simples, oRapid Acesscom Close Order Search (RACS) eRapid AccesscomExtensive
Search(RAES), que comeam a partir de uma soluo de programao construda pela
7/21/2019 Kazama_Elton_Koji Ho and Chang
29/111
28
Rapid Access(RA). Rad, Ruiz e Boroojerdian (2009) modificaram a heurstica NEH ao
adicionar a abordagem da busca local aps o procedimento principal. Pode-se citar
ainda Taillard (1990); Widmer e Hertz (1991) e Nowicki e Smutnicki (1996). Rajedran
e Ziegler (2004) apresentaram dois novos mtodos baseados noant-colony optimization
(ACO). Estas heursticas melhorativas utilizam tcnicas de busca local para melhorar a
qualidade da soluo gerada.
Apesar da vasta gama de estudos na rea de programao da produo em
ambiente flowshop, muitos dos mtodos desenvolvidos so considerados complexos e
requerem grande esforo computacional. Portanto, a busca de mtodos heursticos mais
simples, eficazes e de mais fcil implementao ainda permanecem como objetos de
estudos visando melhoria contnua no ambiente produtivo.
2.5HEURSTICAS CONSTRUTIVAS
A seguir so apresentadas as principais heursticas construtivas que tratam dos
problemas deflowshoppermutacional com critrio de minimizao da durao total da
programao (makespan). Para tal, adotaremos as seguintes notaes:
Seja J={J1, J2, J3, ..., Jj, ..., Jn} um conjunto de ntarefas a serem processadas em
mmquinas distintas na mesma seqncia de processamento.
pij o tempo de processamento de tarefa Jjna mquina i, isto pij (i=1, 2, 3, ...,
m; j=1, 2, 3... n). Vale lembrar que mesmo que todas as tarefas obedecem
mesma seqncia, uma determinada tarefa x pode no ser processada em uma
determinada mquinay, e portanto,pyx=0.
Para problemas de n tarefas que sejam processadas em apenas 2 mquinas,
Johnson (1954) desenvolveu um algoritmo que fornece a soluo tima de
sequenciamento em ambientes flowshop com objetivo de minimizao do makespan.
Para problemas com n tarefas e mmquinas, encontrar uma soluo tima dentro de um
tempo computacional finito ainda no foi possvel. Isto se deve ao fato de que a funo
de complexidade do tempo computacional de problemas de flowtime de natureza
exponencial. E ento para estes casos que se faz necessrio o uso de heursticas para a
resoluo destes problemas com objetivo de alcanar solues boas com esforo
computacional aceitvel.
Campbell, Dudek, e Smith (1970) desenvolveram uma heurstica que conhecida
7/21/2019 Kazama_Elton_Koji Ho and Chang
30/111
29
como CDS. Trata-se de uma heurstica multi-estgio que constri m-1 sequncias,
agrupa as m mquinas originais em duas mquinas artificiais e resolve o problema
gerado de duas mquinas utilizando repetidamente a regra de Johnson. Os tempos de
processamento da tarefa j na mquina i (i=1 ou 2) so gerados iterativamente a partir
dos tempos de processamentos originais nos m-1 estgios.
No estgio 1: e Em outras palavras, a Regra de Johnson aplicada considerando apenas a
primeira e a ltima mquinas, e as mquinas intermedirias so inicialmente ignoradas.
No estgio 2:
e Ou seja, a Regra de Johnson aplicada soma dos tempos de processamento da
primeira com a segunda mquinas e da penltima com a ltima mquinas. Para o
estgio t=m-1, os tempos de processamento das mquinas artificiais 1 e 2 sero dadas
por:
Estgio t:
e
Para cada estgio t (t = 1, 2, ..., m-1), obtm-se uma sequncia de tarefas por meio
da regra de Johnson. Com esta sequncia, calcula-se o makespan com os tempos de
processamento do problema original. Aps m-1 estgios, a sequncia que fornecer o
menor makespan escolhida como a melhor soluo para o problema.
Palmer (1965) desenvolveu uma heurstica que atribui um ndice para cada tarefa,
o chamado slope index, e em seguida, organiza a sequncia de acordo com o ndice
atribudo a cada tarefa. Este ndice calculado de modo a organizar as tarefas em ordemno-crescente de seus tempos de processamento. As tarefas que possuem maiores
7/21/2019 Kazama_Elton_Koji Ho and Chang
31/111
30
tempos de processamento recebem maiores ndices, e ento, cada tarefa organizada de
modo que aquelas com os maiores slope ndex (Sj) ocupam as primeiras posies na
sequncia de execuo. Tal ndice Sjpara a tarefa Jj dado por:
Gupta props uma modificao do slope indexde Palmer que explorava algumas
semelhanas entre os problemas de programao e triagem (Gupta, 1971). Na verdade,
Gupta reconheceu que o algoritmo de Johnson na verdade um mtodo de ordenao detarefas em problemas com 2 ou 3 mquinas, a partir da atribuio de um ndice para
cada tarefa, seqenciando-as de acordo com a ordem crescente de tais ndices. Gupta
ento generalizou o problema mas caso em que m>= 4 mquinas. A seguir
apresentado a forma como Gupta determina os ndices pra a tarefa Jj.
( )
onde:
Hundal e Rajgopal (1988) desenvolveram uma extenso da heurstica de Palmer,
uma vez que a Heurstica de Palmer no considera a mquina (m+1)/2 quando m
impar. Este fato pode afetar a qualidade da soluo. Desta forma, Hundal e Rajgopalpropuseram outros dois mtodos para o clculo dos ndices:
A partir dos ndices obtidos por este mtodo, duas novas sequencias podem ser
encontradas. Seleciona-se a sequencia que apresentar o menor makespan.
7/21/2019 Kazama_Elton_Koji Ho and Chang
32/111
31
Moccellin (1995) props uma heurstica denominada FSHOPH (flowshop
heuristic), semelhante heurstica SPIRIT proposta por Widmer e Hertz (1991). A
heurstica FSHOPH baseia-se no problema do Caixeiro Viajante, porm o conceito de
distncia percorrida entre duas tarefas muito diferente nesta heurstica se comparado
SPIRIT.
O clculo da durao total da programao no problema de Programao de
Operaes FlowshopPermutacional de uma sequncia S com ntarefas e mmquinas
dada por
Onde:
: tempo de processamento da j-sima tarefa na ltima mquina da sequnciaS.
: tempo transcorrido entre o trmino da tarefa que ocupa j-sima posio nasequncia S e o incio da (j+1)-sima tarefa, na ltima mquina.
, representa uma tarefa fictcia, com tempo de processamento nulo e que
ocupa sempre a primeira posio entre as tarefas da sequncia S.Se considerarmos como a distncia entre as j-sima e a (j+1)-sima
posies de S, ento o problema de flowshop permutacional passar a ser tratado como
um tpico problema do Caixeiro Viajante. A sequncia Sx que minimiza o makespan
M(S) dado pela rota mais curta que abrange todas a ntarefas.
Na heurstica FSHOPH, a distncia entre duas tarefas baseada em uma
propriedade apresentada por Moccellin (1993) que ocorre em problemas de flowshop
permutacional:
Considere duas tarefas arbitrrias ue vem um conjunto de ntarefas. Para cada
sequncia S com as tarefa uevposicionados respectivamente nas posies je
(j+1),j=0, 1, 2, ..., n-1, tem-se que:
[
(
) ]
7/21/2019 Kazama_Elton_Koji Ho and Chang
33/111
32
Onde:
um limitante superior de (que o intervalo de tempo de espera da
mquina h que ocorre entre o trmino da tarefa ue o incio da tarefa v).
= tempo de processamento da tarefa ina mquina h.A partir dessa propriedade, tem-se:
Para uma sequncia S de n tarefas, o limitante superior para a durao total da
programao M(S) dada por:
Se considerarmos como a distncia entre as tarefas nas posies je(j+1), ento o problema de programao em flowshop permutacional pode ser
heuristicamente resolvido por analogia direta com o problema do caixeiro viajante
(Moccellin, 1995). No primeiro passo da heurstica FSHOPH, a distncia entre as
tarefas u e v dada por
e procurado a rota (sequncia) que minimize o
limitante superior . Para o segundo passo, utiliza-se tcnicas de busca Tabupara melhorar a soluo inicial.Dannenbring apresentou a heurstica Rapid Acess (RA), que uma mistura das
idias prvias do ndice de Palmer e CDS (Dannenbring 1977). A principal idia por
trs construir um nico subproblema de duas mquinas (ao invs de m-1
subproblemas), onde os tempos de processamento de cada tarefa so determinados pelo
esquema de ponderao linear. Este subproblema resolvido usando o algoritmo de
Johnson para duas mquinas. O procedimento de RA fornece uma boa soluo de
maneira rpida. Os pesos para as tarefas so calculados por:
O desenvolvimento de heursticas construtivas para os problemas de flowshop
permutacional ocorreu principalmente nas dcadas de 1960 e 1970, e proporcionou boas
7/21/2019 Kazama_Elton_Koji Ho and Chang
34/111
33
solues dentro de tempos de processamento razoveis. No entanto, a qualidade das
solues ainda possui muitas oportunidades a serem melhoradas.
Sarin e Lefoka (1993) exploraram a ideia de minimizar o tempo ocioso da ltima
mquina, pois o aumento do tempo ocioso da ltima mquina se traduzir em um
aumento no tempo de concluso total ou makespan. Portanto, a sequncia completada
inserindo-se uma tarefa de cada vez, e dada prioridade ao trabalho que resulta na
mnima adio de tempo ocioso na mquina m.
Nawaz, Enscore, e Ham (1983) desenvolveram uma heurstica construtiva
denominada NEH, que compreende duas fases simples, baseado na ideia de priorizar as
tarefas em funo da soma de seus tempos de processamento em todas as mmquinas.
A heurstica NEH classificada como uma heurstica construtiva, ao passo que exige n
iterao do procedimento, que tem (n2m) clculos possveis, de acordo com Ruiz e
Maroto (2006).
Devido ao bom desempenho da heurstica NEH original, pesquisadores
enfatizaram o aprimoramento do NEH para diferentes abordagens. As principais
direes das pesquisas para a modificao do NEH na literatura de programao da
produo so baseadas em quatro categorias principais, descritas a seguir:
O objeto da primeira categoria estudar o efeito da sequncia inicial na fase I, na
abordagem do NEH para o seu desempenho (NEH original). Framinan et al. (2003)
analisaram 177 diferentes sequncias iniciais, verificando mudanas nas fases iniciais
(fase de indexao) do NEH, a qual os cinco melhores mtodos para as funes objetivo
de minimizao de makespan, tempo ocioso de mquina (idletime) e tempo total de
fluxo (flowtime). Foi calculado a porcentagem de desvio relativo, e os resultados
mostraram que a sequncia do NEH original teve o melhor desempenho para as funes
objetivo de minimizao do makespane tempo ocioso.
Nagano e Moccellin (2002) desenvolveram uma heurstica construtivadenominada N&M, onde esta se difere da heurstica NEH (1983) apenas na fase inicial
de ordenao. Este processo quebrado em duas etapas:
Etapa 1: Calcular Onde:
7/21/2019 Kazama_Elton_Koji Ho and Chang
35/111
34
= tempo de processamento da tarefa ina mquina k;n = nmero de tarefas;
m= nmero de mquinas
(( ) )
( )sendo,
A tarefa u imediatamente precedente de v.
Etapa 2: Ordenar todos o Ii de forma no-crescente e prosseguir os prximos
passos identicamente ao mtodo NEH.
A segunda categoria foca o desempate na fase de insero do NEH original, pois
podem existir vrias seqncias parciais que tm o mesmo makespan parcial nesta
abordagem. A seleo aleatria pode causar maiores makespantotal na prxima etapa.
Kalczynski e Kamburowski (2007) mediram o desempenho do NEH com uma
modificao da etapa de insero para demonstrar o impacto sobre o desempenho no
tempo de desempate. Eles criaram uma heurstica denominada NEHKK, em que h umamodificao no processo de construo da sequncia soluo do NEH. Quando ocorre
empates nas sequncias parciais, h uma avaliao levando em considerao a regra de
Johnson. A seguir apresentado as fases de construo da heurstica NEHKK:
Etapa 1: Calcule , jJ, e organize na ordem no-crescente;Etapa 2: Considere apenas as duas primeiras tarefas da seqncia obtida na etapa
1 e ordene-as de maneira a obter o menor makespane faa ( )Etapa 3:Selecione a prxima tarefa rda ordenao inicial TPje insira na primeiraposio da sequncia parcial. Assuma a sequncia inicial ( )e faa lx1.Para lde 2 at n, faa:
Teste a tarefa rna posio lde e siga o seguinte critrio:SE omakespanda sequncia for menor que o makespanda sequncia OU SE: {o makespan da sequncia for igual ao makespanda sequncia }E: {o makespan da sequncia ( for menor que o makespan da
7/21/2019 Kazama_Elton_Koji Ho and Chang
36/111
35
sequncia ( }Ento faa: lx1 e Uma abordagem de modificao da fase I do NEH original, proposto por Dong et
al (2008) e denominado NEH-D, mostrou uma melhoria significativa ao criar uma regra
de prioridade baseado na combinao linear da mdia (AVGj) e do desvio padro (DEVj)
dos tempos de processamento das tarefas, dado por:
Desta forma, cada tarefa recebe um valor do esquema de ponderao dado pela
combinao linear . Em seguida, essas tarefas socolocadas em ordem no-crescente de acordo com esta regra de prioridade,
caracterizando ento a Fase I do NEH. Dong, Huang e Chen elaboraram ainda uma
estratgia para o caso em que houver empate entre estes pesos dados s tarefas. A
seguir, uma breve explanao sobre a metodologia:
Seja a tarefa da posio xde uma permutao . Logo o tempo deprocessamento de tarefa
na mquina i,
a primeira data de trmino da tarefa
na mquina i, a ltima da de incio da tarefa na mquina i. Com isso,duas medidas podem ser calculadas para a tarefa :
Para o caso em que houver empate, o desempate ocorre inserindo a tarefa na
7/21/2019 Kazama_Elton_Koji Ho and Chang
37/111
36
posioxcom o menor .A terceira categoria na literatura de pesquisas que modificam a heurstica NEH
utiliza etapas adicionais para reinserir tarefas em posies vizinhas, a fim de melhor
acomodar a nova tarefa. Rad et al. (2009) propuseram cinco novos mtodos que
superam o NEH denominados FRB1, FRB2, FRB3, FRB4 e a meta-heurstica FRB5.
Dentre os algoritmos construtivos, FRB3 e FRB4 foram as heursticas com os melhores
desempenho, e por tanto, a seguir eles sero detalhados. Mtodo FRB3:
Etapa 1: Calcule e coloque em ordem no-crescente de TPje ;Etapa 2: Para l= 1 at n, testar a tarefa h, na posio l de TPj, em todas as
possveis posies de e inserir a tarefa na posio de menor makespan.Etapa 2.1: Para i=1 ate l, retire a tarefa hda posio ide e teste hem todas as
posies possveis de , e inserir a tarefa na posio de menor makespan.Para o mtodo FRB4, a nica mudana em relao ao FRB3 est no modo como
feito o processo de busca na Etapa 2.1. O FRB3 realiza a busca em lpossveis solues,
enquanto que o FRB4 busca em um intervalo definido entre o mximo de lepke o
mnimo de l ep+k, ondep a posio em que a tarefa foi inserida no passo 2 e k um
valor pr-definido para mtodo e varia entre {2, 4, 6, 8, 10, 12}. O mtodo FRB4
apresentado a seguir:
Etapa 1: Calcule e coloque em ordem no-crescente de TPje ;Etapa 2: Para l= 1 at n, testar a tarefa h, na posio l de TPj, em todas as
possveis posies de e inserir a tarefa na posio de menor makespan.Etapa 2.1: Para i=Max (i,p-k) at Mn (l, p+k), retire a tarefa hda posio ide e teste a em todas as posies possveis de , e inserir a tarefa na posio demenor makespan.
A ltima categoria abrange alguns outros pesquisadores que trabalham para
reduzir o tempo de processamento do NEH, enquanto que a qualidade da soluo no
um requisito que necessite de cuidados, se comparado com o NEH original. Jin et al.
7/21/2019 Kazama_Elton_Koji Ho and Chang
38/111
37
(2007) introduziram o procedimento de poda baseado nas propriedades de bloco dos
problemas de programao flowshop, que investigado para reduzir o tempo de
execuo, e dentro da heurstica NEH, para reduzir a complexidade computacional. Os
resultados experimentais mostraram que o NEH aperfeioado apresenta uma grande
reduo do tempo de execuo quando comparado com o NEH original. Gao et al.
(2007) propuseram o NEH melhorado, com completos movimentos de inseres para
resolver o problema de flowshop permutacional. Mtodo para o rpido clculo do
makespane a poltica de eliminao de permutaes no-promissoras so introduzidos
para reduzir o esforo da avaliao.
7/21/2019 Kazama_Elton_Koji Ho and Chang
39/111
38
3 CLASSIFICAES EXISTENTES DE HEURSTICAS DEFLOWSHOP PERMUTACIONAL
Framinan, Gupta e Leisten (2004) desenvolveram um trabalho onde, alm de
demonstrar as principais heursticas disponveis na literatura para o problema de
minimizao do makespan, estabelecem um quadro geral que engloba todas elas,
classificando-as em fases de construo comuns. Nos trabalhos prvios de classificao,
considerando que nem todas as heursticas disponveis so da mesma natureza, o termo
heurstica construtiva foi utilizado para um primeira delimitao. Entretanto, esta se
trata de uma classificao superficial e de escopo limitado, segundo Framinan, Gupta e
Leisten (2004), e o significado do termo construtivo permanece confuso (e
consequentemente, o mesmo se aplica s heursticas assim classificadas). Por exemplo,
Pinedo (2008) definiu heurstica construtiva como o oposto heurstica composta, que
so aquelas resultantes da combinao de heursticas simples (construtivas). J
Loureno (1996) definiu heurstica construtiva como um algoritmo que constri
sequncias de tarefas e, uma vez que a deciso tomada, no se deve alter-la.
Alm disso, existiram outras tentativas de classificar as heursticas existentes para
a programao em ambientes flowshop, tal como proposto por Gupta (1971). Segundo
ele, as heursticas so classificadas em trs classes: heursticas funcionais fixas,heursticasfuncionais flutuantes eheursticasfuncionais sintticas. A primeira classe
engloba as heursticas que exploram as caractersticas funcionais de um problema de
classificao. Basicamente, consiste no desenvolvimento de alguns ndices para
classificar as tarefas, podendo estes ndices serem baseados nos tempos de
processamento do problema, por exemplo. Gupta inclui nesta classificao heursticas
como as de Palmer (1965), Campbel et al (1970), e Gupta (1971). Heursticas
funcionais flutuantes, por sua vez, geram uma funo contnua para uma sequnciaparcial. Como exemplo o autor cita os algoritmos MINIT e MINOT de Gupta (1968;
1972). E por fim, como exemplo de uma heurstica funcional sinttica, pode-se citar a
heurstica MINMAX de Gupta (1972), baseado na programao de tarefas, ordenando
primeiro as tarefas com os menores tempos de processamento, e por ltimos, aquelas
com os maiores tempos.
No entanto, de acordo com Framinan, Gupta e Leisten (2004), todas as
classificaes citadas apresentam problemas. Na classificao de Pinedo (2008), seria
difcil classificar algumas heursticas que fossem tratadas tanto como heursticas
7/21/2019 Kazama_Elton_Koji Ho and Chang
40/111
39
simples quanto como uma forma de generalizao de uma heurstica mais simples. Por
exemplo, a heurstica de Campbell et al (1970) pode ser considerada uma forma
generalizada da heurstica de agregao de mquinas de Rck e Schmidt (1983). Na
classificao sugerida por Loureno (1996), vrias heursticas de diferentes naturezas,
tais como Nawaz et al (1983) e Gupta (1971), poderiam ser agrupadas dentro do termo
heurstica construtiva. Porm na prtica, esta ltima heurstica seria considerada como
um ponto inicial para formar a soluo final. Com relao classificao de Gupta, de
um lado ela no cobre os desenvolvimentos de heursticas recentes tais como a de Page
(1961), que se baseia em buscas locais. De outro lado, desenvolvimentos relativamente
novos tais como as meta-heursticas no se encaixam nesta classificao por razes
bvias. Por fim, outros trabalhos como os de Morton e Pentico (1993), simplesmente
distinguem entre heursticas e mtodos de busca local, sem fazer a relao entre eles.
3.1CLASSIFICAO PROPOSTA POR FRAMINAN, GUPTA E LEISTEN
Dando continuidade a estes estudos, Framinan, Gupta e Leisten (2004)
desenvolvem um quadro geral para estender classificaes anteriores de modo a
abranger todas as principais heursticas.
No quadro geral proposto, o desenvolvimento de uma heurstica consiste em trs
fases:
Fase 1: desenvolvimento do ndice
Fase 2: construo da soluo
Fase 3: melhoramento da soluo.
Uma heurstica simples pode se consistir de uma ou mais destas fases, que em
geral so independentes uma da outra. Entretanto, uma heurstica que consista em mais
de uma destas fases deve ocorrer na ordem acima mencionada. As trs fases seroexplicadas com mais detalhes a seguir.
3.1.1 Fase I: Desenvolvimento do ndice
Na fase de desenvolvimento do ndice, as tarefas so organizadas de acordo com
uma certa propriedade baseada nos dados de um problema, por exemplo, os do tipo
Fm/prmu/Cmax, isto , baseados nos tempos de processamento de cada tarefa em cadamquina. Em geral, este procedimento no necessita fazer nenhuma suposio durante o
7/21/2019 Kazama_Elton_Koji Ho and Chang
41/111
40
sequenciamento das tarefas. O resultado desta fase a lista seqenciada das tarefas para
serem inseridas para a prxima fase, ou soluo.
Para derivar o ndice, podemos usar ou no um problema anlogo. Problema
anlogo refere-se ao uso de dados de problemas do tipo Fm/prmu/Cmaxpara construir e
resolver um caso de diferentes classes de problemas. Quando o ltimo problema tiver
sido resolvido por determinados meios, a soluo obtida convertida em uma sequncia
de tarefas para o problema originalFm/prmu/Cmax. Talvez o exemplo mais bvio de um
problema anlogo seja a analogia F2//Cmax, empregada em heursticas como a de
Campbell et al (1970). Nesta heurstica, um problema F2//Cmax construdo por
agregao de mquinas a partir de dados oriundos do problemaFm/prmu/Cmaxoriginal a
ser resolvido. O problema F2//Cmax ento obtido resolvido de forma tima em tempo
polinomial aplicando a regra de Johnson, e a sua soluo tima aceita como uma
soluo para o problema originalFm/prmu/Cmax.
Se nenhuma analogia for usada, a propriedade deve ser simplesmente deduzida a
partir de alguma forma de relacionamento assumido, que envolva o tempo de
processamento das tarefas e suas posies correspondentes dentro da sequncia.
Nos casos onde alguns problemas anlogos precisam ser empregados, as duas
questes seguintes devem ser consideradas:
a) A simplicidade dos problemas anlogos empregados, isto , se existem mtodos
polinomiais disponveis para resolver otimamente o problema anlogo, ou ao
menos alguma heurstica eficiente para este ltimo;
b) A correspondncia entre solues dos problemas de analogia e dos problemas
Fm/prmu/Cmax, isto , se possvel provar que as solues boas ou timas
provenientes do problema anlogo rendem boas (ou timas) solues para o
problema original.
Trs problemas anlogos tm sido usados at agora para derivar uma ordenaodas tarefas:F2//Cmax, o Problema do Caixeiro Viajante (PCV) e a analogia da Soma de
Vetores, explicados a seguir.
Analogia F2//Cmax
Como mencionado antes, a analogia mais clara e a mais utilizada a analogia com
o problema F2//Cmaxvia agregao de mquinas. A agregao de mquinas refere-se a
uma simplificao do problema original em relao s mquinas. Como resultado, oproblema original convertido em um novo problema denominado Aggregated
7/21/2019 Kazama_Elton_Koji Ho and Chang
42/111
41
Problem Instance, com um nmero de mquinas fictciasdenominadas mmenor
que o problema original. Mais especificamente, um problema com n tarefas, m
mquinas transformado em um problema com n tarefas, mmquinas, sendo m < m.
Com relao s duas questes acima sobre as analogias mencionadas na seo
anterior (simplicidade e correspondncia), o primeiro alcanado fixando m= 2, desde
que seja possvel resolver o problema F2//Cmax otimamente em tempo polinomial, de
acordo com a regra de Johnson. Portanto, embora m possa valer teoricamente
qualquer valor m< m, m fixado a 2 em todas as heursticas existentes que utilizem o
procedimento de agregao de mquinas. Por outro lado, o caso de agregao de
mquinas com m > 2 implica na resoluo de um problema cuja complexidade
idntica quela do problema original. Desta forma, no vivel desenvolver uma
heurstica de agregao de mquinas com m > 2, a menos que abordagens heursticas
especficas sejam desenvolvidas para um determinado casoFm//Cmax, sendo 2 < m < m,
ou exista uma heurstica que apresente um desempenho extraordinariamente melhor
para um determinado m > m. Finalmente, perceba que para m < 2, isto , m = 1,
qualquer sequenciamento timo, logo no parece ser possvel converter a soluo do
problema agregado correspondente em uma soluo que faa sentido para o problema
original.
Com relao correspondncia entre solues, nenhuma prova formal foi
desenvolvida at o momento. Desde que os tempos de processamento do caso sejam
envolvidos, a correspondncia ser dependente do caso e, portanto, boas abordagens
para a agregao podem ser distinguidas de abordagens ruins apenas com base
estatstica, isto , o percentual de problemas em que uma certa abordagem para designar
tempos de processamento que produza casos agregados cuja soluo tima representa
uma boa soluo para o problema original. As principais abordagens para designar
tempos de processamento para duas mquinas referem-se a Campbell et al (1970),Dannenbring (1977), Rck e Schmidt (1983), Selim e Al-Turki (1987), e Lai (1996).
Todas essas abordagens resolvem otimamente o problema F2//Cmax(pela regra de
Johnson) e usam essa soluo como soluo para o problema Fm/prmu/Cmax, com
exceo da heurstica de Lai, que simplesmente classifica uma tarefa jem um dos dois
grupos seguintes: U:{j:p1j p2j}, V:{j:p1j > p2j}, como na regra de Johnson.
Entretanto, as tarefas em cada grupo no so classificadas mas sim sequenciadas
arbitrariamente, e unidas com a nica condio de que as tarefas em Udevam precederas tarefas em V. Esse procedimento permite que a heurstica seja muito rpida,
7/21/2019 Kazama_Elton_Koji Ho and Chang
43/111
42
apresentando uma anlise do pior caso no muito diferente de outros procedimentos de
agregao de mquinas. Porm, nenhum experimento computacional foi realizado para
testar a performance desta heurstica (FRAMINAN; GUPTA; LEISTEN, 2004).
Analogia PCV
A analogia do problemaFm/prmu/Cmaxcom o PCV foi apontada pela primeira vez
por Gupta (1968), e tem sido tambm estudada por Stinson e Smith (1982), Widmer e
Hertz (1991) e Moccellin (1995). Nestes trs artigos, a matriz de distncia que define o
caso PCV de ncidades montado utilizando o tempo de processamento das mquinas
(no caso do artigo de Stinson e Smith so apresentados mais de seis diferentes modos de
construo da matriz de distncias). Assim, o PCV resolvido, e a sua soluo
mantida como soluo para o problema originalFm/prmu/Cmax.
Considerando que o PCV seja do tipo NP-hard, no h mtodo disponvel que
garanta uma soluo tima dentro do intervalo de deciso (FRAMINAN; GUPTA;
LEISTEN, 2004).
Analogia da Soma de Vetores
O ento denominado Teorema da Soma de Vetores 43 pode ser enunciado da
seguinte forma: seja V = {v1,...,vn} um conjunto de dvetores dimensionais em que , e seja possvel comput-lo em tempo polinomial uma permutao tal que|| || dmaxj = 1,...,n|| vj||, k = 1,..., n.
Com relao s duas questes discutidas acima quando empregado um problema
anlogo (simplicidade e correspondncia), a analogia empregada pode ser resolvida
utilizando um algoritmo de tempo polinomial baseado em programao linear
(LAWLER et al, 1993).
3.1.2 Fase II: construo da soluo
Nesta fase, uma soluo construda de forma recursiva ao tentar inserir uma ou
mais tarefas no sequenciadas em uma ou mais posies de uma sequncia parcial, at
que todo o sequenciamento esteja completo. Portanto, esta fase consiste de uma srie
limitada de tentativas (loops). Em cada loop k, o conjunto de tarefas dividido em dois
subconjuntos: o subconjunto Sk de tarefas j sequenciadas e o subconjunto Rk de tarefas
7/21/2019 Kazama_Elton_Koji Ho and Chang
44/111
43
no-sequenciadas. Perceba que no k-simo loop, o subconjunto Sk define uma sequncia
parcial de k tarefas. Em cada loop, uma tarefa removida do subconjunto no-
sequenciado e inserida no subconjunto de tarefas j sequenciadas.
Nesta fase existem duas questes em qualquer loop k:
a) Seleo de tarefas, isto , definir qual tarefaj Rk ser inserida no
subconjunto Sk..
A seleo de tarefas deve ser decidida de acordo com uma das seguintes
abordagens:
De acordo com algum ndice obtido a partir de uma aplicao da fase I, ou
Vrias tarefas pertencentes a Rkso testadas. Neste caso, a seleo de tarefas a
serem inseridas feita de acordo com uma determinada medida de desempenho,
isto , visando minimizar alguma propriedade resultante da sequncia parcial.
A propriedade da sequncia parcial utilizada para a seleo de tarefas deve ser a
funo objetivo que visa a minimizao do makespan. O racional para usar esta medida
claro, desde que o makespan possa ser decomposto na soma dos tempos de
processamento de todas as tarefas em todas as mquinas mais a soma desses tempos
com os tempos de espera em cada mquina. Considerando que o primeiro termo da
expresso (tempos de processamento) constante, ao minimizar de alguma forma o
tempo ocioso leva-se a sequncias com menores makespans.
b) Insero da tarefa, isto , definir onde ser inserida a tarefa escolhida na
sequncia parcial Sk.
Com relao insero de tarefas, uma tarefajpode ser inserida em uma posio
fixada na sequncia parcial Sk, ou inmeras posies podem ser testadas. King e Spachis
(1980) distinguem entre sequncias de cadeias simples e cadeias mltiplas,
dependendo se uma ou vrias posies so tentadas, respectivamente.
Novamente, quando diversas posies so testadas, a seleo da posio deve ser
feita de modo a minimizar alguma propriedade da sequncia parcial resultante. Desta
forma, quando vrias tarefas pertencentes a Rk precisam ser inseridas nas diversas
posies da sequncia parcial Sk, a qualidade das medidas de ambas as sequncias
precisa ser a mesma, ou ao menos consistentes entre si. Alm disso, para garantir umaboa performance desta fase, a qualidade das medidas de ambas as sequncias parciais
7/21/2019 Kazama_Elton_Koji Ho and Chang
45/111
44
devem coincidir ou pelo menos ser consistentes com a funo objetivo
(minimizao do makespan). Similarmente ao caso de seleo das tarefas, devero
existir algumas regras de desempate quando mltiplas posies so testadas.
Novamente, este aspecto ignorado pela maioria das heursticas existentes.
Percebe-se que as decises para a seleo e a insero de tarefas (caso sejam
tomadas) so tomadas usando informao parcial (local) e, portanto, apenas
melhoramentos locais podem ser obtidos. Logo, no se pode garantir que a sequncia
resultante fornea um makespan menor que a sequncia inicial desenvolvida na fase I,
ou at mesmo uma sequncia aleatria.
3.1.3
Fase III: melhoramento da soluo
Nesta fase, de acordo com Framinan, Gupta e Leisten (2004), uma soluo
existente melhorada por meio de alguns procedimentos. As duas principais
caractersticas desta fase so:
Uma soluo inicial (soluo de entrada) requerida;
A qualidade da soluo sempre igual ou melhor que a soluo da sequncia
inicial.
Partindo de uma soluo inicial, este procedimento procura mudar a sequncia de
tarefas para melhorar a soluo. Isto pode ser feito em uma base individual por
exemplo, duas tarefas possuem suas posies trocadas ou em uma base de grupos
por exemplo, so alternadas as posies de um conjunto de tarefas adjacentes. No
segundo caso, alguns procedimentos so desenvolvidos a fim de agrupar, e s vezes
reagrupar, um conjunto de tarefas.
Comumente, abordagens de melhoramentos so classificadas em buscas locais
descendentes e meta-heursticas (NOWICKI, 1996; STTZEL, 1998). Como exemplo
de heursticas que utilizam busca local descendente, cita-se Page (1961), e a fase final
da heurstica RAES de Dannenbring (1977), entre outros.
Alm da classificao em meta-heursticas e busca local descendente, para esta
ltima, h a necessidade de distino entre abordagens de vizinhana geral e vizinhana
especfica. As abordagens de vizinhana geral so aquelas em que a vizinhana pode ser
adequada para qualquer problema combinatrio, enquanto que abordagens de
7/21/2019 Kazama_Elton_Koji Ho and Chang
46/111
45
vizinhana especficas so aquelas em que a definio de vizinhana considera algumas
caractersticas especficas para o problemaFm/prmu/Cmax.
3.1.4
Estratgias para cada fase de classificao das heursticas
O emprego da classificao elaborada por Framinan, Gupta e Leisten (2004)
fundamental para estabelecer um parmetro de comparao entre mtodos distintos, e
foi empregado em muitos trabalhos posteriores. Dentre estes, Framinan, Leisten e Ruiz-
Usano (2005) desenvolveram uma investigao do problema de trabalhos seqenciais
em flowshop permutacional, visando minimizar a soma dos tempos de concluso
flowtime.No trabalho, primeiramente foi feita uma classificao e comparao entre as
heursticas existentes. Em seguida, baseado nos resultados experimentais, os autores
sugeriram duas novas heursticas compostas para solucionar o problema, comprovando,
atravs de experimento computacional subsequente, que ambas so eficientes para o
problema considerado.
De acordo com Framinan, Leisten e Ruiz-Usano (2005), at o ano 2000, as
melhores heursticas construtivas disponveis para o problema de minimizao do
makespaneram as heursticas de de Rajendran e Ziegler (1997) e Woo e Yim (1998).
Mais recentemente, outras abordagens heursticas para o problema foram publicadas,
como a heurstica de Liu e Reeves (2001), o conjunto de heursticas compostas de
Allahverdi e Aldowaisan (2002), o trabalho de Framinan et al. (2003) na aplicao da
heurstica NEH para o problema F|prmu|Cj, e a heurstica de Framinan e Leisten
(2003). Algumas dessas heursticas so de naturezas distintas: de um lado, a heurstica
de Liu e Reeves consiste de uma primeira fase onde as tarefas so classificadas de
acordo com um ndice que considera o tempo ocioso, seguido de uma fase de
melhoramento local. Por outro lado, o conjunto de heursticas de Allahverdi e
Aldowaisan pode ser