- 期刊
- OpenAccess
Efficient Optimal Priority Assignment for Fixed Priority Preemption Threshold Scheduling
摘要
This paper proposes an efficient priority assignment algorithm for fixed priority preemption threshold scheduling (PTS), which we named FAST-TRAVERSE. It is optimal in the sense that it always finds a feasible priority assignment if one exists. While there are existing optimal algorithms, they are inefficient to be used in practice. The key ideas of FAST-TRAVERSE are to prune sibling traverses and preemption threshold assignments if possible based on the notion of the effective blocking task. The empirical evaluation results clearly show that FAST-TRAVERSE achieves the largest feasibility and can be employed as an on-line priority assignment algorithm for PTS.
延伸閱讀
- Ling, D. K. (2012). The Liquid Crystal Injection Scheduling Problem with Priority [master's thesis, National Chiao Tung University]. Airiti Library. https://doi.org/10.6842/NCTU.2012.00231
- 蘇海興（2011）。Using Threshold Accepting Algorithms to Solve Multi-Objective Flexible Job Shop Scheduling Problems〔碩士論文，元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-2801201414595340
- 李佳陽（2019）。Flexible Job and Material Delivery Scheduling Problem And Heuristic Solving Methods〔碩士論文，國立臺灣大學〕。華藝線上圖書館。https://doi.org/10.6342/NTU201902703
- Chibani, M., Belattar, B., & Bourouis, A. (2014). Practical Benefits of Aspect-Oriented Programming Paradigm in Discrete Event Simulation. Modelling and Simulation in Engineering, (2014), 390-405. https://doi.org/10.1155/2014/736359
- Wu, W. C. (2014). On Efficient Incremental Placement for Timing Improvement [master's thesis, National Chiao Tung University]. Airiti Library. https://doi.org/10.6842/NCTU.2014.01019