TY - GEN
T1 - Approximation Algorithms for Scheduling Multiple Feasible Interval Jobs
AU - Chen, Jian-Jia
AU - Wu, Jun
AU - Shih, Chi-Sheng
AU - Kuo, Tei-Wei
PY - 2005/8
Y1 - 2005/8
N2 - Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible and preemptible jobs. When jobs are non-preemptible, Algorithm LECF is with a 2-approximation factor; when jobs are preemptible, Algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.
AB - Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible and preemptible jobs. When jobs are non-preemptible, Algorithm LECF is with a 2-approximation factor; when jobs are preemptible, Algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.
UR - http://www.scopus.com/inward/record.url?scp=33749075358&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33749075358&origin=recordpage
U2 - 10.1109/RTCSA.2005.28
DO - 10.1109/RTCSA.2005.28
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 0769523463
SN - 9780769523460
T3 - Proceedings - IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
SP - 11
EP - 16
BT - Proceedings - 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
T2 - 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005)
Y2 - 17 August 2005 through 19 August 2005
ER -