ترکیب سرویس ها در ساخت و تولید ابری: مدلسازی ریاضی و توسعه الگوریتم فراابتکاریِ مبتنی بر آنالیز چشم انداز

نوع مقاله: مقاله پژوهشی

نویسندگان

1 کارشناسی‌ارشد، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران، ایران.

2 استاد، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران، ایران.

3 دانشجوی دکتری، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران، ایران.

چکیده

در این پژوهش، به عنوان نخستین نوآوری، مدلسازی عدد صحیح مساله ترکیب سرویس ها ضمن رعایت ساختار عمومی ترکیب سرویس ها (متشکل از ساختارهای متوالی، موازی و حلقه ای) ارایه شده و حمل و نقل بین منابع تولیدی پراکنده در سطح جغرافیا نیز به عنوان یک نوآوری جدید در مدل ریاضی لحاظ گردیده است. در ادامه، دو مساله نمونه‌ی متفاوت از ترکیب سرویس های ساخت و تولید توسعه می یابد به نحوی که در آنها هر یک از مراکز استان های ایران شامل یک کارخانه تولیدی هستند و توانایی انجام برخی از سرویس های از پیش تعیین شده را خواهند داشت. جهت حل بهینه مسائل نمونه‌ مذکور از الگوریتم شاخه و کران بهره گرفته می‌شود. علاوه بر این، پیش از توسعه الگوریتم فراابتکاری به منظور حل مساله، آنالیز چشم انداز مساله ترکیب سرویس ها صورت می پذیرد. نتایج این آنالیز بیان می دارد که چشم انداز مساله ساختار تصادفی یکنواخت دارد و بهینه های محلی در فضای حل مساله پراکنده شده اند. در چنین شرایطی، الگوریتم های مبتنی بر یک جواب می توانند با آغاز از هر پاسخ اولیه و پس از چند تکرار به یک بهینه محلی نایل آیند. لذا به منظور حل مساله، ساده ترین الگوریتم فراابتکاری مبتنی بر یک جواب، یعنی الگوریتم جست‌وجوی محلی نیز می تواند راهگشا باشد. در پایان، نتایج الگوریتم فراابتکاری با نتایج الگوریتم دقیق مورد مقایسه قرار گرفته که توانایی الگوریتم جست‌وجوی محلی در حل بهینه و یا نزدیک به بهینه مساله ترکیب سرویس ها با هزینه محاسباتی کمتر را نشان می‌دهد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Cloud Manufacturing Service Composition: Mathematical Modeling and Metaheuristic Development Based on Landscape Analysis

نویسندگان [English]

  • Adeleh Kerdegari 1
  • Koroush Eshghi 2
  • Hossein Akbaripour 3
1 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.
2 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.
3 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.
چکیده [English]

Service Composition (SC) is an important problem in the Cloud Manufacturing (CM) paradigm in which, after receiving customers’ requests, a composition of cloud services is determined for accomplishment of their needs. Actually, a customer’s need is decomposed to some distinct tasks such that a manufacturing resource or a group of them can perform each task. The ultimate goal of SC is optimal assignment of tasks to resources while specific objective function(s) and constraint(s) are considered. In this paper, as the main contribution, an Integer Programming (IP) model of service composition problem is presented which includes transportation between manufacturing resources scattered over the globe. Then, two different scenarios of SC problem are generated such that each center of Iran's provinces includes a resource which can perform some pre-determined tasks. In addition, distance of center of Iran's provinces as well as transportation time between them are estimated based on real data. In order to solve the mentioned scenarios, Branch and Bound (B&B) exact algorithm is used. Furthermore, before developing a metaheuristic algorithm for implementation in service composition problem, landscape analysis of the problem is completed. Based on the results of this analysis, the problem has a random uniform nature and its local optima are scattered over the search space. As a result, simple single-solution based algorithms such as Local Search (LS) heuristic can be efficient in SC problem solving. Results of comparison between B&B and LS algorithms indicate superiority of LS in finding optimum or near-optimum solution with lower computational cost.

