Scheduling multiple variant programs under hard real-time constraints

Piotr Jędrzejowicz

doi:10.1016/S0377-2217(99)00487-7

Scheduling multiple variant programs under hard real-time constraints

2000-12-01

3

PRE

AI

DOI：10.1016/S0377-2217(99)00487-7

Original

Original request for help

Save

Abstract

En 中文

The paper proposes approximate and evolution based algorithms for scheduling independent, non-preemptable, multiple variant (m-v) tasks on identical processors. Processing and arriving times may differ per task. Optimization criterion is a total number of the executed program variants under hard, real-time constraints. The paper presents also a competitiveness analysis for the corresponding online problem with two processors. In an online case multiple variants tasks arrive one by one and decisions as:to the number of variants processed and allocation of variants to either of the identical processors must be taken incrementally. The objective in the online problem is to minimize value of the penalty function defined as the schedule length for accepted variants plus the sum of penalties for rejected variants. To evaluate the proposed algorithms a computational experiment has been carried. It is also shown that there exists a 1.618-competitive strategy for the analyzed online problem. (C) 2000 Elsevier Science B.V. All rights reserved.

Keywords:

scheduling theory

fault-tolerance

online scheduling

Scheduling multiple variant programs under hard real-time constraints

Abstract

AI Summary

Journal

Organization