Abstract: With the development of information technology, the quantity of web services in internet has increased rapidly. The time complexity of service composition becomes higher. To solve this problem, a new method of service composition is proposed based on Enhanced Logic Petri nets (ELPNs) in this study. The main innovation is the construction of a composition library. The experiment in this study shows the time complexity of service composition is decreased. Firstly, web services and service compostion are modeled by ELPNs. Then, the reachability of ELPNs is analyzed. All cases of service composition are obtained based on the ELPNs model of service composition. A composition library is constructed. The method of service composition is proposed based on the composition library. Moreover, some theorems are given, such as enabled conditions of transitions, marking computing. Some algorithms are introduced, such as reachable markings, service composition and so on. Finally, the validity and advantages of proposed methods are illustrated by experiments and comparative analysis.