Métodos Heurísticos e Meta-Heurísticos para a Resolução do Problema de Sequenciamento de Ordens de Manutenção Preventiva de Longo Prazo / Heuristic and Meta-Heuristic Methods to Resolve the Long-Term Preventive Maintenance Scheduling Problem

Arthur Almeida Santos; Alexandre Xavier Martins; Marcone Jamilson Freitas Souza; Rafaela Heloisa Carvalho Machado

<page>

<par>

<line> Centro Unv*rsitário Santo Agostinho </line>

</par>

<par>

<line> www*.fsanet.com.*r/revista </line>

<line> ISSN Impresso: *806-6356 I*SN Ele*rônico: 2317-2983 </line>

</par>

<par>

<line> *étodos Heurísticos e Meta-Heurí*t*cos para a *es*lução ** Problema de Se**enciamento *e </line>

<line> Ordens de M*nute*ç*o Prevent*va de Longo Pr**o </line>

<line> Heu*istic and *eta-*euris*i* Method* to Resolve the Long-T*rm *reventive Main***ance </line>

<line> Sche*uling Problem </line>

</par>

<par>

<line> A*thur Alme*da Santos </line>

<line> Me*trado em Engenha*ia *e Produção pela *niversid*de *ederal d* *uro Pre*o </line>

<line> G*aduação em E*g**haria de *rodução pela Uni*e*sidade Fe*eral de Viço*a </line>

<line> arthur.jf.mg@hotm*il.c*m </line>

<line> Alexandre X*vie* Ma*tins </line>

<line> *outor em E*ge*h*ria Elétr*ca p*la Universida*e Federal de Minas Gerais </line>

<line> Profe*sor da Universi*a*e *e*er*l de O*ro P**to - UFOP </line>

<line> xmartins@*f*p.edu.*r </line>

<line> Marcone J*milson F**i*as Souza </line>

<line> Doutor em Engen*aria d* S*stemas e C**p*taç*o pela Un*versidade **deral do *io de Ja*eiro </line>

<line> Prof*ssor *a Univers*dade Fed*ral de *uro Preto - **OP </line>

<line> R*fae*a *eloisa Carvalho Mac*a*o </line>

<line> Douto*ado em E**enhar*a de Produção pela Uni*ersid**e Federal de Minas Gerais </line>

<line> *rofesso*a da Universidade Federa* de Viç*s* - UFV </line>

<line> rafae*a.h.machad*@gma*l.*om </line>

</par>

<par>

<line> E*dereço: Arthu* Almeida Santos </line>

</par>

<par>

<line> Editor-C*efe: Dr. Tonn* Ke**ey de Al*ncar </line>

</par>

<par>

<line> M*nleva*e - *G, Bra*il. </line>

<line> Rodrigues </line>

</par>

<par>

<line> *lexandre Xavie* Martins </line>

</par>

<par>

<line> *rtigo receb*do em 07/07/2*23. Última </line>

<line> versão </line>

</par>

<par>

<line> Monlevade - M*, Br*si*. </line>

<line> recebida em 01/08/2023. Aprova*o em 02/*8/20*3. </line>

</par>

<par>

<line> Endereço: </line>

<line> Marcone Jamils*n Freitas S*uza </line>

</par>

<par>

<line> *ua Trinta * Seis, Nº 115, Loanda, 35931-008, Jo*o </line>

<line> Avaliad* *elo sistema Triple Review: Des* R**ie* a) </line>

</par>

<par>

<line> Monlev**e - MG </line>

<line> *el* E**tor-Chefe; * </line>

<line> b) Doub*e Blind R*view </line>

</par>

<par>

<line> Endere*o: </line>

<line> *afaela *eloisa Carvalho Machado </line>

<line> (*v*l*ação cega po* dois avaliador*s ** á*e*). </line>

</par>

<par>

<line> *m 7 - Zona Rural, *G-230, Rodoviário, 3*81*-000, </line>

</par>

<par>

<line> R*o Parana*ba - MG </line>

<line> Revi*ão: Gram*tical, Normativa </line>

<line> e de Formatação </line>

</par>

<par>

<line> AGENC** DE FOMENTOS: Os a*tores agradecem à CAPES, a* C*Pq, à FAPE*IG e à UFOP *e*o *poio ao </line>

<line> desenvolvimento dest* trabalh*. </line>

</par>

</page>

<page>

<par>

<line> A. *. Santos, A. X. Martins, M. J. *. Sousa, R. *. C. *achado </line>

</par>

<par>

<line> RESUMO </line>

</par>

<par>

<line> O suces*o de *ma empresa *eq*er o bom fun*ionamento * a confi*b*li**de d* s*u* *istema* </line>

</par>

<par>

<line> com *á**ina* e eq*i*amen*os em *om estado. P*r* *sso, é es*encia* um bom p**n* </line>

</par>

<par>

<line> manuten*ão preventiva, que tende a *icar mais complexo com o aumento do *úmero de </line>

<line> equipamentos e o ho*izonte de planejamento. O objetiv* deste *studo é desenvolver </line>

</par>

<par>

<line> a*goritmos *eta-*eurís*i*os ef*cientes para tratar Pr**lem* de Planeja*ento de Orden* o </line>

</par>

<par>

<line> Manutenção Preventiva de Longo Pr**o (PPOMPLP). O trabal*o se inicia com </line>

</par>

<par>

<line> dese*volvi*ento de uma heurís*ica construtiva e de alocação, *eguido *o de*envolvimento de </line>

<line> algor*tmos de *usca local * meta-heurí*tico* base*dos em *reedy Randomized Adap*ive </line>

<line> Search Procedu*e (G*ASP), Simulate* Annealing (SA) e Itera*ed Local Sea*ch (ILS). O </line>

<line> desemp*nho dos algori*mos desenvolvidos **i comparado e*tre eles e com *s da literatura. </line>

</par>

<par>

<line> Para a *a*ibrag*m * validação dos </line>

<line> algori*mos meta-h*urísticos, foram r*sol*i**s instâncias </line>

</par>

<par>

<line> fi*tícia* pequenas. *pós a ca*ibragem, os algoritmos *et*-h*urí*ticos for*m aplicados </line>

</par>

<par>

<line> *nstâncias m*io*es e à *eal. Os ex*er*mentos mostrar** que o ILS **i </line>

</par>

<par>

<line> algoritmo d* m*lhor desem*enh* e s** resultado na ins*â*cia real foi 40,5%, melhor qu* </line>

</par>

<par>

<line> apresenta*o na literatu*a. </line>

</par>

<par>

<line> Palavr*s Chave. Pla*ej*men*o de Ma*utenção de Lo*go Pra*o. Grasp. Simulated A*neal*ng. </line>

<line> *ter*ted Local Se*rch. Met*-Heur*s*icas. </line>

<line> ABSTRA*T </line>

<line> *he *u*cess *f a compan* requires *he prop*r functio*ing and reliability of *ts systems *ith </line>

</par>

<par>

<line> mach*nes and equipment in go** condition. F*r this, go*d preventive maintenance plan is a </line>

<line> e*sential, wh*ch ten** to *ecome more com*lex as t** *umber *f equipm*nt and the plannin* </line>

<line> hori*o* increa*e*. Th* pre*ent w*r* aims to develop efficient meta-h*uristic algor**hms for </line>

<line> the Long-T*rm Preventi*e Ma*ntena**e *cheduling *roblem (PP*MPLP). The work be*in* </line>

<line> with the development of a c*nst*uctive *nd allocati*n heuristi*, *ollowe* by the de*elopm*nt </line>

<line> of local search and meta-heur*stic a**orithms bas*d on Gr*e** *a*d*mize* A*aptiv* Search </line>

<line> Proc*dur* (GR**P), Simulate* Annealing (SA), and Iterated Loca* Se*rc* (ILS). The </line>

<line> performance of the pr*posed algor*thms was compared amo*g *he*sel*es and with *ho*e of </line>

<line> *t**r studies in th* l*terature. Small fict*tious instances wer* us*d *o calib*ate *nd valida** th* </line>

</par>

<par>

<line> m*ta-heurist*c *lgorithms. After c*lib*****n, they w*re applied to solve lar*er </line>

</par>

<par>

<line> instances. The experiments **owed that t** I*S was th* best-per*or*ing *l**rithm, *n* </line>

</par>

<par>

<line> res**t for the re*l instance was 40.5% bet*er than tha* *re*e*ted *n the literature. </line>

</par>

<par>

<line> K*ywords: Lo*g-Ter* Maintenanc* *cheduling. G*asp. Simulat*d Annealin*. Ite*at*d *oc*l </line>

<line> Search. Meta-He**i*tics. </line>

</par>

<par>

<line> w**4.*sanet.com.b*/*evist* </line>

</par>

</page>

<page>

<par>

<line> *étodos Heurísticos * Meta-He*rí*ticos par* a Resolução do P*oblema de S*quenciamen*o *e O*den* </line>

</par>

<par>

</par>

<par>

<line> As atividad** d* *anuten*ão preventiva </line>

<line> são *ssenc*ais *ara dispon*bilid*d* a </line>

</par>

<par>

<line> **nfia*ilidade dos sistemas *ent*o da indústria. *s *ais *iver**s equipame*tos, </line>

</par>

<par>

<line> est**ras tran*p*rt*d*ras a empilhadeiras, *ossuem </line>

<line> um cronog**m* de ma*ut*nçõ*s q*e </line>

</par>

<par>

<line> devem ser </line>

<line> r*al*za*as com *ert* **equênci*, geralment* sug*ridas pelo fabricante. As </line>

</par>

<par>

<line> atividades de manute*ção p*eventiva podem ser inspeção, *impeza, lubrificação, *juste, </line>

<line> alinhamento ou *ubstitu*ção de componente* de**astado* (E*RAHIM*POUR et *l., 2015). </line>

<line> A m*nu*e*ç*o pre*entiva é *spe*i*lmen*e importante par* evitar que oco*ram </line>

</par>

<par>

<line> f**has n* *p*raç** que pos*a* causar *anos consideráv*is *o si*te*a, com* </line>

</par>

<par>

<line> máquina, ou ao ambiente, com* pol**ç*o, explosões, per*a *e informa**o (LEVITIN et al., </line>

<line> 20*1). Normalmen*e, essas ativida**s de man*te*ç*o pre*entiva *ec*s*itam de *ma equipe </line>

<line> especia*izada e **o execu**das e* um equipam*n*o especí*ico. Isso fa* com que um *úm*ro </line>

<line> limita*o de ativ*dade* p*s*a ser exe*utado dent*o de d*terminado período de tempo. </line>

</par>

<par>

<line> Pa*a que o maior </line>

<line> *úm*ro d* ati*idades ou *ara qu* as ma*s importantes sejam </line>

</par>

<par>

<line> executadas, é n*c*ssário que se *ealize a program*ção da* *rden* de manutenção p*eve*tiva. </line>

<line> A**sar da programaçã* da m*nutenç** preventiva *er um tema a*plamente abor*a*o, </line>

<line> alguns est*dos *o** Lee e Cha (*016) e Wang e Miao (20*1) trabalha* apen*s c*m </line>

<line> mo*elos para pre*isã* *as f*lhas e não com mo*elos fo*ados *a prog*a**ção das ordens de </line>

<line> manutenção preventiva. </line>

</par>

<par>

<line> Ou*ros traba*hos como *edja*i (2015) e Al*a*es (2*22) tratam *e model*s p*ra </line>

</par>

<par>

<line> r**olu*ão de proble*as de *ro**amaçã* d* ordens de *an*tenção. Hedjazi (2015) trabalha </line>

<line> com um problema ** p*ogramaçã* d* orde*s de manutenção em m*quinas em par*lelo *ã* </line>

</par>

<par>

<line> rel**i*nadas. Os operad**es, *ependend* *a *ab*l*dade, </line>

</par>

<par>

<line> tem*o dife*ente. As ordens podem s*r alocadas com *traso, e o *bjetivo é min*mizar a mé*ia </line>

<line> ponde*ada dos **mpos de atraso. A*far*s (2022) prop*e um problema de s*quenciamen*o de </line>

<line> or**ns de manutenção preventiva em máquinas em paralelo du**nte u*a pa*ada *e máquinas </line>

</par>

<par>

<line> para a manutenção. *esse c*so, a programação é feita de forma a en*urt*r o *erí*do </line>

</par>

<par>

<line> parada. </line>

</par>

<par>

<line> N* entanto, esses tr**alho* **o trata* a programaçã* *e o*dens de manu*enção </line>

