BUSCA EM FEIXE FILTRADA PARA A PRO-,..,GRAMAÇAO DE TAREFAS COM PENALIDADES

DE ATRASO E ADIANTAMENTO

Marco A. E. CoelhoUniversidade de Brasília - Dep . de Eng. Elétrica/FT - Brasília - DF

egito@ene.unb.br

Paulo M. FrançaUniversid ade Estadual de Campinas - Fac. de Eng. ElétricalDENSIS Campinas - SP

franca@densis.fee.unicamp .br

Resumo: Ap resent amos um algoritmo baseado em busca em árvo re para resolver o problema deprogramação de tare fas em máquinas para lelas com dat as previstas. A função objetivo compreende aminimi zação simultânea de atra sos , adiantamentos e custos de troca entre tarefas. As máqu inas sãonão-relacionadas e o tempo de troca para o processamento de cada tarefa depende da seqüência namáquina. São aprese ntados dois limitantes usados em uma busca Branch-and-Bound e Busca emFeixe Filtrada, para encontrar soluções ótimas e próximas do ótimo .

Abslract: This article presents a tree-searcli based algor ithm f or solving the unrelated parallelniachine schedu ling problem with dl/e dates. The objective fu nction comprises the simultaneousnunimization of the tardiness, earliness and changeover costs of a set of jobs. The machines areunrelated and changeover time to process a job ou niachine depends on the job pre viou slyprocessed 0 11 the niachine. We present two bounds used in a Branch-and-Bound and Filtered BeamSearch pro cedures .tofind optimal and near optimal schedules.

1. INTRODUÇÃO

