Dissertação de Mestrado

Este trabalho aborda o problema de sequenciamento de tarefas em máquinas diferentes em paralelo, considerando elegibilidade e instante de liberação de máquinas e tarefas, com o objetivo de minimização do atraso ponderado total. Segundo a notação de Graham et al. (1979), tal problema pode ser classificado como Rm || rj, rm, e || wjTj. A pesquisa concentrou-se em métodos exatos, seguindo as oportunidades de estudo neste campo mapeadas por Li e Yang (2009), comparando-se o desempenho de 4 modelos de programação inteira mista em termos de gap de otimalidade obtido, sendo um deles baseado em variáveis de precedência entre tarefas processadas (Prec) e os outros três baseados em variáveis de posição (ou slot) de processamento nas máquinas (Pos, PosDv e PosDvH). Os modelos PosDv e PosDvH incorporam desigualdades válidas para estimação de upper bounds e lower bounds. Além disso, o modelo PosDvH inclui uma heurística para estimação da quantidade máxima de posições de processamento necessários por máquina. O maior gap médio resultante para as 138 instâncias testadas foi observado no modelo Prec, seguido pelo modelo Pos e pelos modelos PosDv e PosDvH, estes dois últimos empatados. Os modelos que incorporam as desigualdades válidas (PosDv e PosDvH) invariavelmente tiveram desempenho igual ou superior que os demais modelos testados (Prec e Pos), ambos com a geração de um gap médio cerca de 67 p.p. menor que o modelo Prec e cerca de 52 p.p. menor que o modelo Pos. A diminuição do gap médio em tais modelos deveu-se mais ao aumento do lower bound obtido do que à diminuição do upper bound. A incorporação da heurística no modelo PosDvH não trouxe melhoria significativa no seu desempenho quando comparado ao modelo PosDv, ficando a média e a mediana do delta absoluto dos gaps obtidos nesses modelos em 1,1 p.p. e 0,4 p.p. respectivamente. Por fim, observou-se correlação positiva entre número de máquinas e tarefas com os gaps médios obtidos e correlação negativa entre o fator de dispersão (dsp) dos prazos desejados de entrega com os gaps médios obtidos. Ademais, observou-se gaps médios menores para instâncias com maior fator de postergação (dt) do prazo desejado de entrega.

This research deals with the problem of job scheduling in unrelated parallel machines, considering machine eligibility and task and machine release times, in order to minimize total weighted tardiness. Using the notation of Graham et al. (1979), this problem can be classified as Rm || rj, rm, and || wjTj. This paper focused on exact methods, according to future studies opportunities mapped in this field by Li and Yang (2009), comparing the performance of 4 mixed integer programming models in terms of optimality gap obtained. One model is based on job precedence variables (Prec), and the other three are based on position (or slot) variables for processing on machines (Pos, PosDv, and PosDvH). The PosDv and PosDvH models incorporate valid inequations for upper and lower bound estimation. Additionally, the PosDvH model includes a heuristic for estimating the maximum number of processing positions (slots) required per machine. The highest average gap resulting from the 138 tested instances was observed in the Prec model, followed by the Pos model, with the PosDv and PosDvH models tying for the next position. Models incorporating valid inequalities (PosDv and PosDvH) invariably performed equal to or better than the other tested models (Prec and Pos), both generating an average gap about 67 p.p. lower than the Prec model and about 52 p.p. lower than the Pos model. The decrease in the average gap in these models was mainly due to the increase in the lower bound obtained rather than the decrease in the upper bound. Incorporating the heuristic into the PosDvH model did not bring significant improvement in its performance compared to the PosDv model, with the average and median absolute delta gaps obtained in these models being 1.1 and 0.4 percentage points respectively. Finally, a positive correlation was observed between the number of machines and tasks with the average gaps obtained, and a negative correlation was observed between the dispersion factor (dsp) of delivery times and the average gaps obtained. Furthermore, smaller average gaps were observed for instances with a higher tightness factor (dt) of delivery times.