</par>

<par>

<line> envol*endo o dimensio*amento das equi*es, </line>

<line> as janel*s de </line>

<line> a*endimento das *rdens, </line>

</par>

<par>

<line> ha*ili*ade das equi*es em execu*ar essas ordens, * disponi*ili*ade dos equipamento* usados </line>

<line> *ar* *ea*izar es*as *rdens e o long* pra*o de programação. </line>

<line> Re*. *SA, Teresina PI, v. 20, n. 1*, ar*. 9, p. 175-202, out. 2023 www4.f*anet.c*m.br/revi*ta </line>

</par>

</page>

<page>

<par>

<line> *. A. Santos, A. X. Mar*in*, M. J. F. Sousa, R. H. C. Machado </line>

</par>

<par>

<line> De noss* conhe*ime*t*, o úni** traba*h* en*ontrado na l**eratura </line>

<line> que trata des*as </line>

</par>

<par>

<line> *aracterísticas é o </line>

<line> de *q*ino et al. (2019), que defi** o *r*blema de P**nejam*nto de </line>

</par>

<par>

<line> Ordens d* Ma*utenção *reventiva *e Lon*o Prazo (PPOMPLP). O PPOMPLP </line>

</par>

<par>

<line> considerado um problema de </line>

<line> p*og*amaç*o de ma*u*enções p*ev*ntivas em máquina* em </line>

</par>

<par>

<line> para**lo, sendo discuti*o* pelos *utores por me*o de uma abo*dagem *eurísti*a. Os métodos </line>

<line> heurí*tic*s *ão *plicados po*q*e esse pr*blema é NP-difícil, uma *ez que um caso particula* </line>

<line> de*e, o d* se*uenciamen*o em uma má*uina, * NP-difícil (QI et al., 199*). </line>

<line> Em s*u estudo, Aquino et a*. (20*9) propuse*am *ma formulação de programa*ão </line>

<line> mat*mática (Mixed Integer Linear Progr*mming MILP), ass*m *om* algoritmos meta- </line>

<line> *eu*ísticos b*se*dos em Simulat*d Ann**l**g (SA), Variable Neighborhood *earch (VNS), </line>

<line> Multi-*tart Variable Neighborhood Se*rc* (MSVNS), Bi*sed Random-Key Genetic </line>

<line> Algorith* (BRKGA) e *ias*d Rando*-*ey M*metic Al*o*ithm (BR*MA) *ara *ratar </line>

<line> inst*ncias m*i*re* do p*oblema. No presen*e trabalho são a*resentados, além de um </line>

<line> algo*i*mo b*seado e* SA, a*gori*mos base*dos em Gr*e*y Randomized Adaptive Search </line>

<line> Pr*ce*u*e (GR*SP) e Iterated Lo*al Search (ILS), *s q*a*s t*m si*o us**os *om sucess* </line>

<line> na r*solução de vários o*tros problemas de otimi**ção combi*atória (ERTEM e* al., 2***; </line>

<line> DELORME *t a*., 2021). </line>

<line> Este trabalho *em por o*jetivo des*nvo*ver *lg*ritmos *eta-h*urísticos eficie*tes para </line>

<line> tratar o PPO*PLP, apl*cado a *m cenário real de uma e*presa mineradora, assim como *m </line>

</par>

<par>

<line> Aquino </line>

<line> pr*põe-se inicia*men*e um *éto*o heurísti** construtivo, </line>

</par>

<par>

<line> c*mposto por duas etapas: s*quenciame**o e a*ocação. N* sequencia*en*o, defin*-se </line>

</par>

<par>

<line> seq*ência em que serão al*cadas as ordens; *a etap* d* *lo*açã*, as or**ns são alocadas à* </line>

</par>

<par>

<line> res**ctivas </line>

<line> equipes ao </line>

<line> longo </line>

<line> do período de *rogramação. A parti* da solução o*tida </line>

</par>

<par>

<line> h*urística con*t*utiva, são *esen**lvido* m*todos *e busca local para refin*r *s** </line>

</par>

<par>

<line> Esses métodos </line>

<line> de co*struçã* e r*finamento são, </line>

<line> entã*, inco*p*rados aos algoritmos met*- </line>

</par>

<par>

<line> he*rístico* GR**P, SA * ILS. Para avaliar os algo*itmo* d*senvolvidos, são usad*s inst*ncia* </line>

<line> reais, assim *o*o i**tânc*as f*ctícias baseadas no mesmo contexto de*sas i*stâncias rea*s. Os </line>

<line> re*ultados obtid** sã* comparados en*re si e com a lite*atura. </line>

<line> Este trabalho está or*aniz**o da seguinte forma: a Seção 2 a*r*sen*a o pro*lema de </line>

</par>

<par>

<line> pesquisa. A Seção * apresent* o referencial </line>

<line> teór**o, contextu*lizando o problema de </line>

</par>

<par>

<line> programação de *anutenções heurísticas e *eta-heurísticas. A Seção * apresenta </line>

</par>

<par>

<line> metodolog*a adot*da no estudo. A* S*ç*** 5 e 6 </line>

<line> *pre*entam as *eurísticas construtivas e </line>

</par>

<par>

<line> heurística de aloca*ão. *a Seção 6 apresentam-se *s a*goritmos meta-heurísticos u**lizado*, </line>

</par>

</page>

<page>

<par>

<line> Métodos H*urísticos e Meta-Heurís*icos p*ra * Resolução do Pro*lema de S*q*encia*ento de Ordens </line>

</par>

<par>

<line> e na Seção 8 os resultados obtidos. Po* fim, n* Seçã* 9, são a*res*ntadas as co*clusões * as </line>

<line> *ugestões para traba*hos futuros. </line>

<line> 2 REFERENCIA* TEÓ**CO </line>

<line> 2.1 Proble*a de *esqu*sa </line>

<line> * P*O*PLP *o*sidera que ex*stem diferen**s grup*s de **uipes de man*tenção </line>

<line> co* competências d*ferent*s. Por e*emplo, um grupo de manutençã* m**ânica, out*o de </line>

<line> ma*utenção *létr*c* e diversos outros grupos com *if***ntes especialidade*. Cada grupo </line>

<line> possui um *ú*ero espe*ífico d* equip*s **m u*a determ*nada di*ponibilidad* de te***, e </line>

</par>

<par>

<line> não pode reali*ar mais d* uma manutenção *m para*e**. As manutenções </line>

</par>

<par>

<line> *erem r*a*izadas possuem *omo par*metros um </line>

<line> *rau de prioridade, * tempo de início e de </line>

</par>

<par>

<line> fim em qu* podem ser realizadas, sendo *ssa uma janela d* tempo e* que a ma*ute*ção pode </line>

</par>

<par>

<line> ser pr*gram*d*. Possui t*mbém </line>

<line> uma duração, um ti*o *e manut*nção, *ue *specifica qual </line>

</par>

<par>

<line> g*upo de manutenção é *apaz d* realiza* ma*utenção e a </line>

<line> qual equipa*ento a </line>

</par>

<par>

<line> m*nutençã* deve u*ili*ar. </line>

</par>

<par>

<line> A função objetivo vi*a * mi*imização *o núm*ro de m*nutenções não realizada*. </line>

</par>

<par>

<line> Ca*a ordem não a*o*ada g*ra um cu*to *e te*ceirização para a e*presa. Esse </line>

<line> custo e*tá </line>

</par>

<par>

<line> apresentad* na modelagem do p*oblema como pe*a*idade. O valor da *enalidade f*i de*inido </line>

<line> como *endo * *empo de duração das orden* não alocad*s mult**lica*o pela sua prio*idade. </line>

<line> O proble*a real do tipo PPOMPLP, tratado nes*e trabalho, vem d* uma das plantas </line>

<line> de beneficiamento de minério ** fer** de uma multinacional q*e r**liza * planejamento de </line>

<line> todas as ordens de manutenção para o período de um an* (52 *e*ana*). Quando a empre*a </line>

<line> *ealiza o p*ano *e manutenção, cada área da manuten*ão (ex.: mecânica, elétrica) reali*a seu </line>

<line> p*ó*r*o plano bas*ad* apenas na disponib*lidade do eq**pamento *l*o da manute*ção. E**e </line>

</par>

<par>

<line> plano é inserido no *i*tema ERP (do inglês Enterp*ise *esource Planning, um siste*a </line>

</par>

<par>

<line> g*stão em*resari*l) utilizado </line>

<line> pela empresa; porém, esse sistema não contém informações </line>

</par>

<par>

<line> r*ferentes às restri*ões de c*pa*idade *r**en*es n* sistema real, como, por exemplo, </line>

</par>

<par>

<line> di*poni*ilidade de *ão d* ob*a. *ntão, a programação das manut*nçõ*s * aj*stad* </line>

<line> *en*almente para *ada e**ipe, con*orme a di*po*ibili*ade de mão de obra e equi*a**ntos </line>

<line> necessário*. Est* método de p*anejamento de longo praz* fa* co* que, em geral, apenas </line>

</par>

<par>

<line> 50% d*s ordens </line>

<line> d* manutençã* sejam atendidas. O restante das *rden* </line>

</par>

<par>

<line> www4.fsan*t.com.br/revis*a </line>

</par>

</page>

<page>

<par>

<line> A. A. San*os, A. X. Mar**ns, M. J. F. Sou*a, R. H. C. Machado </line>

</par>

<par>

<line> ter*eiri*ad*, o *ue re*ul*a em mais custo par* a empre**. O pro*lema re** envolve, </line>

<line> normal*en*e, ma*s d* 3300* ord*ns d* manutenç*o pr*ventiva por an*. </line>

<line> As t*cnicas de sequ*nc*amento podem se* aplicada* para a elabor*ç*o de planos de </line>

<line> m*nutenção. Problema* de seq*enciamento são *escritos pela aloca**o de n at*vida**s a um </line>

<line> númer* m de m*qui*as. Est* tipo de pro*lem* pod* ser descrito pelo tr*o | * | (Pi*edo, </line>

<line> **16). O c*mp* des*reve o ambi*nte *a máqu**a. O cam*o detalha a* carac*erís*i**s de </line>

<line> processamen** * as re*trições. O **mpo conté* os objetivos a sere* otimi*ad*s. *ara cad* </line>

<line> u* *esses cam*os, adota-s* uma termin*logia de acordo com o problem* em evi*ência. </line>

<line> Ess* *ermin*lo*ia de Pinedo (2016) fo* util*zada *or Aquino et a*. (20*9) para </line>

<line> representa* uma simplificaçã* *o PPOMPLP como um pr*blema Pm | *jMj | . U* ponto de </line>

<line> d*scordância é qu*nto ao campo , um* *ez que Aquino e* al. (20*9) **nsi*e*a* *ue o *bje***o </line>

</par>

<par>

<line> de otimização s*ria minimizar a mão </line>

<line> de ob** necessária </line>

<line> par* executar o ma*or número </line>

</par>

<par>

<line> taref*s, não havend* notação correspondente, * campo perman**e . Porém, o problema em </line>

</par>

<par>

<line> q*estão possui </line>

<line> dois objeti*os d* *timiza*ão: minimizar o custo *elacionado às ordens de </line>

</par>

<par>

<line> *anutenção não a*end*das e mi*imizar o custo d* m** de obra. O cus*o de mão de obra tem </line>

</par>

<par>

<line> grandeza muito menor comparado ao custo de ca*a *anutenção não r*alizada; </line>

</par>

<par>

<line> port**t*, o s*gund* *ode ser considerado o *ri*cipal objetivo de otimiza*ão. </line>

<line> Se*uindo essa m*sma ter*i*ologia de Pinedo (2016), o presen*e t*abalho abord* um </line>

<line> *r*blema Pm | r*Mj | . O campo Pm r**ere-se * *r*blemas com m m*quinas </line>

<line> paralelas, onde rj *i*nif*ca que * *tividade j não pode começar seu *roc*ssame*to an*es da </line>

<line> d**a *e lançamento. Mj é utilizado para probl*m*s de máqui*as par*l*las, nos q*a*s nem toda* </line>

</par>

<par>

<line> m máquinas s*o capazes *e process*r todas as atividades. * últ*** *ampo, </line>

</par>

<par>

<line> à média p*nde*ad* dos tempos de atraso. A*esar d* *s manutenções não poderem se* </line>

</par>

<par>

<line> alocadas com atraso, </line>

<line> as or**ns não a*ocadas **t*a* </line>

<line> como custo pa*a a funçã* objet*v*, </line>

</par>

<par>

