Embedded and distributed systems are becoming more and more available all over the world, and opening new perspectives for a large range of applications in aeronautic, avionic, robotic and intelligent transportation systems. However, this very large potential of computing power remains largely unexploited this being, mainly due to the lack of adequate and efficient scheduling tools that addresses the realistic nature of these resources. One of the underlying problems, behind this topic is the problem of task scheduling in heterogeneous computing system with heterogeneous communication network.
The main problem of scheduling computing systems has been studied for many years with many variations. We consider, here, the version in which communicating tasks are to be assigned to heterogeneous processors with heterogeneous communication links to minimize the makespan.
Our contributions are three fold: taking into account the heterogeneous communication delay in its general form; a slender linear mathematical formulation of the problem that uses a minimum number of variables and constraints; a heuristics integration which improves a solving time of the mathematical model by endowing good cuts and good bounds.
We use this model to push forward the limit of the exact method. We are able to solve a problem with up to 50 tasks on 8 computing units in few seconds. We develop and compare several approaches for the mathematical models.
| Subject : | : | typdoc_1455 |
| Language of text | : | English |
| Topics | : | Scheduling, planning and production management |
| Keywords | : | Heterogeneous ; Task Scheduling ; Task Mapping ; CPU ; FPGA ; Communication delay ; Mixed Integer Program |
| PDF version | : |  PDF version |
