Unrelated parallel machine scheduling problem: a cement industry case study

Abstract

This dissertation considers the problem of scheduling unrelated parallel machines, with unequal release dates and machine eligibility constraints, to minimize the total flow time of the system. It establishes an analogy between this problem and an existing process in the cement industry { the loading of trucks by the customers. Hence, it intends to find opportunities for improvement in the reduction of the customers' interaction times and in their experience inside the cement plants. To achieve this goal, three optimization models are proposed, one exact and two heuristics. Also, an extensive series of computational tests are carried out to compare the performance of the methods. The exact method, based on a mathematical formulation of the problem, requires a high computational time and it is incapable of dealing with large instances. Consequently, it is not a viable solution for an industrial sized problem. However, it contributes to a better understanding of the structure of the problem and to develop efficient heuristics. The heuristics, one based on dispatching rules and the other on a simulated annealing algorithm, show potential for the implementation in a real life scenario. Although simulated annealing gives considerably better solutions than the other heuristic, it takes more time to give results and it is more complex to implement. The dispatching rules based heuristic gives solutions almost instantly and more easily includes certain characteristics of the problem. In general, these methods improve the quality of service provided, reducing the overall time the customers are spending inside the cement plants. Thus, cement industry can and should use optimization models to improve their operations and the customers' experience.

Esta dissertação considera o problema de agendamento de máquinas paralelas não relacionadas, com datas de disponibilidades diferentes e restrições de elegibilidade, para minimizar o tempo total de fluxo do sistema. Esta estabelece também uma analogia entre este problema e um processo existente na indústria cimenteira - o carregamento de camiões pelos clientes. Assim, pretende encontrar oportunidades de melhoria na redução dos tempos de interação dos clientes e na sua experiência dentro das cimenteiras. Para atingir este objetivo, três modelos de otimização são propostos, um exato e duas heurísticas. Além disso, uma extensa série de testes computacionais é realizada para comparar o desempenho dos métodos. O método exato, baseado numa formulação matemática do problema, requer bastante tempo computacional e é incapaz de lidar com instâncias grandes. Consequentemente, não é uma solução viável para um problema de tamanho industrial. No entanto, contribui para uma melhor compreensão da estrutura do problema e para desenvolver heurísticas eficientes. As heurísticas, uma baseada em regras de despacho e a outra num algoritmo de simulated annealing, mostram potencial para uma implementação num cenário da vida real. Embora o simulated annealing ofereça soluções consideravelmente melhores do que a outra heurística, este necessita de mais tempo para fornecer resultados e é mais complexo de implementar. A heurística baseada em regras de despacho fornece soluções quase instantaneamente e pode incluir mais facilmente certas características do problema. Em geral, estes métodos melhoram a qualidade do serviço prestado, reduzindo o tempo total que os clientes gastam dentro das cimenteiras. Assim, a indústria cimenteira pode e deve usar modelos de otimização, para melhorar as suas operações e a experiência dos clientes.