UMA ABORDAGEM HEURÍSTICA PARA O SINGLE-FINGER KEYBOARD LAYOUT PROBLEM

O problema associado ao desenvolvimento de layout de teclado para um dedo é denominado SK-QAP e definido como variante do Quadratic Assignment Problem (QAP), um problema clássico de otimização. Este trabalho aborda o SK-QAP através de um algoritmo Iterated Local Search (ILS), denominado ILS-SKQAP, que conta com três estruturas de vizinhança em sua fase de busca local. Duas delas foram anteriormente utilizadas na resolução do SK-QAP e a terceira (two pairs swap) adaptada, neste trabalho, de 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.