A programação (schedulingy em máquinaspar alel as é, atualmente, um pro blema bem conheci-do. No entanto, pouc o pode se r enc ontr ado na lite-ratura, sobre programação em máqu inas paral elasnão relacionadas (unrelaie di, principalmente quandoex iste a necessidade de inserir entre as tarefas, tem-pos de troc a (changeoveri dependentes da seqüên-c ia, isto é , dependentes da última tarefa processada .Além disto, considera-se que cada tarefa tem umadata previ sta de término (due date) distint o, é possí-vel inserir tempos oc iosos (idle tiniesí entre as tare-fas e ainda minimi zar uma função obje tivo compos tapelos atrasos (tardiness) , pelos adiantamentos tear-linessi e também por custos de troca entre tare fas.Uma programação que considere as característicasacima é conv eniente para muit as indústri as reais quelidam com es tes problemas no seu dia -a-di a. Indús-trias como as de produção de papel, de produção detecidos e talvez indú strias químicas ou de produçãode alimentos são alguns exemplos.

Muitos trabalhos relativos à program açãode tarefas em máquinas paralel as, são diri gido s àaplicação indu strial , mas qua se sempre são feitas vá-rias hipóteses restritivas com o intuit o de simplificaro modelo, talvez par a adequá-l o a uma limitada ca-

111

pacidade de processamento disponível. A preocupa-ção em modelar as características acima, não é iné-dit a, trabalho s como o de SERAFINI &ZA (1992) e GUINET (199 1), mostram que a in-dústria têxtil deseja introduzir estes melhoramentos.

2. REPRESENTAÇÃO DAS ALOCAÇÕES ESEQÜENCIAMENTOS.

GAREY, TARJAN and ·WILFONG (1988)demonstraram que uma instância mais simples doproblema (sem custo s ou tempos de troca depen-dentes da seqüência, custos de atraso e adiantamentoidênticos e apenas uma máquina) é NP-completa, re-sultado que pod e ser estendido para o problema des-crito no item an terior. Segundo OW & MORTON( 1988), Brancli & Bound (B&B ) é o 'método mai seficient e para a so lução deste tipo de problema, ape-sa r do tempo de processamento tipicamente expo-nencial com o tamanho da en trada.

Uma forma adequada para o tratamento deprobl emas com custo de atra so e adiantamento, é aseparação das duas atividades (BAKER & SCU-DDER , 1990) :li!) seqüenciamento e aloc ação de tarefas2i!) cá lculo de tempos ociosos, tempos de término,atras os e adiantamentos de tarefas.

minimize IJB ;. z(j )+aj .e(j )]+ I <kjET jET

kE M jiEAj ,.

Será utili zad o um método de busca em ár-vore pa ra a execução da primei ra ati vidade. A busca,do tipo in formada, será guiada por fu nções heurísti -cas de ava liação (ou limitantes) baseadas no mod elo_do item 2.1 , que executa apenas a segunda atividadelistada ac ima . DAVIS & KANET ( 1993), utili zamum procedimento seme lhante para a mini mização deatrasos e ad iantamentos em uma única máq uina.

O seqüenc iamento e alocação de tare faspode se r esquemat izado como abaixo :

Sujeito a:

a(j )- a (i ) -id(j )= Cijk + Pjk ;

a(j) - z(j )+ e(j )=d i; .i E T

.i E TkE M j

i E A;k

Muq A LI_l_L-I._--L -L_...J

M a'l o L..-I._--L_..L_L .L----J

t\·1aq Iof LI_...1-_.1.------1_ -"- --'-_

No esquema aci ma , cada máqu ina terá N (= númerode tarefas a serem executadas) posições pa ra aloc artare fas . 'Estas pos ições serão chamadas de S/OfSvirtua is , pois se refe rem apenas ao seqüenciamen todas tarefas na máquina, uma vez que oposicionament o exato só ser á feit o depois dedefinidos os tempos oci osos pelo modelo do item2.1. O s/ot mais à esque rda em uma máquinaqualquer , se rá ocupado pela primeira tarefa a serexecutada, o slo t contíguo à d ireit a deste, seráocupado pela segunda tare fa a se r executada, e ass imaté o S/Of mais à di reita que dever á co nter a últim atarefa a se r executada naqu ela máq uina. Pararepresentar um programa qua lquer, cada S/Of se rápreen chido com um número intei ro de I a Nrepresentand o a tare fa alocada naquela pos ição , ou Ose a posição não estiver ocupada.

Considerando qu e algumas posições do ga-barito ac ima poderão não es tar ocupadas, é possívelrepresentar a mesma seqüênc ia em uma máquina demu itas maneiras. De forma a pad roni zar es tas repre-sentações, pode-se util izar um gabarito de permut a-ªºcomo desc rito aba ixo :- O seq üenciamento das tare fas determina em quecoluna ve rtica l do gab ar ito ac ima, estará cada tarefa.- A alo cação da tarefa determina em que máquina(linha do gaba rito) esta será co locada.

Isto permite cons ide rar todas as máquinascom o mesmo seqüenciamento embora, na mai orparte do s casos, nenhuma. máquina possua todas asposições do seqüenciamento ocupadas , pois só have-rá uma tare fa não nula em cada co luna ou posição doseqüenciamento .

2.1 Modelo com seqüenciamento e alo-cações fixas.

Um a vez definidas as posições de cada ta-refa no gabarito do item anterior, define-se um pro-blema de programação linear , para determ inar amelhor escolha: de tempos oc iosos.

112

a(j) ? O,id(j)? O, e(j)? O, z(j )? O; .i E T

onde:T =conjunto de tarefas a serem executadas.M-= conjunto unitário con tendo a máquina onde aJtarefa } es tá alocada .Ajk = conjunto unitário contendo a tarefa i anterior ajna máquin a k.a(j )= instante de térm ino da tarefa } (variáve lcontínua).id(j) = temp o ocioso anterior à execução da fração datarefa} (var iável contínua) .z(j)=atraso da tarefa j (var iável contínua).e(j) =adiantamento da tarefa } (variáve l contínua) .d · = data prevista (du e dat e) para o t érminodaJ

tarefa j.[J;k = tempo de proce ssamento da tarefa} na m áquina

k.a - = coe ficiente de ad iantamento da tar efa i naJ •

função objetivo.

f3 . = coefic iente de atra so da tarefa i na funçãoJ .

objetivo.cu, = tempo de troca tchan geover fime) entre a tarefai e a tarefa j na máquina k.C"k = custo de troca tc hungeover cos i) e ntre a tarefa iIJ '

e a tare fa j na máquin a k.

A solução ótima do mode lo aci ma pode serobtida com o método simplex clá ssico ou simplexrevi sado, porém , o procedimento de busca que ser ádesenvolv ido ad iante ficaria bastante comprometidodevido ao grande número de operações ex igido pores tes métodos. No modelo acima é fáci l constatarque não ex iste influ ência de tare fas aloc adas em umadeterminada máquina nas tarefas alocadas em outrasmáquinas, o que significa que é possível fazer a mi-nimi zação em uma máqu ina de cada vez. DAVIS &KANET ( 1993), desen vol veram um proced imentoque minimi za os tempos oc iosos em uma única má-quina apenas deslocando blocos de tarefas adjacen-tes , sem a utilização do método simplex.