<line> *o*ma ponde**da, de acordo com *ua *riorida*e. </line>

</par>

<par>

<line> Problemas de sequenciamen*o de *áquin*s *m p*ralelo têm sido e*t*dados </line>

</par>

<par>

<line> dé*adas. Alidaee * *osa (199*) </line>

<line> estão en*** os primeiros * p**lic**em u*a abordagem </line>

</par>

<par>

<line> heur*st*ca para reso*ução desse tip* de </line>

<line> problema. Porém, os autor** tratam *p*nas *o </line>

</par>

<par>

<line> s*quenciamento da produção. Pr*blemas de sequenciamento de pro*u*ão e de man*tenção </line>

<line> têm *ido tratados d* forma difer**te, tanto na lite*atura quanto na i*dú*tria. *pesar de serem </line>

</par>

<par>

<line> problemas </line>

<line> seme*h*ntes, as programações podem ser </line>

<line> confli*antes *orque a progra*a**o </line>

</par>

<par>

<line> manutençõ*s p*event**a* interfer* </line>

<line> na progr*mação de pr*dução e **ra a *e*lização da </line>

</par>

<par>

<line> ma*ute*çã* preventiva, o equip**ento deve cessar a *rodução (Avalos-R*sales et al., 20*8). </line>

<line> Rev. FS*, Te*esina, v. 20, n. 1*, art. 9, *. 175-202, out. 2023 w*w4.*sanet.com.br/revista </line>

</par>

</page>

<page>

<par>

<line> Métodos *euríst*cos e Meta-Heurísticos para a Resolução do Pro*le*a d* Sequenciamento de Ordens </line>

</par>

<par>

<line> A Tabela 1 apr*senta os pr*ncipai* *studos que tratam de progr*ma*ão de </line>

<line> manutenç*e* prev*nt*vas em máq*inas em *aralelo por m*i* de uma abo**agem *eurística. </line>

</par>

<par>

<line> *s estudos f*r*m clas*ifi*ados em </line>

<line> relação a* tipo de máq*ina e de prog*ama*ão. Entre os </line>

</par>

<par>

<line> estudos citados, a maioria foc* na p*ogramação de produção em conjunto com as </line>

<line> man*tenções. A*é* disso, em *e*ação aos *roblemas de m*quinas em p**alelo, pa*t* dos </line>

<line> t*abalhos trat* de um subtipo, *ue são as *áquinas em paralelo não rel*cionadas. Em relaç*o </line>

<line> ao "*bj*tivo a minimizar", são *presen*ad*s q*ai* os indicadores de desempenh* f*ra* </line>

<line> utiliza*os na função objetivo. A *aio*ia t*m *omo objetivo *in*mizar o m*kespan, **e é o </line>

<line> temp* t*tal de proce*samento. </line>

<line> Tabela 1 - Revi**o De Literat*ra. </line>

</par>

<par>

<line> Tipos de </line>

</par>

<par>

<line> Máquinas </line>

<line> programação </line>

<line> m*n*mizar </line>

<line> média pon*era*a </line>

<line> paralelas n*o </line>

</par>

<par>

<line> dos tempos de </line>

<line> rel*ciona*as </line>

<line> construtiva </line>

<line> atraso </line>

</par>

<par>

<line> FAKHER; </line>

<line> produção e </line>

<line> alg*ritm* ge*ético </line>

</par>

<par>

<line> NOURELFA*H; </line>

<line> paral*las </line>

<line> m*nu*enção </line>

<line> e tabu search </line>

</par>

<par>

<line> G*NDREA* (2016) </line>

</par>

<par>

<line> RUIZ-TORRES; </line>

<line> idênticas em </line>

<line> produção * </line>

<line> heurísticas </line>

</par>

<par>

<line> PALETTA; </line>

<line> makespan </line>

<line> manutenção </line>

<line> construtivas </line>

</par>

<par>

<line> algoritmo memético </line>

</par>

<par>

<line> UPASANI et al. </line>

<line> idêntica* em </line>

<line> manutenção </line>

<line> *ustos </line>

</par>

<par>

<line> *aralelo </line>

<line> *ptimizat*on </line>

</par>

<par>

<line> AVALOS-ROSALES </line>

<line> paralelas não </line>

<line> produção e </line>

<line> makespan </line>

<line> mult*-start </line>

</par>

<par>

<line> rela*ionadas </line>

<line> manut*nção </line>

<line> three-level particle </line>

<line> idênti*as em </line>

<line> p**dução e </line>

</par>

<par>

<line> sw*rm optimization </line>

<line> pa*alelo </line>

<line> manute*ção </line>

<line> cooperative co- </line>

<line> paral***s </line>

<line> produção e </line>

</par>

<par>

<line> evolutio*a*y </line>

<line> sinc*onizada* </line>

<line> ma*utenção </line>

<line> genetic algori*hm </line>

</par>

<par>

<line> ALFARES; </line>

<line> idênticas em </line>

<line> produção * </line>

</par>

<par>

<line> MOHAMMED; </line>

<line> paralelo </line>

<line> m*nutenção </line>

</par>

<par>

<line> GHALEB (2021) </line>

</par>

<par>

<line> DELORME; IO*I; </line>

<line> paralela* não </line>

<line> produção e </line>

</par>

<par>

<line> MENDES (2*21) </line>

<line> **lacionadas </line>

<line> ma*utenção </line>

<line> produção e </line>

</par>

<par>

<line> paralelas </line>

<line> makespan </line>

<line> m*n*tenção </line>

<line> black hole </line>

<line> heu*ística </line>

</par>

<par>

<line> ALFARES (2022) </line>

<line> paralela* </line>

<line> ma*utenção </line>

<line> co*strutiva </line>

</par>

<par>

<line> ERTEM et al. (*02*) </line>

<line> *aralelas </line>

<line> *an*tenção </line>

</par>

<par>

<line> Rev. FSA, Teresina PI, v. 20, *. 1*, ar*. 9, p. 175-*02, *ut. 2023 </line>

<line> www4.*sanet.com.br/revis** </line>

</par>

</page>

<page>

<par>

<line> A. A. S*n*os, A. X. Marti*s, M. J. *. Sousa, R. H. C. Ma*hado </line>

</par>

<par>

<line> Na Tabela 1, a c*lun* "Abordagem" in*ica qu*i* abordagens heurísti*as f*ram </line>

<line> aplicadas para resolução *o pro*le*a de prog*amação de ma*utenções prev*nt*vas *m </line>

<line> máquinas *m p*r*lelo. *oram aplicadas abordagens v*ri*das *ara e*s* tipo de *roblema. As </line>

<line> h*urística* mais apl*c*das foram a* *eurísticas co*strutivas e a VNS. Em *elação às m*ta- </line>

</par>

<par>

<line> h**rísticas, GRASP, SA e ILS, fo*os deste **tudo, dest*c*-se *studo d* D*lor*e et al. o </line>

</par>

<par>

<line> aplicação do ILS, e Ertem et al. (2022), </line>

<line> do GRASP. Não </line>

</par>

<par>

<line> foram ***tac*dos e*tudos </line>

<line> *e programação de manutenções preventivas </line>

</par>

<par>

<line> *á*uinas em paralelo aplicand* a meta-heurí*tica *A. </line>

<line> O I*S é amplamente aplicado à *esolu*ão de *roblema* de pro*ramação de </line>

<line> *rod**ão, qu* é um pro*l*ma *n*logo a* prob*ema d* programação de ordens ** manut*n*ão </line>

</par>

<par>

<line> preventiv* (XU </line>

<line> et al., 2*19). Delorme </line>

<line> e* al. (2021) abo*dam um problema de </line>

</par>

<par>

<line> sequenc*amento *e or*ens de pr*dução * ma*utenções *reventivas em m*quinas em paralelo </line>

<line> nã* rela*ionada*. O objetivo é min*mizar o makespan. Os autor*s utili**m o MI*P pr*posto </line>

</par>

<par>

<line> al. (2016) e propõem quatro </line>

<line> no*os mod*l*s matemáticos </line>

<line> partir d* </line>

</par>

<par>

<line> *iferentes po*tos de </line>

<line> do problema. Os autores propõem *ambém um </line>

<line> al**ritmo meta- </line>

</par>

<par>

<line> heu*ís**co ILS para resol*ção do problem*. D*nt*e o* *od*los e*ato*, uma </line>

<line> *ormula*ão </line>

</par>

<par>

<line> ba**ada em flu*o *e a*co obteve melh*r d*sem*enho. O método *LS teve resultados </line>

<line> compe*itivos para *s inst*ncias grand*s *o probl*ma. </line>

<line> Outra técnica d* r*pida implementação * b*ns resu*tados é o G*ASP. O GRAS* é </line>

</par>

<par>

<line> uma **ta-h*ur*sti*a **lti-start que cons*ste de duas fases: a *ase </line>

<line> construt*va, na qu*l uma </line>

</par>

<par>

<line> soluç** viável é produzida, e a segu*da fa*e, que * um mét*do de *usca local, que busc* </line>

</par>

<par>

<line> u*a solução </line>

<line> óti** local (FEO; R*SE*DE, 1995). Ertem *t al. (*0*2) ab**dam um </line>

</par>

<par>

<line> *roblema </line>

<line> de sequenciamento de or*ens de manute*ção pr*v*n*iva com máquina* </line>

</par>

<par>

<line> p**al*lo. O objetivo minimizar o makesp*n que, nesse é </line>

<line> caso, * equivalente a m**imiza* </line>

</par>

<par>

<line> número de t*re*as em atraso. Co*o mét*do de re*olução, são propo*to* dois modelos M*LP </line>

</par>

<par>

<line> pa** res*lução da* instânci*s peq**nas </line>

<line> * calibragem </line>

<line> das *eurísticas. Do** métodos </line>

</par>

<par>

<line> he*rísticos construtivos foram *ropos*os, *endo * primeiro d*pen*ente de uma </line>

<line> s*lução </line>

</par>

<par>

<line> inici*l gerado por um mét*do exato * segun*o q** utiliza um métod* de **plor*ção das o </line>

</par>

<par>

<line> vizin**nças semelha*te ao GRASP. Apesar de </line>

<line> a* heurí*ticas nã* atingirem v*lores óti*os </line>

</par>

<par>

<line> em toda* as instânci*s peq*en*s, com* o MILP, e*as a**ese*t*m m*lhor dese*pen*o nas </line>

<line> instânc*as grandes. A segunda heurística apresen*a res*ltados melhores que a primeir*. </line>

</par>

<par>

<line> O co***ito de SA foi a*licado </line>

<line> pela primeira vez para resolução de problemas de </line>

</par>

<par>

<line> oti*ização por K*rkpa*rick *t *l. (1*83). O método é um* meta-heurí*tica i**pirad* no </line>

</par>

<par>

<line> pro*esso *ísico de resfriamento len*o de u* materia*, *o qual solução atual é *odif*cada a </line>

<line> Rev. F*A, T*resina, v. 20, n. 10, art. 9, p. 1*5-202, out. 2023 *ww4.*sane*.com.br/revista </line>

</par>

</page>

<page>

<par>

<line> Mét*d*s Heurísticos e Meta-H*urís*icos para a R*solução do Pr**lema de Sequenciamento de **den* </line>

</par>

<par>

<line> iterat*vam*nte com b*se em movim*ntos aleatóri*s * aceita*ão *e soluções pio*es, d* ac*r*o </line>

<line> c*m uma proba*ilidade d*te*min*da pel* te*p*ratura. Ao longo do tempo, a temperatur* </line>

</par>

<par>

<line> algoritmo * convergi* para um* solução ótima ou aproximadamente </line>

</par>

<par>

<line> ótima. </line>

</par>

<par>

<line> 3 ME*ODOLOGIA </line>

<line> Esta pesq*isa segue as etapa* conforme e*q*ema *a *igura 1, que se in**ia p*la *efi*ição do </line>

</par>

<par>

<line> escop* </line>

<line> da p*squisa. ** sequên**a, * realizado o desenvolvimento da heurística constru**va, </line>

</par>

<par>

<line> que prod*z uma *rogram*ção inicial. Co* a sequênc*a d*fin**a pela he*rística **nstrutiva, a </line>

<line> heurística de al*cação é utilizada *ara estruturar as at*vid*d*s de cada *quipe ao longo do </line>

<line> período de pr**r*mação. *s res**tados des*a heu*ística constru***a f*ram com*ar*dos ao* </line>

<line> resultados do *odel* *xato, par* sua validação. </line>

<line> *igu** 1 - Es*u*ma d* metodologia </line>

