When a composition of Web services is designed, available services are put together to form a defined flow of executions. In a discovery process, a trader proposes available Web services as potential candidates. In a succeeding selection, for each task a trader chooses one candidate to form the optimal composition due to selection criteria. This paper discusses how the selection can consider different Quality-of-Service (QoS) categories to determine the most suitable candidates for the composition. If more than one category is used for optimisation, a multi-dimensional optimisation problem arises. This mentions similarities to similar combinatorial problems. Then, possible solutions are proposed and their performance is evaluated.