Meta-heurísticas para o sequenciamento de famílias de tarefas em máquinas paralelas uniformes de processamento em lote

Abstract

Este trabalho aborda o problema de sequenciar um conjunto de n tarefas com in- compatibilidade de famílias, com tamanhos arbitrários e tempos de processamento distintos, em um conjunto de m máquinas paralelas uniformes com capacidades di- ferentes. Neste problema, as máquinas têm uma característica especial, processar um lote de tarefas simultaneamente, desde que a capacidade da máquina não seja exce- dida. Apenas tarefas de mesma família podem ser agrupadas em um lote. O tempo de processamento do lote é igual ao maior tempo de processamento entre todas as tarefas do lote. O problema consiste em agrupar as tarefas em lotes e, em seguida, se- quenciar os lotes nas máquinas de tal maneira que o tempo de conclusão de todos os lotes seja minimizado (minimização do makespan). Como o problema pertence à classe NP-Difícil, neste trabalho, são propostos: i) um modelo de Programação Inteira-Mista para obter soluções ótimas para instâncias pequenas do problema; e ii) dois algorit- mos heurísticos baseados em meta-heurísticas para obter soluções de alta qualidade e em tempo computacional aceitável para instâncias de problemas de grande porte. Os algoritmos são baseados nas meta-heurísticas Iterated Greedy (IG) e Discrete Differential Evolution (DDE). Também estas meta-heurísticas são hibridizadas fazendo uma com- binação com métodos de busca local, utilizando uma seleção aleatória de vizinhan- ças. Os resultados dos experimentos mostram que os desempenhos dos algoritmos propostos são de alta qualidade, tendo o algoritmo DDE-Híbrido apresentado os me- lhores resultados em comparação aos algoritmos da literatura. Palavras-chave: Sequenciamento de tarefas. Máquinas paralelas de processamento em lote. Incompatibilidade de família de tarefas. Otimização combinatória. Heurísticas. Meta-heurísticas.

This work addresses the problem of scheduling a set of family incompatible jobs, with arbitrary sizes and different processing times, into a set of uniform parallel machines with different capacities. In this problem the machines have a special feature that is to process a batch of jobs simultaneously, as long as the machine capacity is not exceeded. Only jobs of the same family can be grouped together in a batch. The batch processing time equals the longest processing time of all the jobs in the batch. The problem is to group the jobs into batches and then sequence the batches on the machi- nes in such a way that the completion time of all batches is minimized (minimization of makespan). Since the problem belongs to the NP-Hard class, this work proposes: i) a Mixed Integer Programming model in order to obtain optimal solutions for small instances of the problem, and ii) two heuristic algorithms based on metaheuristics, in order to obtain high quality solutions in acceptable computational time, for ins- tances of the large problem. The algorithms are based on Iterated Greedy - IG and Discrete Differential Evolution - DDE metaheuristics. Also, these metaheuristics are hybridized by combining them with local search methods, both algorithms present high quality and using a random selection of neighborhoods. The results of the ex- periments show that the performance of the proposed algorithms are of high quality, with the DDE-Hybrid algorithm showing the best results compared to the algorithms in the literature. Keywords: Scheduling jobs. Parallel batch processing machines. Incompatibility of job family. Combination optimization. Heuristics. Metaheuristics.