</par>

<par>

<line> Posteriormente, for*m de*en*ol*idos os **t**o* de busca local fi*st improvement e </line>

</par>

<par>

<line> heurísticos são *ubordinados </line>

<line> *lgoritmos meta- </line>

</par>

<par>

<line> heurísticos. Por*anto, a etapa seguint* é a implementaç*o *os *lgoritmos me*a-heurísticos </line>

<line> GRA*P, SA e ILS par* resol*ção do PPO**LP. A parametri*a*ão de*ses *lgoritmos **i*iza </line>

<line> Rev. FSA, T*resina PI, v. *0, n. 1*, a*t. 9, *. 175-202, ou*. *023 www*.fsanet.c*m.b*/revista </line>

</par>

</page>

<page>

<par>

<line> A. A. Sa*tos, A. X. Ma*tin*, M. J. F. *ousa, R. H. C. *achado </line>

</par>

<par>

<line> o pacote IRACE (*ópez-Ibáñe* et al., 2016), rea*iz*ndo rod*das teste com u*a amos*ra das </line>

</par>

<par>

<line> *ns*ân*ias fi*tícias. O* *alores </line>

<line> d*s parâmetro* testados para cada algo*it*o meta-he*rísti*o </line>

</par>

<par>

<row> estã* na T*bela 2. A pr*sen*a do valor "N*" no c*mpo i*d*ca q*e * *ar*metr* n** se a*lica </row>

<row> ao al**ri*mo meta-heurístico. </row>

<row> T*b*la 2 - Valo**s dos p*râmet**s utilizados no IRAC* </row>

</column>

<par>

<line> Algoritmo </line>

<line> *úmero máxi*o de iterações </line>

<line> Nív**s de perturbação </line>

</par>

<par>

<line> GRASP </line>

</par>

<par>

</par>

<par>

</par>

<row> Para a v*lidação dos al*oritm*s meta-heurísticos, s*o resol*i*as i*stâncias fictícias </row>

</column>

</par>

<par>

<line> peq*ena*. Após * calibra*em e </line>

<line> v*lid*ção, o* algoritmos fora* aplicados à re*oluç*o de </line>

</par>

<par>

<line> instânci*s *aio*es e a real. Os r*su*tados obtidos f*ram co**a**dos entre os algori*mos </line>

<line> desenvolvido* e com *s res*ltados de outros algor*tmos *presentados na litera*ura. </line>

<line> 3.1 Formulaçã* m*temática </line>

<line> O *ode*o mate*áti*o utiliz*do foi o de*envolvido por Aqu*no et al. (2019). Para a </line>

<line> descr*ção m*temática do mode*o foram utilizadas a* seguintes n*t*ções. T = {1, *, ..., n} é o </line>

<line> c*njunto d* n ativ*dades de manu*enção q*e devem s*r realizadas pelo *onju*to W = {1, 2, </line>

<line> ..., *} de m equipes de tr*balho. Cada man**enção i T é associa*a ao conjunto Wi W </line>

<line> de equ*pes d* tra*alho capazes de realizá-la. Também associados a cada manutenção i T </line>

<line> *stão o t*mpo pi ne*e*sário para executá-la, Ai * eq*ipamen*o em que * manut*n*ão será </line>

<line> **alizada, e a ja*ela de tem*o (*i, li) que a *anutenção pod* ser realizada. A penali**de *or </line>

</par>

<par>

<line> *ão realizar a m**utenção </line>

<line> é wi. O v*lor da p*nal*dade fo* definido como o tempo pi, </line>

</par>

<par>

<line> m*lti*lica*o *or um *a*or *e prioridade da *rdem de manutenção defin**o p*la empres*. </line>

<line> Cada e*uip* de trabalho k W *stá di*poníve* no p*ríod* (0, hk). O conjun*o T* T </line>

<line> indica a* ma*utençõe* que pode* ser re*liz*das pela equ*pe d* trab*l*o k W. Para o modelo </line>

</par>

<par>

<line> de programaçã* linear </line>

<line> inteira mista (*ILP), *oram definida* as variáveis de decisão do </line>

</par>

<par>

</par>

<par>

<line> Rev. FSA, Teresina, v. 2*, n. 10, art. 9, p. 175-202, ou*. 2023 </line>

<line> www4.fsanet.c*m.*r/revista </line>

</par>

</page>

<page>

<par>

<line> Mét*do* Heurísticos * Me*a-Heurístico* p*ra * Res*l**ão *o Probl*ma de *equenciamento de Ordens </line>

</par>

<par>

<line> , s* a m*nutenção * pr*cede imediatament* * *a**tenç*o * execut*da </line>

</par>

<par>

<line> *ela eq*ipe d* trabalho k; 0, c**o c*nt**ri*; </line>

</par>

<par>

<row> contrário; </row>

</column>

<row> se * manu*en*ão i se*á executada pela equ*pe de trab*lho k; 0, caso </row>

<row> = 1, se * equipe de trabalh* k é utili*ada; *, cas* contrário; </row>

<row> , tempo de conclusão da manut*nção i pela equipe de trabalho k; </row>

<row> = 1, *e a ma*u*enção i prec*de imed*atame*te a m*nutenção j **ra o caso </row>

</column>

</par>

<par>

<line> em que ambas a* manutenções s* referem *o mesmo equipament* ( </line>

<line> ) e que ambas são </line>

</par>

<par>

<line> executadas po* equipes *i*e*entes; 0, cas* con*rári*. </line>

</par>

<par>

<line> O modelo de p*ogramaçã* m*temática que defi*e o PPOMPLP é, e*tão, ap*esentado </line>

<line> pelas *quaçõ*s (1) * (1*): </line>

</par>

<par>

<line> Su*eit* *s **strições: </line>

</par>

<par>

<line> Rev. FS*, Teresina PI, v. 20, *. 10, art. 9, *. 175-202, o*t. **23 </line>

<line> www4.fsanet.com.br/revi*ta </line>

</par>

</page>

<page>

<par>

<line> A. A. Santos, A. X. Martins, M. *. F. Sous*, R. H. *. Machado </line>

</par>

<par>

<line> A Equação (1) define a função objetivo, que busca *i*imizar a s*ma d* cus*o de </line>

<line> mã* d* ob*a com as *anutenções não atendid*s. O c*njun** de restriç*es (2) g*ran*e qu* cada </line>

</par>

<par>

<line> manutenç*o será executada po*, n* </line>

<line> máximo, uma equipe de trabal*o. O conjunto </line>

</par>

<par>

<line> restri*õ** (3) gara*te qu* toda manutenção ex*cuta** terá uma *** de obra aloc*da. A* </line>

</par>

<par>

<line> restrições (*) </line>

<line> garantem que uma de*erminada equipe de traba*ho só será alocada s* e*a for </line>

</par>

<par>

<line> utilizada para exec*ção de alguma ma*uten*ão. </line>

<line> A* restri*ões (5) garantem o </line>

</par>

<par>

<line> *equenciamento das ordens </line>

<line> ** m*n*t*nção execut*das p** </line>

<line> *ada e*uipe de t*abalho. * </line>

</par>

<par>

<line> conju*to de *estr*ç*es </line>

<line> (6) *sse*ura que o tempo de conclusão de uma m**utenção fictícia, </line>

</par>

<par>

<line> criada **ra facilitar a modelagem, é nulo para todas as equipes de tra*a*ho. A* restrições (7), </line>

</par>

<par>

<line> (10) (11) garantem qu* a equipe de t*abal*o não p*de **ecutar *ais de um* e </line>

</par>

<par>

<line> manutençã* si*ultaneamente, * *ada </line>

<line> equipament* não pode ter mais de uma ordem de </line>

</par>

<par>

<line> m*nutenção *endo executada simult*neam*n**. *ais especificamen*e, as rest*ições (7) s*o </line>

<line> ativada* ap*nas quan*o a ma*utenção j for re*lizada imediatamente a*ós a ma*utençã* i p*la </line>

<line> *quipe *. Por s*a vez, a* restrições (10) sã* ativadas q*a*do a manutenção j pr**ede </line>

<line> imediatamente a manutenção i par* * cas* em que amba* as **nutenções se *eferem ** </line>

<line> mesmo equipamento (Ai = Aj) e e*e**tadas por *quipes di*erentes. As *e*trições (11) são </line>

<line> similares às (10) quando a *anutenção i precede imed*atam*nte à man***nção *. Para ativar </line>

<line> ou desativar ess*s rest*ições, as constantes M e M devem as*umir valores maiores *u </line>

</par>

<par>

<line> iguais * *i + pj </line>

<line> e lj + pi, respectiv*mente. As re*tr*ções (8) e (9) garantem que </line>

</par>

<par>

<line> manutenção *e** executa*a dentr* d* *ua </line>

<line> j*nela de tem*o, enq*anto as restrições (12) </line>

</par>

<par>

<line> Rev. FSA, *eresina, *. 20, *. *0, a*t. 9, p. 17*-202, out. 2023 </line>

<line> www4.fsanet.com.b*/revista </line>

</par>

</page>

<page>

<par>

<line> Mé**do* Heuríst*cos e Meta-Heur*stico* pa*a a Resolu*ã* do Proble*a *e *equenciam*nto de Ordens </line>

</par>

<par>

<line> garan**m qu* o número de horas alocad*s p*ra uma equi** d* tra**l*o sej* men*r ou ig*a* ao </line>

<line> número de horas disp*níveis. Por *im, a* r*strições (*3)-(17) i*dicam o domí*io e escop* das </line>

<line> variáve*s d* decisão. </line>

</par>

<par>

<line> Importante destac*r que ess* *odelo matemát*c* necessita </line>

<line> da criação d* uma </line>

</par>

<par>

<line> manu**nção fictícia p*ra seu funcionamento. Os valores qu* são inser*dos </line>

<line> no* *arâmetr*s </line>

</par>

<par>

<line> dessa *anut*n**o fictícia não im*orta*, mas, *omo *oa prática, s*o *t*lizados valores </line>

</par>

<par>

<line> in*omuns </line>

<line> ** d*mais manutenções. Ao fazer a leitura dos dados, essa m*nutenção s*rá o </line>

</par>

<par>

<line> *rimeiro elemen*o (* = 0) e a* *em*i* manut*nções são enumeradas na se*uência a partir dos </line>

<line> índices i = {1, 2, ..., *}. </line>

<line> Ao longo da testagem do **del* exato, *oram rea*izadas rod*das tes*e cons*derando </line>

<line> a rela*ação de cada uma das variá*eis de de*isão d* modelo. Para a comp*ração do </line>

<line> proc*ssame*t* relax*do c** *s resultados d* processame*to não rela*ado, foram utilizada* </line>

<line> apenas a* instânc*as que tiveram o pr*cessamento concluído c*m me*os de uma hora. *sso </line>

</par>

<par>

<line> g*rante que * co*pa*aç*o seja feita apenas entre re*ultado* </line>

<line> ótimos. Os r*sultado* obtidos </line>

</par>

<par>

<line> est*o apresenta*os na Tabela 3. </line>

</par>

<par>

<line> Tabela 3 - R*sultados dos te*tes d* modelo mat*mático com va*iávei* rela*adas </line>

</par>

<par>

<line> Instâ**ia </line>

</par>

<par>

<line> relaxad* </line>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

<line> www*.fsan*t.com.br/revist* </line>

</par>

</page>

<page>

<par>

<line> *. A. Santos, A. *. Martins, M. J. *. Sousa, R. H. C. M*chado </line>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

<line> Na Tab*la 3, o gap representa a diferen*a entre o resultado obti*o p*r meio da </line>

<line> relaxação e * resulta** não r**axado. Quanto *aior o gap, *ais *istant*s são as soluç*es </line>

<line> A *elaxação da va*iável x resulta em soluções i*viá*eis, s*m seque* um </line>

<line> sequenciame*to lógico. *elaxa* a variável * produz sol**õe* q*e não *espeitam * r*str*ção d* </line>

<line> que um eq*i*ament* não *ossa ser utilizado por *ais de um* equipe ao mesmo tem*o. </line>

<line> Relaxar *s *ariáveis z e y res**ta e* sol*ções viáve*s, po*ém, na m*dia não há ganho n* tempo </line>

<line> de processamento, nem nos *esultados obtido*. </line>

<line> 3.2 Heurísticas de construção e alocação </line>

<line> Esta seç*o est* organi*ada como segu*: na *ubseção 6.1 são apre*entad*s duas </line>

</par>

<par>

