A metaheuristic algorithm to solve satellite broadcast scheduling problem

In this paper a new effective and scalable differential evolution algorithm is proposed for optimizing the Satellite Broadcast's Scheduling problem (SBS). The satellite broadcast's scheduling optimization problem is known to be an NP-complete problem in which the aim is to find a valid broadcasting pattern to earth-stationed terminals which maximizes the number of timeslots utilized for broadcasting under certain constraints. The algorithm proposed SD-BDE, is a binary version of Differential Evolution hybridized with ideas extracted from Stochastic Diffusion search. On top of that a repair heuristic mechanism is added to resolve constraint violations. Preliminary analysis shows that the repair heuristic is very effective as compared to other versions which include other heuristics. Further, the performance of the proposed algorithm is tested thoroughly against published work toward solving SBS problem as well as state-of-the-art existing binary-coded population-based similar algorithms. In this paper, we used, along with instances reported in the literature for such problem, randomly generated benchmark's instances of varying sizes for the sake of creating a unified large-scale set to compare different algorithm against. Experimental results show that the proposed algorithm outperformed the existing algorithms by finding better or optimal solutions for almost all tested benchmarks.