FenixEdu™

Dissertação

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

Detalhes: {pt=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%, en=Quality control laboratory scheduling has huge potential to reduce costs and increase production. However, this is not widely discussed or supported by academics. This thesis proposes a hybrid genetic algorithm with and without variable neighborhood search to minimize the total completion time. The problem is formulated as an extension of a Dual Resource Constrained Flexible Job Shop Problem for the allocation of both machine and worker resources. This extension divides each job into three phases allowing the worker to perform other jobs in between these mandatory presential stages. While maintaining the traditional structure of genetic algorithms, this work presents a way of creating the Initial Population, based on increment tables that groups the most compatible jobs together. Also, rules regarding the allocation of resources to sequential tasks were introduced. A new combination of crossover operations with weighted probabilities are proposed, proving that combining multiple types of crossovers achieves fitter results. Additionally, a novel combination of mutation operations is implemented and a variable neighborhood search with four different structures was introduced alongside a dynamic termination criteria that adapts the parameters of the algorithm. A tuning of the parameters was performed and the final results were compared to the benchmark. This study is competitive with the compared study for small instances, achieving the optimal solution for seven of them. For medium-sized instances the proposed genetic algorithm surpasses it. For large-sized instances this study generated significant results surpassing the compared results by 57%}
Keywords: {pt=Laboratório de Controlo de Qualidade, Escalonamento de Duplo Constrangimento, Algoritmo Genético Híbrido, Tempo total de conclusão, en=Quality Control Laboratory, Dual Resource Constrained, Hybrid Genetic Algorithm, Total Completion Time}

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