Optimal real-time scheduling with minimal rejections and minimal finishing time

Sheng-Tzong Cheng, Shyh In Hwang

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.

Original languageEnglish
Pages (from-to)229-253
Number of pages25
JournalReal-Time Systems
Volume20
Issue number3
DOIs
Publication statusPublished - 2001 May 1

Fingerprint

Optimal Scheduling
Rejection
Correctness
Scheduling
Real-time
Avionics
Scheduling algorithms
Search Space
Conformations
Schedule
Computer systems
Robots
Robot Control
Testing
Instrumentation
Conformation
Scheduling Algorithm
Costs
Manufacturing
Valid

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modelling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering

Cite this

@article{32590789da2e4b11b30a976468aa1f44,
title = "Optimal real-time scheduling with minimal rejections and minimal finishing time",
abstract = "Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.",
author = "Sheng-Tzong Cheng and Hwang, {Shyh In}",
year = "2001",
month = "5",
day = "1",
doi = "10.1023/A:1008150101419",
language = "English",
volume = "20",
pages = "229--253",
journal = "Real-Time Systems",
issn = "0922-6443",
publisher = "Springer Netherlands",
number = "3",

}

Optimal real-time scheduling with minimal rejections and minimal finishing time. / Cheng, Sheng-Tzong; Hwang, Shyh In.

In: Real-Time Systems, Vol. 20, No. 3, 01.05.2001, p. 229-253.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimal real-time scheduling with minimal rejections and minimal finishing time

AU - Cheng, Sheng-Tzong

AU - Hwang, Shyh In

PY - 2001/5/1

Y1 - 2001/5/1

N2 - Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.

AB - Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.

UR - http://www.scopus.com/inward/record.url?scp=0035341716&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035341716&partnerID=8YFLogxK

U2 - 10.1023/A:1008150101419

DO - 10.1023/A:1008150101419

M3 - Article

AN - SCOPUS:0035341716

VL - 20

SP - 229

EP - 253

JO - Real-Time Systems

JF - Real-Time Systems

SN - 0922-6443

IS - 3

ER -