{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T23:32:08Z","timestamp":1780097528677,"version":"3.54.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>Service-Oriented Architecture (SOA) provides a flexible framework for service composition. Using standard-based protocols (such as SOAP and WSDL), composite services can be constructed by integrating atomic services developed independently. Algorithms are needed to select service components with various QoS levels according to some application-dependent performance requirements. We design a broker-based architecture to facilitate the selection of QoS-based services. The objective of service selection is to maximize an application-specific utility function under the end-to-end QoS constraints. The problem is modeled in two ways: the combinatorial model and the graph model. The combinatorial model defines the problem as a multidimension multichoice 0-1 knapsack problem (MMKP). The graph model defines the problem as a multiconstraint optimal path (MCOP) problem. Efficient heuristic algorithms for service processes of different composition structures are presented in this article and their performances are studied by simulations. We also compare the pros and cons between the two models.<\/jats:p>","DOI":"10.1145\/1232722.1232728","type":"journal-article","created":{"date-parts":[[2007,6,8]],"date-time":"2007-06-08T15:00:08Z","timestamp":1181314808000},"page":"6","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":789,"title":["Efficient algorithms for Web services selection with end-to-end QoS constraints"],"prefix":"10.1145","volume":"1","author":[{"given":"Tao","family":"Yu","sequence":"first","affiliation":[{"name":"University of California, Irvine, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yue","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kwei-Jay","family":"Lin","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE International Conference on Service Computing (SCC'04)","author":"Aggarwal R."},{"key":"e_1_2_1_2_1","unstructured":"BPMI.org. 2002. Business Process Modeling Language (BPML) version 1.0. http:\/\/www.bpmi.org\/bpml.esp.  BPMI.org. 2002. Business Process Modeling Language (BPML) version 1.0. http:\/\/www.bpmi.org\/bpml.esp."},{"key":"e_1_2_1_3_1","unstructured":"Cardoso J. SWR algorithm. http:\/\/lsdis.cs.uga.edu\/proj\/meteor\/Composition\/SWR_Algorithm.htm.  Cardoso J. SWR algorithm. http:\/\/lsdis.cs.uga.edu\/proj\/meteor\/Composition\/SWR_Algorithm.htm."},{"key":"e_1_2_1_4_1","volume-title":"Tech. Rep. HPL-200039, Software Technology Laboratory","author":"Casati F.","year":"2000"},{"key":"e_1_2_1_5_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press."},{"key":"e_1_2_1_6_1","unstructured":"Curbera F. Goland Y. Klein J. Leymann F. Roller D. Thatte S. and Weerawarana S. 2003. Business Process Execution Language for Web Services Version 1.1. http:\/\/www-106.ibm.com\/developerworks\/webservices\/library\/ws-bpel.  Curbera F. Goland Y. Klein J. Leymann F. Roller D. Thatte S. and Weerawarana S. 2003. Business Process Execution Language for Web Services Version 1.1. http:\/\/www-106.ibm.com\/developerworks\/webservices\/library\/ws-bpel."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 8th IEEE International Conference on Enterprise Distributed Object Computing (EDOC'04)","author":"Jaeger M. C.","year":"2004"},{"key":"e_1_2_1_8_1","unstructured":"Khan S. 1998. Quality adaptation in a multisession multimedia system: Model algorithms and architecture. Ph.D. dissertation Department of ECE University of Victoria.   Khan S. 1998. Quality adaptation in a multisession multimedia system: Model algorithms and architecture. Ph.D. dissertation Department of ECE University of Victoria."},{"key":"e_1_2_1_9_1","first-page":"157","article-title":"Solving the knapsack problem for adaptive multimedia systems","volume":"2","author":"Khan S.","year":"2002","journal-title":"Studia Informatica Universalis"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of 20th Joint Conference of IEEE Computer and Communications Societies (INFOCOM'01)","author":"Korkmaz T."},{"key":"e_1_2_1_11_1","unstructured":"Ludwig H. Keller A. Dan A. King R. P. and Franck R. 2003. Web Service Level Agreement (WSLA) Language Specification. http:\/\/www.research.ibm.com\/wsla\/WSLASpecV1-20030128.pdf.  Ludwig H. Keller A. Dan A. King R. P. and Franck R. 2003. Web Service Level Agreement (WSLA) Language Specification. http:\/\/www.research.ibm.com\/wsla\/WSLASpecV1-20030128.pdf."},{"key":"e_1_2_1_12_1","first-page":"70","article-title":"Algorithms for Knapsack problems","volume":"31","author":"Martello S.","year":"1987","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Menasce D. A. 2004. Composing Web services: A QoS view. IEEE Internet Comput. 10.1109\/MIC.2004.57   Menasce D. A. 2004. Composing Web services: A QoS view. IEEE Internet Comput. 10.1109\/MIC.2004.57","DOI":"10.1109\/MIC.2004.71"},{"key":"e_1_2_1_14_1","unstructured":"Rao J. 2004. Semantic Web service composition via logic-based program synthesis. PhD thesis. Department of Computer and Information Science Norwegian University of Science and Technology.  Rao J. 2004. Semantic Web service composition via logic-based program synthesis. PhD thesis. Department of Computer and Information Science Norwegian University of Science and Technology."},{"key":"e_1_2_1_15_1","volume-title":"Tech. Rep. UM-CSE-TR-456-02 (http:\/\/irl.eecs.umich.edu\/jamin\/)","author":"Winick J.","year":"2002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2005.857212"},{"key":"e_1_2_1_17_1","unstructured":"Yu T. 2006. Quality of service (QoS) in Web services: Model architecture and algorithms. Ph.D. thesis University of California Irvine CA.   Yu T. 2006. Quality of service (QoS) in Web services: Model architecture and algorithms. Ph.D. thesis University of California Irvine CA."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE'05)","author":"Yu T.","year":"2005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2004.11"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1232722.1232728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:47:17Z","timestamp":1672256837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1232722.1232728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1232722.1232728"],"URL":"https:\/\/doi.org\/10.1145\/1232722.1232728","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}