Compositionallity of process scheduling techniques in workflow

Os sistemas de workflow são componentes presentes nas empresas de hoje para automatizar e otimizar processos de negócio. Uma das atividades desses sistemas é a de direcionar a execução de tarefas para seus participantes, e quando há um excesso dessas tarefas, uma decisão quanto à ordem de sua execução deve ser tomada. Os sistemas de workflow atuais utilizam principalmente a técnica FIFO (First In First Out) para realizar tal ordenação executando as tarefas na ordem de sua chegada. Mas ganhos mensuráveis podem ser atingidos quando se realiza tal ordenação de maneira diferente. Este trabalho apresenta um estudo aprofundado do comportamento de técnicas de escalonamento em sistemas de workflow e propõe uma metodologia de aplicação destas técnicas de escalonamento em cenários de workflow complexos. Para construir esta metodologia, analisou-se primeiramente o comportamento de técnicas de escalonamento escolhidas em cenários básicos de workflow. Foram usadas tanto técnicas locais de escolha de tarefas quanto algoritmos genéticos, que possuem uma visão global do problema. Os cenários de workflow estudados levam em conta três características importantes: eles são dinâmicos, possuem incertezas quanto ao tempo de processamento das tarefas em suas atividades, e também possuem incertezas quanto à rota que tais tarefas seguem nos desvios condicionais dos processos.Para manipular tais incertezas, o trabalho utiliza a técnica guess and solve, proposta pelos autores em trabalhos prévios. Simulações foram feitas para se gerar os resultados do comportamento das técnicas escolhidas nos cenários básicos de workflow, e tais resultados foram analisados numérica e estatisticamente utilizando ANOVA. Propôs-se então uma metodologia para a aplicação destas melhores técnicas de escalonamento já conhecidas nos componentes mais básicos de cenários mais complexos. Um conjunto de cenários complexos foi submetido a testes de simulação seguindo os mesmos parâmetros dos cenários básicos, utilizando a metodologia proposta, e os resultados mostram que tal metodologia traz ganhos em relação às métricas estudadas na maioria dos casos, quando não se tem execução paralela nos cenários, sendo que no pior caso a metodologia é tão boa quanto as outras, e em seu caso geral, é melhor que o das outras técnicas. Mostram também que quando se adiciona esta execução paralela nos cenários, os resultados se deterioram, apontando em direções futuras de pesquisaWorkflow systems are present in today's companies to automate and optimize their business processes. One activity of these systems is to direct the execution of its tasks to their executors, and when there is an excess of these tasks, a decision must be made regarding the order of execution of these tasks. Current workflow systems use the FIFO (First In First Out) policy to make those decisions, executing the tasks according to their arrival order. But it is possible to achieve measureable gains by doing this task ordering differently. This work presents a study of the behavior of scheduling techniques in workflow systems and proposes a methodology to apply these techniques to more complex workflow scenarios. To build this methodology, the authors analyzed the behavior of selected scheduling techniques in basic workflow scenarios. Both local and global scheduling techniques were chosen, ranging from dispatching rules to a genetic algorithm. The studied workflow scenarios have three important characteristics: they are dynamic, they have uncertainties on the processing time of the tasks in the process, and they also have uncertainties on the route each task follows within its process. To handle these uncertainties, this work uses the guess and solve technique, proposed by the authors in previous works. Simulation experiments were performed to generate the results on the behavior of the scheduling techniques in the basic workflow scenarios, and the mentioned results were analyzed numerically and statistically using ANOVA. The work then proposes a methodology to apply the best scheduling techniques in subcomponents of complex scenarios. The authors applied simulation to the complex scenarios using the proposed methodology, and the results show that it brings improvements when compared to the other tested techniques. When there is no parallel execution in the process, the worst case of the methodology is that it is no worse then the others, and its general case brings measureable improvements. When there is parallel execution, the methodology has its results deteriorated, which points to future research in the fiel