Web services as independent software components are published on the Internet by service providers and services are then called by users’ request. However, in many cases, no service alone can be found in the service repository that could satisfy the applicant satisfaction. Service composition provides new components by using an interactive model to accelerate the programs. Prior to service composition, the most important issue in finding suitable candidate services samples is their compliance with non-functional requirements. Thus, designing an efficient way to combine a chain of connected services is important. Recently, numerous studies have been done to reduce the search time in finding a service composition. However, many of these methods to examine and investigate all Web services in a Web repository require a long time, which occupy the user's time significantly. This paper provides an approach for automatic quality-aware service composition as well as the users’ preferences in achieving the optimum composition results. For this purpose, modified Graph coloring method to filter the data before compositions in large-scale data is used which decreases selected services set. The application of KPL algorithm in this study provided some proper solutions to the user so that these solutions can be used instead of the best composition if necessary. Therefore, the results derived from the analysis of the proposed method, indicates a good optimization in runtime and memory consumption. The evaluation results show that the proposed method in memory consumption and runtime has improved by about 20%.