Scheduling on Heterogeneous Resources with Heterogeneous Reconfiguration Costs

A. Nahapetian, S. Ghiasi, and M. Sarrafzadeh (USA)


Reconfiguration, Heterogeneous Resources, Fully PolynomialApproximation, Rijndael.


In this paper, we provide an optimal algorithm and a fully polynomial time approximation algorithm for the problem of scheduling independent tasks onto a fixed number of heterogeneous unrelated resources with heterogeneous reconfiguration costs. The notion of solution dominance is used to consider all or approximately all possible assignments of tasks to resources. To demonstrate the utility of the approximation algorithm, it is used to schedule blocks of data that are to be encrypted using the Rijndael encryption algorithm on a general purpose processor and an FPGA. The results confirm the theoretical conclusions.

Important Links:

Go Back