3. BUSCA EM ÁRVORE.

Com o modelo de seqüenciamentos e alo-cações fixas, o problema de obter uma solução apartir de um grupo de tarefas em um gabarito, estáreso lvido e de forma ótima . Resta então, a obtençãode um gabarito cuja solução ótima se aproxime omais possível da solução ótima do grupo. O métodoproposto aqui para resolver .este segundo problem a,é a busca em árvore do tipo Branch & Bound parachega r a um gabarito ótimo, ou Filtered Beani Se-arch para chegar a um gabar ito cuj a função objetivoda solução ótima se aproxima do menor valor possí-vel.

Existem apenas 2 decisões a serem tomadas·seqüenciamento global e alocação das tarefas nas m á-quinas disponíveis. Partind o de um programa vazio, éfeito o preenchimento simultâneo de todos os slots emuma determinada posição na seqüência. Na figuraabaixo, está representada uma arbor ização que se ini-

c.ia com os primeiros slots da seqüência e prosseguehnearmente até os últimos. Desta maneira tem-se umaárvore uniforme de profundid ade N (= número de ta-refas), com um grau de ramificação maior nos primei-ros nós e menor próximo às folhas (PEARL, 1984). A-cada passo ambas as decisões (seqüenci amento e alo-. cação) são tomadas simultaneamente, o que permitechegar a qualquer combinação possível envolvendotais decisões. Em cada nó da árvore, o gabarito parcialrelativo àquelas posições na seqüência, pode ser re-presentado por apenas 2 números. O primeiro repre-senta a tarefa que foi designada para a posição da se-qüência e o número inteiro entre parênteses representaa alocação decidida para aquela tarefa. Este últimopoderá variar entre I e M, onde M é o número de má-quinas disponíveis .

Para representar um programa completo, sãonecessários N nós descend entes e/ou ascendentes unsdos outros.

n í v c I I n í v c I 2 n í v c I 3

I R A lZ I

A figura acima representa apenas uns poucos nós da árvore em somente 3 posições da seqüênc ia.

3.1 Busca Branch & Bound.Devido ao número grande de combinações

possíve is, é necessário guiar a busca pela árvore deforma a expandir apenas os nós mais promissores(busca informad a). As funções heurísticas de ava lia-ção ou funções limit antes são números que servempara guiar a busca, fornecendo uma est imativa damelhor função objet ivo possível de se obter poraquele nó, caso seja esco lhido para expansão. Emcada expansão, deve-se avaliar cada um dos novosnós gerados, para a comparação com os outros daárvore. A estratégia best-fi rst esco lhe o nó que apre-sen tar o menor limitante entre todos dispon íveis para

113

