FenixEdu™

Dissertação

Dual Resource Constrained Flexible Job Shop Problem using Hybrid Genetic Algorithm: Application to Quality Control Laboratory Scheduling EVALUATED

Detalhes: O escalonamento de um laboratório de controlo de qualidade tem um enorme potencial para reduzir custos e aumentar a produção. Todavia, este problema tem tido pouco suporte por parte da academia. Esta tese propõe um algoritmo genético híbrido com a possibilidade de realizar uma procura local para minimizar o total de conclusão. Este problema é formulado como uma extensão do escalonamento flexível de duplo constrangimento de recursos para a alocação de tanto máquinas como trabalhadores. Esta extensão, divide cada trabalho em três fases, possibilitando ao analista ser alocado em mais do que uma tarefa ao mesmo tempo, em maquinas diferentes, durante os períodos em que este está livre. O trabalho desenvolvido combina novas maneiras de criar a População Inicial, baseadas em tabelas incrementais que junta os trabalhos mais compatíveis. Ainda, regras para alocação sequencial de recursos foram introduzidas. Uma nova combinação de operações de crossover com probabilidades baseadas em pesos é proposta, provando que combinando diferentes tipos de crossover obtém-se melhores resultados. Adicionalmente, uma nova combinação de mutações é também aplicada e uma procura local com quatro estruturas distintas foi introduzida juntamente com um critério de paragem dinâmico que adapta os parâmetros do algoritmo. Um afinação dos parâmetros foi realizada e os resultados finais foram comparados com os da literatura. Este estudo é competitivo para pequenas instancias, alcançando soluções opimas para sete destas. Para instancias médias o algoritmo genético ultrapassa os resultados da literatura. Para grandes instancias este estudo gerou resultados significantemente melhores ultrapassando os estudos anteriores por 57%
Keywords: Laboratório de Controlo de Qualidade, Escalonamento de Duplo Constrangimento, Algoritmo Genético Híbrido, Tempo total de conclusão

Discussão: dezembro 14, 2021, 10:0