Job-shop Scheduling Over a Heterogeneous Platform

Authors

  • Hector Benitez-Perez UNAM
  • Jose A. Hermosillo-Gomez

Keywords:

Embedded systems, real-time, uniform heterogeneous platform, non-preemptive jobs

Abstract

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

[1] D. Applegate and W. Cook, A Computational Study of the Job-Shop Scheduling Problem, INFORMS Journal on Computing, vol. 3, pp. 149-156, May 1991. https://doi.org/10.1287/ijoc.3.2.149

[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

2021-05-18

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.