Job-shop Scheduling Over a Heterogeneous Platform
Keywords:
Embedded systems, real-time, uniform heterogeneous platform, non-preemptive jobsAbstract
Real-time scheduling involves determining the allocation of platform resources in such a way tasks can meet their temporal restrictions.
This work focuses on job-shop tasks model in which a task have a finite number of nonpreemptive different instances (jobs) that share a unique hard deadline and their time requirements are known until task arrival.
Non-preemptive scheduling is considered because this characteristic is widely used in industry. Besides job-shop scheduling has direct impacts on the production efficiency and costs of manufacturing systems. So that the development of analysis for tasks with these characteristics is necessary.
The aim of this work is to propose an online scheduling test able to guarantee the execution of a new arriving task, which is generated by human interaction with an embedded system, otherwise to discart it. An extension of the schedulability test proposed by Baruah in 2006 for non-preemptive periodic tasks over an identical platform is presented in this paper. Such extension is applied to non-preemptive tasks that have hard deadlines over a heterogeneous platform. To do that, some virtual changes over both the task set and the platform are effectuated.
References
[2] H. Baek, J. Kwak and J. Lee, Non-Preemptive Real-Time Multiprocessor Scheduling Beyond Work-Conserving, in 2020 IEEE Real-Time Systems Symposium (RTSS), Houston, TX, USA, 2020 pp. 102-114. https://doi.org/10.1109/RTSS49844.2020.00020
[3] S. K. Baruah, The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors, Real-Time Systems Journal, vol. 32, pp. 9-20, 2006. https://doi.org/10.1007/s11241-006-4961-9
[4] J. Carpenter, S. Funk, P. Holman, J. Anderson, and S. Baruah, A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms, in Handbook of Scheduling - Algorithms, Models, and Performance Analysis, Chapman and Hall/CRC, pp. 1-19, 2004.
[5] F. G. Filip, A Decision-Making Perspective for Designing and Building Information Systems. International Journal of Computers Communications & Control, [S.l.], v. 7, n. 2, p. 264-272, sep. 2014. ISSN 1841-9844. https://doi.org/10.15837/ijccc.2012.2.1408
[6] M. R. Garey, D. S. Johnson, and S. Michael, Computers and Intractability: A Guide to the Theory of NP-completeness, in Books in mathematical series, W. H. Freeman publisher, 1979.
[7] N. Guan, W. Yi, Z. Gu, Q. Deng, and G. Yu, New Schedulability Test Conditions for Nonpreemptive Scheduling on Multiprocessor Platforms, in 2008 Real-Time Systems Symposium, pp. 137-146, Nov 2008. https://doi.org/10.1109/RTSS.2008.17
[8] K. Jeffay, D. F. Stanat, and C. U. Martel, On non-preemptive scheduling of period and sporadic tasks, in Proceedings Twelfth Real-Time Systems Symposium, pp. 129-139, Dec 1991.
[9] S. Nogd, G. Nelissen, M. Nasri and B. B. Brandenburg, Response-Time Analysis for Non- Preemptive Global Scheduling with FIFO Spin Locks, 2020 IEEE Real-Time Systems Symposium (RTSS), 2020, pp. 115-127. https://doi.org/10.1109/RTSS49844.2020.00021
[10] M. A. Palomera Perez, H. Benitez-Perez and J. Ortega-Arjona, Coordinated Tasks: A Framework for Distributed Tasks in Mobile Area Networks, vol. 5, May 2011.
[11] S. Kato and N. Yamasaki, Scheduling Aperiodic Tasks Using Total Bandwidth Server on Multiprocessors, in 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, vol. 1, pp. 82-89, Dec 2008. https://doi.org/10.1109/EUC.2008.28
[12] J. Zhang, G. Ding, Y. Zou, S. Qin, and J. Fu, Review of job shop scheduling research and its new perspectives under Industry 4.0, Journal of Intelligent Manufacturing, vol. 30, No. 4, pp. 1809-1830, Apr 2019. https://doi.org/10.1007/s10845-017-1350-2
Additional Files
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
