Real-time job scheduling in hypercube systems

Abstract

In this paper, we present the problem of scheduling real-time jobs in a hypercube system and propose a scheduling algorithm. The goals of the proposed scheduling algorithm are to determine whether all jobs can complete their processing before their fixed deadlines in a hypercube system and to find such a schedule. Each job is associated with a computation time, a deadline, and a dimensional requirement. Determining a schedule such that all jobs meet before their respective fixed deadlines in a hypercube system when preemption is not allowed is an NP-complete problem. Hence, we present a heuristic scheduling algorithm for scheduling non-preemptable real-time jobs in a hypercube system. Finally, we evaluate the proposed algorithm using simulation.