Cloud service composition problem (CSCP) is usually long-term based in practice. A logical request is to maximize end users' long-term benefit. Thus, the overall long-term QoS properties of the composite service should be optimized and the users' requirements during the period should be satisfied. However, the benefit-maximization has not been considered under the background of long-term based CSCP in existing research yet. To fill this gap, in this paper, a new formulation LCSCP is proposed to define the long-term based CSCP as an optimization problem. Then, for the sake of efficiency, three meta-heuristic approaches (i.e, Genetic Algorithm, Simulated Annealing and Tabu Search) are studied. Comprehensive experiments are designed and conducted to test their various aspects of performance on different test sets with different workflows. Experimental results provide a basic perspective of how these three widely adopted meta-heuristic frameworks work on this new problem, which can be baseline work for further research.
