[en] A SIMPLE AND EFFECTIVE HYBRID GENETIC SEARCH FOR THE JOB SEQUENCING AND TOOL SWITCHING PROBLEM

[pt] UMA BUSCA GENÉTICA HÍBRIDA SIMPLES E EFETIVA PARA O PROBLEMA DE SEQUENCIAMENTO DE TAREFAS E TROCA DE FERRAMENTAS

[pt] JORDANA ZERPINI MECLER

[pt] METAHEURISTICAS

[pt] TROCA DE FERRAMENTAS

[pt] BUSCA GENETICA HIBRIDA

[pt] SEQUENCIAMENTO DE TAREFAS

[pt] OTIMIZACAO COMBINATORIA

[en] METAHEURISTICS

[en] TOOL SWITCHING

[en] HYBRID GENETIC SEARCH

[en] JOB SEQUENCING

[en] COMBINATORIAL OPTIMIZATION

[pt] O problema de sequenciamento de tarefas e troca de ferramentas (job sequencing and tool switching problem - SSP) tem sido extensivamente estudado na área de pesquisa operacional, devido à sua relevância prática e interesse metodológico. Dada uma máquina que pode carregar uma quantidade limitada de ferramentas simultaneamente e um número de tarefas que requerem um subconjunto das ferramentas disponíveis, o SSP procura uma sequência de tarefas que minimize o número total de trocas de ferramentas na máquina. Para resolver este problema, é proposta uma busca genética híbrida simples e efetiva baseada em uma representação de solução genérica, um operador de decodificação sob medida, buscas locais eficientes e técnicas de gerenciamento de diversidade. Para orientar a busca, um objetivo secundário desenvolvido para tratar empates é introduzido. Essas técnicas permitem explorar soluções estruturalmente distintas e escapar de ótimos locais. Conforme apresentado nos experimentos computacionais em instâncias clássicas, o algoritmo proposto supera significativamente todas as abordagens anteriores, mesmo sendo de fácil entendimento e implementação. Por fim, resultados obtidos em um novo conjunto de instâncias maiores são reportados para estimular futuras pesquisas e análises comparativas.

[en] The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.

THIBAUT VICTOR GASTON VIDAL

ANAND SUBRAMANIAN

MARCO SERPA MOLINARO

MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO

ANAND SUBRAMANIAN

THIBAUT VICTOR GASTON VIDAL

2020-08-19

2020-04-29

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=49103@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=49103@2

https://doi.org/10.17771/PUCRio.acad.49103