کلیدواژه‌ها [English]

  • Cloud Manufacturing
  • Service Composition
  • Optimization
  • Local Search Algorithm
  • Landscape Analysis

 

[1]      کردگاری، عادله (1394). بهینه‌سازی مسئله ترکیب سرویس‌ها در فضای ساخت و تولید ابری، پایان­نامه کارشناسی ارشد، دانشگاه صنعتی شریف، تهران.

[2]      Zhang, L., Luo, Y., Tao, F., Li, B.H., Ren, L., Zhang, X., Liu, Y., (2014). “Cloud manufacturing: a new manufacturing paradigm, Enterprise Information Systems”, 8(2): 167-187.

[3]      Bai, L., Liu, M., (2008). “A fuzzy-set based semantic similarity matching algorithm for web service”, In IEEE International Conference on Services Computing, 529-532.

[4]      Bakhshi, M., Mardukhi, F., Nematbakhsh, N., (2010). “A fuzzy-based approach for selecting the optimal composition of services according to user preferences”, In IEEE International Conference on Computer and Automation Engineering, (ICCAE), 129-135.

[5]      Gabrel, V., Manouvrier, M., Megdiche, I., Murat, C., (2012). “A new 0–1 linear program for QoS and transactional-aware web service composition”, In IEEE Symposium on Computers and Communications (ISCC), 845-850.

[6]      Kang, G., Liu, J., Tang, M., Xu, Y., (2012). “An effective dynamic web service selection strategy with global optimal QoS based on particle swarm optimization algorithm”, In IEEE 26th International Parallel and Distributed Processing, 2280-2285.

[7]      Tao, C., Z. Feng., Xu, C., (2009). “Optimization of Web Service Composition Using Factored Markov Decision Process”, Second International Workshop on Computer Science and Engineering, 93-96.

[8]      Tao, F., Zhao, D., Zhang, L., (2010). “Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system”, Knowledge and information systems, 25(1): 185-208.

[9]      Zhang, L., Yuan, W., Wang, W., (2005). “Towards a Framework for Automatic Service Composition in Manufacturing Grid”, Lecture Notes in Computer Science and Grid and Cooperative Computing (GCC), 238-243.

[10]   Zhang, W., Chang, C.K., Feng, T., Jiang, H., (2010). “QoS-Based Dynamic Web Service Composition with Ant Colony Optimization”, In COMPSAC, 10: 493-502.

[11]   Huang, S., Zeng, S., Fan, Y., Huang, G.Q., (2010). “Optimal service selection and composition for service-oriented manufacturing network”, International Journal of Computer Integrated Manufacturing, 24(5): 416-430.

[12]   Guo, H., Tao, F., Zhang, L., Su, S., Si, N., (2010). “Correlation-aware web services composition and QoS Computation Model in virtual enterprise”, The International Journal of Advanced Manufacturing Technology, 51(8): 817-827.

[13]   Tao, F., Zhang, L., Venkatesh, V.C., Luo, Y., Cheng, Y., (2011). “Cloud manufacturing: a computing and service-oriented manufacturing model, Proceedings of the Institution of Mechanical Engineers”, Part B: Journal of Engineering Manufacture.

[14]   Liu, W.N., Liu, B., Sun, D.H., (2013). “Multi-task oriented service composition in cloud manufacturing”, Computer Integrated Manufacturing Systems, 19(1): 199-209.

[15]   Li, B.H., Zhang, L., Wang, S.L., Tao, F., Cao, J.W., Jiang, X.D., Chai, X.D., (2010). “Cloud manufacturing: a new service-oriented networked manufacturing model”, Computer Integrated Manufacturing Systems, 16(1): 1-7.

[16]   Zou, G., Chen, Y., Yang, Y., Huang, R., Xu, Y., (2010). “AI planning and combinatorial optimization for web service composition in cloud computing”, In Proceeding of international conference on cloud computing and virtualization, 1-8.

[17]   Hu, Y., Tao, F., Zhao, D., Zhou, Z., (2009). “Manufacturing grid resource and resource service digital description”, The International Journal of Advanced Manufacturing Technology, 44(10): 1024-1035.

