Computing has reached the time of distributed applications everywhere. Service-oriented architectures are more and more used to organize such complex and highly dynamic applications into business processes calling services discovered in registries at load-time. In this context, Quality of Service (QoS) and agility in business processes become key issues. Instead of binding business processes to services at load-time, this paper proposes to monitor sets of candidate services for their current QoS and to choose among them at call-time. This new form of late-binding paves the way to more agile and robust applications called adaptive business processes. Besides the conceptual background and implementation of this late-binding in an industrial-strength web service platform, this paper presents the LCP-net formalism introduced to provide programmers with a mean to express qualitatively their preferences among the different QoS properties of services, hence tackling the multi-criteria decision making arising from the run-time choice among candidate services given several unrelated QoS properties.