Heuristics-based scheduling of composite web service workloads

ABSTRACT

Web services can be aggregated to create composite workflows that provide streamlined functionality for human users or other systems. Although industry standards and recent research have sought to define best practices and to improve end-to-end workflow composition, one area that has not fully been explored is the scheduling of a workflow's web service requests to actual service provisioning in a multi-tiered, multi-organisation environment. This issue is relevant to modern business scenarios where business processes within a workflow must complete within QoS-defined limits. Because these business processes are web service consumers, service requests must be mapped and scheduled across multiple web service providers, each with its own negotiated service level agreement. In this paper we provide heuristics for scheduling service requests from multiple business process workflows to web service providers such that a business value metric across all workflows is maximised. We show that a genetic search algorithm is appropriate to perform this scheduling, and through experimentation we show that our algorithm scales well up to a thousand workflows and produces better mappings than traditional approaches.

REFERENCES

• 1: A. Ankolekar, et al. "DAML-S: Semantic Markup For Web Services," In Proc. of the Int'l Semantic Web Working Symposium, 2001.
• 2: Lawrence Davis, Job Shop Scheduling with Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.136-140, July 01, 1985
• 3: Hsiao-Lan Fang , Peter Ross , Dave Corne, A Promising Genetic Algorithm Approach to Job-Shop SchedulingRe-Schedulingand Open-Shop Scheduling Problems, Proceedings of the 5th International Conference on Genetic Algorithms, p.375-382, June 01, 1993
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: John H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press, Cambridge, MA, 1992
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: "Business Processes in a Web Services World," www-128.ibm.com/developerworks/webservices/library/ws-bpelwp/.
• 8: Gokul Soundararajan , Kaloian Manassiev , Jin Chen , Ashvin Goel , Cristiana Amza, Feedback-based Scheduling for Back-end Databases in Shared Dynamic Content Server Clusters, Proceedings of the Second International Conference on Automatic Computing, p.348-349, June 13-16, 2005 [doi>10.1109/ICAC.2005.29]
• 9: B. Srivastava and J. Koehler. "Web Service Composition Current Solutions and Open Problems," ICAP, 2003.
• 10: Bhuvan Urgaonkar , Abhishek Chandra, Dynamic Provisioning of Multi-tier Internet Applications, Proceedings of the Second International Conference on Automatic Computing, p.217-228, June 13-16, 2005 [doi>10.1109/ICAC.2005.27]
• 11: Liangzhao Zeng , Boualem Benatallah , Marlon Dumas , Jayant Kalagnanam , Quan Z. Sheng, Quality driven web services composition, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775211]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

Keywords:
QoS, heuristics, scheduling, web services, workflows