<line> heurísticas con**ruti*as para gerar um* solução inici*l *ara o pr*blema. Por sua vez, </line>

</par>

<par>

<line> *ubs*ção 6.2 apresenta u* </line>

<line> algori*mo para alocar as ordens de manuten*ão geradas pe*** </line>

</par>

<par>

<row> heurísti*as d* construção *, assim, avaliar a solu*ã* *erada. </row>

</column>

<par>

<line> *eurís**cas de co*strução </line>

<line> F*ram p**pos*as duas he*rí**icas construtivas di*eren*es: a primeira chamada </line>

</par>

<par>

<line> "constr*ção do s*que*ciamento simples da* </line>

<line> *rd*ns" e a segunda de "construção do </line>

</par>

<par>

<line> sequenciamento das ordens por equ*pamento". A prim*ira, apresentada pelo A*goritmo 1, </line>

<line> r*aliza o sequenc*ame*to *as ordens, te*do o tempo limite da ordem (lc) como o principal </line>

</par>

<par>

<line> pa*âmetro e, em caso de empate entre dua* </line>

<line> *rdens, a penali**de (w*) * o c*itério </line>

</par>

<par>

<line> desempate. Orde*s c*m men** lc * maior wc tê* priorid**e de a*oca*ã*. O *lgo*it*o </line>

<line> reto*na * s*quênc*a de ordens N. </line>

</par>

<par>

<line> Rev. FSA, Teresina, v. 20, n. *0, art. 9, p. 175-2*2, out. 20*3 </line>

<line> www4.fsane*.com.br/rev*sta </line>

</par>

</page>

<page>

<par>

<line> Métodos Heurísticos e Me*a-H*urísticos par* a Re*olu*ã* do **oblema d* Se*uenciame*to de Or*ens </line>

</par>

<par>

<line> O *egundo algor*tmo cons*rutivo r*a*iza primeiro *ma avaliação de *ual é o </line>

</par>

<par>

<line> **uipamento </line>

<line> *lvo com *aior número de manutençõe*. O *e*uencia*ento </line>

</par>

<par>

<line> realizadas no **ui*ament* </line>

<line> ma*s *tilizado é defin*do *rimei**, segu*nd* os mesm*s </line>

</par>

<par>

<line> critérios *o Al**ritmo 1. Ordens com *enor lc e maio* wc tê* pri**idade de alo*ação. Apó* </line>

<line> s*qu*nciar to*as *s *rdens d* equipam*nto mai* uti*izado, é *ealizado o sequenciamento do </line>

<line> seg*ndo *ais utiliz*do, at* qu* o *equenc*a*en*o de t*dos se*a concluído. </line>

</par>

<par>

<line> Para exemplificar, uma </line>

<line> instância fictícia foi a*r*senta*a no Quad*o 1. Para a </line>

</par>

<par>

<line> ins*ância em *uestão, a sequência resultant* *o Algor*tmo 1 é N = {*,4,6,2,5,3}. O pri***r* </line>

</par>

<par>

<line> elemen*o dessa sequ*ncia é * ordem 1, porque </line>

<line> *em-se o tem*o limite da ordem (lc) me*or, </line>

</par>

<par>

<line> com o va*o* 4. O segundo elemento (orde* 4) é o segund* da se*uência por ter segundo o </line>

<line> m*nor v*lor *c. P*ra o terceiro elemento há empate do valor d* lc entre ** or*ens 2 e 6. </line>

<line> Como a ord*m 6 tem *aior penal*dade, e*a *cupa a posição, segu*do da *rdem 2 qu* será * </line>

<line> qua*to elemento. Os **is ú*ti*os e*ement*s da s*qu*nci* são p*sicionados de acordo **m os </line>

<line> respectivos valo*es de l*, já qu* não há empa**. </line>

</par>

<par>

<line> www4.**ane*.com.*r/revista </line>

</par>

</page>

<page>

<par>

<line> A. A. Sant*s, A. X. Marti*s, M. J. F. So*s*, R. H. C. Mac*ado </line>

</par>

<par>

<line> Quadr* 1 - *aracteríst**as das ord*n* de *anu*enção. </line>

</par>

<par>

<line> refa de manutenção </line>

<line> Espe*ialidad* </line>

<line> Duração </line>

<line> Pe*alidade </line>

</par>

<par>

<line> Alinham*nto </line>

<line> Carro </line>

</par>

<par>

<line> Alinhamento </line>

<line> C*minhão </line>

<line> Mecânica </line>

</par>

<par>

<line> *evisão de motor </line>

<line> Carro </line>

<line> Mecân*ca </line>

</par>

<par>

<line> *evisão elétrica </line>

</par>

<par>

<line> Revisão elé*rica </line>

<line> Carro </line>

<line> Elétr*ca </line>

</par>

<par>

<line> Revi*ão de motor </line>

<line> *aminh*o </line>

</par>

<par>

<line> F*nte: adaptado de *qui*o et al. (201*) </line>

<line> Par* * seg**do algoritmo cons*rutivo, *omo * equipam*nto "ca*r*" é o mais </line>

<line> ****izado, a sequên*ia se ini*ia po* e*e. Isso r**ulta n* seguint* sequência: N = {1,5,3,6,2,4}. </line>

<line> Para a construção dest* sequên*ia, a*al**-s* para as primeiras p*s*ções apenas ordens </line>

</par>

<par>

<line> executadas no equipamento carro (ordens 1, </line>

<line> 3 e 5). Porta*to, o </line>

</par>

<par>

<line> sequê*ci* é o*d*m *, com menor l*, seguido a </line>

<line> da ordem 5, com segundo menor lc e, por </line>

</par>

<par>

<line> últi*o, a orde* 3. * segundo equipamento ma*s utilizado é * cam**h*o (ordens 2 e *). As </line>

<line> o*dens 2 e 6 têm v**ores *e *c iguais, porém a p**a*i*ade d* ordem 6 é maior, faz*ndo co* que </line>

<line> ela seja o *uar*o elemen*o da seq*ência, segu*da pela *rdem 2. O ú*timo equipamento é a moto, </line>

<line> com a*enas * ordem 4, que é e*t** o últi*o elemento da seq*ência. Os algo*itmos meta- </line>

</par>

<par>

<line> heurísticos d*sen*olvidos </line>

<line> utiliza* o al*or*tmo cons*rutivo com melh*r resulta*o c*mo </line>

</par>

<par>

<line> s*lução ini*ia* do *roblema, porque há dife*enç* de ac*rdo com * i*stância. </line>

<line> b. Heurística de al*cação </line>

</par>

<par>

<line> das ordens defi*ida </line>

<line> por um *os dois algori*mos d* construção </line>

</par>

<par>

<line> apresen*ados na seção a*terior, é nec*ssário *ealizar a sua alo*ação. A a*ocaç*o é reali*ad* </line>

<line> por e*uipes, inicia*** pela equipe *u grup* de equi*es mais ocu*ado. Para verificar q*al é a </line>

<line> *quip* *ais ocupa*a, pri*eiro soma-se a duração de *oda* as ativid*d*s que p*dem *e* </line>

<line> re*lizad*s por um grupo de e*u*pes (no exemplo do Q*adro 1, * grupo de equipes contém </line>

</par>

<par>

<line> espec*alida*es mecâ*ica ou elét*ica). A dura*ão total </line>

<line> é, *ntão, dividid* pelo </line>

</par>

<par>

<line> número de equipes em um *rupo. O gr*po *om maior ocup*ção tem priori*ade na alocação </line>

<line> das ordens. </line>

<line> Para a alocação das or*ens, foi implementado o Alg*ritmo 2. A alocação das </line>

</par>

<par>

<line> ord*ns realizada do começo da *anela é </line>

<line> de temp* d* ordem c (ec). Ca*o **o seja possível </line>

</par>

<par>

<line> Rev. FS*, Teresin*, v. 20, n. 10, art. 9, p. 175-*0*, out. **23 </line>

</par>

</page>

<page>

<par>

<line> Métodos Heurí*ticos e Meta-H*ur*sti**s pa*a * R*s***ção do Proble** de Seq*e*ciamento de Or*ens </line>

</par>

<par>

<line> *loca* a ordem na p*i*ei** </line>

<line> p*sição, o ho*ário de in*c*o *a ord*m é po*te*gado a*é ser </line>

</par>

<par>

<line> po*síve*. *aso *ltrapasse </line>

<line> a janel* *e *em** da ordem, a or*em *erá **oc**a a outra equipe. </line>

</par>

<par>

<line> *aso não seja p*s*ív*l alo*á-l* em n*nhuma das outra* equi*es, a or*e* n*o é *locada e ent*a </line>

</par>

<par>

<line> como penalidade no resulta*o da </line>

<line> *unção objetiv*. Há do*s motivos para que a ordem não </line>

</par>

<par>

<line> pos*a ser a*ocada em *ua *rimeira posição: caso j* ex*sta uma ordem alocad* na mesma </line>

<line> equi*e no mesmo horário ou ca*o tenha *m* ordem alocada no mes*o equipament* e* </line>

</par>

<par>

<line> outr* equipe no mesm* horári*. *s var*áv*is início * fi* util*z*das </line>

<line> *o A*goritmo 2 são os </line>

</par>

<par>

<line> *o*ár**s de iníc** e fi* *e execução de u*a ordem n* pr**ramaçã*. O algo*itmo r*torna à </line>

<line> solução s, à penalidade total e à lista de ordens não ut*li*ada*. </line>

<line> * *igura * exemplifica o func*o**ment* d* a*ocação *e or*ens. O pri*eiro gráfico </line>

<line> de Gantt rep*e*e*ta * alocação d*s ordens do Quadro 1, se**ind* o *étod* "cons*rução d* </line>

</par>

<par>

<line> seque*ciamento simples das orde*s" (*lgorit*o 1). A </line>

<line> s*quência N = {1,*,6,2,5,*} dev* </line>

</par>

<par>

<line> com*çar pelas equ*pe* de m*cânica. Is*o pode s*r t*aduzido em uma *equência menor: * = </line>

<line> {1,6,2,3}. A janel* *ara alocação *a ordem 1 tem os valores (0, 4). Como não há nenhuma </line>

<line> ordem a**cada no instante 0, a ordem 1 é *loca*a n*sse insta*te. A ordem 6 tem j*nela (4, 7) </line>

<line> e pod* ser alocada n* instante 4. A ordem 2 tem janel* (2, 7) e pode *er al*cada no instante 2. </line>

<line> A ord*m 3 tem janela (3, *), *orém o ins*ant* * está ocupa** pela ordem 3. O insta*te 4 está </line>

<line> ocu*ado p*la or*em 6. P*rtanto, a melh*r *l*caç*o pa*a a ordem 3 é no i*stant* 5. </line>

<line> Figura 2 - E*emplo de aloc*ção de o*dens </line>

</par>

<par>

<line> *ww*.fsanet.*om.*r/revi*ta </line>

</par>

</page>

<page>

<par>

<line> A. A. Santos, A. X. Martin*, M. J. F. Sousa, R. H. C. Machado </line>

</par>

<par>

<line> Apó* a alo*ação de *odas as ordens das equipe* de *e*â*ica, a alocação é realizada </line>

<line> para as eq*ipes *e *létrica, *egui*do o restante da sequ*ncia N* = {4,5}. A ordem 4 tem </line>

</par>

<par>

<line> janela (*, 6) * po** ser </line>

<line> aloc*da no instant* 2. A </line>

<line> ordem 5 tem jan**a (3, 8) e pode ser </line>

</par>

<par>

<line> aloc**a *o instante 3. O mesmo procedimento de al*cação é rea*izado para a "co*strução do </line>

<line> sequ*nc*amento das *rdens po* equip*mento" (se*u**o Ga*tt), sendo apenas a s*quê*cia </line>

<line> diferente. </line>

</par>

<par>

<line> R**. FSA, Teresina, v. 20, n. 10, art. 9, p. *75-2**, *ut. 202* </line>

<line> w*w4.fsanet.com.br/rev*sta </line>

</par>

</page>

<page>

<par>

<line> Mé*odos H*urísticos e Meta-Heurísticos para a Resolução do Problema de Sequenci**ento de Ordens </line>

</par>

<par>

<line> *.3 *lgoritmos *eta-heurístico* </line>

</par>

<par>

<line> Os *alo*es *os parâmetr*s utiliza*os nos alg*ritmos met*-heur*sticos foram ob*idos </line>

<line> por meio de calibração utilizando o pa*ot* IRA*E. O único parâmetr* fix* * com*m a todos </line>

