Speaker
Description
Conclusions and Future Work
Obtained results show that scheduling problems can be solved using grid based approaches. Although we had impressive results, new strategies are needed in order to best use grid resources. Asynchronous and random algorithms seem viable candidates for these problems. We plan to experiment with a Scatter Search strategy that uses an intelligent strategy for the asynchronous coordination of the intermediate solutions and to adapt other scheduling applications for the SchedScripter framework.
URL for further information
http://www.csl.ece.upatras.gr/ett
Keywords
Grid based Workflow, BPEL, Human-Resources Scheduling, Examination Timetabling
Detailed analysis
Past experience from research projects in human-resource scheduling has shown that the some of the best performing approaches are composed from a set of optimization solvers, coordinated by a solution strategy. The optimization solvers can be assigned on grid worker nodes while the coordination strategy orchestrates them in way that they exchange solution information in their effort to reach the required solution. In order to assist this process, we developed SchedScripter, as a web services based, BPEL workflow framework for distributed scheduling applications, over a Grid environment. SchedScripter provides services for the composition of the workflow swarm of worker nodes, the subproblems selection and distribution, collection of intermediate and final subproblem solutions and implementation of the strategy interface. The SchedScripter implementation is based on the JAX-WS 2.0 RI for web services, apache ODE for WS-BPEL 2.0 and BPEL4WS and apache commons java library.
Impact
The first SchedScripter case study adapted a University Examination Timetabling application, which is the evolution of the application that achieved the second place in theInternational Timetabling Competition 2007. The adaptation, including refactoring of the original code base to decompose the solver components, required only a weeks effort. This decoupling provided the possibility to experiment with different solution strategies and synchronization schemes between the solvers. The tested strategies included independent solvers with parameter sweep and a tournament approach to solvers coordination. The tournament approach lets the solvers improve the solution for a designated time frame and the best solutions become candidates for the next phase of the improvement, selected using a tournament algorithm. The first experiments, using both approaches, managed to achieve the best published solutions for most of the competition problem datasets given the same clock time allowance.