As cloud computing becomes the prevailing aspect of software engineering, paradigms such as Service-Based Systems (SBSs) or Software as a Service (SaaS) are coming into focus. They are based on cloud services responding to numerous client requests. Selecting the actual service instance for request can be an issue, if requirements for multiple Quality of Service (QoS) attributes need to be satisfied for many users simultaneously. The problem becomes more complex if we take into account the compositeness of users applications, consisting of many tasks, where QoS properties are calculated over the whole composition. The existing approaches for this problem lack either efficiency or generality. In this paper, we propose a fast heuristic method for multi-criteria service selection, designed for multi-user composite workflows with the goal of satisfying all, or as many as possible, of the given QoS requirements. The proposed method reduces the problem to several independent transportation problems, using a global-aware utility cost based on expected compositional QoS, and iterative solution improvements. Apart from being more general than the existing approaches, the proposed method turns out to be more efficient than the alternatives (up to 5x faster), as shown by extensive experiments covering both special and more general cases.