Heuristic Scheduling Algorithms Designed Based on Properties of Optimal Algorithm for Soft Real-Time Tasks

摘要

A soft real-time task is one whose completion time isrnrecommended by a specific deadline. However, should therndeadline be missed, such a task is not considered to havernfailed; only the later it finishes, the higher the penalty thatrnis paid. For a set of soft real-time tasks that are to be scheduledrnon a single machine, our objective is to minimize therntotal penalty paid. Since the problem is NP-hard, it is notrnknownwhether an optimal schedule can be found in polynomialrntime. We prove four properties of any optimal schedulingrnalgorithm for the problem. Then, we derive a numberrnof heuristic algorithms which hold the properties obtainedrnherein. The heuristic algorithms differ in the way that therntasks priorities are assigned. These algorithms assign prioritiesrnby using functions of task execution times, penaltyrnfactors or deadlines. Numerical simulations are presentedrnto compare the penalty to be paid by each algorithm.