Scheduling with temporal and logical constraints

The scheduling of tasks in a real-time system requires that, in addition to existing logical constraints, temporal constraints must also be met. We consider real-time systems where timing constraints are imposed on tasks through a function of multiple deadlines with cumulative penalties for missing deadlines. Logical constraints are enforced through the partial ordering of tasks, and penalties are assessed for violating these precedence constraints. We propose a bi-criteria scheduling approach in which tasks are scheduled to meet both logical and temporal constraints without preference to either. When both logical and temporal constraints cannot all be met simultaneously, a mechanism for trading off performance in one measure for performance gains in the other is developed. We use a frontier of possible solutions to express the relative merits of schedules that perform well in each performance measure. A branch and bound algorithm plus heuristic methods are proposed to solve several different classes of related problems