Abstract: Based on the analysis of state-chart workflow model, a model of service composition with multiple QoS (Quality of Service) constra ints in grid is presented, the method of formal description for the dynamic service scheduling problem is introduced, and a novel approach based on genetic algo rithm(GA) is proposed to optimize the service scheduling, which uses the number of service areas and service instances as the coding method and adopts the utility function involving the validity of service composite plan and global QoS as the fitness function. The proposed approach is verified by comparing with other algorithms. Simulation results show that the proposed GA-based approach can be a competitive choice for scheduling dynamic service composition in terms of both scheduling efficiency and the relative solution quality as compared with other algorithms.