Web services are modular, self-describing, self-contained, platform-independent software components that can be published by service providers over the Internet. Since web services became available, many organizations prefer to only keep their principal business, but outsource other application services over the Internet. Web service composition (WSC) is the task of combining a chain of connected single services together to create a more complex and value-added composite service. WSC requires a computer program to automatically select, integrate, and invoke multiple web services to achieve a user-defined objective. For those web services providing the same functionality, quality of service (QoS) has been mostly applied to represent their nonfunctional properties and differentiate them for service composition. QoS is a broad concept that encompasses a group of nonfunctional properties, such as execution price, execution duration, availability, execution success rate, and reputation. Existing QoS-aw are WSC approaches fall short on finding solutions with globally optimal QoS, because it is a very difficult optimization problem with logical reason-ing, discrete decisions, temporal constraints, and numerical optimization . In particular, when the number of we b services becomes large, there is a huge search space. It cannot make sure its overall QoS is optimal, considering other workflows. Another is that these approaches do not guarantee finding a solution satisfying the global QoS constraints for a composition task, even if there exists one under a different workflow. Existing approaches only try to find a composite service satisfying the functionality requirement, but do not consider QoS at all. To address the above issues, we propose a novel planning-based approach to WSC with QoS optimization. One can specify multiple global QoS constraints and user preferences, and our method finds a composite service that optimizes the overall QoS, while satisfying those specified global QoS constraints.