Choosing the global optimal execution plan is an important process in the semantic Web service composition. The plan selection based on QoS is still challenging because the heterogeneous QoS values make dataaggregation and decision making hard. This paper presents a novel Fuzzy Multi-attribute decision making-basedsemantic Web service Composition algorithm (FuMuCom) to solve the above difficulties for the first time.FuMuCom takes all possible QoS expression types (real number, interval and linguistic expression) intoconsideration. It includes three main steps: defuzzifying linguistic data, normalizing the decision matrix andevaluating alternatives synthetically. Other contributions of the paper include an extensible QoS ontology to expressthe heterogeneous QoS values, an ontology evolution strategy for aggregating QoS and a set of experiments thatdemonstrate the benefits and effectiveness of our approach.