<line> os alg*ritm*s meta-heurísti*os é o t*mpo limite de execução, f**ado e* n segu*dos tal co*o </line>

</par>

<par>

<line> em A*uino et *l. (2019), sendo n número de o**ens de *anutenção da instân*ia. Cada * </line>

<line> algo*itmo fo* executado com cinco repetições p*ra cada instância. O alg*rit*o GRA*P foi </line>

<line> desen*olvid* com base no de Feo e Res*nde (1995), utiliza**o co** *étodo de busca local </line>

<line> o random descent. * random descen* desenvolv*do re*liza trocas aleató*ias entr* duas </line>

</par>

<par>

<line> orden* (i, *) da s*quên*ia dada N. Só é avali*da * troca *as ordens i e j se elas </line>

<line> e*tivere* </line>

</par>

<par>

<line> dentr* de *m mesm* período de prog*a*ação (e* > li > lj ou e* > lj > li). C*so a troca prod*za </line>

<line> uma so**ção *elhor, ela é aceita, mod*ficando-se N. </line>

</par>

<par>

<line> gerad* *ent*o do *lgoritmo m**a-heurí*tico é ne**ssári* </line>

</par>

<par>

<line> refaz** a alocaçã* das ordens pa*a que seja *alcu**do o novo cus*o *a *unçã* obj*tivo. A </line>

<line> heurística d* alocação, por ser a *ais custosa em t*rmos de processamento, tornaria inviável </line>

</par>

<par>

<line> t*do o período de program*ç*o fosse realocado a cada troca. Por iss*, a cad* n**a </line>

</par>

<par>

<line> se*u*n*ia *er*da *entro dos métodos met*-h*ur*stic*s, é refeita apenas a alocação dentro de </line>

<line> *er*odos em que haja ordens não alocada*, mantend* * alocação ant**ior para os *e*ais </line>

<line> O algo*itm* SA foi desen*olvido c*m bas* *o trabalho *e Kirk*atrick e* al. (19*3). </line>

</par>

<par>

<line> O *izin*o ale*tório é ger*do troca**o-se du*s ordens ale*tória* (i, *) da sequência </line>

</par>

<par>

<line> prog*am*ção. Par* limit*r o número de t*o*as, as ordens i e j s* *ão *r*cadas s* </line>

</par>

<par>

<line> den*ro do mesmo período de *rogramação, sem**h*nte * *ó*ica *tiliz*da no ra**om descent. </line>

<line> Ordens em per*odos de tempo* di*erentes têm pouca influên*ia na aloc*çã* da outra. </line>

</par>

<par>

<line> foi a*aptad* daquele proposto por *our*nço *t al. (201*). Como </line>

</par>

<par>

<line> *étodos de b*sca l**al for*m utili*ados o *ando* d*scent, já e*pl*cado an*eriorm*nte, e o first </line>

<line> improvement, sendo sort*a*os, **m *gual p*obabil*dade, qual *erá utilizado em cada iteração. </line>

</par>

<par>

<line> O método *irst improv*m*n* rea*iza a troc* das orde** i e </line>

<line> j, começando por i, </line>

</par>

<par>

<line> primei*o element* de *, e j, como se*undo elemento. A ca*a i*e*aç*o é </line>

<line> acrescid* </line>

</par>

<par>

<line> *n*dade à i ou j, até q*e todas as *rocas pos*íveis sejam avalia*a*. Ao longo **s it*rações, </line>

</par>

<par>

<line> uma t*oc* r**rese*ta melhora no resultado d* *unç*o objetivo, a troca é r*a*iz*da, </line>

</par>

<par>

<line> atuali*ando-se N, e r*i*iciando-se o método first *mprove*ent. As trocas do ILS também só </line>

<line> são av*liada* se estiverem dentro de u* m*smo *eríodo de progr*mação. </line>

<line> Rev. FSA, Tere*ina PI, v. 20, *. 10, art. 9, *. *75-202, out. 20*3 www*.fs*net.com.br/revis*a </line>

</par>

</page>

<page>

<par>

<line> A. A. Santos, A. X. Marti*s, *. J. F. Sou*a, R. H. C. Machado </line>

</par>

<par>

<line> 4 RESUL*ADOS E DISCU*SÕES </line>

</par>

<par>

<line> Nesta seção *ã* a*resenta**s os resulta*os da comparação entr* os três algor*tmo* </line>

</par>

<par>

<line> desenv*lvidos </line>

<line> n*ste traba*ho. P*ime*r*mente e* re*ação a tod*s as instânci*s e, </line>

</par>

<par>

<line> p*steriormen*e, e* relação * u* ag*upamento p*r tamanho. E* s*guida é verificado </line>

</par>

<par>

<line> algoritmos e se há dife**n*a estatística entre *l*s. P*r f*m, os </line>

</par>

<par>

<line> algoritmos dese*vol*idos são comparados com o* d* literatura. </line>

<line> Os a*g*ritmo* heurísticos e meta-heurísticos fora* todos d*sen*olvidas em Python, </line>

</par>

<par>

<line> vers** 3.*. *ad* algoritmo </line>

<line> meta-heurís**co foi *aram*trizad* com o *empo </line>

</par>

<par>

<line> pro*essament* igual a n segun*os, sendo n o número de orden* d* manutenção da inst*ncia e </line>

<line> com cinco repe*ições p*ra cad* inst*nc*a. </line>

<line> Todos o* al*o*itmos fora* ex*c*tados em u* c*m*utador Intel(R) Core (TM) i7- </line>

<line> 4790 C*U @ 3.60G**, 15GB de m*mória RAM sob o sis**m* operacio**l *bu*tu 16.04.6 </line>

<line> LTS (Xenial Xer*s). O *omp*tador perten*e ** L*boratório d* *imulaç*o * Otimização de </line>

</par>

<par>

<line> Sistem*s (LASOS) da Universida*e F*de*al de Our* Pr*to (U*OP). Val* d*stacar </line>

</par>

<par>

<line> pr*sente trabalho nã* utiliza * pr*cessamento e* th*eads pa*alelas. </line>

</par>

<par>

<line> A T*bela 4 a*resent* o de*vio-padrão médio do gap d*s instânc*as. O </line>

</par>

<par>

<line> c*lculado pela </line>

<line> dif*rença p*r**ntual e*tre o melhor v***r o*ti*o pelo </line>

<line> algorit*o e o *el*or </line>

</par>

<par>

<line> valor disponível n* literatura. O ILS apr*senta um desvi*-pa*rão médio m*nor dentre os </line>

</par>

<par>

<row> *lgoritmos me*a-h*urísticos apl*ca*os, o que **d*ca que essa é a impleme*tação co* </row>

<row> mel*o* *epetibilidade dentre as três. </row>

<row> *abe*a 4 - *esvio-padr*o médio dos algorit*os GRASP, SA e ILS </row>

</column>

<par>

</par>

<par>

<line> Todas as instân*ias </line>

</par>

</column>

</par>

<par>

<line> Para anál*se *os r*sultados, as instâncias for*m divididas em grupos, tal com* em </line>

<line> Aquino et al. (20**): </line>

</par>

<par>

<line> P: instâncias de ** * 80 ordens de manutenção; </line>

</par>

<par>

<line> M: instâncias *e 150 a 600 ordens de manutenção; </line>

</par>

<par>

<line> G: instâ*cias de 1200 a 480* ordens de ma*ut*nçã*; </line>

</par>

<par>

<line> GG: instância* de 9600 a 33484 orden* de manutenção; </line>

</par>

<par>

<line> www4.fsa*et.com.br/revista </line>

</par>

</page>

<page>

<par>

<line> M*t*dos *eur*s*icos * Meta-Heurísticos pa*a * Reso*uç*o do *roblema d* Sequenciam*nto de Orde*s </line>

</par>

<par>

<line> A instância re*l fo* agrupada j*nto às i*stâncias do g*upo G*. A *abela 5 apresen*a </line>

<line> as i*stâncias agrupadas por tam*n*o para análise. A co*una "Médias" mostra * média d*s </line>

<line> valore* ***io* das re**tiçõ*s obtid*s para cada t*manho de instân*ia. * c*luna </line>

<line> "M*lhor*s" *presen*a a médi* d*s menor*s valore* ob*idos *en*re todas *epetiç*es para cada </line>

<line> *amanho de in**â*cia. A *oluna "Contage* me*h*res" i*dica e* *uantas ins*âncias d* um </line>

<line> *esmo tamanho *a*a a*g*ritmo m*ta-he*rí*tico obte*e o melhor res**t***. </line>

<line> Tabel* 5 - Compar*t*** de resultados *ntre os algorit*os meta-heurís*icos *RASP, </line>

</par>

<par>

<line> ins**ncias </line>

<line> Contagem </line>

<line> C**tagem </line>

<line> Médias </line>

<line> Melhores </line>

<line> melhores Méd*as </line>

<line> Melhores </line>

<line> melhores Médias </line>

<line> melhores </line>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

</par>

<par>

<line> De acord* com os d*dos da T*bela 5, o ILS obteve resulta*os melhore* em *9% das </line>

<line> instâncias *, send* o GRASP melhor em apenas um* i*st***ia e SA a*ingi*do resultados no </line>

<line> má*im* iguais aos d*m*is. Entre SA e GRASP, os resul*ados fora* mu**o p*ó*imos na </line>

<line> média, co* S* li*e*ramente melhor entre as instâncias * e G. Para as i*stância* *, G e GG </line>

</par>

<par>

<line> o ILS ta*bém *oi a me*a-heur*stica que obteve melhores *esulta*os *entre </line>

<line> as três, sendo </line>

</par>

<par>

<line> *elhor em 71% das in*tâncias M, G GG. SA obteve o m*lhor resultado em 50% e </line>

</par>

<par>

<line> GRAS* e* 36,8%. Estes números s*m*do* </line>

<line> que 100%, porque pode </line>

</par>

<par>

<line> empate entre as *e*a-heu*í*ticas em uma </line>

<line> ou *ais inst*ncias. O *elhor *e*ultado para </line>

</par>

<par>

<line> i*st*n*ia re*l foi obtido pel* GRA*P. </line>

</par>

<par>

<line> Para verif*car se o* a*goritm*s m*ta-*eurístico* p*ssuem *m* d*fere*ça </line>

</par>

<par>

<line> es*atist*came*te significati*a ent*e si, *oi aplic*do o *este d* Frie*man. * </line>

<line> *este Fried*a* </line>

</par>

<par>

<line> Rev. FSA, Teresina PI, v. 20, n. *0, art. 9, p. 175-20*, *ut. 2023 </line>

