A Petri-Net-Based Anytime A∗ Search for Scheduling Resource Allocation Systems

被引:5
作者
Lv, Jianyong [1 ]
Huang, Bo [1 ]
机构
[1] Nanjing Univ Sci & Technol, Sch Comp Sci & Engn, Nanjing 210094, Peoples R China
基金
中国国家自然科学基金;
关键词
Anytime search; intelligent search; place-timed Petri net (PN); system schedule; HYBRID HEURISTIC-SEARCH; MANUFACTURING SYSTEMS; ALGORITHM; FMS;
D O I
10.1109/TII.2023.3296909
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This article proposes a novel anytime search method for the scheduling problem of resource allocation systems (RASs) based on Petri nets (PNs). The method combines the A* search with the depth-first search to iteratively search for transition firing sequences from a start state to a goal state within the reachability graph of a place-timed PN. It usually finds a near-optimal solution quickly and continuously improves the solution until an optimal solution is reached if given more time. When compared with similar work, this method requires only one parameter and does not require any deadlock control policy. Additionally, it can handle generalized PNs with flexible routes and weighted arcs, which are common in the PN models of RASs. Experimental results on benchmark systems demonstrate the effectiveness of the proposed method.
引用
收藏
页码:2865 / 2872
页数:8
相关论文
共 50 条
[31]   Scheduling and Resource Allocation in Downlink Multiuser MIMO-OFDMA Systems [J].
Femenias, Guillem ;
Riera-Palou, Felip .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2016, 64 (05) :2019-2034
[32]   QoS Based Efficient Resource Allocation and Scheduling in Cloud Computing [J].
Chahal, Harvinder ;
Bhasin, Anshu ;
Kaveri, Parag Ravikant .
INTERNATIONAL JOURNAL OF TECHNOLOGY AND HUMAN INTERACTION, 2019, 15 (04) :13-29
[33]   A Petri net-based particle swarm optimization approach for scheduling deadlock-prone flexible manufacturing systems [J].
Han, Libin ;
Xing, Keyi ;
Chen, Xiao ;
Xiong, Fuli .
JOURNAL OF INTELLIGENT MANUFACTURING, 2018, 29 (05) :1083-1096
[34]   Petri net based decision system modeling in real-time scheduling and control of flexible automotive manufacturing systems [J].
Basak, Ozkan ;
Albayrak, Y. Esra .
COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 86 :116-126
[35]   Resource Allocation Strategy in Fog Computing Based on Priced Timed Petri Nets [J].
Ni, Lina ;
Zhang, Jinquan ;
Jiang, Changjun ;
Yan, Chungang ;
Yu, Kan .
IEEE INTERNET OF THINGS JOURNAL, 2017, 4 (05) :1216-1228
[36]   Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets [J].
Lei, Hang ;
Xing, Keyi ;
Han, Libin ;
Gao, Zhenxin .
APPLIED SOFT COMPUTING, 2017, 55 :413-423
[37]   Wavelet-based downlink scheduling and resource allocation for long-term evolution cellular systems [J].
Shadmand, A. ;
Dilmaghani, R. ;
Ghavami, M. ;
Shikh-Bahaei, M. .
IET COMMUNICATIONS, 2011, 5 (14) :2091-2095
[38]   Design and Verification of Petri-Net-Based Cyber-Physical Systems Oriented toward Implementation in Field-Programmable Gate Arrays-A Case Study Example [J].
Wisniewski, Remigiusz ;
Wojnakowski, Marcin ;
Li, Zhiwu .
ENERGIES, 2023, 16 (01)
[39]   TIMED PETRI-NET BASED FORMULATION AND AN ALGORITHM FOR THE OPTIMAL SCHEDULING OF BATCH PLANTS [J].
Gu, Tianlong ;
Bahri, Parisa A. ;
Cai, Guoyong .
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, 2003, 13 (04) :527-536
[40]   Petri net-based modeling and performance analysis of transaction scheduling in grid database [J].
Han, Yaojun ;
Jiang, Changjun ;
Luo, Xuemei .
COMPEL-THE INTERNATIONAL JOURNAL FOR COMPUTATION AND MATHEMATICS IN ELECTRICAL AND ELECTRONIC ENGINEERING, 2009, 28 (06) :1458-1470