ИСТИНА

We address the problem of static scheduling for multiprocessor systems, with minimization of makespan, and constraint on the number of interprocessor data transfers. Such problems arise during development of real-time data processing systems, such as telecommunication and control systems. A hybrid algorithm is proposed, combining greedy approach to construction of the initial solution and simulated annealing for its refinement. A specialized operation was developed, aimed at filling idle intervals in the schedule during simulated annealing phase. Experimental evaluation results are presented, demonstrating the advantage of the hybrid algorithm over both standalone greedy algorithm and simulated annealing with straightforward construction of the initial solution.