The Grid has emerged as a new distributed computing infrastructure for advanced science and engineering. It aims at enabling resource sharing as means to facilitate a problem-solving approach for dynamic environments that is based on the integration of available resources. Wide agreement that a flexible Grid is not possible without the support of semantic technologies, has lead to the term "Semantic Grid". Transparent service composition has a great potential to facilitate the integration of Web Services deployed in the Grid. However, discovering, dynamically composing and optimizing large-scale Web Services (e.g., in the rank of 1, 000 to 100, 000 services) is a challenging problem. We approached the problem of Web Service compositions in the Grid as an optimization problem, in which for a given request a good plan has to be generated. In this work, we propose the definition of several optimization strategies to identify good orderings of Web Service compositions.