[18]   Tian, S., Liu, Q., Xu, W., Yan, J., (2013). “A Discrete Hybrid Bees Algorithm for Service Aggregation Optimal Selection in Cloud Manufacturing”, In Intelligent Data Engineering and Automated Learning, 110-117.

[19]   Ter Beek, M. H., Bucchiarone, A., Gnesi, S., (2007). “Formal methods for service composition”, Annals of Mathematics, Computing & Teleinformatics, 1(5): 1-10.

[20]   Tao, F., Qiao, K., Zhang, L., Li, Z., Nee, A.Y.C., (2012). “GA-BHTR: an improved genetic algorithm for partner selection in virtual manufacturing”, International Journal of Production Research, 50(8): 2079-2100.

[21]   Zhang, L., Guo, H., Tao, F., Luo, Y.L., (2010). “Flexible Management of Resource Service Composition in Cloud Manufacturing”, IEEE International Conference on Industrial Engineering and Engineering Management, (IEEM), 2278-2282.

[22]   Tao, F., Zhang, L., Lu, K., Zhao, D., (2012). "Research on manufacturing grid resource service optimal-selection and composition framework”, Enterprise Information Systems, 6(2): 237-264.

[23]   Jin, H., Yao, X., Chen, Y., (2015). “Correlation-aware QoS modeling and manufacturing cloud service composition”, Journal of Intelligent Manufacturing.

[24]   Lartigau, J., Xu, X., Nie, L., Zhan, D., (2015). “Cloud manufacturing service composition based on QoS with geo-perspective transportation using an improved Artificial Bee Colony optimisation algorithm”, International Journal of Production Research, 53(14): 4380-4404.

[25]   Zheng, H., Feng, Y., Tan, J., (2016). “A fuzzy QoS-aware resource service selection considering design preference in cloud manufacturing system”, The International Journal of Advanced Manufacturing Technology, 84(1-4): 371-379.

[26]   Xiang, F., Jiang, G., Xu, L., Wang, N., (2016). “The case-library method for service composition and optimal selection of big manufacturing data in cloud manufacturing system”, The International Journal of Advanced Manufacturing Technology, 59-70.

[27]   Zheng, H., Feng, Y., Tan, J., (2017). “A Hybrid Energy-Aware Resource Allocation Approach in Cloud Manufacturing Environment”, IEEE Access, 5: 12648-12656.

[28]   Lu, Y., Xu, X., (2017). “A semantic web-based framework for service composition in a cloud manufacturing environment”, Journal of manufacturing systems, 42: 69-81.

[29]   Akbaripour, H., Houshmand, M., van Woensel, T., Mutlu, N., (2017). “Cloud manufacturing service selection optimization and scheduling with transportation considerations: mixed-integer programming models”, The International Journal of Advanced Manufacturing Technology, 95: 1-28.

[30]   Xu, X., (2012). “From cloud computing to cloud manufacturing”, Robotics and computer-integrated manufacturing, 28(1): 75-86.

[31]   Wu, D., Greer, M.J., Rosen, D.W., Schaefer, D., (2013). “Cloud manufacturing: Strategic vision and state-of-the-art”, Journal of Manufacturing Systems, 32(4): 564-579.

[32]    فتح­اله، مهدی.، نجفی، مهدی. (1395). «توسعه الگوی مدیریت مالی زنجیره تأمین و تأمین مالی زنجیره‌ای»، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 9: 257-269.

[33]    فاروقی، هیوا.، اشرفی شفی، محمد (1396). «طراحی شبکه زنجیره تأمین چند سطحی با در نظر گرفتن راهبردهای پایای چندگانه در سطح مراکز توزیع»، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 10: 53-67.

[34]   Talbi, E.G., (2009). “Metaheuristics: from design to implementation”, John Wiley & Sons.

[35]   Akbaripour, H., Masehian, E., (2013). “Efficient and robust parameter tuning for heuristic algorithms”, International Journal of Industrial Engineering & Production Research, 24(2): 143-150.