Please use this identifier to cite or link to this item: https://repositorio.ufpb.br/jspui/handle/123456789/13109
Full metadata record
DC FieldValueLanguage
dc.creatorHerthel, Ana Beatriz Fernandes-
dc.date.accessioned2019-01-28T20:30:52Z-
dc.date.available2019-01-28-
dc.date.available2019-01-28T20:30:52Z-
dc.date.issued2018-03-14-
dc.identifier.urihttps://repositorio.ufpb.br/jspui/handle/123456789/13109-
dc.description.abstractThe popularization of mobile devices and other equipments with virtual singlefinger keyboards unveils the fact that the QWERTY layout, originally developed for typing with all ten fingers, is not suited for the users’ needs. The problem associated with the design of a single-finger keyboard layout is denoted SK-QAP and it was formally introduced in the literature as a variation of the Quadratic Assignment Problem (QAP), a classical and challenging optimization problem. A literature review was conducted to gather related work regarding single-finger and n finger keyboard layouts’ design that employ an Operations Research-based methodology. This work proposes a heuristic approach to solve the SK-QAP by means of an Iterated Local Search (ILS) algorithm, called ILS-SKQAP. Three neighborhood structures were incorporated in the local search fase of the algorithm. Two of them (contour filling and pairwise-exchange) were previously applied to solve the SK-QAP, whereas two pairs swap was adapted, in this work, from a QAP neighborhood. Furthermore, two perturbation mechanisms were developed for the ILS-SKQAP: ejection chain and multiple pairwise-exchange. ILS-SKQAP was used to solve the 24 existing instances for English, French, Italian and Spanish languages with highly competitive results both in terms of solution quality and CPU time. Moreover, a set of six instances for the Portuguese language was developed and solved by the algorithm.pt_BR
dc.description.provenanceSubmitted by Flávia Sena da Silva (flaviasena.s@gmail.com) on 2019-01-28T20:30:52Z No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) Arquivototal.pdf: 2469731 bytes, checksum: cda3c6ec41845a5701e4b519a4e7d2d0 (MD5)en
dc.description.provenanceMade available in DSpace on 2019-01-28T20:30:52Z (GMT). No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) Arquivototal.pdf: 2469731 bytes, checksum: cda3c6ec41845a5701e4b519a4e7d2d0 (MD5) Previous issue date: 2018-03-14en
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal da Paraíbapt_BR
dc.rightsAcesso abertopt_BR
dc.rightsAttribution-NoDerivs 3.0 Brazil*
dc.rights.urihttp://creativecommons.org/licenses/by-nd/3.0/br/*
dc.subjectSingle-fingerpt_BR
dc.subjectLayoutpt_BR
dc.subjectTecladopt_BR
dc.subjectQuadratic assignment problempt_BR
dc.subjectIterated local searchpt_BR
dc.subjectKeyboardpt_BR
dc.titleUma abordagem heurística para o single-finger keyboard layout problempt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Subramanian, Anand-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/2752210156480636pt_BR
dc.creator.Latteshttp://lattes.cnpq.br/1955053147716950pt_BR
dc.description.resumoA popularização de dispositivos móveis e outros aparelhos com teclados virtuais utilizados com um dedo revela o fato de que o layout QWERTY, desenvolvido originalmente para uso com os dez dedos das mãos, não atende às necessidades dos usuários. O problema associado ao desenvolvimento de um layout de teclado para um dedo é denominado SK-QAP e foi formalmente apresentado na literatura como uma variante do Quadratic Assignment Problem (QAP), um problema clássico de otimização conhecido por sua dificuldade de resolução. Uma revisão da literatura foi conduzida para reunir trabalhos relacionados ao desenvolvimento de teclados para um dedo e para n dedos que empregassem métodos vinculados à Pesquisa Operacional. Este trabalho utiliza uma abordagem heurística para resolver o SK-QAP através de um algoritmo Iterated Local Search (ILS), chamado ILS-SKQAP. Três estruturas de vizinhança foram incorporadas à fase de busca local do algoritmo. Duas delas (contour filling e pairwise-exchange) já utilizadas na resolução do SK-QAP, enquanto que a estrutura two pairs swap foi adaptada, neste trabalho, de uma vizinhança do QAP. Além disso, dois mecanismos de perturbação foram desenvolvidos para o ILS-SKQAP: ejection chain e multiple pairwise-exchange. O ILS-SKQAP foi usado na resolução das 24 instâncias existentes do SK-QAP para os idiomas inglês, francês, italiano e espanhol, obtendo resultados altamente competitivos em termos de qualidade das soluções encontradas e tempos computacionais. Ademais, seis novas instâncias foram desenvolvidas para a língua portuguesa e resolvidas pelo algoritmo.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentEngenharia de Produçãopt_BR
dc.publisher.programPrograma de Pós-Graduação em Engenharia de Produçãopt_BR
dc.publisher.initialsUFPBpt_BR
dc.subject.cnpqCNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAOpt_BR
Appears in Collections:Centro de Tecnologia (CT) - Programa de Pós-Graduação em Engenharia de Produção

Files in This Item:
File Description SizeFormat 
Arquivototal.pdfArquivo total2,41 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons