https://scholars.lib.ntu.edu.tw/handle/123456789/323947
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Chen, Jian-Jia | en_US |
dc.contributor.author | Wu, Jun | en_US |
dc.contributor.author | CHI-SHENG SHIH | en_US |
dc.creator | Chen, Jian-Jia;Wu, Jun;Shih, Chi-Sheng | - |
dc.date.accessioned | 2018-09-10T05:58:13Z | - |
dc.date.available | 2018-09-10T05:58:13Z | - |
dc.date.issued | 2006 | - |
dc.identifier.uri | http://www.scopus.com/inward/record.url?eid=2-s2.0-33747231851&partnerID=MN8TOARS | - |
dc.identifier.uri | http://scholars.lib.ntu.edu.tw/handle/123456789/323947 | - |
dc.description.abstract | 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. Earlier works developed an optimal off-line algorithm to schedule all the jobs in a given job set and on-line heuristics to schedule the jobs in a best effort manner. 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 Least Earliest Completion Time First (LECF) is shown to have a 2-approximation factor; when jobs are preemptible, Algorithm Least Execution Time First (LEF) is proved being a 3-approximation algorithm. We show that our analysis for the two algorithms are tight. We also evaluate our algorithms by extensive simulations. Simulation results show that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms in average. | - |
dc.format | application/pdf | en |
dc.format.mimetype | application/pdf | - |
dc.language | en | en |
dc.relation | Real-Time Systems 34 (3): 155-172 | en |
dc.relation.ispartof | Real-Time Systems | en_US |
dc.source | AH-Scopus to ORCID | - |
dc.subject.other | Approximation theory; Computer simulation; Heuristic methods; Job analysis; Optimization; Real time systems; Scheduling; Feasible intervals; Off-line algorithm; On-line heuristics; Real-time jobs; Algorithms | - |
dc.title | Approximation algorithms for scheduling real-time jobs with multiple feasible intervals | - |
dc.type | journal article | en |
dc.identifier.doi | 10.1007/s11241-006-8198-4 | - |
dc.identifier.scopus | 2-s2.0-33747231851 | - |
dc.relation.pages | 155-172 | - |
dc.relation.journalvolume | 34 | - |
dc.relation.journalissue | 3 | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.fulltext | with fulltext | - |
item.cerifentitytype | Publications | - |
item.openairetype | journal article | - |
item.grantfulltext | open | - |
crisitem.author.dept | Networking and Multimedia | - |
crisitem.author.dept | Computer Science and Information Engineering | - |
crisitem.author.dept | Intel-NTU Connected Context Computing Center | - |
crisitem.author.dept | MediaTek-NTU Research Center | - |
crisitem.author.orcid | 0000-0001-8936-8255 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | Others: University-Level Research Centers | - |
crisitem.author.parentorg | Others: International Research Centers | - |
crisitem.author.parentorg | Others: University-Level Research Centers | - |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。