Sistema de escalonamento de processos baseado em casos

A necessidade de se ter tarefas processadas em uma planta de manufatura, clientes de banco aguardando para serem atendidos pelos caixas, aeronaves esperando autorização para pousar e unidades de programa para serem executadas em um computador têm em comum o problema de escalonamento que surge quando há necessidade de se escolher a ordem na qual as tarefas devem ser executadas e a atribuição de tarefas aos servidores para processamento. O problema de escalonar processos computacionais pode ser resolvido automaticamente por um algoritmo dedicado. Encontrar uma solução no menor tempo possível é um dos objetivos pretendidos. A metodologia Raciocínio Baseado em Casos (RBC), que é uma abordagem para representação de conhecimento e utilização deste conhecimento para auxiliar na resolução de novos problemas, toma possível reduzir o tempo gasto para se encontrar uma solução à medida que os problemas ficam maiores. Este trabalho apresenta a proposta e implementação de um sistema baseado no método RBC para a resolução de problemas de escalonamento de processos, em sistemas de tempo real crítico estático e centralizado em um ambiente monoprocessado. Esses processos devem respeitar restrições de tempo de pronto, tempo de execução e prazo de término, além das relações de precedência. O Sistema de Escalonamento de Processos Baseado em Casos (SEBC), implementado neste trabalho, possui como característica principal a idéia de simplificação de um problema através de substituições de seus subproblemas similares a problemas armazenados em uma base de casos e adaptação das soluções destes problemas na busca de uma solução para o problema apresentado. Os resultados obtidos pelo SEBC para os problemas estudados mostram que à medida que tratamos com problemas maiores, a reutilização de soluções de problemas passados pode reduzir substancialmente o tempo necessário para resolver esses problemas, ou detectar que os mesmos não têm soluçãoMultiple jobs that should be processed in a manufacturing plant, bank customers waiting to be served by tellers, aircrafts waiting for landing c1earances,and program tasks to be run on a computer have in common the scheduling problem that emerges whenever there is a choice concerning the order in which tasks can be performed and the assignment of tasks to servers for processing. The scheduling problem of computer processes can be automatically solved with a dedicated algorithm. One of the goals is to find a solution whenever one exists in a minimum time. The Case-Based Reasoning methodology (CBR), an approach for knowledge representation and problem solving, makes it possible to reduce processing time to get a solution when the problems become large. This work implements and evaluates a CBR-based algorithm for solving the problem of process scheduling, in critical real time systems with a monoprocessor environment. These processes must respect restrictions of ready time, computation time and deadline, besides precedence relations. The Case-Based Reasoning Real-Time Scheduler system (CBR-RTS), implemented in this work, holds, as main characteristic, the idea of simplification of a problem. This is made by substitutions of parts of the problem, that are in a case base, and adaptation of that problems aiming a solution for the presented problem. The experiments described in this work suggest that the CBR-RTS system can contribute to an expressive reduction in processing times required to schedule complex problems. In the tested examples, our algorithm performed better than the dedicated algorithm for large problem