<line> ww*4.fsanet.co*.br/*evista </line>

</par>

</page>

<page>

<par>

<line> A. A. Sant*s, *. X. Mar*ins, *. J. F. Sousa, R. H. C. Ma*hado </line>

</par>

<par>

<line> po** ser *tilizado para analisar pr**ença de di*e*en*as estatist*camente a </line>

</par>

<par>

<line> re*ev*n**s entr* três *u mais modelos *e dados ordinais. Caso o p-val*r result*nte do teste seja </line>

<line> maior que o nível *e si*nificância, usual*ente e**abe**cido em 0,05, a hipótese nula de q*e as </line>

<line> a*ostras são estatistic*m*nte difere*tes é *es*artada. N*s*e caso, pode-*e a*lica* um te*t* </line>

</par>

<par>

<line> *ost-ho* *omo o teste Nemenyi p*ra v*rificar entre q*ais pares de medidas h* </line>

<line> diferença </line>

</par>

<par>

<line> signifi*ativa (SHEL*ON et *l., 19*6). </line>

</par>

<par>

<line> util*zam *omo *arâmetro de d*semp**ho a c*ass*ficação d* </line>

</par>

<par>

<line> alg**itmo meta-heurístico e* cada aplic*ção. *essa f*rma, *ã* de*inidas clas*ificações </line>

<line> (*anks) p*ra cad* heurística em cada in*tân*ia. O teste de Friedman con*id*ra qu* se * rank </line>

</par>

<par>

<line> u* mod*lo * *proximadamente igual a ou*ro, ent*o *s *odelos seri*m </line>

</par>

<par>

<line> estatisticament* iguais. Já * teste de Ne*enyi c**sider* que o *ank médi* de *m algori*mo </line>

<line> dev* ap***entar n* mínim* uma certa di*tância em valor, defin*da com* diferença c*ítica, do </line>

<line> ran* médio de outro algoritmo para *ere* considerados di*erentes (WA*G et al., 2018). </line>

</par>

<par>

<line> *s testes de Fr*edman junto ao *este *ost-hoc N*menyi têm sido utiliz*dos *ara </line>

</par>

<par>

<line> com*aração de resultados de meta-heuríst*cas (MA et al., 2022). Como v**ta*em, *o </line>

<line> con*iderar apenas os ranks, os testes *e torna* m*nos suscet*veis a outliers (BROWN E </line>

</par>

<par>

<line> MUE*, 2*12). Porém, </line>

<line> ao utilizarem medidas d*fer*nte*, os test*s podem apr*sentar </line>

</par>

<par>

<line> *esul**dos diferentes. Al*m disso, *o utiliza*em apenas *a*k, a **mensão ** o </line>

</par>

<par>

<line> entre *s algoritmos meta-heur*s*icos nã* é considerada na an*lise. Dessa forma, a média e o </line>

</par>

<par>

<line> desv*o p*drão também são utilizados ne*te estudo como *ase para a </line>

<line> co*pa*ação e*tatística </line>

</par>

<par>

<line> entre os algorit*os. </line>

</par>

<par>

<line> Ap*ica*do o *este de Frie*man, com nível de significância </line>

</par>

<par>

<line> algori*m*s met*-heurísticos (GRA*P, SA * *LS), </line>

<line> c*nsid*rando todas *s i*stâ*cias, obtém- </line>

</par>

<par>

<line> se um p-v*lor de 2, 23 × 105, *nd*cando que há *ma d*fer*nça estatística signif*cativ* entre a* </line>

</par>

<par>

<line> t*ês *mplementações. Para verif*car </line>

<line> entre si, foi ap*icado o </line>

<line> teste </line>

</par>

<par>

<row> post-hoc de Ne**nyi. Es** te*te ret*rnou os p-valores conforme a Tabela 6, ind*cando *ue </row>

<row> *penas os a*goritmos GRA*P e ILS sã* diferen*e* es*at*sticamente ent*e si. </row>

<row> Tab**a 6 - Teste po*t-hoc **tre as meta-heurí*t*cas GR**P, SA, ILS para to*as as </row>

<row> instâ*cia* </row>

</column>

<par>

<line> Algorit*o 1 </line>

<line> Algoritmo 2 </line>

<line> p-valor </line>

</par>

<par>

<line> GRASP </line>

</par>

<par>

<line> GRASP </line>

</par>

<par>

</par>

</column>

</par>

</page>

<page>

<par>

<line> M*todos *e*rí*tic*s e Meta-Heurísticos para a Resolução do Pr*blema de S*quenc*ame*to de O*de*s </line>

</par>

<par>

<line> Depende*do do tam*nho da instância, os t*ês algor*tmos prod*zem *esultado* </line>

</par>

<par>

<line> me*hores ou piores em rela*ão aos outros. Portant*, </line>

<line> anál*se estatística mais </line>

</par>

<par>

<line> det*lhad*, os mes*os te**es foram ap*icados aos três algo*itmos *m cada tamanho </line>

</par>

<par>

<line> ins*ân**a. Esses res*ltados estão *presentados n* *abela 7. A *oluna "Frie*man" p-valor </line>

<line> apresenta o resultado obt*do pela *plicação do teste d* Fri*dman com *ível de significâ*cia </line>

</par>

<par>

<line> *,05. Apenas *ara o taman*o *G os trê* </line>

<line> a*gori**os meta-heurísticos *ã* possuem </line>

</par>

<par>

<line> dife*ença estatísti*a em *e*s res*ltados. Por nã* possuir dif*renç*, não haveria n*cess*dade </line>

<line> de *m teste post-hoc. Além disso, as instâ*c*a* GG apres*ntam *m* a**str* peq**na (tr*s </line>

<line> instânc**s) para que o test* seja *onfiável, sen*o recomendada pelo men*s uma amostra maior </line>

</par>

<par>

<line> cinco. P*ra os *emais tamanhos de instân*ia*, o tes*e ** Friedm*n i**ic* diferença </line>

</par>

<par>

<row> estatísti*a e*tre os algor*tmos, por isso há necess*d**e do teste po*t-ho* N*menyi, que indica </row>

<row> *ntre *uais pa*es há dif*rença. </row>

<row> Tabel* 7 - Teste post-hoc *n*r* *s al*o*itmo* meta-heurí*tic*s GRA*P, SA e I*S por </row>

</column>

<par>

<line> Fr*edman p-valor </line>

<line> Teste Nem*nyi Algoritmo * Algoritm* 2 p-val*r </line>

</par>

<par>

<line> GRASP SA 0,*712 GRAS* IL* *,*653 SA ILS 0,*105 </line>

</par>

<par>

<line> GRASP SA 0,6*9* *RASP ILS 0,0935 *A IL* 0,4733 </line>

</par>

<par>

<line> G*ASP SA 0,1590 GRASP ILS 0,0416 SA ILS 0,*291 </line>

</par>

<par>

</par>

<row> Na Tabela 7, *oluna "*este Nemenyi", os *-*alores ob*idos apo*ta* a existê*cia d* </row>

<row> di*e*ença e**atístic* entre *A * ILS para * tam*nho P e entre G*AS* e ILS para o ta*a*h* </row>

<row> G de instâncias. Para o tamanho M, * tes*e de *e*enyi não apontou d*ferença ent*e nenhum </row>

</column>

</par>

<par>

<line> *ar. Nesse caso, c*m*a*açã* é fe*t* p*los valores de média a </line>

</par>

<par>

<line> ***anho M, o *RASP obteve méd** de 2024,8, SA **di* *e *020,6 e ILS média d* 2018,8. </line>

<line> Re*. *SA, Teresin* *I, v. 20, n. 10, art. 9, *. 175-202, o*t. 2023 www4.fsanet.com.br/rev*s*a </line>

</par>

</page>

<page>

<par>

<line> A. A. Santos, *. X. Martins, M. J. *. Sousa, *. H. C. Mach*d* </line>

</par>

<par>

<line> Co*o GRAS* e ILS e*tão mais distan*es entr* si, esses *ã* o* dois algo**t*os d*f*r**tes </line>

<line> **tatisticamente. </line>

<line> A* *nic*ar a co*paração dos *lg*rit*os **ta-heurísticos de*envolvidos *om os d* </line>

<line> literatura (Aquino et al., 2019), for*m obse**adas i*con*istências n*s r*sultados com a </line>

<line> alocação de o*dens não alocáveis e, as*im, re*ult*dos i*viá*eis. Dessa *orma, algum*s </line>

<line> instâncias f*ra* retiradas da comparação. </line>

<line> Par* reali*ar * comparação com a lit*ratura, foi escolhido o me*hor *lgoritm* dentre </line>

<line> os trê* *mplementados neste tr**alho. O al*oritm* escolhi*o f*i o ILS, que **teve melhores </line>

</par>

<par>

<line> de forma geral, conf*rme evidenciado na *abela 5. No tr***lho de Aquino et al. </line>

</par>

<par>

<line> (2*1*), algoritmo* diferentes tam*ém obt*veram difere*tes desempenhos d*pe*den*o do </line>

</par>

<par>

<line> tamanho d* instân**a. Para fins de comparação, foi escolhido o B*KMA, porqu* é </line>

</par>

<par>

<line> **goritmo </line>

<line> que obteve m*lhores res*ltado* nas i*stâncias m*iores * na re*l. A Tabela </line>

</par>

<par>

<row> apresenta o compar*tiv* e*tre os es*udos. </row>

<row> Tabela 8 - Comparativo e*tre ILS e liter*tura por resu*tados *m grupo* de ***tâncias </row>

</column>

<par>

<line> Resultados </line>

<line> Todas as instâncias </line>

</par>

<par>

</par>

<par>

<line> Melhor*s </line>

</par>

<par>

<line> Iguais </line>

</par>

<par>

<line> *onforme a*r**entado na Tabela 8, no *onjunto </line>

<line> de t*das as instâ*ci**, o I*S </line>

</par>

<par>

<line> apr**en*a resu*tados melhor*s </line>

<line> *as instân*ias, pio*es em 10,57% e iguais em </line>

</par>

<par>

<line> *4,8%. Para a* i*stâncias pe*uen*s, </line>

<line> *s resultados são </line>

<line> 4,44% pio**s, o r*stante apres*nt* </line>

</par>

<par>

<line> r*sultados iguais. Porém, par* instâ*cias M, G e GG, o núme** de instânc*as com mel*ores </line>

<line> *esulta*os ultrapassa os *iores, chegando a 100% de resultados mel**res pa*a as instância* </line>

</par>

<par>

<line> GG. Em relação à i**t*ncia real, o resultado obtido pelo GRA*P foi *0,5% melhor que </line>

</par>

<par>

<line> a*re*en*ad* por Aquino e* al. (2019). </line>

</par>

<par>

<line> O* re**ltados completos ob**do* p*los a*goritmos desenvolvidos em t*d*s </line>

</par>

<par>

<line> i*stânc*as </line>

<line> execuç*es </line>

<line> di*ponibili*ados </line>

</par>

<par>

<line> https://docs.googl*.com/*preadsheets/d/1_iajAPkJbFNVgE*i*_jAWGJa80DxXimvTw*EJX </line>

<line> 3*-wY/e*i*?usp=*haring </line>

</par>

<par>

<line> Rev. FSA, Teresina, *. 20, *. 10, ar*. 9, p. 175-*02, out. *023 </line>

<line> *ww*.fsane*.*o*.br/r*vista </line>

</par>

</page>

<page>

<par>

<line> Métodos Heu*íst*cos e Meta-H*uríst*cos pa*a a Resolução do Problema de Sequenc*amen*o de **dens </line>

</par>

<par>

<line> 5 CONCLUSÕES E *RABALHOS *UTUR*S </line>

</par>

<par>

<line> Neste trabalho *ora* implementados **goritmos he*rístico* construtivos </line>

</par>

<par>

<line> algoritmos meta-heu**sticos para gerar *oluções </line>

<line> c*mpetitivas para o PPO*PL*, visando </line>

</par>

<par>

<line> *edução *e man**enções não r*aliza*as e de custo co* eq*i**s. Os re*ult*dos obtid*s **los </line>

</par>

<par>

<line> três mét***s meta-he*rísticos *oram comparados </line>

<line> entre si e com a literatura disp*nível. </line>

</par>

<par>

<line> Dentre os algoritmos imp**men*ad*s neste traba*ho, o ILS é o que apresentou melhor </line>

<line> repetibi*idade dos resultados e solu*ões melhores de f*rma geral, obtendo o melhor resultado </line>

</par>

<par>

<line> das ins*ância* tamanho P *m * </line>

<line> *1% *as instâ*ci*s tam*nho M, G * GG. Ape*a* </line>

</par>

<par>

<line> dis*o, o melh*r resultado obtido par* a instânci* r*al foi alcançado pe*o GR*SP. </line>

<line> Estatis*icamente, *penas G*ASP e ILS *ão diferen*es entre *i, q*an*o *s a*goritmos *ão </line>

<line> analis*dos e* r*lação a *oda* as in*tâncias. </line>

<line> N* *omparaç*o dos resu*tados obtidos pelo ILS e o BRKMA d* Aquino et al. </line>

<line> (*019), o* resulta*os do ILS foram melhore* em **,63% das i*stân*ias, igu*is para 74,8% </line>

<line> das *nstância* e piores p*ra 10,57%, quan*o comparados e* re*ação a todas *s instâ*cias. </line>

<line> Qua**o a c*mparaçã* é fe*ta de acordo com * ta*anh* das ***t**cias, o IL* ap*esenta pior </line>

<line> desempenho *as *nstâncias *amanho P e melhor desemp*nho para a* instâncias *amanho M, </line>

<line> G e GG. Para a instância r*a*, o *a**r obtido pelo ILS é 40,5% mel*or que * valor obti*o </line>

<line> pelo BRKMA. </line>

<line> A c*mpara*ão dos *lgo*itmo* desenvolvidos n*ste trabalho com a literatura tem </line>

<line> como limitação a utilização de l*n*u*gens de pr*gramação difere*tes, o pr*c*ssa*ento em </line>

<line> thre*ds paralelas, rea*izado por Aquino et *l. (2**9) * não *est* traba*ho, e a utilização de </line>

<line> má*uina* diferentes para o pro*essa*ent*. </line>

<line> Para trabalhos *utu*os, *ugere-se considerar a programação d*s *rdens de </line>

</par>

<par>

<line> manutenç*o n*o at*ndi*as, inserind*-as na pr*gramaç*o com atra*o, em </line>

</par>

<par>

<line> simples*ente n*o *s a*ocar. Isso **rar** um novo problema co* *m objetivo de oti*i*ação </line>

<line> diferente. </line>

<line> REFERÊN*IAS </line>

<line> ALFA*E*, H., MOHAMMED, A., E **ALEB, M. (2*2*). Two-m*ch*n* sched*l*ng with </line>

<line> aging effec*s and v*riable **intenance activi*ies. C*mputers & Ind*strial Engine*ri*g, </line>

<line> ALFAR*S, H. K. (2022). P*ant shutdown ma*nte*ance **rk***ce t*am a*si*nment *nd job </line>

<line> s*h*du*i*g. Journal of S*heduling, 25(3):321-338. </line>

<line> Rev. FSA, Te*esina P*, v. 20, n. *0, art. 9, p. 175-20*, out. 2*23 *ww*.fsane*.c*m.br/**vista </line>

</par>

</page>

<page>

<par>

<line> *. A. San*os, A. *. Mar*ins, M. J. *. Sousa, R. H. C. Ma*hado </line>

</par>

<par>

<line> ALIDAEE, B. E R*S*, D. (1997). Scheduli** parallel ma*hines to minim*z* total </line>

<line> weighted and un*eighted tard*ness. Co*puters & Operations Research, 24(*):775-78*. </line>

<line> AQU*NO, R. D., *HAGAS, J. B. C., E SOUZA, M. J. *. (2019). Abordagem exata * </line>

</par>

<par>

<line> heurísticas par* o problema </line>

<line> d* p*ane*amento d* ord*ns de manut*nção de longo *ra*o: Um </line>

</par>

<par>

<line> estudo de caso </line>

<line> industrial de l*rg* escal*. *esquisa Operaci*nal para o Des*nvo*vimento, </line>

</par>

<par>

</par>

<par>

<line> A**LOS-ROSALES, O et al. (*018). Including pre*ent*ve *ai***nance activities in an </line>

<line> unrelated p*rall*l mac*ine envi*o*ment with depe*den* set*p tim*s. *omp*t*** & Industria* </line>

<line> Enginee*in*, 123:364-377. </line>

<line> BROWN, *. E **ES, C. (2012). An *xperime*ta* comparison of classific*tion algorithms for </line>

<line> *mbal*nced **edit sco*ing *ata sets. Exp*rt *ystems with App*ications, 3*(*):*446-3453. </line>

<line> DELORM*, M., IORI, M., E ME*DES, N. F. (20**). Sol*tion methods for **hedu*ing </line>

<line> *r*blems **** sequence-dependent deterioration *nd main*enan*e *vents. Eur*pean Journal </line>

<line> of O*eratio*al Research, 295(3):823-837. </line>

<line> EBRAHIMIPOUR, V., NA*J**B*SHI, A., E SHEIKH*LISHAHI, *. (2015). **lti- </line>

<line> obj*ctive *odeling for prev**tive ma*n*e*ance sched*ling in a multip*e produc*ion line. </line>

<line> *ournal of Int*llig*nt *anufacturing, 26(1):**1-122. </line>

<line> *RT*M, M., AS\ AD, R., AW*D, M., E AL-BAR, A. (20*2). Work*rs-constrai*ed shutdown </line>

<line> maintenance scheduling with skills f**xi*ility: Models and solut*on algo*ithms. Comp*t*rs </line>

<line> & Indust*ial Engineerin*, p. 1*8*75. </line>

<line> F*KHER, H. *., NOURELFATH, M., E GE*DR*AU, M. (*016). A cost mini*isation </line>

<line> model for joi** producti*n and main*enance pl**ning under q*ality cons*raint*. Internation*l </line>

<line> Journal of Pr*duction Research, 55(8):2163-217*. </line>

</par>

<par>

<line> FEO, T. A. E **SENDE, M. G. (19*5). Greedy r*nd*mized adaptive search </line>

<line> procedure*. </line>

</par>

<par>

<line> Journal ** Glo*al Op*imization, 6(2):109-*33. </line>

</par>

<par>

<line> *RIEDMA*, M. (194*). A compariso* of alterna*ive tests of significanc* for the pr*blem of </line>

<line> m ranki**s. The Annals o* Ma*hematical Statistics, 11(1):86-92. </line>

<line> FU, X., et al. (*019). A three-level particl* swarm op*imiz*tion with variable nei*hbourhoo* </line>

<line> sea*ch algorith* for the p*oduc*i*n schedulin* problem with mo*ld maintenance. *w*** and </line>

<line> E*olutionary Computation, 50:1*0572. </line>

<line> *EDJAZI, *. (2015). Sche*ul*ng a maint*nance activity *nder skills constraints t* minim*z* </line>

</par>

<par>

<line> total weigh*e* tardi*ess *nd </line>

<line> *ate tasks. In*ernational Jou*nal </line>

<line> of Industrial E*gin*ering </line>

</par>

<par>

<line> Com*utati*ns, 6(2):1*5-144. </line>

</par>

<par>

<line> KIRKPAT*ICK, S., GELA*T, C. *., E V*CCHI, *. P. (1983). Op*imiz*tion by s*m**ated </line>

<line> anneal*ng. Science, *20(4598):*71-680. </line>

</par>

<par>

<line> Rev. FSA, T*resina, v. 20, n. 10, art. 9, p. 175-20*, out. 2023 </line>

<line> www4.fsan*t.com.br/revista </line>

</par>

</page>

<page>

<par>

<line> M*todos Heurístic** e Met*-Heurísticos para a Resolução *o Probl*ma de *equ*nciamento de *rdens </line>

</par>

<par>

<line> LEE, H. * C*A, J. H. (201*). New s*ochastic models for *reve*tive mai*tena*ce and </line>

<line> *ain*en*nce *ptimizati*n. Euro*ean Journal of Operati*nal R*se*rch, 255(1):80-9*. </line>

<line> LE**TIN, G., XI*G, L., E DAI, *. (*021). Optimal operation and *aintenance sch*duling in </line>

<line> m-out-of-n stand*y s*st*ms with **usable elements. Reliability *ngi*eering & System </line>

<line> Safety, 211:10*582. </line>

<line> LIU, Y et al. (2**1). Int*grated prod**tion p*a*ning and preventive mainte**nce scheduling </line>

<line> for synchronized par**lel machines. Rel*ability Engineering & Sy*tem Safety, 2**:1***69. </line>

<line> LÓPEZ-IBÁÑEZ, M et al. (2016). The i*ac* pa*ka*e: Iterate* racing *or au*o*atic algorithm </line>

<line> *onfiguration. Operatio*s Research Perspe*t*ves, 3:43-*8. </line>

<line> LOUR***O, H. R., MARTIN, O. C., E STÜTZLE, *. (201*). Iterated loc*l s*a*ch: </line>

<line> Fra*ework and applica*ions. *n *andbook of m**aheurist*cs, p. *2*-1*8. Sp*inger. </line>

<line> LU, S et *l. (2021). A *ybrid DBH-VNS for high-end **uip*e*t prod*ction schedu*ing with </line>

<line> mach*ne failur*s and preventive mai*tenance *cti*iti*s. *ourna* of Co*putational a*d </line>

<line> Appl*ed Mathematics, 384:113195. </line>

</par>

<par>

<line> *A, J et al. (2022). A compre*ensive comparison am*ng **tahe*r*stics (MHs) </line>

</par>

<par>

<line> geohazard modeling us*ng ma*hi*e learn*ng: In*ights f*om a case stud* of </line>

<line> **ndslide </line>

</par>

<par>

<line> dis**acement prediction. Engineering Appl*cati**s of Artificial Inte*li*ence, 114:105150. </line>

<line> MARMIER, F., VARNIE*, C., E ZERH*UNI, N. (2009). *tatic *t *ynamic scheduling of </line>

</par>

<par>

<line> maintenance activities un*er the constraints of s**ll*. </line>

<line> Journ*l *f Oper*tions and Logistic*, </line>

</par>

<par>

</par>

<par>

<line> PINEDO, M. (2016). Scheduling: theor*, algo*ithms, and **st*ms. *pringer, *ham, 5 *dition. </line>

<line> QI, X., CHEN, T., E **, F. (1999). Sch*duling t*e mai*t*nance *n a single *ac*ine. </line>

<line> Journal of the Operational Research Society, 50(10):1071-1*78. </line>

<line> RUIZ-TORRES, A. J., PALETT*, G., E M\HALLAH, R. (2016). Makesp*n mi*i*i*ation </line>

</par>

<par>

<line> *ith sequence depe*dent machine d*ter*ora*ion and maintena*ce </line>

<line> events. Int*rn**ional </line>

</par>

<par>

<line> Journal *f Productio* Rese*rch, *5(2):4*2-4*9. </line>

</par>

<par>

<line> *HELD*N, M. R., F*LLYAW, M. J., E THOMPSO*, W. D. (1*96). The *se a** </line>

</par>

<par>

<line> in*erpretation of th* fri*dman </line>

<line> t*st in the analysis of o*d*nal-scale da*a in *epeated m*asures </line>

</par>

<par>

<line> de*igns. P*ysiothe*apy *esear*h *nternational, 1(4):22*-228. </line>

<line> UPASANI, * ** al. (20*7). Distributed maint**an*e plannin* i* manufact*rin* industries. </line>

<line> *omput*rs & Indust*ia* *ngineering, *08:1-14. </line>

<line> VAL**DA, E. * *UIZ, R. (2*11). A genetic a*g*rithm fo* the unr*lated par**lel machine </line>

<line> scheduling pro*l*m with sequenc* dep*ndent setup t**e*. European *o*rnal of Operational </line>

<line> Research, *11 (3):612-622. </line>

</par>

<par>

<line> Rev. FSA, T*resina PI, v. 20, n. 10, art. 9, p. ***-2*2, out. 2023 </line>

<line> www4.fsa*et.com.b*/*evista </line>

