Combinatorial Optimization in Real-Time Scheduling: Theory and Algorithms

Shyh In Hwang, Sheng Tzong Cheng

Research output: Contribution to journalArticle

4 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)345-375
Number of pages31
JournalJournal of Combinatorial Optimization
Volume5
Issue number3
DOIs
Publication statusPublished - 2001 Dec 1

Fingerprint

Scheduling Theory
Combinatorial optimization
Combinatorial Optimization
Scheduling Algorithm
Correctness
Scheduling
Real-time
Avionics
Scheduling algorithms
Search Space
Conformations
Schedule
Computer systems
Robots
Robot Control
Testing
Instrumentation
Conformation
Costs
Manufacturing

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

@article{4533e376f2404f6b8494c960b9271d81,
title = "Combinatorial Optimization in Real-Time Scheduling: Theory and Algorithms",
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 = "Hwang, {Shyh In} and Cheng, {Sheng Tzong}",
year = "2001",
month = "12",
day = "1",
doi = "10.1023/A:1011449311477",
language = "English",
volume = "5",
pages = "345--375",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "3",

}

Combinatorial Optimization in Real-Time Scheduling : Theory and Algorithms. / Hwang, Shyh In; Cheng, Sheng Tzong.

In: Journal of Combinatorial Optimization, Vol. 5, No. 3, 01.12.2001, p. 345-375.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Combinatorial Optimization in Real-Time Scheduling

T2 - Theory and Algorithms

AU - Hwang, Shyh In

AU - Cheng, Sheng Tzong

PY - 2001/12/1

Y1 - 2001/12/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=0042829284&partnerID=8YFLogxK

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

U2 - 10.1023/A:1011449311477

DO - 10.1023/A:1011449311477

M3 - Article

AN - SCOPUS:0042829284

VL - 5

SP - 345

EP - 375

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 3

ER -