Composite services are widely popular for solving complex problems where the required QoS levels are often demanding. The composite service that provides the best utility while meeting the QoS requirements has to be found. This paper proposes a network model where many complementary candidates could be selected for each service class to improve the benefits, while the conventional model limits the selection to a single service candidate or service level per service class. The selection of services step is NP-hard because it can be reduced to a multi-constraint knapsack problem. Yet, the decision has to be reached rapidly so that it does not increase the overall workflow time. Large-size networks and problems with high restriction levels (strong QoS requirements) are the most problematic. Traditional multiple-constrained-shortest-path (MCSP) heuristics are improved in this paper using the novel concept “potential feasibility”. When our modified MCSP heuristic algorithms are compared to the CPLEX solver, one of them demonstrates a significantly smaller average runtime. Further, it provides solutions within a 2.6 percent optimality gap on average for small networks, and a 10 percent optimality gap on average for large networks, regardless of the restriction level. Our algorithm uses a general utility function, not derived from the QoS parameters.