ALATO: An efficient intelligent algorithm for time optimization in an economic grid based on adaptive stochastic Petri net

详细信息    查看全文

• 作者：Mohammad Shojafar ; Zahra Pooranian…
• 关键词：Grid computing ; Petri nets ; Learning automata ; Optimization ; Modeling
• 刊名：Journal of Intelligent Manufacturing
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：26
• 期：4
• 页码：641-658
• 全文大小：1,729 KB
• 参考文献：Aissani, N., Bekrar, A., Trentesaux, D., & Beldjilali, B. (2011). Dynamic scheduling for multi-site companies: A decisional approach based on reinforcement multi-agent learning. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-011-0580-y .
  Al-Ali, R., Rana, O., Walker, D., Jha, S., & Sohail, S. (2002). G-QOSM: Grid service discovery using QOS properties. Computing and Informatics Journal, Special Issue on Grid Computing, 21(4), 363鈥?82.
  Al-Khasawneh, A., & Bsoul, M. (2010). Job scheduling in economic grid environments. International Journal of Information and Communication Technology, 2(3), doi:10.鈥?504/鈥婭JICT.鈥?010.鈥?32410 .
  Arab, A., Ismail, N., & Lee, L. S. (2011). Maintenance scheduling incorporating dynamics of production system and real-time information from workstations. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-011-0616-3 .
  Archimede, B., Letouzey, A., Memon, M. A., & Xu, J. (2013). Towards a distributed multi-agent framework for shared resources scheduling. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-013-0748-8 .
  Assuncao, M., & Buyya, R. (2006). An evaluation of communication demand of auction protocols in grid environments Technical report, University of Melbourne, Melbourne, Australia.
  Baranauskas, V., Bartkevi膷ius, S., & 艩arkauskas, K. (2006). Coloured Petri nets鈥攖ool for control systems learning. Electronics and Electrical Engineering., 4, 41鈥?6.
  Bilyk, A., & M枚nch, L. (2010). A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-010-0464-6 .
  Boppana, R., & Halldorsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Magazine, Published By BIT Computer Science and Numerical Mathematics, 32(2), 180鈥?96. doi:10.鈥?007/鈥婤F01994876 .
  Bui, T. N., & Eppley, P. H. (1995). A hybrid genetic algorithm for the maximum clique problem. In Proceedings of 6th international conference on genetic algorithms, San Francisco, CA, USA, pp. 478鈥?84.
  Buyya, R. (2002). Economic-based distributed resource management and scheduling for grid computing, Ph.D. Thesis, School of Computer Science and Software Engineering, Monash University, Melbourne, Australia.
  Buyya, R. (2002). The World-Wide Grid (WWG). http://鈥媤ww.鈥媌uyya.鈥媍om/鈥媏cogrid/鈥媤wg/鈥?/span> .
  Czajkowski, K., Foster, I., Kesselman, C., Sander, V., & Tuecke, S. (2002). SNAP: A protocol for negotiating servi\(^{2}\) ce level agreements and coordinating resource management in distributed systems. In 8th workshop on job scheduling strategies for parallel processing, pp. 153鈥?83.
  Fleszar, K., Charalambous, C., & Hindi, K. S. (2011). A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-011-0522-8 .
  Guinet, A. (1995). Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria. Journal of Intelligent Manufacturing, 6, 95鈥?03.View Article
  Hirel, C., Wells, S., Fricksy, R., & Trivedi, K. S. (2000). ISPN: An integrated environment for modeling using stochastic petri nets. In Center for advanced computing and communication department of electrical and computer engineering Duke University. Durham, NC 27708鈥?291.
  Jain, L. C., & Martin, N. M. (1998). Fusion of neural networks, fuzzy sets, and genetic algorithms: Industrial applications, 1st ed.. FL, USA: CRC Press ISBN: 0849398045.
  Jeng, M. D., Lin, C. S., & Huang, Y. S. (1999). Petri net dynamics-based scheduling of flexible manufacturing systems with assembly. Journal of Intelligent Manufacturing, 10, 541鈥?55. doi:10.鈥?023/鈥婣:鈥?008960721370 .
  Khosla, R., & Dillon, T. (2002). Intelligent hybrid multi-agent architecture for engineering complex systems. International Conference on Neural Networks, 4, 2449鈥?454. doi:10.鈥?109/鈥婭CNN.鈥?997.鈥?14540 Houston, TX.
  Mahdavifar, Y., & Meybodi, M. R. (2007). Cost-time optimization in economic computational grids. In Proceedings of the third information and knowledge technology, Mashad, Iran: Ferdowsi University of Mashad.
  Mahdavifar, Y., & Meybodi, M. R. (2007). Time optimization in economic computational grids using learning automata. In Proceedings of the first Iranian data mining conference. Tehran, Iran: Amirkabir University of Technology.
  Mirzaee, A., & Rahimzadeh, P. (2011). A agent-based decentralized algorithm for resource semantic discovery in economic grid. In IEEE 3rd international conference on communication software and networks (ICCSN), pp. 306鈥?11. doi:10.鈥?109/鈥婭CCSN.鈥?011.鈥?013721 .
  Moore, J., & Hahn, L. (2003). Petri net modeling of high-order genetic systems using grammatical evolution. Bio Systems, 72(2), 177鈥?86. doi:10.鈥?016/鈥婼0303-2647(03)00142-4 .View Article
  Murata, T. (2002). Some recent applications of high-level Petri nets. IEEE International Symposium on Circuit and System, 2, 818鈥?21. doi:10.鈥?109/鈥婭SCAS.鈥?991.鈥?76488 .
  Narendra, K. S., & Thathachar, M. A. L. (1989). Learning automata: An introduction. Englewood Cliffs, NJ, USA: Prentice-Hall, ISBN 0134855582.
  Pasandideh, S. H. R., Niaki, S. T. A., & Hajipour, V. (2011). A multi-objective facility location model with batch arrivals: Two parameter-tuned meta-heuristic algorithms. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-011-0592-7 .
  Peterson, J. (1981). Petri net theory and the modeling of systems. Englewood Cliffs, NJ, USA: Prentice-Hall, ISBN 0136619835.
  Pla, A., Gay, P., Mel茅ndez, J., & L贸pez, B. (2012). Petri net-based process monitoring: A workflow management system for process modelling and monitoring. Journal of Intelligent Manufacturing, doi:10.鈥?023/鈥婣:鈥?012292102123 .
  Pooranian, Z., Shojafar, M., Abawajy, J. H., & Abraham, A. (2013). An efficient meta-heuristic algorithm for grid computing. Journal of Combinatorial Optimization (JOCO), doi:10.鈥?007/鈥媠10878-013-9644-6 , Springer.
  Pooranian, Z., Shojafar, M., & Javadi, B. (2012). Independent task scheduling in grid computing based on queen bee algorithm. IAES International Journal of Artificial Intelligence (IJ-AI), 1(4), 171鈥?81. doi:10.鈥?1591/鈥媔j-ai.鈥媣1i4.鈥?229 .
  Pooranian, Z., Shojafar, M., Abawajy, J. H., & Singhal, M. (2013b). GLOA: A new job scheduling algorithm for grid computing. International Journal of Interactive Multimedia and Artificial Intelligence (IJIMAI), 2(1), 59鈥?4. doi:10.鈥?781/鈥媔jimai.鈥?013.鈥?18 .
  Pooranian, Z., Shojafar, M., Tavoli, R., Singhal, M., & Abraham, A. (2013b). A joint meta-heuristic algorithm applied in job scheduling on computational grids. Informatica, 37(2), 157鈥?64.
  Poznyak, A. S., & Najim, K. (1997). Learning automata and stochastic optimization. NY: USA: Springer, ISBN: 3540761543.
  Radakovi膷, M., Obitko, M., & Ma艡铆k, V. (2011). Dynamic explicitly specified behaviors in distributed agent-based industrial solutions. Journal of Intelligent Manufacturing, doi:10.鈥?007/鈥媠10845-011-0593-6 .
  Reddy, S. R. (2006). Market economy based resource allocation in grids Master鈥檚 thesis. Indian Institute of Technology, Kharagpur, India.
  Reisig, W. (1985). Petri nets: An introduction, EATCS monographs on theoretical computer science. USA: Springer. ISBN: 3642699707.
  Sarhadi, A., & Meybodi, M. R. (2010). New algorithm for resource selection in economic grid with the aim of cost optimization using learning automata. International Conference on Challenges in Environmental Science and Computer Engineering (CESCE), 1, 32鈥?5. doi:10.鈥?109/鈥婥ESCE.鈥?010.鈥?85 .
  Schwardy, E. (2001). Optimization of Petri nets structure using genetic programming. Dept. of Cybernetics and Artificial Intelligence. Faculty of Electrical Engineering and Informatics. University of Technology Koice. Slovakia.
  Shojafar, M., Barzegar, S., & Maybodi, M. R. (2011). Time optimizing in economical grid using adaptive stochastic Petri net based on learning automata. In Proceedings of International Conference on Grid Computing & Applications (GCA), WORLDCOMP, pp. 67鈥?3.
  Shojafar, M., Pooranian, Z., Abawajy, J. H., & Meybodi, M. R. (2013). An efficient scheduling method for grid systems based on a hierarchical stochastic Petri net. Journal of Computing Science and Engineering (JCSE), 7(1), 44鈥?2. doi:10.鈥?626/鈥婮CSE.鈥?013.鈥?.鈥?.鈥?4 .View Article
  Venkataramana, R. D., & Ranganathan, N. (1999). Multiple cost optimization for task assignment in heterogeneous computing systems using learning automata. Heterogeneous Computing Workshop (HCW鈥?9), IEEE Computer Society, pp. 137鈥?45. doi:10.鈥?109/鈥婬CW.鈥?999.鈥?65118 .
  Zhou, M. C., & Jeng, M. D. (2002). Modeling analysis simulation scheduling and control of semiconductor manufacturing systems: A Petri net approach. IEEE Transaction on Semiconductor Manufacturing, 11(3), 333鈥?57. doi:10.鈥?109/鈥?6.鈥?05370 , ISSN: 0894鈥?507.
  Zimmermann, A., Rodriguez, D., & Silva, M. (2001). A two phase optimization method for Petri net models of manufacturing systems. Journal of Intelligent Manufacturing, 12, 409鈥?20.View Article
  