</par>

</page>

<page>

<par>

<line> A. A. Santos, *. X. Martins, *. J. *. Sousa, R. H. *. Mac**d* </line>

</par>

<par>

<line> *ANG, J. E *I*O, *. (2021). Optimal prevent*ve maintenance pol*c* of th* b*lanced </line>

<line> system under the semi-ma*kov *odel. Reliability E*g**eering & Sy*tem Safe*y, </line>

<line> *ANG, * e* al. (*018). Source term *stim*tion of haz**dous *aterial rel*ases using hybrid </line>

<line> g*netic algor*thm *i*h composite *ost fun*tions. Eng*n**ring Applic*tions o* Art*fi*ia* </line>

<line> I*telli*e*ce, 75:102-113. </line>

</par>

<par>

<line> XU, J et a*. (2019). An iterated local search an* tabu search </line>

<line> for two-parall*l machine </line>

</par>

<par>

<line> sch*duling pro*lem to minimiz* the maximu* to*al c*mpl*tion ti*e. Jour*al of </line>

<line> Info*mation and Optim*zatio* Sciences, 40(3):751-766. </line>

</par>

<par>

<line> Como Re**renciar este Artigo, *on*orme ABNT: </line>

<line> SAN*OS, *. A; MARTINS, A. X; SOUSA, *. *. F; MACHA*O, R. H. C. Mé*odo* Heur**ticos e </line>

</par>

<par>

<line> M*t*-Heurís*icos para a *e*ol*ção do </line>

<line> Problema *e Sequenciamento de Ordens *e M*n*tenção </line>

</par>

<par>

<line> Preventiva d* Longo Prazo. Rev. FSA, *eresina, v. *0, n. 1*, art. *, p. *75-*02, out. *023. </line>

</par>

<par>

<line> Contribui*ão dos A*t*res </line>

<line> A. X. **rtins </line>

<line> R. H. C. *achado </line>

</par>

<par>

<line> 1) c*ncepçã* e *lanejament*. </line>

</par>

<par>

<line> 2) anál*se e int*rpretaç*o dos dado*. </line>

</par>

<par>

<line> 3) el**oraç*o do ra**unho ou na re*isão *rítica do conteúdo. </line>

</par>

<par>

<line> 4) participação na a*r*vação da *ers*o final do manuscrito. </line>

</par>

<par>

<line> Rev. FSA, Teresi**, v. 20, n. 10, art. 9, p. 175-202, out. 2023 </line>

<line> *ww4.fsanet.com.br/*ev*sta </line>

</par>

</page>

</document>

Refbacks

There are currently no refbacks.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

ISSN 1806-6356 (Print) and 2317-2983 (Electronic)

Username
Password
Remember me