na árvo re. Esta estratég ia pe rmite chegarao ót imo com um tipo de limitante con hecido comolimitante inferior (lower bou ndi , porém estes últi-mos costumam levar a ramificações excessivas (eum tempo de busca muito grande)'até se chegar aoresultado final.

3.1.1 Limitante Inferior 1 (LIl )Um nó da árvore de busca, define um grupo

de tarefas e um gabar ito para este grupo . Um limi-tante inferior para o grupo, é uma avaliação que nãopode ser reduzida nos nós descendentes, isto é,quando as tarefas ainda não prog ramad as forem in-cluídas no grupo. A adição de uma nova tarefa cor-

responde à introdução de novas vari áveis e restri-ções no modelo de scq ücnciarnentos e aloca ções fi-xas. Portanto , a resolução do problema incompleto(sem as novas tarefas) corresponde a uma relaxaçãodo problema completo , isto é, o valor da função ob-jetivo obtida se rvirá como limitante inferi or sobre ()va lor da função obje tivo da so lução Ótima do pro-blema completo.

4. BUSCA EM FEIXE FILTRADA (FILTEREDBEAM SEARCH)

Resumidamente, a busca em fe ixe. uti liza amesma árvo re de busca do Branch & Bound, porémsem a necessidade de utili zação de limitantes inferi-ores . A busca é executada em apenas uma dir eção,isto é, não são permitidos retorn os (back tracks) a umnó de nível ma is ba ixo. Quand o é feita a prime iraexpansão a partir de um nó vaz io, não apenas I, masos BI1I (= nll de Fei xes) melhores nós, seg undo aavaliação do limit ant e, são esco lhidos . Na expansãoseguinte, tod os os nós esco lhidos são expandidos enov ament e os Bnt melhores entre todos do novo ní-vel são escolhidos. No caso estudado aqui , cada ní-vel correspond e a uma nova tarefa ad ic ionada, o quesignifica que após N níveis a pro gramação estareicompleta e poderá ser esco lhido o programa commen or função objetivo como grupo e so lução final.

A filtragem prop osta por OW & MORTON(1988) , tem o obj etivo de evitar que um limit antecomputac iona lmente ca ro seja aplicado a tod os osnós descendentes, uma vez feita a expansão dos Btnnós em um determinado nível. A filtrage m é fe itapor um critério de qualidade inferi or e computacio-nalmente barato, que faz uma pré-seleção dos nós aserem avali ados pelo limitante caro. Port anto , a lar-gura da filtragem deve se r sempre maior do que BIII .

4.1 Implementação da FiltragemOW & MORTON ( 1988) comentam que

ex iste uma defi c iênc ia no tipo de filtrage m que elesutilizaram , pois como a função adotada para a filtr a-gem possui validade local , isto é, co nsidera sempreuma mesma tarefa e seqüência anterior ao nó sobanáli se, não faz sentido comparar os nós expandidosa partir do nó n com os nós expandidos a partir donó m. Por es te motivo, a filtragem só co nsidera I nóde cada ex pa nsão; em bora os auto res reconheçamque isto não é o idea l.

As funções responsáveis pela filtrage m uti-lizada aqui (item 4 .2. 1 com todas as tarefas), possu -em um caráter globa l, permitindo uma comparaçãoequivalente em qualquer nível da busca. A carac te-rística glob al egj, de cada tarefa é um número realcalculado ant es do iníci o da busca e permaneceinalterada até o final desta . Certamente tais funçõ essão inferiores às funções locais, mas poder ão seleci-onar qu aisqu er novos nós gerado s, até mesmo tod os

114

de um mesmo pai , dei xand o a escolh a final para oslimitantes.

Outra diferença fundament al em relação aotrahalho orig ina l de OW & MORTON (1988), é quenão ex iste um número [ixo de nós seleci onados pelafilt ragem , que poderá varia r ampl amente durante ahusca. Esta filtr agem apanhará a menor das caracte-ríst icas g loba is entre as tarefas restantes e somaráum term o fixo chega ndo a eg lll i ll + FI . !leg. onde Scgé a variação máxima das ca rac terís ticas globa is antesdo início da busca. Qu and o eg; C,(tlll i ll + FI . S cg , osnós com a tarefaj serão os esco lhidos pa ra avaliaçãopel os limitantes . Dest a forma, muitos n ós serão es-colhidos quando a característica g loba l mostrar pe-qucnas diferenças de prioridade entre as tarefas , oque parece se r razoável. A filt ragem se leciona ape-nas tarefas e não alocações específicas , isto é, paracada tarefa se lec ionada haver ão nós com todas asalocações possíveis.

4.2 Limitante superiorUma boa avaliação so bre a função obje tivo

ótima prec isa co nside rar todas as tarefas envo lvidas,o que não foi feito no cálculo do limitante inferior.Montando as tarefas restantes não progr amadas so -bre o nó a ser avali ado, seg undo urna ordem deter-min ada pela pri orid ade g loba l da s .tare fas e aloca-ções baseadas em uma heurístic a que se rá desen vol-vida ad iante, é possível obter uma avali ação muit omais precisa. O lim itante ass im ca lculado, pode serchamado de lim itante superior. pois se rá a própriafunção objetivo do programa complet o formado apartir do nó sob ava liação.

4.2. I Característica global das tarefasFunções de baix o custo computac ional (re-

gras de despacho) se rão utili zadas para procedercom o seqüenc iamento das tare fas rest ant es. Serãoutilizad as as seg uintes definições pa ra a ca rac terísti-ca global de cada tare fa.DD - data prev ista. A característica glo ba l se rá ape-

nas a data previ sta da tarefa , o que despreza ainfluência que o tamanh o da tarefa e a ve loc i-dad e de cada máquinas 'tem sobre a caracterís-tica.

LO - folga das tare fas. Neste ca so a folga se rá a dife-rença entre a data previ sta e o menor tempo detérmin o possível , supo ndo que não existemoutras tarefas nas máquinas e a tare fa es tá alo-cada unicamente na máqu ina mais rápida. Estadefinição des preza a influ ência das outras má-quinas so bre a caracterís tica da tar e fa.'

4.2.2 Alocação das tarefas restan tesA heurística de alocação estará sempre sen-

do ap licada à última tare fa da seqüê nc ia no mo-ment o , isto é, não exis tem informações so bre as tan

fas seg uintes que provocarão adiantame ntos sobre atare fa atua l, de maneira que es tes são desprezados.No momento da alocação as tarefas anteriores sãoco ns ideradas fixa s, isto é, desp reza-se o aco pla-me nto entre a tare fa atual e as anteriores.

A máquina escolhida será a que apresenta-na o men or cus to caso a tare fa es tivesse aloc adanela.

4 .2.3 Limitante 2 (L2)A pa rtir do n§ a ser ava liado, as tarefas

restantes são ordenadas pelas meno res ca racterísti -cas globais (i tem 4.2.1), resultando nas seqüênc iasEDD ou LLO. A cada nova tare fa ad icionada, exe-cuta -se uma minimi zação apenas na máquina. esco-lhid a pe la heurística do item 4 .2 .2 o que automati-came nte reproduzirá o efeito da tarefa incl uída sobreas anteriores e também produzirá uma me lhor apro-ximação da so lução fina l, melh orando os es tadosinic ia is na aplicação da heurística a tarefa seg uinte.

5. GRÁFICOS DE RESULTADOS

Os resultados aba ixo se referem à méd ia de5 ins tâncias geradas aleatoriamente como descritonos itens anteriores . Dois dos gráficos abaixo se re-ferem a exemp los const ruídos com grupos de tarefasdesacopla dos (onde sempre existem tempos oc iososnão nulos entre os grupos) . Nestes casos a so luçãoótima é a soma das so luções ót imas dos grupos , istoé, é possível co nstruir exemplos de qua lquer tama-nho onde uma sol ução ótima é co nhecida. Os doisúltimos gráficos se referem a exemplos onde não hágarant ia de desacoplamento entre os grupos, isto é,não se conh ece uma , so lução ót ima. Cada gráf ico

descreve o comportamento médi o da busca em feixeem exemplos com diferentes valores do par âmetro Rque é chamado de fator de faixa de datas prev istas ed iferentes valores do parâmetr o i" que é o fator deatrasos multimáquinas.

As medidas de desempenho foram os de s-vios percentuais em relação ao ótimo (ia_ar) que ésempre positivo. Uma outra medida (lo_UB) foi uti -lizada para medi r -o desvio percentual em rel ação àso lução obtida por uma regra de despacho (no caso ,seq üenciamento de tarefas com LLO e a locação coma heurística do ítem 4.2 .2) . Os resultados obtidoscom esta última são todos negativos.

Em todos os exemplos utilizou-se Bm = 8 e7 valores d ife rentes de n ( 100%, 40%, 20%, 10%,5%: 2%, 1%). Nos tes tes com os grupos desacopl a-do s, verificou-se que a seqüênc ia LLOem L2 produ zos melhores resultados em relação ao ótimo, o quelevou a adotá-lo como padrão em todo s os proble-mas de tes te. Apenas os melh ores resultados médios,segundo fo _UB, es tão nos gráficos abaixo , repre-sentados por quadrados no gráfico de f o_or'e triân-gulos nos gráficos de fo _UB. Nos gráficos aba ixoes tão representadas as dis persões do valor médi o,quando Ft varia de ntro da fa ixa acima (quadra-do /triângulo claro) e também a dispers ão em torn odo menor va lor méd io considerando cad a uma das 5instâncias sepa radamente (quadra do/triâ ngulo escu-ro) . O gráfico dos tempos de busca abaixo é relati voaos tempos médios dos problemas com R" = 0,33ei " =0,66, pois es tes apresentaram tempos um poucomaio res para cada um dos problemas. Porém, ostempos para os outros problemas do mesmo tamanhoé aproximadamente igual em escala logarítmica.

Legenda: N X M, Ft = filtragem em porcentagem de Scg e t tempo de busca.

tempo de busca (s)10000,OQ-r- - - - - - - - - - -------- - ----

1000,00+-- - - - - ------- - - --=--- 1

1

10 ,00 .,.... - - - ---;=------r-,----I

0 ,10 .L-LL- - - - - - - - - - - - - - - - - - - - -18X1 18X3 18X9 30X1 30X3 30X9 60X1 60X3 60X9 120X1 120X3

115

resultados obtidos com o limitan te L2 são encoraj a-I

dores e mostram que este método pode ser aplicadoa problemas reais nas linha s de produção de indú s-trias de porte razoável.

7. BIBLIOGRAFIA

[I ] BAKER, K. R. & SCUDDER, G. D.: "Sequen-cing with Earliness and Tardiness Penalties: AReview" . Operations Research , 38 , p. 22-36,1990 .

[2] BAZARAA, M. S. & JARVIS , J. J .: "LinearProgramming and Network Flows." John WiIey& Sons, 1977.

[3] COELHO, M. A. E. & FRANÇA, P. M.:"Heurísticas para Programação em MáquinasPara lelas Não-Rel acionadas Sujeitas a Div isãode Tarefas ". ENEGEP- UFSCar, São Carl os-SP , 1995.

[4] COELHO, M. A. E. & FRANÇA, P. M.: "Buscaem Árvore para o Problema de Programação emMu ltiprocessad ores com Custos de Atraso eAdiantamento". XI Congresso Brasileiro deAutomática, USP - São Paulo - SP, 1996

[5] COELHO, M. A.: "Programação em MáquinasParalelas Não-Relacionadas Sujei tas a Divisãode Ta refas". Tese de DoutoramentoUNICAMP, Campinas - SP, 1996

[6] DAVIS , 1. S. & KANET, J. 1.: "Single-Ma chin eScheduling with Early and Tardy CompletionCosts". Naval Research Logistics, 40, pp . 85-101 , 1993.

[7] GAREY , M. R. ; TARJAN, R. E.; WILFONG,G. T.: "One-Processo r Scheduling with Sym -metri c Ea rliness and Tard iness Penalties " . Ma-thematics of Operations Research, 1312, pp.330-348, 1988

[8] GUINET, A. : "Text ile Production Systems: aSuccession 01' Non-identical Parallel ProcessorShops ". Journal of the Operational ResearchSociety, 42 , p. 665-671, 1991 .

[9] OW, P.S .; MORTON, T. E.: "Filtered beam se-arch in scheduling" . International Journal ofProduction Research, 26/1 , pp . 35 -62 , 198 8.

[ lO] OW , P. S.; MORTON, T- E.: 'The SingleMach ine Ear ly/Tardy Problern" . ManagementScience, 35 , No 2, p. 177-191, 1989.

[ lI] PEARL, J.: "HEURISTICS : Intell igent SearchStrategies for Com puter Problem Solving."Addison-Wesley, 1984.

[12] SERAFINI, P. & SPERANZA, M. G.: "Pro-duction Scheduling Problems in a Textil e In-dustry". European Journal of O perationalResearch, 58 , p. 173-190, 1992.

I. o;'p.F1I... Oisp. lnsq

,

.; I

•::.;::.

dT ''' 'li" t '''.:.

I t •I1.1" " I, ." ", ' '' 1. 11\1' 7.

I,'", :." .

..,,,..,,,... .

R=O,66 1= 0,33

• I

•I " t1'1''' ' " ' .1," .1.

. _ - _..... .. ..18X1 1aX3 18X9 30XI 30X330X9 60X160X360X!f 120X1 120X3 120X9

l aX11 8X3 18X930X l 30X330X9 60X 1GOX360X9 t20Xt 120X31 20X9

-200/.

-30%

·100/.

·1000/.

Grupos desaco plados

25°/.

20%

'0_01 [_ OisP. losll

10%

5% !I f rl!JjIJ If1aX1 1aX3 30X I 30X3 GOXl 60XJ 120Xl 120X3

0%

-10%

-20% ·I-30% .·400/.

·500/.to_UB

·60%

·70°/.

rI " I oI-aO% I , ;:....

Xi-90%,".J.

n u'", I , UV '

-100% , '.J .

18X1 rsxa JOX1 JOX3 60X1 60X3 120X1 120X3

Grupos desacoplados

R = 0,99 t =O

-50%to_UB

O%t------ - - - - - - - ---------,

-10%

-20%

6. CONCLUSÃO

A prin cipal contribuição deste artigo éapresentar um modelo para um problema de pro gra-mação da produção em máquinas paralelas com umasérie de cara cterísticas que o torna muito próximo avários problemas práticos encontrados em pro cessosprodutivo s reais . Por outro lado , isto o torna bastantecomplexo quanto a sua resolução. São propostos trêslimitantes que são usados para achar so luções atra-vés da reso luçã o de um problema de busca em gra-fos. O primeiro deles ga rante o ótimo do modelo . Os

116