NDLI: Approximation algorithms for scheduling real-time jobs with multiple feasible intervals

Content Provider	Springer Nature Link
Author	Chen, Jian Jia Wu, Jun Shih, Chi Sheng
Copyright Year	2006
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 $${\cal N}{\cal P}$$ -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.
Starting Page	155
Ending Page	172
Page Count	18
File Format	PDF
ISSN	09226443
Journal	Real-Time Systems
Volume Number	34
Issue Number	3
e-ISSN	15731383
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	2006-07-31
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Performance and Reliability Computer Systems Organization and Communication Networks Special Purpose and Application-Based Systems Communications Engineering, Networks Control Engineering
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Computer Networks and Communications Control and Systems Engineering Electrical and Electronic Engineering Computer Science Applications Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms

QoC elastic scheduling for real-time control systems

Scheduling algorithms to reduce the static energy consumption of real-time systems

Compositional multiprocessor scheduling: the GMPR interface

Real-time scheduling for energy harvesting sensor nodes

Garbage collection-aware utility accrual scheduling

Special issue on scheduling and timing analysis for advanced real-time systems

Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

DESH: overhead reduction algorithms for deferrable scheduling

Approximation algorithms for scheduling real-time jobs with multiple feasible intervals

Similar Documents

Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms

QoC elastic scheduling for real-time control systems

Scheduling algorithms to reduce the static energy consumption of real-time systems

Compositional multiprocessor scheduling: the GMPR interface

Real-time scheduling for energy harvesting sensor nodes

Garbage collection-aware utility accrual scheduling

Special issue on scheduling and timing analysis for advanced real-time systems

Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

DESH: overhead reduction algorithms for deferrable scheduling

Approximation algorithms for scheduling real-time jobs with multiple feasible intervals