Kazama_Elton_Koji Ho and Chang

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


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


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)


4/111

Dedico este trabalho a minha amada, Tssia Marques.


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!


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/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.


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 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 14 - Grfico de Gantt da sequncia parcial obtida J5 - J2 ................................... 66


Figura 16 - Grfico de Gantt da sequncia parcial obtida J4 - J2 - J5 ............................ 66



Figura 19 - Grfico de Gantt da sequncia parcial obtida J1 - J2 - J4 - J5 ..................... 68




Figura 23 - Grfico de Gantt da sequncia obtida J3 - J1 - J2 - J4 - J5 .......................... 69



9/111




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 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






10/111







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 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


11/111

Figura 72 - Grfico de Gantt da sequncia obtida J2J8J10J7J5J9J3J1J6J4 .................................................................................................... 103

Figura 73 - Quadro Geral de Classificao das Fases Construtivas ............................. 104


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


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


14/111

4.2.2 Nagano e Moccellin (2002) ...................................................................... 964.3 QUADRO DE CLASSIFICAO .................................................................. 103

5

CONSIDERAES FINAIS ............................................................................ 105

6 REFERNCIAS BIBLIOGRFICAS ............................................................ 106


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


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


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


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).


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


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


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)


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.


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


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


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


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:


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


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


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


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


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.


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:

[

(

) ]


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


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:


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


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


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.


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.


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


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


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


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,


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


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


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


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

Documents

Kazama_Elton_Koji Ho and Chang