Companies are daily trying to find new ways to cope with the increasing competitive pressures imposed by the global economy. Static and huge enterprises are being replaced by dynamic business networks where each participant offers to the others specialized services. Service-Oriented Computing (SOC) is being considered by many as a very interesting technological solution to the new B2B interactions introduced by this economical scenario. This paper presents a Virtual Marketplace infrastructure, called VM-Flow, which supports Dynamic Virtual Enterprises, is workflow-based and introduces a series of interaction policies that treat aspects like autonomy and privacy. Also, Service Composition is shown as a suitable solution to implement these policy-based interorganizational interactions. Some issues on the developed prototype are discussed and an application built over it is described. © 2004 Springer Science + Business Media, Inc.146 265285van der Aalst, W.M.P., The application of Petri Nets to Workflow Management (1998) The Journal of Circuits, Systems and Computers, 8 (1), pp. 21-66Ávila, P., Putnik, G.D., Cunha, M.M., Brokerage function in Agile/Virtual Enterprise integration - A literature review (2002) 3rd IFIP Working Conference On Infrastructures For Virtual Enterprises (PRO-VÉ02), pp. 65-72. , Portugalvan der Aalst, W.M.P., Weske, M., The P2P Approach to Interorganizational Workflows (2001) Proceedings of the 13th International Conference On Advanced Information Systems Engineering (CAiSE'01), 2068, pp. 140-156. , Lecture Notes in Computer Science, Springer-Verlag, BerlinBichler, M., Beam, C., Segev, A., An electronic broker for business-to-business electronic commerce on the Internet (1998) Int. Journal of Cooperative Information Systems, 7, pp. 315-331(2003), http://www-106.ibm.com/developerworks/webservices/library/ws-bpel/, BEA Systems, IBM, Microsoft, SAP AG and Siebel Systems. Business Process Execution Language for Web Services (BPEL4WS) - Version 1.1(2002), http://www.sun.com/software/xml/developers/wsci/sci-spec-10.pdf, BEA Systems, Intalio, SAP and Sun Microsystems. Web Services Choreography Interface 1.0Curbera, F., Khalaf, R., Mukhi, N., Tai, S., Weerawarana, S., The next step in Web Services (2003) Communications of the ACM, 46 (10), pp. 29-34(2003), http://alphaworks.ibm.com/tech/bpws4j/, IBM. Business Process Execution Language for Web Services Java Run TimeMin, H., Zhou, G., Supply chain modeling: Past, present and future (2002) Computers & Industrial Engineering, 43, pp. 231-249Ouzounis, V., (2001) An Agent-Based Platform For the Management of Dynamic Virtual Enterprises, , Doctor Thesis, TU BerlinOuzounis, V., Tschammer, V., Towards Dynamic Virtual Enterprises (2001) Proceedings of the First IFIP Conference On E-Commerce, E-Business, E-Government (I3E 2001), pp. 177-192. , Zurich, SwitzerlandPeltz, C., (2003) Web Services Orchestration - a Review of Emerging Technologies, Tools, and Standards, , White Paper, Hewlett PackardPapazoglou, M.P., Georgakopoulos, D., Service-oriented computing (2003) Communications of the ACM, 46 (10), pp. 25-28Santos, I.J.G., Madeira, E.R.M., Policy-based Orchestration and Choreography of Services on Dynamic Virtual Enterprises (2003) 3rd IFIP I3E Conference On E-Commerce, E-Business and E-Government, , Research Colloquium, BrazilSchulz, K., Orlowska, M., Architectural Issues for Cross-Organisational B2B Interactions (2001) International Workshop On Distributed Dynamic Multiservice Architectures (DDMA), , IEEE Computer Society Press, USAStrieker, C., Riboni, S., Kradolfer, M., Taylor, J., Market-based Workflow Management for Supply Chains of Services (2000) 33rd Annual Hawaii International Conference On System Sciences (HICSS-33)Silva, F.R.S., Wainer, J., Madeira, E.R.M., Ellis, C., CORBA Based Architecture for Large Scale Workflow (2000) IEICE Transactions On Communications, 83 B (5), pp. 988-998Tolle, M., Bernus, P., Vesterager, J., Reference Models for Virtual Enterprises (2002) IFIP Working Conference On Infrastructures For Virtual Enterprises (PRO-VÉ02), pp. 3-10. , PortugalVandermeer, D., Datta, A., Dutta, K., Thomas, H., Ramamritham, K., Navathe, S.B., FUSION: A System Allowing Dynamic Web Service Composition and Automatic Execution (2003) IEEE International Conference On E-Commerce, p. 399. , California, USA(2004) Web Services Description Language (WSDL) Version 2.0 - Part 1: Core Language, , http://www.w3.org/TR/wsdl20, World Wide Web Consortium (W3C), W3C Working Draft, March(2004) Web Services Choreography Description Language Version 1.0 (WS-CDL), , http://www.w3.org/TR/ws-cdl-10/, World Wide Web Consortium (W3C), W3C Working Draft, April