In order to realize the full-scale sharing, free circulation and transaction, and on-demand-use of manufacturing resource and capabilities in modern enterprise systems (ES), Cloud manufacturing (CMfg) as a new service-oriented manufacturing paradigm has been proposed recently. Compared with cloud computing, the services that are managed in CMfg include not only computational and software resource and capability service, but also various manufacturing resources and capability service. These various dynamic services make ES more powerful and to be a higher-level extension of traditional services. Thus, as a key issue for the implementation of CMfg-based ES, service composition optimal-selection (SCOS) is becoming very important. SCOS is a typical NP-hard problem with the characteristics of dynamic and uncertainty. Solving large scale SCOS problem with numerous constraints in CMfg by using the traditional methods might be inefficient. To overcome this shortcoming, the formulation of SCOS in CMfg with multiple objectives and constraints is investigated first, and then a novel parallel intelligent algorithm, namely full connection based parallel adaptive chaos optimization with reflex migration (FC-PACO-RM) is developed. In the algorithm, roulette wheel selection and adaptive chaos optimization are introduced for search purpose, while full-connection parallelization in island model and new reflex migration way are also developed for efficient decision. To validate the performance of FC-PACO-RM, comparisons with 3 serial algorithms and 7 typical parallel methods are conducted in three typical cases. The results demonstrate the effectiveness of the proposed method for addressing complex SCOS in CMfg.