Workflow management systems (WfMSs) have been used to support a variety of business processes. As organizations adopt new working models, such as e-commerce, new challenges arise for workflow systems. These challenges include support for the adequate management of quality of service (QoS) and the development of new solutions to facilitate the composition of workflow applications involving Web services. The good management of QoS directly impacts the success of organizations participating in ecommerce activities by better fulfilling customer expectations and achieving customer satisfaction. To enable adequate QoS management, research is required to develop mechanisms that specify, compute, monitor, and control the QoS of the products or services to be delivered. The composition of workflows to model e-service applications differs from the design of traditional workflows due to the number of Web services available during the composition process and to their heterogeneity. Two main problems need to be solved: how to efficiently discover Web services and how to facilitate their interoperability. To enhance WfMSs with QoS management, we have developed a QoS model that allows for the description of nonfunctional aspects of workflow components, from a quality of service perspective. To automatically compute the overall QoS of a workflow, we have developed a mathematical model and implemented an algorithm (SWR algorithm). Our QoS model and mathematical model have been validated with the deployment and execution of a set of production workflows in the area of genetics. The analysis of the collected data proves that our models provide a suitable framework for estimating, predicting, and analyzing the QoS of production workflows. To support, facilitate, and assist the composition of workflows involving Web services, we present a solution based on ontologies. We have developed an algorithm that workflow systems and discovery mechanisms can use to find Web services with desired interfaces and operational metrics, and to assist designers in resolving heterogeneity issues among Web services. Our approach provides an important solution to enhance Web service discovery and interoperability.