Correlation-aware resource service composition and optimal-selection in manufacturing grid. (English) Zbl 1177.90425

Tao, Fei; Zhao, Dongming; Yefa, Hu; Zhou, Zude

Eur. J. Oper. Res. 201, No. 1, 129-143 (2010).

Summary: For a multi-resource service request task (MRSRTask) in manufacturing grid (MGrid) system, in addition to the search for all qualified resource services according to each subtask, the system selects one candidate resource service for each subtask. Then the system generates a new composite resource service (CRS) and selects the optimal resource service composite path from all possible paths to execute the task with the given multi-objective (e.g., time minimization, cost minimization and reliability maximization) and multi-constraints. The above problem is defined as multi-objective MGrid resource service composition and optimal-selection (MO-MRSCOS) problem. The formulation is presented for an MO-MRSCOS problem. The correlations among resource services are taken into account during MGrid resource service composition, and a QoS description mode supporting resource service correlation is presented. The basic resource service composite modes (RSCM) for CRS are described, and the principles for translating a complicated RSCM into a simple sequence RSCM are presented for simplifying the resolving process and complexity of MO-MRSCOS problem. A new method based on the principles of particle swarm optimization (PSO), is proposed for solving MO-MRSCOS problem. Unlike previous works: (a) the proposed PSO algorithms combine the non-dominated sorting technique to achieve the selection of global best position and private best position; (b) the parameters of particle updating formulation in PSO are dynamical generated in order to make a compromise between the global exploration and local exploitation abilities of PSO; (c) permutation-based and objective-based population trimming operators are applied in PSO to maintain diversity of solutions in population. The experimental results and performance comparison show that the proposed method is both effective and efficient.

MSC:

90C59

Approximation methods and heuristics in mathematical programming

Keywords:

manufacturing grid (MGrid); resource service composition; particle swarm optimization (PSO); resource service composition model; resource service composition and optimal-selection

References:

[1]	Fan, Y.; Zhao, D.; Zhang, L.; Huang, S.; Liu, B., (), 653-654
[2]	R.G. Qiu, Manufacturing grid: A next generation manufacturing, in: 2004 IEEE International Conference on System, Man and Cybemetics (SMC2004), The Hague, Netherlands, October 10-13, 2004, pp. 4667-4672.
[3]	Tao, F.; Hu, Y.F.; Zhou, Z.D., Study on manufacturing grid & its resource service optimal-selection system, International journal of advanced. manufacturing technology, 9-10, 1022-1041, (2008)
[4]	Tao, F.; Zhao, D.; Hu, Y.; Zhou, Z., Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system [J], IEEE transactions on industrial informatics, 4, 315-327, (2008)
[5]	Kalasapur, S.; Kumar, M.; Shirazi, B.A., Dynamic service composition in pervasive computing, IEEE transactions on parallel and distributed systems, 7, 907-918, (2007)
[6]	Fujii, K.; Suda, T., Semantics-based dynamic service composition, IEEE journal on selected areas in communications, 12, 2361-2372, (2005)
[7]	Gu, X.; Nahrstedt, K., Distributed multimedia service composition with statistical QoS assurances, IEEE transactions on multimedia, 1, 141-151, (2006)
[8]	Maamar, Z.; Benslimane, D.; Thiran, P.; Ghedira, C.; Dustdar, S.; Sattanathan, S., Towards a context-based multi-type policy approach for web services composition, Data & knowledge engineering, 2, 327-351, (2007)
[9]	Liang, W.Y.; Huang, C.C.; Chuang, H.F., The design with object (dwo) approach to web services composition, Computer standards & interfaces, 1, 54-68, (2007)
[10]	Yue, P.; Di, L.; Yang, W.; Yu, G.; Zhao, P., Semantics-based automatic composition of geospatial web service chains, Computer & geosciences, 5, 649-665, (2007)
[11]	Rao, J.; Kungasa, P.; Matskinb, M., Composition of semantic web services using linear logic theorem proving, Information systems, 4-5, 340-360, (2006)
[12]	Chi, Y.L.; Lee, H.M., A formal modeling platform for composing web services, Expert systems with applications, 2, 1500-1507, (2007)
[13]	Madhusudan, T.; Uttamsingh, N., A declarative approach to composing web services in dynamic environments, Decision support systems, 2, 325-357, (2006)
[14]	Sirin, E.; Parsiab, B.; Wu, D.; Hendler, J.; Nau, D., HTN planning for web service composition using SHOP2, Journal of web semantics, 4, 377-396, (2004)
[15]	Tao, F.; Hu, Y.F.; Zhou, Z.D., Application and modeling of resource service trust-QoS evaluation in manufacturing grid system, International journal of production research, 6, 1521-1550, (2009)
[16]	Tao, F.; Hu, Y.F.; Zhao, D.; Zhou, Z.D.; Zhang, H.J.; Lei, Z.Z., Study on manufacturing grid resource service QoS modeling and evaluation, International journal of advanced. manufacturing technology, (2008), (Online first)
[17]	G. Zhang, X. Shao, P. Li, L Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Computers & Industrial Engineering, in press, Corrected Proof, Available online 6 August 2008. doi:10.1016/j.cie.2008.07.021.
[18]	Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan T, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 2, 182-197, (2002)
[19]	J. Kennedy, R. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Conference on Neural Networks, vol. 4, Perth, Aust, November 27-December 1, 1995, pp.1942-1948.
[20]	Kennedy, J.; Eberhart, R.; Shi, Y., Swarm intelligence, (2001), Morgan Kaufman San Mateo, CA
[21]	R.C. Eberhart, Y. Shi, Evolving artificial neural networks, in: Proceedings of International Conference on Neural Networks and Brain, 1998, pp. 5-13.
[22]	V. Tandon, Closing the Gap between CAD/CAM and Optimized CNC End Milling, Master Thesis, Purdue School of Engineering and Technology, Indiana University Purdue University Indianapolis, 2000.
[23]	H. Yoshida, K. Kawata, Y. Fukuyama, Y. Nakanishi, A particle swarm optimization for reactive power and voltage control considering voltage stability, in: Proceedings of International Conference on Intelligent System Application to Power Systems, 1999, pp. 117-121.
[24]	Yin, P.Y., Particle swarm optimization for point pattern matching, Journal of visual communication and image representation, 17, 143-162, (2006)
[25]	Ratnaweera, A.; Halgamuge, S.K.; Watson, H.C., Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients, IEEE transactions on evolutionary computation, 3, 240-255, (2004)
[26]	Tripathi, P.K.; Bandyopadhyay, S.; K Pal, S., Multi-objective particle swarm optimization with time variant inertia and acceleration coefficients, Information sciences, 22, 5033-5049, (2007) · Zbl 1121.90130
[27]	Lei, D., A Pareto archive particle swarm optimization for multi-objective job shop scheduling, Computers & industrial engineering, 4, 960-971, (2008)
[28]	Coello Coello, C.A.; Pulido, G.T.; Lechuga, M.S., Handling multiple objectives with particle swarm optimization, IEEE transactions on evolutionary computation, 3, 256-279, (2004)
[29]	F. van den Bergh. An Analysis of Particle Swarm Optimizers, Ph.D. thesis, Faculty of Natural and Agricultural Science, University of Pretoria, Pretoria, November 2001.