A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems

Abstract

To cope with the task scheduling problem under multi-task and transportation consideration in large-scale service oriented manufacturing systems (SOMS), a service allocation optimization mathematical model was established, and then a hybrid discrete particle swarm optimization-genetic algorithm (HDPSOGA) was proposed. In SOMS, each resource involved in the whole life cycle of a product, whether it is provided by a piece of software or a hardware device, is encapsulated into a service. So, the transportation during production of a task should be taken into account because the hard-services selected are possibly provided by various providers in different areas. In the service allocation optimization mathematical model, multi-task and transportation were considered simultaneously. In the proposed HDPSOGA algorithm, integer coding method was applied to establish the mapping between the particle location matrix and the service allocation scheme. The position updating process was performed according to the cognition part, the social part, and the previous velocity and position while introducing the crossover and mutation idea of genetic algorithm to fit the discrete space. Finally, related simulation experiments were carried out to compare with other two previous algorithms. The results indicate the effectiveness and efficiency of the proposed hybrid algorithm.

Keywords

service-oriented architecture (SOA) / cyber physical systems (CPS) / multi-task scheduling / service allocation / multi- objective optimization / particle swarm algorithm

References

[1] KarnouskosS, BaeckerO, SouzaL, MS D, SpiessP. Integration of SOA-ready networked embedded devices in enterprise systems via a cross-layered web service infrastructure. [C]//12th IEEE Conference on Emerging Technologies and Factory Automation, 2007Patras, GreeceIEEE Press25-28

[2] TaischM, ColomboA W, KarnouskosS, CannataASOCRADES road map [EB/OL], 2010

[3] LeeE A. Cyber physical systems: Design challenges. [C]//Proceeding of the 11th IEEE International Symposium on Object Oriented Real-Time Distributed Computing, 2008Los Alamitos, CAIEEE Computer Society363-369

[4] KleshA T, CutlerJ W, AtkinsE M. Cyber-physical challenges for space systems. [C]//2012 IEEE/ACM Third International Conference on Cyber-Physical Systems, 2012Beijing, ChinaIEEE/ACM45-54

[5] Industrial Internet [EB/OL]. [2014–08–18]. http://www.ge.com/stories/industrial-internet, 2014.

[6] LiB-h, ZhangL, WangS-l, TaoF, CaoJ-w, JiangX-d, SongX, CaiX-dong. Cloud manufacturing: A new service-oriented networked manufacturing model [J]. Computer Integrated Manufacturing Systems, 2010, 16(1): 1-7

[7] LiB-h, ZhangL, RenL, ChaiX-d, TaoF, LuoY-l, WangY-z, YinC, HuangG, ZhaoX-pei. Further discussion on cloud manufacturing [J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 449-457

[8] HollandJ HAdaptation in natural and artificial system [M], 1975Ann ArborThe University of Michigan Press141-153

[9] GoldbergD EGenetic algorithms in search, optimization and machine learning [M], 1989Reading, MAAddison-Wesley89-145

[10] EberhartR C, KennedyJ. A new optimizer using particle swarm theory. [C]//Proceedings on 6th International Symposium on Micromachine and Human Science, 1995NagoyaIEEE Service Center39-43

[11] KennedyJ, EberhartR C. Particle swarm optimization [C]//Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia: IEEE Press, 19951942-1948

[12] CarZ, BarisicB, IkonicM. GA based CNC turning center exploitation process parameters optimization [J]. Metallugica, 2009, 48(1): 47-50

[13] WeiY, LiD-b, TongY-fei. Multi-objective reconfiguration and optimal scheduling of service-oriented networked collaborative manufacturing resource [J]. Transactions of the Chinese Society for Agricultural Machinery, 2012, 43(3): 193-199

[14] MaX-f, DaiX-d, SunS-dong. Optimization deployment of networked manufacturing resources [J]. Computer Integrated Manufacturing Systems, 2004, 10(5): 523-527

[15] NavalertpornT, AfzulpurkarN V. Optimization of tile manufacturing process using particle swarm optimization [J]. Swarm and Evolutionary Computation, 2011, 1(2): 97-109

[16] TaoF, ZhaoD-m, HuY-f, ZhouZ-de. Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system [J]. IEEE Transactions on Industrial Informatics, 2008, 4(4): 315-327

[17] TaoF, ZhangL, LuK, ZhaoD-ming. Study on manufacturing grid resource service optimal-selection and composition framework [J]. Enterprise Information Systems, 2012, 6(2): 237-264

[18] TaoF, HuY-F, ZhouZ-de. Study on manufacturing grid & its resource service optimal-selection system [J]. International Journal of Advanced Manufacturing Technology, 2008, 37(9/10): 1022-1041

[19] TaoF, ZhaoD-m, ZhangLin. Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system [J]. Knowledge and Information Systems, 2010, 25(1): 185-208

[20] TaoF, ZhaoD-m, HuY-f, ZhouZ-de. Correlation-aware resource service composition and optimal-selection in manufacturing grid [J]. European Journal of Operational Research, 2010, 201(1): 129-143

[21] TaoF, LailiY-j, XuL-d, ZhangLin. FC-PACO-RM: A parallel method for service composition optimal-selection in cloud manufacturing system [J]. IEEE Transactions on Industrial Informatics, 2013, 9(4): 2023-2033

[22] LiuW-n, LiuB, SunD-hua. Study on multi-task oriented service composition in cloud manufacturing [J]. Computer Integrated Manufacturing Systems, 2013, 19(1): 200-209

[23] PezzellaF, MorgantiG, CiaschettiG. A genetic algorithm for the flexible job-shop scheduling problem [J]. Computers & Operations Research, 2008, 35(10): 3202-3212

[24] KacemI, HammadiS, BorneP. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2002, 32(1): 1-13

[25] WangW-l, ZhangJ, XuX-l, JieJ, WangH-yan. A hybrid discrete particle swarm optimization for Job shop Scheduling. [C]//2010 International Conference on Computational Aspects of Social Networks, 2010Taiyuan, ChinaIEEE CS Press303-306

[26] ShaoX-y, LiuW-q, LiuQ, ZhangC-yong. Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2013, 67(12): 2885-2901

[27] ZhangG-h, ShaoX-y, LiP-g, GaoLiang. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem [J]. Computers & Industrial Engineering, 2009, 56(4): 1309-13