Scheduling on Heterogeneous Resources with Heterogeneous Reconfiguration Costs
Ani Nahapetian, Soheil Ghiasi, Majid Sarrafzadeh · 2004
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 generalpurpose processor and an FPGA. The results confirm the theoretical conclusions. 1.