A framework for dynamic scheduling based on quality of service metrics

Abstract

In this thesis the scheduling process in production environments is improved through the development of a framework that implements a distributed dynamic scheduling methodology based on quality of service. Such methodology takes into account contingency, priority fluctuations and incorporates a scheduling algorithm referred to as Quality of Service-based Maximum Urgency First (QB-MUF) algorithm. The QB-MUF algorithm gives high priority to jobs with low probability of failing according to suitable failure probabilities for particular application environ- ments. The contribution of this research is related to the use of quality of service metrics, calculated from the job meta-data, as part of the information used in the decision making process of the scheduling. To validate the dynamic scheduling framework, two study cases are considered. First a simplified model of the digital publishing workflow is build upon the framework in order to observe the behavior of the proposed scheduling strategy. Second, a grid environment where resources are connected via two-level hierarchical networks is simulated. In this case, the first level is a wide area network connecting local area networks at the second level. The implemented model represents the composition of two, wide-area distributed, image operators providing treatment of data images. Experimental results, show that the QB-MUF algorithm outperforms traditional scheduling strategies such as the Minimum Laxity First and the First In First Out algorithms.

En esta tesis el proceso de planificación en entornos de producción es mejorado a través del desarrollo de un sistema que implementa una metodología dinámica de planificación basada en calidad de servicio. Dicha metodología toma en cuenta contingencias, fluctuaciones de prioridad e incorpora un algoritmo de planificación nombrado como "Quality of Service-based Maximum Urgency First (QB-MUF)". E algoritmo "QB-MUF" da mayor prioridad a aquellos trabajos con baja probabilidad de fallar de acuerdo a algunas probabilidades de falla que se adecuan para cada problema en particular La contribución de esta investigación esta relacionado con el uso de métricas para calidad del servicio, las cuales son calculadas a partir de de meta-datos extraídos del trabajo, como parte de la información usada en la toma de decisiones durante el proceso de planificación Para validar el sistema de planificación dinámica, dos casos de estúdio se consideraron. Primero, un modelo simplificado de flujo de trabajo en impresión digital estrategia de se construye sobre el sistema para observar el comportamiento de la planificación propuesta. Segundo, se simula un ambiente de computación en malla donde los recursos están conectados por redes separadas jerárquicamente en dos niveles. En este caso, el primer nivel corresponde a una red de área amplia (WAN por su nombre en inglés) conectando redes de área local (LAN por su nombre en inglés) como segundo nivel. El modelo implementado representa la composición dos operadores de imágenes, distribuidos en la red WAN, proveyendo tratamiento para datos de imágenes. Resultados experimentales, muestran que el algoritmo "QB-MUF" supera otros algoritmos tradicionales como son "minima laxitud primero" y "primero en entrar primero en salir”.