Tabu Search and Genetic Algorithm to Generate Test Data for BPEL Program To solve the combination explosion and the undecidable problem on feasibility of complete computation paths when testing the composed Web services programmed by business process execution language (BPEL), this paper presents a simple strategy for generating complete computation paths of BPELprogram and an approach for generating test data for feasible complete computation paths based on tabu search and genetic algorithm (Tabu GA). Firstly, the basic structure graph is built from BPELprogram based on an open source tool BPEL4WS20WLS. Then the basic structure graph is converted to middle structure graph for facilitating to generate complete computation paths by selected test adequacy criteria, which a complete computation path is corresponding to operation sequence. Lastly, we apply Tabu GA into searching the whole input space which is made from all operation parameters of each operation sequence, and generating test data for each feasible complete computation path. Experiments show that the method could determine efficiently whether the complete computation path is feasible or not and generate automatically test data for each feasible complete computation path of BPEL program.