Selection Constructive based Hyper-heuristic for Dynamic Scheduling

A função de escalonamento desempenha um papel importante nos sistemas de produção. Os sistemas de escalonamento têm como objetivo gerar um plano de escalonamento que permite gerir de uma forma eficiente um conjunto de tarefas que necessitam de ser executadas no mesmo período de tempo pelos mesmos recursos. Contudo, adaptação dinâmica e otimização é uma necessidade crítica em sistemas de escalonamento, uma vez que as organizações de produção têm uma natureza dinâmica. Nestas organizações ocorrem distúrbios nas condições requisitos de trabalho regularmente e de forma inesperada. Alguns exemplos destes distúrbios são: surgimento de uma nova tarefa, cancelamento de uma tarefa, alteração na data de entrega, entre outros. Estes eventos dinâmicos devem ser tidos em conta, uma vez que podem influenciar o plano criado, tornando-o ineficiente. Portanto, ambientes de produção necessitam de resposta imediata para estes eventos, usando um método de reescalonamento em tempo real, para minimizar o efeito destes eventos dinâmicos no sistema de produção. Deste modo, os sistemas de escalonamento devem de uma forma automática e inteligente, ser capazes de adaptar o plano de escalonamento que a organização está a seguir aos eventos inesperados em tempo real. Esta dissertação aborda o problema de incorporar novas tarefas num plano de escalonamento já existente. Deste modo, é proposta uma abordagem de otimização – Hiper-heurística baseada em Seleção Construtiva para Escalonamento Dinâmico- para lidar com eventos dinâmicos que podem ocorrer num ambiente de produção, a fim de manter o plano de escalonamento, o mais robusto possível. Esta abordagem é inspirada em computação evolutiva e hiper-heurísticas. Do estudo computacional realizado foi possível concluir que o uso da hiper-heurística de seleção construtiva pode ser vantajoso na resolução de problemas de otimização de adaptação dinâmica.Scheduling plays an important role in manufacturing systems. It produces a scheduling plan, in order to share resources to produce several different products in the same time period. However, dynamic adaptation and optimization is a critical need in real-world manufacturing scheduling systems, since contemporary manufacturing organizations have a dynamic nature, where disturbances on working conditions and requirements occur on a continuous basis. Disturbances often arise unexpectedly, and can be for example: urgent job arrival, job cancelation, due date change, delay in the arrival, among others. These dynamic events must be taken into account, since they may have a major impact on the scheduling plan, they can disorder the plan making it ineffective. Therefore, manufacturing environments require immediate response to these dynamic events, using a real-time rescheduling method, in order to minimize the effect of such unexpected events in the performance of the production’ system. As result, scheduling systems should have the ability of automatically and intelligently maintain real-time adaptation and optimization to efficiently update the scheduling plan to the unexpected events. This way, the organization keeps clients satisfied and achieves its objectives (costs minimized and profits maximized). This dissertation addresses the problem of incorporating new tasks in a scheduling plan already generated by the scheduling system. Therefore, it proposes an optimization approach - Selection Constructive based Hyper-heuristic for Dynamic Scheduling - to deal with dynamic events that can occur over time in a manufacturing environment, with the main goal of maintaining the current scheduling plan feasible and most robust as possible. The development of this dynamic adaptation approach is inspired on evolutionary computation and hyper-heuristics. The viability of the proposed approach is tested by performing a set of experiments and analysing the results achieved. From the obtained results it is possible to conclude that the use of a selection constructive hyper-heuristic could be advantageous on solving dynamic adaptation optimization problems