Graph colouring approaches for a satellite range scheduling problem |
| |
Authors: | Nicolas Zufferey Patrick Amstutz Philippe Giaccari |
| |
Affiliation: | (1) HEC, Faculté des Sciences économiques et Sociales, University of Geneva, Boulevard du Pont-d’Arve 40, 1211 Geneva 4, Switzerland;(2) Department of Communication and Computer Science, Swiss Federal Institute of Technology, Lausanne, Switzerland;(3) Centre d’Optique, Photonique et Laser, Université Laval, Québec, Canada |
| |
Abstract: | A goal of this paper is to efficiently adapt the best ingredients of the graph colouring techniques to an NP-hard satellite
range scheduling problem, called MuRRSP. We propose two new heuristics for the MuRRSP, where as many jobs as possible have
to be scheduled on several resources, while respecting time and capacity constraints. In the permutation solution space, which
is widely used by other researchers, a solution is represented by a permutation of the jobs, and a schedule builder is needed
to generate and evaluate a feasible schedule from the permutation. On the contrary, our heuristics are based on the solution
space which contains all the feasible schedules. Based on the similarities between the graph colouring problem and the MuRRSP,
we show that the latter solution space has significant advantages. A tabu search and an adaptive memory algorithms are designed
to tackle the MuRRSP. These heuristics are derived from efficient graph colouring methods. Numerical experiments, performed
on large, realistic, and challenging instances, showed that our heuristics are very competitive, robust, and outperform algorithms
based on the permutation solution space. |
| |
Keywords: | Oversubscribed satellite scheduling Graph colouring heuristics |
本文献已被 SpringerLink 等数据库收录! |
|