Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Scheduling multiple divisible loads in star systems

SpeakerMaciej Drozdowski

Co-authorM. Lawenda

We analyze complexity of scheduling multiple divisible loads on star-interconnected parallel processors. It is shown that this problem is computationally hard for identical processors. Providing polynomial time algorithms is a challenging task even for the simplest forms of this problem. Nevertheless, some polynomially solvable cases are identified.