### 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 language | English |
---|---|

Pages (from-to) | 345-375 |

Number of pages | 31 |

Journal | Journal of Combinatorial Optimization |

Volume | 5 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2001 Dec 1 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Cite this

}

*Journal of Combinatorial Optimization*, vol. 5, no. 3, pp. 345-375. https://doi.org/10.1023/A:1011449311477

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

Research output: Contribution to journal › Article

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 -