• 作者单位：Mohammad Shojafar (1)
  Zahra Pooranian (2)
  Mohammad Reza Meybodi (3)
  Mukesh Singhal (4)
  
  1. Department of Information Engineering, Electronics, and Telecommunications (DIET), Sapienza University di Roma, Rome, Italy
  2. Department of Computer Engineering, Dezful Branch, Islamic Azad University, Dezful, Iran
  3. Computer and IT department, Amirkabir Technical University, Tehran, Iran
  4. Electrical Engineering and Computer Science, University of California, Merced, CA, USA
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Production and Logistics
  Manufacturing, Machines and Tools
  Automation and Robotics
  
• 出版者：Springer Netherlands
• ISSN：1572-8145

文摘

Cost and execution time are important issues in economic grids, which are widely used for parallel computing. This paper proposes ALATO, an intelligent algorithm based on learning automata and adaptive stochastic Petri nets (ASPNs) that optimizes the execution time for tasks in economic grids. ASPNs are based on learning automata that predict their next state based on current information and the previous state and use feedback from the environment to update their state. The environmental reactions are extremely helpful for teaching Petri nets in dynamic environments. We use SPNP software to model ASPNs and evaluate execution time and costs for 200 tasks with different parameters based on World Wide Grid standard resources. ALATO performs better than all other heuristic methods in reducing execution time for these tasks.