Scheduling multiple variant programs under hard real-time constraints

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 alogrithms a computational experiment has been carried out. It is also shown that there exists a 1.618-competitive strategy for the analyzed online problem.